Problem A (link)
A quick dp problem to boot. I guess. There are a couple of complications. The length 5000, shall make it tight to stay under the 256 MB limit. This is a dp that although it may be straightforward to see that it just needs dp, you need to know how to guard a couple of details, one is the memory limit (At most you can do a [2][5000][5000] int array). The other is taking care of a couple of details...
Eventually, after trying some stuff that made me redo the problem, I decided it is best to move the dp inside another loop. Let us iterate for the position of the last character of the substring. Then solve the subproblem: How many pairs of substring of s, subsequence of t are equal such that the substring's last character is at the given position?
Then we should avoid counting empty strings. Simply add a variable to the state (nonempty) if we want to count empty strings or not. (We would like to count empty strings in a sub problem if we already found a pair of characters that match).
Thus we have the recurrence f(nonempty, a, b) which should return the number of pairs such that:
- The last character of the substring is at position (a-1).
- The last character of the subsequence is at a position less than b.
- If nonempty is 1, count the empty substrings/sequences that match.
The logic works as follows. We know that the substring must begin at (a-1), so s[a-1] must be matched to a character from t. From t, we can remove any number of characters. So, if (s[a-1]==t[b-1]) we have the option to match them. If we do, then we
have to add to the result f(1, a-1, b-1) , because that is the result of subsequences and substrings that we can append to s[a-1] and t[b-1] to get a result.
We can also move to f(nonempty, a, b-1) , in other words, just ignore the character at position t[b-1], until we find a match for s[a].
string s, t;
const int MOD = 1000000007;
int dp[2][5001][5001];
#define SUBMOD(x) if (x>=MOD) { x-=MOD;}
int rec(int nonempty, int a, int b)
{
int& res = dp[nonempty][a][b];
if (res == -1) {
if ( (a==0) || (b==0) ) {
res = nonempty;
} else {
res = 0;
if (s[a-1] == t[b-1]) {
res += rec(1, a-1, b-1);
SUBMOD(res);
}
res += rec(nonempty, a, b-1);
SUBMOD(res);
}
//cout << sstart<<", "<<a<<", "<<b<<" = "<<res<<endl;
}
return res;
}
int solve()
{
memset(dp,-1,sizeof(dp));
int res = 0;
for (int i=1; i<=s.length(); i++) {
res += rec(0, i, t.length() );
SUBMOD(res);
}
return res;
}
Problem B (link)
I think the high level idea of my approach is correct, but details need to be polished. I submitted almost knowing that it was unlikely I would pass. When you want to minimize the maximum time to assign to some variables. It is almost always an indication to use binary search for the time. There is an issue in this case, and it is that times are real values, so your binary search would need many iterations to be precise.
I cut down some iterations by noticing that the height h is irrelevant as we do not really need to output the time. Its overall effect on the time is always a factor of h, since that factor is constant we can just switch to minimizing the worst (i/v_j). This is helpful because it reduces the maximum time from 10^9 to 10^5.
For a given time, is it possible to solve the problem in a time less than or equal to it? Once the time is fixed, you can find, for each lemming, the maximum position it can be assigned to. Then for each position from greater to lower, you can just assign the lemming with the maximum weight available to that position. (Making sure not to pick a lemming heavier than the one in the above position). This greedy strategy will always work correctly. The problem is to implement it in a way that is quick. Whether it is the constant factor or the logarithmic factor I used to do things like find the maximum weight, it seems it is too slow.
Problem C (link)
I didn't do much, except note that d=(l/(v1+v2))*v1 is the length of the interval of positions in which a chocolate can be picked. After that you need to do some data structure magic to get all the probabilities in O(n*log(n)) or something like that.
Problem D (link)
I tried many things without much success. At first I thought of simple ideas like always distributing each prime number with an exponent >= 3 evenly between the side lengths and then deciding on exponent%3. But examples like V=8*7*7, break such idea.
Outcome
Failed B, my A submission was very slow. I hope I at least earn some rating.
