03.07.21–05.07.21
I was too lazy to fill this blog by 1 story per day. So it will be story about three days of training.
It was a contest on Codeforces on the 3rd of July. It was not very successful but result was descent, because I was fast enough. Problems A, B, C got accepted and I got +91 to rating.
Problem D was solved by no more than 400 people at the end of the contest but I had no idea. The problem is: you have a sequence A of ‘-’ and ‘+x’. You are iterating through all subsequences B of A and count its sum. Sum of B is counted by going through B from left to right and maintaining multiset. If you see ‘-’, you delete the smallest element from B if it not empty, else you add element x to B. Sum of B is the sum of elements of resulting multiset. On the contest I tried to fix element x and ‘-’, that will delete it from multiset, but is is dead-end idea. Also tried to fix something else. But the key idea was to fix one element position pos with element + x, mark all elements that are smaller with S and all that are greater with G. Equal elements are called S if their position ≤ pos and G else. So then you are maintaining dp[prefix][number of S] — number of ways to choose B such that it should contain pos and have fixed number of elements marked as S. So the answer is sum of dp[n][s] for all s ≥ 1. dp[prefix > pos][0] = 0 because you have already lost your element x.
Conclusion: TRY TO FIX SOME PARAMETER IN THE WAY THAT WILL SIMPLIFY THE PROBLEM AS MUCH AS POSSIBLE. ESPECIALLY IN DP PROBLEMS.
Also I made very stupid bug in this problem. I spent a lot of time trying to find bug in DP transitions, but here we are:
I found this bug only on next day after second Umnik’s contest.
Conclusion: TRY TO FIX SOME STUPID BUGS FIRST AND THEN FIND LOGICAL FALLACIES. IF YOU CANNOT FIX IT NOW, TRY LATER!!!
On 4th and 5th of July I was upsolving E1 and E2 from this contest. It is also DP problem. You should count number of pairs (p, q) p, q — permutations such that p < q (lex) and inv(p) > inv(q). In E1 n ≤ 50, in E2 n ≤ 500. That is all. The idea is showed at the picture below:
So I need to count the number of pairs (p’, q’) of fixed length n such that the difference of their inversions is more than fixed k. Let this number be f(n, k). In E1 is is enough to count dp[n][k] — number of permutations of length n with exactly k inversions. f(n, k) is counted through dp[n][k]. It will lead to O(n⁵) solution. In E2 you count f[n][k] directly and get O(n³) solution. Details are not important, but to get transitions to both DPs you have similar idea. How to count something for permutation of length n if you have all answers for length n -1? Look at picture:
Conclusion: LOOK AT THE DEFINITION OF LEX!!!
I have also found some interesting recurring idea in tasks on permutations. You can see it in tasks J from Umnik’s day 2 and this task. This idea is to represent permutations in the form of the graph i->p[i]. So this graph consists of only directed cycles! This idea greatly simplifies further reasoning in the problem. For example, any swap operation or a similar one can be represented as joining or disjoining some cycles. And using this cycles you can count some useful characteristic of the whole permutation.
Conclusion: IF YOU SEE TASK ON PERMUTATION AND YOU SHOULD SOMEHOW CHANGE IT REMEMBER ABOUT REPRESENTATION OF PERMUTATION AS GRAPH I →P[I]
What’s about bugs again? This can be one the best examples of my carelessness:
Example: submissions on task H from Umnik’s Day 2. This problem was solved by using ternary search. I got AC, but I should check normal solution in analysis later!
BINARY SEARCH! Remember these words forever! A lot of tasks are much easier than it seems if you try to apply it.
This problem is the example of using tins and touts on tree to maintain some data structure like segment tree or Fenwick to answer some queries. Main idea is to use to check whether u is an ancestor of v.
tin[u] ≤ tin[v] and tout[v] ≤ tout[u]. then u is an ancestor of v
Queries in this task:
Let’s maintain 2 segment trees (minimum — ‘mn’ and maximum — ‘mx’ on range with update in point) with tin[v] is index(point) and its value is tout[v] if this vertex is added in structure or ∞(-∞) respectively.
2. Add v in ‘mn’
- While you query minimum on range [tin[v], ∞) in tree ‘mn’ and find vertex u with tout[u] ≤ tout[v], delete it from ‘mn’. If at least one u was found — put p[v] in ‘mn’
3. Query maximum on range (-∞, tin[v]] in tree ‘mx’. If some u with tout[u] ≥ tout[v] is found, so v is filled. But then query minimum on range [tin[v], ∞). If some u with tout[u] ≤ tout[v] is found that means that THIS VERTEX U CLEARED VERTEX V AND THEN NOONE FILLED IT.
Conclusion: YOU CAN QUERY SOMETHING ON RANGES OF TYPE [TIN[V], TOUT[V]] IN TREES. YOU CAN PUT VERTEX IN STRUCTURE AND THEN DELETE IT ALSO
Last idea I want to mention is idea with flows in task A from Umnik’s Day 2 contest. In this problem you can add k extra capacity at every edge of the network to get maximal possible flow. So let’s add duplicate for every edge. This duplicate will have infinite capacity and cost 1. Original edges will have cost 0. Now you should find maximal flow with cost ≤ k! Amazing task reduction!
