12.07.2021–13.07.2021
Interesting task on segment tree from virtual CF Educational 6. Again you see tree and queries in subtrees, so may be it is tin-tout ST? Yes, it is. But here you should maintain info about ≤ 60 unique elements in each node and do lazy propagation. So may be merging vectors of size ≤ 60? Yes, but it is TL 54. May be some optimizations? No, TL 67. Hmm, ≤ 60 and long long < 2⁶³. What does it mean? Yes, bitmasks. So < 800 ms instead of TL with 3000.
Conclusion: MAY BE YOU CAN REPLACE SOME “HEAVY” STRUCTURE BY SOMETHING LIKE BITMASK?
This task seems so hard for me on Umnik’s Day 5 contest. You have set of pairs a, b such that it should be oriented path in graph from a to b. Minimize number of all edges in graph that meets all the restrictions. Can you replace some graph without cycles on chain? Yes, using topsort. And some graph wuth cycle on just one cycle? Yes, just do cycle. Is it minimal cases? Yes, obviously. That is the solution!
Conlcusion: TASK MAY SEEM HARD BUT JUST TRY TO COME UP WITH SOME (EVEN STUPID) IDEA AND TRY TO APPLY IT. MAY BE IT IS WHAT YOU NEED
Wrote CF Educational 8. Again task E was on data structures. The task was to count number of Z-patterns in matrix. So let’s look at picture:
This is diagonal. js and i are points on the diagonal, L is maximal segment to the right of the point and R is the same to the left. So points i and j form Z-pattern if and only if R ≥ i — j + 1 and L ≥ i-j + 1. Let’s fix point i, so we need to find number of points j in range [i -R + 1, i-1], such that Lj ≥ i -j + 1. For example, points j3 and j4 are only appropriate for point i. L2, L1 are too small, j0, j1 are out of range.
That can be done with segment tree on vectors with binary search with O(log²n) on each query. But it is TL (I checked). So new approach should be invented. It can be seen that every point j can possibly make Z-pattern with all points i in range [j+1, j+L-1]. So when we fix point i, we should find number of js in range [i -R + 1, i-1] that currently affect i. It can be done with Fenwick tree with +1, -1 trick. For point i we query sum of ones on segment [i -R + 1, i-1]. If we are on point, that is the end of impact of some j, we “delete” corresponding one on position j in Fenwick.
Conlcusion: IF YOU CAN INVENT SOME HEAVY STRUCTURE FOR SOLVING, BUT IT CAN BE TL WITH HIGH PROBABILITY, TRY TO COME UP WITH LIGHTER REPLACEMENT
Solved (with analysis) 2 interesting problems on flows. First can be solved finding maxflow on this network:
Second is based on idea that prime can only be made with sum of even and odd number (if all numbers ≥ 2, case with 1s is different). So we have network on bipartite graph with 2 sets: odd and even numbers. For every even make an edge connecting to odd, such that even + odd = prime. Capacity is 1. So we should find exactly 2 odds for every even, and 2 evens for every odd, so make edges from s to evens and from odds to t with capacity = 2. Run Dinic. If maxflow is equal to n (n/2 * 2, if sizes of sets are not equal, answer if Impossible), we split the graph into cycles. That’s what we need.
