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.

nice : )

ReplyDeleteI couldn't complete the remaining problems because the site showed up a "wrong answer" for my CREATING A WORMHOLE PROGRAM. There was only one test case found correct, and i am so sure my code is correct!

ReplyDeletecheck it up guys:

#include

void quickSort( long int*, long int, long int);

long int partition( long int* a, long int l, long int r) ;

long int check(long int* a, long int n, long int sum);

int main()

{

long int sum;

long int t,n,i;

long int a[10000];

scanf("%ld",&t);

while(t--)

{

sum=0;

scanf("%ld",&n);

for(i=0;i pivot );

if( i >= j ) break;

t = a[i]; a[i] = a[j]; a[j] = t;

}

t = a[l]; a[l] = a[j]; a[j] = t;

return j;

}

long int check(long int* a, long int n, long int sum)

{

for(;n>=3;n--)

{

sum-=a[n-1];

if(sum>a[n-1])

return n;

}

return -1;

}

hash include stdio.h isnt being pasted..so ignore that

Deletepaste the ideone link naa...!!!!

Deleteand mostly the error is the datatype u have used...the max value of sum can go upto 10^9 * 10000 i.e. 10^13....so u need to use long long...instead of long...:)

DeleteIs there any chances after getting 190 rank in amritapuri and in college 7th rank .

ReplyDeletePretty good chances actually. There are 400 slots and around 250 distinct teams approx. Assign 1 slot worst case to each college. So next 150 will be filled in order of ranks. So, if "40 distinct college firsts are there in top 190", you will get through.

DeleteDont hold me to the numbers, this is just an approximate analysis.

Surprising to see that there is a pretty simple solution for Blurry Vision. We used recursion to check if two submatrices are equal.

ReplyDeletehttp://pastebin.com/ccx2mn7M

Please provide solution for galaxy search problem. I tried Recursive backtracking but it exceeds time limit for N>21. I think there exists iterative solution (maybe a DP solution) but I am unable to formulate the solution.

ReplyDeleteI coded it. Technique is DP with bitmask.

DeleteA very good resource for everybody that wants to read a good blog.Your blog was absolutely fantastic! Great deal of great information and this can be useful some or maybe the other way. Keep updating your blog, anticipating to get more detailed contents.

ReplyDeleteget online votes || buy facebook votes