### Qingyu's blog

By Qingyu, history, 15 months ago, How to solve Problem 7, 10? Is there any tutorial available? Comments (34)
 » How to solve Nanoassembly from div2?
•  » » Just google a formula for flipping a point over a line
 » 15 months ago, # | ← Rev. 2 →   In problem 7 there's a simple dp in O(C*B). You run it for C<=1e4 and see that you only need small number of B (200ish). IIRC For C <= 2e5 ans <= 301
•  » » I did that + realize that the pattern depends on the parity of N, so just make a program to print all ranges of answers and then submit a hardcoded solution (because of troubles with ML)
•  » » I also got this fact. Also I noticed that we can use ternary search to get the answer. However, for C = 2e5 my solution worked for about 5 — 6 seconds.
•  » » » Well, if you managed to let it finish in 5 sec you could send all the answers in static array. Our solution works 0.8s
 » 15 months ago, # | ← Rev. 2 →   For problem 10, use FFT to find, for each cell, how many # are there if the rectangle starts in this cell that should be . and vice versa(it's a match if both are 0). Due to the tight memory limit, you'll probably need to use NTT instead of FFT.
•  » » I would also mention that 1) we need only two 2000x2000 arrays instead of 4000x4000 (therefore my custom complex was perfectly fine in terms of memory), and 2) we can do only one multiplication, if we assign $1$, $i$, and $1+i$ to cells ., # and _ of the board, and $1$, $-i$, and $0$ to these cells of the vault.
•  » » » How to use only two 2000x2000 arrays?
•  » » » » Just multiply them as you always do. In res[i][j] you will have the sum of all coefficients of $x^{2048k+i}y^{2048l+j}$ of the result. It is because 1) you got this result only looking at the values in $2048$-th roots of unity, or 2) because in when you use fft to multiply two 1d polynomials, you basically do this in the ring modulo $x^n-1$.After this you can manually exclude all candidates who correspond to vault being placed on the torus instead of the normal board.
 » Task 6 is the worst thing that I have met. 5 hours just to have 19 test. Can anyone explain how to write robust Gauss method?
•  » » What do you mean by robust? We are working in $\mathbb{Z}_7$, so there are no precision problems
•  » » » I mean something mystical like solve all existing problems. Do you mean that it is enough to use Gauss by module?
•  » » » » Well, yes, because you are only interested in the rank of the matrix over $\mathbb{Z}_7$. Calculating the rank over $\mathbb{R}$ does not work, since, for example, (it is not a valid example, but you can construct a valid one similarly) one button that switches the day in the first universe 7 times does not work, but the rank over $\mathbb{R}$ is 1
•  » » » » » Thanks a lot)
 » How to solve A from div. 2. I tried two pointeres but got WA12.
 » how to solve problem 1 and problem 6? i tried to debug for 2 hours but still didn't understand what's wrong.
 » How to solve 2: Orienteering?
•  » » I was iteratively adjusting the points, each adjustment of a single point was some binary search. However, it costed me +20 to find proper number of iterations of each and I do not think it was intended.
•  » » What we did was the following:First, choose MAGIC points on each circle and choose the best route in O(n * MAGIC^2). Now near each of the points on the optimal path choose MAGIC points again and find the optimal path again.
•  » » We did gradient descent to find the optimal route. Each point was parametrised with the angle. However, this solution was very prone to converge to local optimum instead of global optimum if angles were not initialised properly.The last initialisation that worked for us was finding the optimal point in the circle if only the previous and next circles were relevants. Circles in the endpoints were initialised pointing the adjacent circle.
•  » » The "official" solution is to take $K$ samples on each circle, and compute minimum distance through them using $O(N K^2)$ dynamic programming. Quite importantly, the case of $N = 2$ must be considered analytically. For $N >= 3$ it can be proved that relative error of sampling solution does not exceed $\Theta(1 / K)$ with some constant. Taking $K = 2500$ should provably suffice, although even something as low as $K = 200$ passes due to smooth nature of the distance function.Also, circular shape is too nice to stop various local searches from getting ACCEPTED. I personally implemented one with randomly perturbing polar angle on random circle many times.
 » Can anyone tell me what is worth paying attention to in Hockey? I debugged for 2 hours and got 5 WAs.
•  » » My AC solution, you can try to stress with it.
 » How to solve problem 9? I thought a solution using trie but got WAs.
•  » » 15 months ago, # ^ | ← Rev. 3 →   You replace each a[i] with a[i]*i! and do the trie solution. The answer is len(poly1) + len(poly2) — 2 * len(common suffix)
•  » » » thanks a lot!
 » Here is tutorial (in Russian) by problem authors: https://www.youtube.com/watch?v=NFS6_6m6c4g
 » Can anyone please explain problem 1(Polesov and Work)?
•  » » You have a vector $v = (a, b)$, so consider point $P = \frac{v}{||v||} \cdot r$ first. This is the point giving maximum dot product, but it is real-valued. Let's round both its coordinates down to integers, and you'll get some pretty good point $Q$, which gives initial estimate on the goal function.Which points can be better than $Q$? Draw a line passing through $Q$ normal to $v$, it will cut a thin segment from the circle. The integer points in this segment are better than the initial record. The thickness of the segment is $O(1)$, so it contains at most $O(\sqrt{R})$ integer points. Iterate through all of them and find the best one — that would be the answer.The remaining is technical details. Usually you find $X_{min}$ and $X_{max}$ bounding the segment (e.g. compute angle of the segment from thickness and radius, then find min/max points), then iterate through all $X \in [X_{min} \ldots X_{max}]$, and check $Y = \sqrt{R^2 - X^2}$ for each of them. Just note that double precision is not enough to compute such $Y$ precisely, so you might need plus/minor one adjustments.
•  » » » Is Q equal $r\frac{\sqrt{2}}{2}$?
 » Any hints for problem 11?
•  » » 15 months ago, # ^ | ← Rev. 3 →   Here are some hints. Hint 1The function $f$ (and $g$) can be represented as a directed graph with edges $(i,f(i))$. Hint 2The graphs for $f$ and $g$ have the following structure: each connected component is a cycle with trees attached to it. For each vertex we can find its depth $d[v]$ in the tree it is on, its cycle's id $c[v]$, its cycle's length $l[v]$, the position of the vertex on the cycle $p[v]$. For the latter we enumerate the vertices on the cycle from $0$ to $l[v]-1$ in order of traversal: each vertex on the cycle gets a position, each vertex on the attached tree gets a position of the vertex it would be on if we applied the function to it $l[v]\cdot k$ times for some $k$. Hint 3Consider a meeting vertex $v$ for a query $(x, y)$, i.e. $v=(f^t)(x)=(g^t)(y)$ for some $t\geq0$. It's one of the three types: $v$ is on a cycle in both $f$ and $g$, $v$ is on a tree in both $f$ and $g$, or $v$ is on a cycle only in one of the functions. We should solve the problem separately for the three types of $v$ and join the solutions by logical OR. The following hints show how to solve the problem for the three cases. Hint 4The first case: $v$ is on cycles in both $f$ and $g$. Then, $p_f[x] - p_g[y]$ must be equal $p_f[v] - p_g[v]$ modulo $GCD(l_f[v], l_g[v])$. Also, $c_f[x]=c_f[v]$ and $c_g[y]=c_g[v]$. Throw $(x, y)$ pairs into a map with a key $[c_f[x], c_g[y], (p_f[x] - p_g[y]) \% GCD(l_f[x], l_g[y])]$. Now, iterate through $v$ and mark as YES-queries all those by the key $[c_f(v), c_g(v), (p_f[v] - p_g[v]) \% GCD(l_f[v], l_g[v])]$. Hint 5The second case: $v$ is on trees in both $f$ and $g$. Now, the first condition is $d_f[x] - d_g[y] = d_f[v] - d_g[v]$. The other conditions are more complicated: we need $x$ to be in $v$'s subtree in $f$ and we need $y$ to be in $v$'s subtree in $g$. We will now get rid of the first condition (about depths). We break the queries into classes by the value of $d_f[x] - d_g[y]$. We break the vertices into classes by the value of $d_f[v] - d_g[v]$. A query class matches a vertex class if the values are the same. Now for each vertex class find the matching query class and solve the subproblem for the two classes. In each subproblem we only have the subtree conditions. Hint 6Run a series of DFS's on reversed edges from the root of each tree. Remember the in and out times for each vertex ($tin[]$ and $tout[]$). Now, the subtree conditions are written as: $tin_f[v] \leq tin_f[x] < tout_f[v]$ and $tin_g[v] \leq tin_g[y] < tout_g[v]$. Hint 7Look at the subtree conditions. Each vertex $v$ defines a rectangle on a plane spanning from $tin_f[v]$ to $tout_f[v]-1$ on one axis and from $tin_g[v]$ to $tout_g[v]-1$ on the other axis. Each query $(x, y)$ defines a point $(tin_f[x], tin_g[y])$ on the plane. If a point is covered by a rectangle, the query is a YES-query. Hint 8Compress the coordinates and use the sweep-line technique with a Fenwick's tree to keep track of the opened rectangles. This solves the second case. Hint 9Finally, the third case: $v$ is on a tree in one of the functions and on a cycle in the other one. Try mixing the ideas from previous cases:) You may want to use binary lifting to advance the queries to the time when one of the query vertices is on a tree and the other is on a cycle.
 » Is there testdatas or .pdf tutorial for the contest?