CF #87

A - Party
Find longest chain in a DAG, and each node has at most one predecessor. A simple DP in topological order.
Passed.

B - Lawnmower
This is an implementation problem. When work on row[i], assume you are moving right, then you have to arrive right[i]. Then you need to look at next nonempty row[k], if row[k] is moving right, then you have to move to left[k], otherwise row[k] is moving left and you have to move to right[k]. You also need to count in the steps moving between rows. And you stop when you have visited all 'W' cells. Notice that you do NOT have to end at last row.

The DP idea below got TLE.

It appears that your move is essentially fixed as you can only go down and in each row you can only move to one direction, left or right. But then you can have several empty rows in between and this will affect your move. So another DP problem. dp[row][first][last] is the number of moves you need to complete current row to last row. If you have some W cells outside [first,last], then it is infeasible and dp[][][] is INF. However during contest forgot to check outside last and didn't finish.

D - Unambiguous Arithmetic Expression
Hacked as TLE. My solution need 1000^3=10^9 and seems too slow. On local machine, the hacking case
1+1+1+...+1 runs in 26s.

Didn't get a good idea about C and E.

rating: 1711 to 1675, almost into div2.

C - Plumber I have to read the tutorial to get the problem. It looks you should arrange from top to bottom, from left to right. But the constraint is huge, each cell has 4 possible orientations and you have 10^5 cells. Even try to enumerate one row seems prohibitive. Now is the catch. When the constraints seem too big, any DP strategy destined to doom, there is a simple formula to count. If it is only 1D, then everybody sees it. Each plumber is either left or right, and once the first one is determined, then every cell will be determined in the same row. So you have the solution now. Each row, and each column, has to have plumbers alternating. That is, for a row, if the first one is chosen to be left, then 2nd one is right, and 3rd one is left and 4th one is right and so on. So you just check 2 possible orientations for each row. If both are good, then your ans will be multiplied by 2, if only one is good, then your ans does not change, if neither is good, you know your ans is zero.