07.07.2021–08.07.2021
07.07.2021 — Upsolving of Umnik’s Day 4 and Codeforces Div. 2 Round 730
Talking about round, 4 tasks were solved — A, B, C, D1
I was stupid a lot during the contest. D1 is very easy task, but I spent too much time. It could be solved much quicker. Also I came up with a solution of D2, even succeeded to wrote it, but due to some bugs (how could I live without them) I have got it accepted only in upsolving.
Let’s talk about task C and D2 (D1 is just a case of D2).
In problem C you have 3 doubles — c, m, p. c + m + p = 1. They are probabilities of choosing corresponding item. Also there is double v:
0.1 ≤ v ≤ 0.9.
If you choose, for example, first item (with probability c), you have 2 cases:
- c ≤ v, so these item is no longer a valid item for choosing and c is distributed equally among the other remaining valid items.
- c > v, so c is decreased by v and v is distributed equally among the other remaining valid items.
So the sum of c + m + p is always 1. The goal is to count the expected number of choices before choosing third item.
The note is that v ≥ 0.1, p can only be increased, so c + m can only be decreased. If v ≥ c, this item is no longer valid, it is good. If v < c, so c + m is decreased by v /2 ≥ 0.05. So the answer cannot be great! (but I don’t want to give any estimations). So let’s run some recursive function and emulate choices. This is AC.
I don’t want to describe the D2 problem, but the key idea is to figure out how to determine z from this equation:
It is bitwise sum by modulo k ≤ 100. So let a be bit number i of x, b — of z, c — of y. Every time in this problem you have number x and you query some number y and if x is not equal to y, x becomes z. Let’s fix number x and we want to learn how to every time determine what will be x after past changes? So we will fix x. So a is fixed.
So (a + b = c) mod k. (b = c — a) mod k. Let’s query some number y1. How b will be changed? (a + b = c1) mod k, so (a = c1 — b = c1 — c + a) mod k. So every time we have constant c and sign of a. You change sign of a and change c on (c1 — c) mod k. That is idea how to get AC.
It was interesting idea on Umnik’s analysis about this task (A from his Day 3). We can run recursive function if we know that every internal node of recursive tree has at least one leave. That means, that size of tree is O(number of leaves). Check code:
I used this idea also in task F from Umnik’s Day 4. In this task you run recursive function to count the result from the suffix of string, like rec(c0, c1, result). c0 — number of left zeros, c1 — ones, result — result I wanna get from the left prefix of the string. Transitions are described in task and they are arranged in such a way that I can calculate some combinatorics instead of recursive run, so I found leave in almost every internal node. 31 ms and AC! Well done.
Conclusion: IF YOU RUN SOME RECURSIVE FUNCTION AND YOU CAN TERMINATE RECURSIVE CALL IN EVERY INTERNAL NODE — IT CAN TURN EXPONENTIAL TIME TO SOME VERY FAST POLYNOMIAL!
Story below will be about Umnik’s Day 4 tasks.
Task E can be reduced to checking the uniqueness of the perfect matching. The checking of uniqueness of maximum matching can be implemented by finding augmenting path from not saturated vertex or some cycle. If we find some, we can change not saturated edges to saturated and get new matching. But here we have even perfect one, so we can only find cycles. So let’s find matching by Kuhn algorithm, check whether it is perfect. Then try to find cycle. That’s all. I implemented this, but it is TL. Sad.
Task D was easy DP, but one of states was gcd of some set of numbers, that can be ≤ 10⁹. I was puzzled and tried to come up with another DP without this state or even greedy algorithm, until it dawned on me that gcd is some divisor of some number, amount of this numbers ≤ 300, so there are no more than 300*10³(as every number ≤ 10⁹). So it is easy 300*300*10³ ≤ 10⁸ solution with dp[i][gcd] = minimum cost.
Other tasks that were solved on contest are not worth of wasting my time, I will go to upsolve the remaining ones.
