Thursday, October 24, 2013

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.

10 comments:

  1. I 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!
    check 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;
    }

    ReplyDelete
    Replies
    1. hash include stdio.h isnt being pasted..so ignore that

      Delete
    2. paste the ideone link naa...!!!!

      Delete
    3. and 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...:)

      Delete
  2. Is there any chances after getting 190 rank in amritapuri and in college 7th rank .

    ReplyDelete
    Replies
    1. Pretty 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.

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

      Delete
  3. Surprising to see that there is a pretty simple solution for Blurry Vision. We used recursion to check if two submatrices are equal.
    http://pastebin.com/ccx2mn7M

    ReplyDelete
  4. 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.

    ReplyDelete