CF 182

The number is different from the actual round number, but refers to the final problem set index.

A: Shortest Path, Dijkstra.

B: easy, just add a fixed offset and you get the answer.

C: you are given an array of n int, n=10^5, and a number k, a number len, you are to compute the maximum sum (sum of int, then take abs of the sum), with the condition that you can flip at most k int in the current window of size=len. It is a typical problem with 1D array and sliding fixed-length window. You can query min in current window in O(n) time. But this problem is a bit different. This kind of problem is about what you need to remember in the past elements.

This solution is from watashi's code. When you are dealing with current window, you know you can flip signs of k numbers, and they must be same sign, all + or all -, so you need only the best k positives, and the best k negatives. But how do you update that information as the window slides to the right. Well, you need to drop one element x=a[pos-len] and you have one more element y=a[pos]. So if x is in top k, then x needs to be removed, after that you may need to put back the best one in remaining elements in a[pos-len+1] to a[pos-1] into top k. Now check y, if y can make into top k, then send y into top k, as a result the min in top k will get kicked out and you put it to the reserve. With that you can maintain a BST with count of appearance in each element. A multiset or a map comes in handy.

D: compute the number of factors between two strings, s1 and s2, with length up to 10^5. My approach is fairly complicated and I am a bit surprised to see it get AC. Basically I compute a gcd of s1 and s2, then get all factors of that gcd. To do a gcd in strings, assume s1 is longer. then keep taking s2 from s1 until it is no longer possible. Then the remaining s1, if still longer than s2, you know gcd is empty string. Otherwise let swap s1, s2 and keep going. To get all factors of gcd, simply try all factors of gcd.length() and this could take 10^5 * sqrt(10^5) = 10^7 which is fast enough, since n has at most O(sqrt(n)) factors. Actually this number is an over-estimate, as I tested numbers up to 10^7, the max is only about 500.

E: combinatorial counting and needs a DP solution. The problem statement is wrong but there are 200+ people got AC. It seems they can read the problem setter's mind to see what solution is intended. Actually that's exactly what you need to have when dealing with a DP problem.