SRM 536

This SRM was scheduled for 5:30 pm IST. I was at office then. This time my approach was different. I first approached for DIV-II 250. I was able to successfully submit the code at 240 points. Then I opened 500 points problem. This time 500 points was relatively easy. I was able to submit at 431 points. This ascended me to within 70 ranks in DIV-II (after 25 minutes of SRM starting). I had sufficient time to approach for 1000 points. I opened it, problem was awesome. I thought it in DP + Maths way. After 25 minutes of opening 1000 points , I felt like I cannot do it.

System test results: Both 250 and 500 passed. I couldn’t solve 1000 pointer(i had no idea how to solve during contest). Finally I finished at 113th position in DIV-II among 1350 coders. This time again I ascended to DIV-I.

Let’s discuss the 1000 pointer problem (250 and 500 pointer were simply brute force) :

1000 pointer problem (DIV-II)

http://community.topcoder.com/stat?c=problem_statement&pm=11802&rd=14728&rm=311958&cr=22938770

You can refer the problem from here(p.s. due to copyright issue I am not publishing it’s contents)

 The Java implementation of the above problem is :

double[][] DP = new double[55][55];

public static int INF = Integer.MAX_VALUE;

public double findMaximum(int[] revenues, int k)
{
    Arrays.sort(revenues);
    double ans = -INF;

    for(int i = 0; i <= revenues.length; i++)
    {
        for(int j = 0; j <= revenues.length; j++)
        {
             DP[i][j] = ans;
        }
    }

    DP[0][0] = 0;

    for(int i = 1; i <= revenues.length; i++)
    {
        for(int j = 1; j <= revenues.length; j++)
        {
            int cnt = 0;
	    double sum = DP[i - 1][j - 1];
	    if(i - 1 != 0) cnt++;
	    for(int m = i; m <= revenues.length; m++)
	    {
		cnt++; sum += revenues[m - 1];
		if(cnt >= k) DP[m][j] = Math.max(DP[m][j], 1.*sum / cnt);
	    }
	}
    }
    for(int i = 1; i <= revenues.length; i++) ans = Math.max(DP[revenues.length][i], ans);
    return ans;
}

SRM 535

This SRM was scheduled for 10:35 pm IST. This timing was pretty much good for all the coders from India. This time I was in DIV-II. I had a feeling that I would ascend to DIV-I after this SRM. I decided to approach problems as Hard, Easy, Medium.

Hard problem was a bit tougher and complicated and I gave up after some minutes of reading and thinking. Then I opened easy problem, which I was able to solve for 242 points. Then again I went for Hard. Finally after 40 minutes I gave up and opened Medium problem. Here I am discussing about Medium problem statement of DIV-II.

http://community.topcoder.com/stat?c=problem_statement&pm=11364&rd=15037&rm=311842&cr=22859464

The question is above mentioned. I couldn’t solve this question in time as I opened this question in the last 30 minutes. The question was based on Mathematics.

Below is the code that I wrote after the contest.

public long GCD(long a, long b)
{
    if (a < 0) return GCD(-a, b);
    if (b < 0) return GCD(a, -b);
    return b == 0 ? a : GCD(b, a % b);
}
public long get(long G, long L)
{
    long ans = (long)1e18;
    if(L % G != 0) return -1;
    for(int d = 1; ; d++)
    {
        if(G * d > L / d) break;
        if(L % d != 0) continue;
        if(GCD(G * d , L / d) == G)
        {
            ans = Math.min(ans, G * d + L / d);
        }
    }
    return ans == (long)1e18 ? - 1 : ans;
}

Explanation and Mathematical Proof:

Let’s say the two numbers are a and b such that a <= b. The maximum value GCD can have is the minimum number between a  and b. Here a <= b. Therefore GCD always lie towards the left region of ‘a’ with some factor f. Similarly the minimum value LCM will have is the maximum number between a and b. Here b is greater than a. Therefore LCM lies towards the right region of ‘b’ with some factor.

Example : Let’s say gcd(a, b) = 3 and lcm(a, b) = 36.

Then a = 9, b = 12. i.e. GCD lies towards the left region of [a, b] and LCM lies towards the right region of [a, b]. And in each case it lies with some factor f. Thus we can deduce the concept that

a = someMultiple * gcd  and b = lcm / someMultiple. Thus keeping gcd * lcm constant. The same logic is induced in the code given above.

The above mentioned code runs at max. 10^6 times. Thus can be computed in the range of 2 seconds.

SRM 534

This SRM was scheduled for 7:30 am IST. I woke up at 7:05 am IST, quickly registered for the match. As usual, being in DIV-I i thought of opening 250 points problem first.

Problem definition: 

http://community.topcoder.com/stat?=problem_statement&pm=11791&rd=14727&rm=311688&cr=22859464

My Approach:

I first saw the constraints, and felt that greedy approach won’t work( i thought of greedy approach just after reading the problem). I simulated the test cases to produce results, and felt that it requires bit-masking. I thought simple approach wont work, as the constraint could have been grown more for simple approach. I quit thinking in greedy approach. But verdict was, I was wrong. The optimal solution exists even with the greedy approach.

Using greedy approach:

Since every checkers can move until they reach the end of the board, the answer was simple. If the sum of difference between last index and checkers current position is odd, player A wins else player B wins. Pretty much simple approach.

public String getWinner(String board)
{
    int ans = 0;
    for(int i = 0; i < board.length(); i++)
    {
        if(board.charAt(i) == 'o') ans += board.length() - 1 - i;
    }
    if(ans % 2 > 0) return "YES";
    return "NO";
}

Using bit masking to generate all the possibilities:

private int N;
private int[] M = new int[1 << 20];
public int solve(int mask)
{
    if ((mask & 1) > 0)
        mask--;
    if (mask == 0)
        return 2;
    if (M[mask] != 0)
        return M[mask];
    boolean flag = false;
    int i, k;
    for (i = 1; i < N && !flag; i++)
    {
        if ((mask & (1 << i)) != 0)
        {
            if ((mask & (1 << (i - 1))) == 0)
            {
                k = (mask - (1 << i)) + (1 << (i - 1));
                if (solve(k) == 2)
                flag = true;
            }
            if (i > 2 && (mask&(1 << (i - 1))) != 0 && (mask&(1 << (i - 2))) != 0 && (mask & (1 << (i - 3))) == 0)   
            {
                k = (mask - (1 << i)) + (1 << (i - 3));
                if (solve(k) == 2)
                    flag = true;
            }
        }
    }
    if (flag)
        return M[mask] = 1;
    else
        return M[mask] = 2;
}
public String getWinner(String board)
{
    N = board.length();
    int i, j, k;
    k = 0;
    for (i = N - 1, j = 0; i >= 0; i--, j++)
    {
        if (board.charAt(i) == 'o')
            k = (k | (1 << j));
    }
   if (solve(k) == 1)
       return "YES";
   else
       return "NO";
}