ICPC Amritapuri Online Contest 2013 - Editorials

There were 4 problems in total. 3 problems were adhoc in nature. The fourth problem was a tiling problem which my team could not solve during the contest. The problems took some time to load initially (about 5 minutes) but after that the contest went on without any major problems.

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.