721D: Maxim and Array(!!!)

1. If we have 0, we need to mark them +1 or -1 to ensure final product is negative. Thus, we need to keep track of the number of negs we have so far. If there is not enough k to fill 0s, return 0;

2. If final product is still positive, we need to pick minimal abs(value) and try flip the sign

3. Now we enlarge them one by one with a PQ in a greedy way. Note that to answer the final queries, in PQ we need to keep track both value and original index

724D: Dense Subsequence(!!!)

Insights

1. If the final answer has more than letter a, we should list ALL a in the string
2. If the final answer has only a, we should list a few as as possible. Morever, each a should not be separate by more than m. If not, we
   know that the answer must exist some letter other than 1, then by 1 we have to take all as
3. Therefore, the only letter that we don't take all is the last one, all we need to do is the find the biggest letter in the answer, and
  keep track of that count.

743D: Chloe and pleasant prizes

From the root, we have a few options,

1. take the root, and the whole subtree 

2. don't take the root, and take the best subtree from it 

3. don't take the root, and take the best two subtree from it

So the state we keep

best2(node) = best choice of having 2 cuts from tree rooted at node 

best(node) = best choice of having only 1 cut from the tree rooted at node

Note implementation wise, we need 3 DP, best2, best , and rootSum

742D: Arpa’s weak amphitheater and Mehrdad’s valuable Hoses

Union-Find to group Hoses into groups, the state we keep is best[gn][w] = best score we can get with group 0…gn, with total weight w;

options we have

1. pick the whole group

2. pick anyone from the group. note that for each w, we go through all n only once, so the overall time is still O(n^2)

3. ignore the group

Note implementaion wise, it is similar to a knapsack problem, i.e., bottom-up with exactly same recurrsion as top-down. However, we do not trigger the DP step until we know Find(i) = i. Otherwise, we just let best[i][w] = best[i-1][w], i.e., no op on this step

738C: Road to Cinema

bsearch on the min fuel capacity, and try to spend all gas before the next station

738D: Sea Battle

scan from left to right, find the first cell that the subarray 1..l can hold k ships, must hit that cell, after that , every time we have enough to hold a ship, we need to hit it once.