## Wednesday, December 28, 2011

### SRM 528: System tests delayed again

Update: Results are up. I got 104 new rating points, it is still less than I lost last match...

I think both my solutions are correct, too bad the system tests had to be delayed. This time I had a lot of spare time I tried to use to solve the 1000 points problem, with no success.

Div1 500: SPartition
Given a string of up to 40 characters that are 'o' or 'x', count the total number of ways to partition the string in two subsequences, such that the two subsequences are equal.

The low constraint sort of led me to the solution. Another important aspect is the small alphabet. Usually, that the string can only have two characters means there is something that really depends on the characters. First of all, for the two strings to be equal, they need to have an equal number of characters, so the strings will have length n/2. More so, they need to have an equal number of 'o' and 'x' characters. Thus let us say nx is the half of the total number of 'x' in the original string and no is the half of the total number of 'o's. The subsequences will have nx 'x' characters and no 'o' characters.

Let the alphabet come into play. How many strings of nx 'x's and no 'o's exist? You will see that with n=40, the maximum result would be 10 'x's and 10 'y's in each half. That gives Binomial(20, 10) different strings that can form the subsequence. That number is actually small.

Second, given the string that we want the subsequences to be equal to, let us count the total number of ways to partition the original string so that both subsequences follow the condition. Let the wanted string be want. The solution is a simple dynamic programming algorithm. Let us define a recurrence F(a,b), where we have already taken the first a+b characters of the original string. a characters were correctly assigned to the first subsequence and b characters to the second subsequence. Note that if s[a+b] is equal to want[a], then we can assign the (a+b)-th character of the original string to the first subsequence. Similarly, if s[a+b] is equal to want[b], we can assign that character for the second subsequence. Finally, if both subsequences already have n/2 characters, then there is exactly one valid way to complete them. The recurrence is thus :

F(a,b) {    res = 0    if (a==n/2 && b==n/2) {        return 1    }    if ( want[a] == s[a+b] ) {        res += F(a+1,b)    }    if ( want[b] == s[a+b] ) {        res += F(a+1,b)    }}

The dynamic programming algorithm is n^2 and the rest is O(C(n/2, n/4) ) this solution is fast enough.

struct SPartition {     string s;     int n;          char want[20];          long long mem[21][21];          long long rec(int a, int b)     {         long long & res = mem[a][b];         if (res == -1) {             if ( (a==n/2) && (b==n/2) ) {                 //final                 res = 1;             } else {                 res = 0;                 if ( (a < n/2) && s[a+b]==want[a] ) {                     res += rec(a+1,b);                 }                 if ( (b < n/2) && s[a+b]==want[b] ) {                     res += rec(a,b+1);                 }             }         }         return res;     }          // Iterate all strings of nx 'x' characters and no 'o' characters.     // for each of them, call the dynamic programming algorithm to     // count the number of ways to find that string.     long long backtrack(int p, int nx, int no)     {         if (nx + no == 0) {             //done             //solve the dp.             memset(mem,-1,sizeof(mem));             return rec(0,0);                      } else {             long long res = 0;             if(nx) {                 want[p] = 'x';                 res += backtrack(p+1, nx-1, no);             }             if(no) {                 want[p] = 'o';                 res += backtrack(p+1, nx, no-1);             }             return res;         }     }          long long getCount(string s)     {         this->s = s;         n = s.size();         int nx = count(s.begin(), s.end(), 'x');         int no = n - nx;         if ( (nx % 2 == 1) || (no % 2 == 1) ) {             return 0;         }         nx /= 2;         no /= 2;         return backtrack(0, nx, no);     } };

Div1 250:
We have up to 50 "eels" of length eelLength[i] each. We can make at most maxCuts of integer length. What is the maximum amount of length-10 eels we can have?

During the match, I used dynamic programming, but the following greedy approach works too.

Notice that usually each cut you make will generate one eel of length 10. There is one exception and it is when the length of the original eel is a multiple of 10. In that case, you can make (length/10 - 1) cuts to get length/10 parts. That means that for each eel with length that is a multiple of 10, you have the chance to save up one cut.

Thus the optimal strategy is to first try to cut all the eels that are multiples of 10. And then focus on the remaining eels. This way, we might save up some cuts.

After the order has been decided, for each eel that is a multiple of 10, find if it is possible to split it into exactly length/10 parts. If it is not cut min(maxCuts, length/10) parts, else add the extra eel.

Edit: Actually, do notice that when picking the multiples of 10 first, you also would like to pick the lowest values first, else you might consume your cut limit by cutting a large multiple of 10 and then become unable to gain the extra cuts in the other numbers.

PS: I have no idea what an eel is.

Joy said...

An eel is a kind of fish that looks like a snake

Manish said...

Sort the numbers is also necessary in 250.

vexorian said...

You mean besides picking multiples of 10 first. Is it? well, just glad I used dynamic programming.

Manish said...

multiple of 10 should be picked in increasing order.
otherwise 50 30 30 and 4 will give wrong answer.

Smit said...

Smit said...

Sorry I meant dp approach for DIV1 250

vexorian said...

It is the one discussed in the blog and by Manish. First cut the eels that are multiples of 10, and if there are many of them, try the smallest first. It is greedy because of picking those convenient steps first.

I used dynamic programming to select the best order of eels, it was over complicated but I think it saved me from the common mistake of not sorting the multiples of 10...

vexorian said...

Ah ok. Here we go.

Let F(p, maxCuts) be a recurrence that solves the problem for all eels with index >= p and a given value of maxCuts. Then for p-th eel you can assign a number i of cuts to do (from 0 to maxCuts). In that case, the result is max10(p, i) + F(p + 1, maxCuts - i).

max10(p, c) is the function that returns the maximum amount of length-10 eels you can get by cutting the p-th eel at most c times. This is similar to the greedy solution in that it gets an extra length-10 eel if the eel is a multiple of 10.

The dp really just replaces the logic that selects the order in which you pick the eels. In reality, it will find the optimal solution by assigning some values of 0 for the number of cuts to do in certain eels (the ones you'll pick last).

Manish said...

Gawd! I made a 1 letter mistake in my dp-solution :( , loop should start from 0 not 1. :( , back-to-div-2-may be.
(Sorry for writing this here)

vexorian said...

Doh, but unless you got negative overall score I don't think you would return to div2.

Manish said...

Yeah -25 ! , maximum negative (cap) i can get is -157, my current rating is 1283.
The test case I tried to challenge on which i got -25, could have challenged my code. I did not test my solution.

Nikhil Garg said...

I coded a very neat meet-in-the-middle solution for D1-500. However your DP solution is much simpler.