TC SRM 528

p250
you get length=10 for free and the only extra you get is by cutting a 20 into 10 and 10, with 1 cut you get 2 items. So sort the sticks by length and first process length with multiples of 10, then process others. I made a mistake forgot to check avail cuts >=0 and got challenged.

p500
Given a string with 'o' and 'x', find number of ways that splits into two identical substrings. string length =40.

The algorithm works by noticing that substr has length =20. So you can guess all 2^20 substr. For each of the guess, compute dp[i][j] as number of ways to match first[0..i) and second[0..j) to s[0..i+j). dp[n/2][n/2] is the answer for this guess. And ans is the sum of all guesses. Need to prune the guess with wrong number of 'o' and 'x', otherwise will TLE.

p1000
Given a[] of n=50 integers, each a[i]<=2000. P1 and P2 are two integers 50<= P1,P2 <=2000.
Find number of ways to get as many (P1,P2) pairs from a[].

Since the feasible solution is monotone. If we can make k pairs, we can also make k-1 pairs.
So we can binary search ans. low=0, high=2000*50/(50+50)=1000.

dp[n][p] is max #P2 if we use a[0..n-1] and we have #P1=p.

When update dp[i][j], we iterate all possible usage of a[i].
a[i] can offer #P1 from k=0 to a[i]/P1. the corresponding P2 offer is from 0 to (a[i]-k*P1)/P2

set all dp[i][j] to -1
dp[0][0] is 0 since we got 0 P2 if we do not use any of a[] and our P1 is 0
let i=0 to n
let j=0 to mid // if dp[i][j]>=0
let k=0 to a[i]/P1 // a[i] offer P1 as k
dp[i][j+k] updated by dp[i][j] + min(avail[i][j], mid-k) // min is due to a[i] cannot offer more than maxP1 - its own offer of P1

a valid answer is dp[n][mid] >= mid
and take the best over all mid we got the answer.