02.07.2021
First day of Umnik’s summer intensive. I solved 5 tasks — A, C, D, K, O
The most significant mistake of the whole contest was the fact that I did 11 submissions on problem O. That was some greedy idea with STL set or map, so it was O(nlogn) with major constant and n ≤ 10⁶. I believed that this is right solution and was trying to fit the time limit, trying to reduce constant and making some questionable optimizations. That was the cost of 7 TL submissions. The thing that it was wrong solution and I should not spend so much time trying to optimize WA algo. I ended up with 30³ solution with idea of decomposition of numbers of array A on powers of 2. You can break up large powers if is necessary, trying to make numbers of array B in ascending order. Conclusion: TRY TO COME UP WITH ANOTHER IDEA, IF CURRENT IDEA IS DEAD-END.
Task D was relatively quickly thought up, but was spoiled by foolish bug: there are 26 different letters in english, so if you want to count the number of substrings with x different characters for any x, you should create an array of size 27, NOT 26. Conclusion: LOOK AT ARRAY BOUNDS.
Task K is the kind of task I like: some stuff with segments, so it is maybe data structures or STL + scanline or both. I like it. Here I simplified the task so: find the number of segments with both ends in range [L, R]. If c[R] is the count of r ≤ R such that r is right end of some segment and to_left(L, R) is the numbers of segments with L ≤ r ≤ R and l < L, so first end is to the left of L and second is inside range. So the answer is c[R] - c[L]- to_left(L, R). c[R] is easily calculated at O(R). But to_left(L, R) needs for every r an array a[r] = {l1, l2, …}, so that l1 ≤ l2 ≤ … and every (l1, r), (l2, r) … are segments. So I need a query on range [L, R] on array a getting the number of ls < L. It is segment tree with sorted arrays {l1, l2, …} in nodes and binary search to find the number of ls < L in every such node-array. So it is O(log²n) for every query. I didn’t believe but it got AC. Cool.
In the evening I upsolved 4 tasks. It was funny that 2 of them I could easily think up using binary search. Tasks are J and G. Conclusion: ALWAYS THINK ABOUT BINSEARCH. IT CAN SURPRISINGLY SIMPLIFY THE SOLUTION.
Task I was not hard DP task with dp[2010][2050][2][2], first is prefix, second is the sum I got, third is parity of number of 2s at the end of prefix, fourth is the flag whether I have already got necessary sum. The idea is simple: if the parity of 2s is 1 and you want to put 4 at the end of prefix, then your sum becomes 4, else your sum can be increased. Sample: 4 2 2 4 4 2 4 2 2 2 4 -> 16 2 8 2 4. Transitions are obvious.
Task P I solved with the help of analysis. It is constructive task. The task is: cut the edges of given graph on paths of size 2. You can do it with every graph with even number of edges. You should run a recursive algorithm that is trying to cut the component of vertex v with not blocked edges. You find all sons u of v by unblocked edges. Block this edges. Find the answer for every u. If in component of u edge (u, w) is not blocked, you find a path {w, u, v}. If in components u1 and u2 all edges are blocked you can create a path {u1, v, u2}.
Constructive tasks are my weak side so I should practice more solving them.
