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.
0 comments:
Post a Comment