750D: New Year and Fireworks(!!!)

Why I was stuck during the contest

1. I realize that the input size is small enough that I can keep states to avoid recomputing, but my upperbound is too much, in fact, each direction needs only 150 cells, but my bound is too loose at 300. Therefore, I spent much time reasoning about memory usage 
 - I calculated one more 0!

2. I was not sure about how to implement the starting point in the middle of the map. Should it be at (160, 160) or (0, 0) ? In retrospect this doesn't matter much.

3. For the state to capture, I failed to identify the depth itself is enough to uniquely identify a state

Code-wise, I had problem how to handle the start of the whole sequence. It turns out I should do all the step iterations within that step call, because the state [curStep] we capture is unique, so we don’t have to worry about other steps overriding our curStep=0 case, that is , it represents at (x, y), we are about to start at step i, with direciton heading at d

The overall memory = 300 * 300 * 8 * 30 < 25 mil, each cell in memory is filled once only => the running time is same

722D: Generating Sets

Since we care about the max number, we can bsearch on that number, and reduce it to the prefix to fall under that, if there is no space, they we know the lowerbound is too low.

Note that my first idea is to be purely greedy: highest number try reducing to the lowest number, but I had difficulty proving it, and it actually failed one of the test cases

682D : Alyona and Strings(!!!)

Idea 1: Greedy (My approach)

Calculate LCS at (i, j), and then for the best(i, j, k), it is the best of

1. best(i-1, j, k) => pass the current pair

2. best(i, j-1, k) => pass the current pair

3. best(i-lcs(i,j), j-lcs(i,j), k-1) => try using the current pair

Idea 2: Pure DP (Official answer)

I realize the kernel of the problem is that need to know if the tail of the string pair is used, so that we can know when we glue the new pair if it is a new segment. This means the best(i, j, k) state is not enough, and we need to introduce another flag to mark if the end pair is used

Note that to handle the “previous” index nicely, we will use then length as state instead of index

When s[i] = t[j], best(i+1, j+1, k, 1) = max(best(i,j, k, 1) , best(i,j, k-1, 0)) + 1

the base case is best(i, j, k, 0) = max of

1. best(i-1, j, k, 0) => ignore the current end pair

2. best(i, j-1, k, 0) => ignore the current end pair

3. best(i,j, k, 1) => use the current end pair

The final answer will be best(n, m, k, 0)