The following solutions use my Competitive Programming template which you can find here: http://machlearner.blogspot.in/2013/01/in-competition-programming-where-speed.html
Problem 1: Blurry Vision
Problem Statement:
https://icpc.hackerrank.com/contests/amrita13/challenges/blurry-vision
Solution:
Our objective in this problem is to find whether two sub matrices of a given matrix (which might potentially overlap) are the same. If multiple such sub matrices occur, find the one with maximum number of elements.
We could just iterate through all possible sub matrices, keep adding them to a map (either by converting the sub matrix into a string or a vector<string>). If the current sub matrix already exists in the map, we take answer to be maximum of current answer and number of elements in the current sub matrix.
Code:
map<string,int> m1;
string a[11];
int main()
{
int t,n,m,ans;
string s;
t = ni();
while(t--) {
n = ni(); m = ni(); ans = 0;
REP(i,0,n)
cin >> a[i];
REP(i,0,n)
REP(j,0,m)
REP(k,i,n)
REP(l,j,m) {
s = "";
REP(p,i,k+1) {
REP(q,j,l+1)
s.pb(a[p][q]);
s.pb('$');
}
if(m1.find(s) != m1.end())
ans = max(ans,m1[s]);
else
m1[s] = (k-i+1)*(l-j+1);
}
printf("%d\n", ans);
m1.clear();
}
return 0;
}
Complexity: O((n*m)^3) per test case.
Problem 2: Flee to Shelter
Problem Statement:
https://icpc.hackerrank.com/contests/amrita13/challenges/flee-to-shelter
Solution:
This was the easiest problem of the contest. Objective of the problem was to find the total time taken to transfer all the instruments.
ans = ceil(n/m)*time_taken_for_one_trip*2
Code:
int main()
{
int t,n,m,T,ans;
t = ni();
while(t--) {
n = ni(); m = ni(); T = ni();
if(n%m == 0)
ans = (n/m)*T*2;
else
ans = (n/m+1)*T*2;
printf("%d\n", ans);
}
return 0;
}
Complexity: O(1) per test case.
Problem 3: Creating a wormhole
Problem Statement: https://icpc.hackerrank.com/contests/amrita13/challenges/creating-a-wormhole
Solution:
Given an list of edge lengths, our objective is to find the polygon with maximum number of edges which can be formed from the given edges.
We use the generalization of triangle inequality to any polygon - http://en.wikipedia.org/wiki/Triangle_inequality#Generalization_of_the_inequality_to_any_polygon
First, we sort the array. Then we check for each edge i (0 based index), whether its length is smaller than sum of lengths of all previous edges. If this is true, ans = i+1, else we continue the process. ans is initialized to -1 to account for the case where no such polygon is possible.
Code:
int a[10005];
int main()
{
int t,n,ans;
LL sum;
t = ni();
while(t--) {
n = ni(); ans = -1;
REP(i,0,n)
a[i] = ni();
sort(a,a+n);
sum = a[0] + a[1];
REP(i,2,n) {
if(sum > a[i])
ans = i+1;
sum += a[i];
}
printf("%d\n", ans);
}
return 0;
}
Complexity: O(n*logn) per test case.Problem 4: Galaxy Search
Problem Statement:
https://icpc.hackerrank.com/contests/amrita13/challenges/galaxy-search
Solution: (to be updated soon...)
Note: These are just my personal solutions and not an official editorial.
Feel free to leave suggestions or alternate solutions as comments.
![x := \sum_{i} a_i \frac{N}{n_i} \left[\left(\frac{N}{n_i}\right)^{-1}\right]_{n_i}](http://upload.wikimedia.org/math/7/9/0/7900728a23224d40167ad92714699ac2.png)