This is a newbie question. I am confused with transition equations in DP, and always mess them up.

The official solution of this problem looks like:

               // dp[time][number of people]    
               rep(i, 1, t) rep(j, 1, n)
                        dp[i+1][j-1] += dp[i][j] * p;
			dp[i+1][j] += dp[i][j] * (1-p);

Why it is incorrect (gave me WA) if it is written like this:

dp[i+1][j+1] = dp[i][j]*p + dp[i][j+1]*(1-p)

I have a very vague feeling that dp[i][j+1] may not be updated completely before it is added to dp[i+1][j+1] , but not very sure, since it is supposed to be calculated in previous outer loop already.

How can I treat similar DP problems effectively, and more important, correctly?

The USACO 2015 February contest is available from February 20 through February 23. The contest is 4 hours in length, and can be taken any time during the larger contest window. More info: http://usaco.org/

The contest is over. I guess it's OK to discuss the problems here.

It appears Ontology is not very difficult to most people. However, I don't even have a smart way to parse the parenthese-expression. All I did is just to generate a huge hash and transverse the relevant elements, and apparently it resulted in TLE. I wonder what kind of tree structure is recommended?

I have the similar issue in best representing the problem with appropriate data structure in Wombats too. Even if I tried randomized optimization, it is hard for me to construct a stuffed animal removal sequence.

What categories of algorithms do these two problems belong to?