### Qingyu's blog

By Qingyu, history, 8 months ago,

Let's discuss the problems here.

How to solve H. (Hoshi Sudoku) and I. (Imbalance)?

• +36

 » 8 months ago, # |   +26 How to solve G, M?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +30 G can be solved by finding a partition s.t. every vertex has more neighbours in other part than in its part. This can be done by iteratively taking a vertex that does not satisfy this condition and moving it to the other part. The number of inner edges decreases and thus this process converges.
•  » » 8 months ago, # ^ |   +21 G: If you can find a cycle of even size in every connected component, you can keep a tree with 1 edge added such that the only cycle in the result will be that even cycle, so the graph will obviously be bipartite. To find a cycle of even size, find a maximal path. Because it's maximal, all 3 of the endpoints' neighbours will be on the path; one will obviously be right next to it on the path, one will be $a$ edges away and one will be $b$ edges away. If $a$ is odd, you found an obvious even cycle. If $b$ is odd, you found an obvious even cycle. If $a$ and $b$ are even, you can make an even cycle of the path between those 2 neighbours and the original endpoint.M: Make a graph with edges $x$ -> $(x+c_i)$ $mod$ $c_0$ with cost $c_i$, now the answer is (the maximum distance from $0$ to any other node)-$c_0$. You don't have to run dijkstra with $n \cdot c_0$ edges for each query; you can keep the distances from the previous iteration of dijkstra and just use the edges using the new $c_i$ because the order in which the $c_i$ are added doesn't matter, so you can answer each query in $O(c_0$ $log$ $c_0)$.
•  » » » 8 months ago, # ^ |   +5 M: you don't even need log, you can update values greadily: staring from each s, try s->s+c, s+c->s+2c while you do better. You can see that this way you try each edge O(1) times
•  » » » » 8 months ago, # ^ |   0 Or now that I think about it, as I said (and implemented) it doesn't seem to be true
•  » » » » » 8 months ago, # ^ |   0 It will work, if you run each cycle twice.
•  » » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 yeah, if you run full two cycles, then yes. What I did was "do it while it's better approach" and I think it should be $\Theta(c_0^2)$ in bad cases
•  » » 8 months ago, # ^ |   0 Thank you!
 » 8 months ago, # |   +15 How to solve F?
•  » » 8 months ago, # ^ |   +8 Let dp[i][j] be the minimum amount of money required for the first $i$ days if the $j$-th student wasn't working on the $i$-th day, and let pref[i][j] be the prefix sum by rows of $c$. If dp2[i][j] is the minimum amount of money required for the first $i$ days if the $j$-th student was working on the $i$-th day, then dp2[i][j] is the minimum from $k=i-a_j$ to $k=i-1$ of dp[k][j]+pref[j][i]-pref[j][k]. You can separate pref[j][i] from dp[k][j]-pref[j][k] and minimizing dp[k][j]-pref[j][k] can easily be done using one monotonic queue for each $j$. dp can easily be computed from dp2.
•  » » » 8 months ago, # ^ |   0 Thanks
•  » » » 8 months ago, # ^ |   +10 An alternative solution: note that the optimal solution always uses one of the three cheapest students on each day (otherwise, you could use one of them instead, since there are only 2 potentially forbidden students, the neighbors of this day). Thus, we can do the naive dp where we store the cheapest cost if the last student was $s$ and has been awake for $d$ days, but we only process the 3 cheapest students on each day.
 » 8 months ago, # |   +28 H: There are about 10^12 solutions to the puzzle. If we consider permutations of 1-9 in the solved puzzle as equivalent, the number of solutions drops to about 2 million. We can fix the numbers in one region and use recursion/backtracking to enumerate all the solutions. This can be done in a way similar to classical sudoku solvers: go through the cells in some order and try all digits that don't share a row or region with another instance of the same digit.After precomputing these solutions, we need to check whether each one is compatible with the clues with some permutation of 1-9, and if so, the number of permutations. This turns out to always be (number of digits that do not appear in the clues)!
 » 8 months ago, # |   0 Is there a mirror / website where you can upsolve the problems?
 » 8 months ago, # | ← Rev. 3 →   +8 I: we will construct the tree bottom to top. Fix $h$, and consider lowest vertices with height $\geq h$. Consider these vertices left to right, and write down heights of their children in a sequence. Initially $h = 2$, and the sequence consists of $0$'s and $1$'s. Going from $h$ to $h + 1$, we can: combine two adjacent $h - 1$'s into a single $h$; combine adjacent $h-2$ and $h-1$ into an $h$, increase imbalance by $1$; leave an $h - 1$ as it is (note that in this case imbalance will increase by $1$ on the next step). Let $x, y$ be the number of $h - 1$'s and $h - 2$'s in the sequence. Note that: $y \leq k$ at all times; for $h = 2$ values of $x$ and $y$ determine $n$ unambiguously, this is our base case. Compute $dp[x][y][b] =$ the number of ways to obtain a sequence with given $x$ and $y$, and accumulated imbalance $b$ ($h$ is unimportant!). Crucially, upon careful examination of the above $h \to h + 1$ transformation, we find that reachable permutations of $h - 1$ and $h - 2$ are equally distributed if $x, y$ are fixed. The new values $x', y'$ depend only the number of elements chosen with option 3, and the number of ways to proceed (assuming equal distribution) is found with simple combinatorics in each case. The answer is $dp[1][0][k]$. Complexity is $O(nk^3)$.Elaborating on the transtition: suppose that $y'$ copies of $h - 1$ are carried over. Then: $y'$ copies are reserved; further $y$ copies are matched with the $h - 2$'s, the remaining $x - y' - y$ copies are split into pairs. Then $x' = p + y$, where $p = (x - y - y') / 2$ is the number of pairs. The number of ways to do choose a permutation and do this is $W = {x' + y' \choose y', p} \times 2^y$. Thus, we should add $\frac{dp[x][y][b]}{x \choose y} \times W$ towards $dp[x'][y'][b + y]$.
•  » » 8 months ago, # ^ |   0 Come to think of it, top-to-bottom version of this is significantly easier: start from $dp[1][0][0] = 1$, and successively choose how many copies of $h$ will be decomposed into $h - 1, h - 2$.
•  » » » 8 months ago, # ^ |   0 You can do this without the dp; the number ways of writing a number as at most 20 powers of $2$ is quite small, so you can just do recursion with pruning (adding memoization makes the complexity the same as yours).
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Actually, I didn't realize exactly what your solution is. I'm pretty sure there are only $O(poly(k) polylog(n))$ different reachable states if you go top down, so this problem should be solvable for very large $n$.
•  » » » » » 8 months ago, # ^ |   0 Yes, my submit from the contest is $O(\log n \cdot k^4)$ dp (probably there is an additional $\log k$ for how much bigger than $\log n$ height can be, not sure), if ignore $O(n)$ precalculation of factorials, which is not necessary.
•  » » » » » 8 months ago, # ^ |   0 Very nice observation!
 » 8 months ago, # |   0 How to solve K? We tried sampling but we could not reach the precision error in the statement.
•  » » 8 months ago, # ^ |   +10 We integrated numerically over $z$; within a plane, we used black-box halfplane intersection and circle-polygon intersection, both from KACTL.We found that surprisingly, you only need to take $z$ in increments of $0.01$ ($10^{-2}$) in order to have enough precision to pass all tests.
•  » » » 8 months ago, # ^ |   0 Amazing! Thanks for the solution!
 » 8 months ago, # |   0 A: whats the proof that the answer is always in the shape of young table? C: whats the efficient way to implement it? i did bfs with 25 bit bitmask. ran the bfs for each of the 5 numbers. I implemented the operations in ~5 bitwise operations. got tle. not sure if generating/storing the string along with the mask is costly or not.
•  » » 8 months ago, # ^ |   +8 For C, you can do a single BFS from the target state, so you shouldn't have to repeat it for each number/each testcase.
•  » » 8 months ago, # ^ | ← Rev. 2 →   +8 For C there are only $\binom{25}{5} \approx 53000$ useful states, so naive implementation (each state takes $5^2$) should be enough for the time limit, no need to struggle on bitwise operation. The key point is to do BFS only once.
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 For A, I think you can just you can just make the figure compact and see that the number of sides shared by two cells does not decrease: suppose all cells have positive coordinates $(x, y)$ and you first keep moving all cells downward (i.e. along $y$-axis) as long as cells have positive coordinates and no two cells coincide. Then you do the same thing but along $x$-axis. You can see the figure then has the shape of Young tableau.This gives you the maximal perimeter you can achieve while the area is fixed. And the perimeter is equal to the perimeter of the bounding box of the figure. It is also easy to see that you can achieve any perimeter (which has to be even) between the lower bound shown above and the trivial upper bound (by moving one cell to the border and thus making bounding box larger).
 » 7 months ago, # |   -10 How to be as strong as Qingyu?
 » 7 months ago, # | ← Rev. 2 →   0 How to solve A, L?