**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.

structSPartition{

strings;

intn;

charwant[20];

longlongmem[21][21];

longlongrec(inta,intb)

{

longlong&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);

}

}

}

returnres;

}

//Iterateallstringsofnx'x'charactersandno'o'characters.

//foreachofthem,callthedynamicprogrammingalgorithmto

//countthenumberofwaystofindthatstring.

longlongbacktrack(intp,intnx,intno)

{

if(nx+no==0){

//done

//solvethedp.

memset(mem,-1,sizeof(mem));

returnrec(0,0);

}else{

longlongres=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);

}

returnres;

}

}

longlonggetCount(strings)

{

this->s=s;

n=s.size();

intnx=count(s.begin(),s.end(),'x');

intno=n-nx;

if((nx%2==1)||(no%2==1)){

return0;

}

nx/=2;

no/=2;

returnbacktrack(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.

## 12 comments :

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

Sort the numbers is also necessary in 250.

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

multiple of 10 should be picked in increasing order.

otherwise 50 30 30 and 4 will give wrong answer.

can you tell about your greedy approach?

Sorry I meant dp approach for DIV1 250

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

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).

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)

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

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.

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

Post a Comment