### Qingyu's blog

By Qingyu, history, 14 months ago, GP of Beijing is finished now. How to solve H(Nonsense) and I(Number Theory)? Comments (28)
 » What's wrong with problem N in Div2? Isn't is a pretty straight forward bin search?
•  » » Overflow in case of small $t$ values. When we count the number of parts that we can produce in $\frac{10 ^ {18}}{2}$ minutes, the answer will be about $10 ^ 5 * 10 ^ {18}$
 » 14 months ago, # | ← Rev. 2 →   H: The problem asks $\frac{1}{a!b!} \left. \left(\frac{\partial}{\partial X}\right)^a \left(\frac{\partial}{\partial Y}\right)^b \sum_{i=0}^n X^i Y^{n-i} \right|_{X=x,Y=y} = \frac{1}{a!b!} \left. \left(\frac{\partial}{\partial X}\right)^a \left(\frac{\partial}{\partial Y}\right)^b \frac{X^{n+1}-Y^{n+1}}{X-Y} \right|_{X=x,Y=y}$. It is the same as $\frac{1}{a!b!} \left. \left(\frac{\partial}{\partial X}\right)^a \left(\frac{\partial}{\partial Y}\right)^b \frac{(X+x)^{n+1}-(Y+y)^{n+1}}{(X+x)-(Y+y)} \right|_{X=0,Y=0}$, so we want the coeffient of $X^aY^b$ in $\frac{(X+x)^{n+1}-(Y+y)^{n+1}}{(X+x)-(Y+y)}$. For $x \ne y$, this division can be done in increasing order of $a$ and $b$ (i.e. f[a][b]/=(x-y); f[a+1][b]-=f[a][b]; f[a][b+1]+=f[a][b];). For $x = y$, the answer is $\binom{n+1}{a+b+1} x^{n-a-b}$ (which can also be deduced combinatorically).
•  » » Could you please elaborate, how you came up with the formula for $f[a] [b]$?
•  » » » 14 months ago, # ^ | ← Rev. 2 →   Consider multiplying a given bivariate polynomial $f$ by $(X - Y + (x-y))$. This can be done by f[a+1][b]+=f[a][b]; f[a][b+1]-=f[a][b]; f[a][b]*=(x-y); in decreasing order of $a$ and $b$. Then the division is its inverse.
•  » » » Divide one polynomial by the other polynomial. You only need coefficients of small powers, works pretty much the same as in one-variable case.
•  » » I will describe the combinatorial idea of H here.Consider a digraph of $(a + b)$ vertices $1, \dots, a, a + 1, \dots, a + b$. For each $1 \leq i < a + b$, there is an edge $i \to i + 1$. For each $1 \leq i \leq a + b$, there are $x$ self-loops $i \to i$. For each $a + 1 \leq i \leq a + b$, there are $(y - x)$ self-loops $i \to i$. There loops are called special. Now, $f(a, b)$ is the number of paths of length $(n + 1)$ from $1$ to $a + b$. Consider one of such paths. If it doesn't pass through any special loop on vertex $a + 1$, the number of ways is $f(a + 1, b - 1)$. Otherwise, we can split the path at its first encounter, it's $(y - x) f(a + 1, b)$. Therefore, we have $f(a, b) = f(a + 1, b - 1) + (y - x) f(a + 1, b)$. Or equivalently, $f(a, b) = \frac{f(a - 1, b).- f(a, b - 1)}{y - x}$.
 » How to solve G and J?
•  » » G: The answer for the first $i$ nodes is always going to be of the form of 2 paths: one path $a_0$, which is made up of only edges with 0s written on them, and another path $a_1$, which is made up of only edges with 1s written on them. Let the $i$-th node of $a_0$ be $a_{0,i}$, and the $i$-th node of $a_1$ be $a_{1,i}$. Let the length of $a_0$ be $l_0$, and the length of $a_1$ be $l_1$. It will always be true that $a_{0,1}=a_{1,1}$ and $a_{0,l_0}=a_{1,l_1}$, meaning that those paths always start and end at the same node. It is also possible that $l_0=1$, meaning that the answer is a cycle of 1s, or that $l_1=1$, meaning that the answer is a cycle of 0s.When adding node $i+1$, by looking at the cases where $l_0=1$ based on $C_{i+1,a_{1,1}}$ and $C_{i+1,a_{1,2}}$, $l_1=1$ based on $C_{i+1,a_{0,1}}$ and $C_{i+1,a_{0,2}}$ and $l_0,l_1>1$ based on $C_{i+1,a_{0,1}}$, $C_{i+1,a_{1,2}}$ and $C_{i+1,a_{0,2}}$ you can always find a way to add $i+1$ to the answer.
•  » » 14 months ago, # ^ | ← Rev. 3 →   J: Let $\mathrm{dp}[l][r][a][b]$ be the solution to the problem if we are only allowed to include the elements that are in positions $l \ldots r$ and have value in $a \ldots b$, such that the maximum value we pick is exactly $b$. To calculate it, notice that we only have one position $m$ where the array has value $b$. If we include it, the maximum of the elements with positions $l \ldots m - 1$ must be less than the minimum of the elements with positions $m + 1 \ldots r$. We can now calculate the dp by iterating over al possible maximum values of the left side. The complexity is $O(n^5)$ but it has a very small constant.G: There are probably many constructions but here is mine. I interpret the input as a graph, with 1 meaning "edge" and 0 meaning "no edge".Let's consider the spanning forest obtained by DFS. It is always possible to remove some path from the root of a tree down to some vertex of the same tree, such that after removing, no connected component will contain more than half (rounded up) of the remaining vertices. You can prove this with a greedy argument, similar to the existence of a centroid. This removed path will be the first part of the permutation we are asked to find.For the second part, remove vertices from the remaining connected components so that you will never take from the same component in a row. This is kind of a well-known problem. The removed vertices in the order you remove them form the second part of the permutation. Since the original spanning forest was constructed by DFS and the construction of the permutation does not allow you to take a descendant or ancestor of a vertex right after picking a vertex, we can be sure that adjacent vertices in the permutation are not connected by an edge.Finally, if the first vertex you removed in the first part happens to be from the same tree as the last vertex you removed in the second part, you may need to perform a cyclic shift.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   G: You just construct this cycle inductively adding vertices in 1, 2, 3, ..., n order. If the cycle is monochromatic then you put the new vertex anywhere. If it isn't then you take one of the two vertices where color changes. Based on the color of the edge from it to the new vertex you put the new one either directly before or after it.Another advantage of that solution is that it queries only 2n edges, so could be linear if edges were provided through library IsEdge(u, v).I like your solution as well though.EDIT: Whoops, I noticed that dorijan already posted about that solution xd
 » I: Rewrite $\sum_{k} o_k x_k = n$ as $\sum_{k} (10^k - 1) x_k = 9n$ and then as $\sum_{k} 10^k x_k = 9n + \sum_{k} x_k$. All the $x_k$ (except $x_1$) are bounded by 5, because otherwise we can replace $6 o_k x_k$ as $o_{k+1} - 4 o_k x_k - o_1$ which is not worse. So, $\sum_{k} x_k$ is bounded by $5 len + O(1)$. If we will choose $x_k$ in decreasing order of $k$, the already chosen sum $\sum_{k} 10^k x_k$ cannot differ much from $9n$. Thus, we can do digit dp, storing $\sum_{k} x_k$ and the difference between already constructed sum and $9n$ in higher ranks. It stops working when we come close to $5 len$, so we will stop after reaching 5 lowest ranks, and will just optimally construct the remaining difference, which we can precalculate with dijkstra in the beginning.It's $O(len^2)$ with big constant, the first version of our solution didn't pass, but it wasn't hard to optimize.
•  » » The model solution starts from this idea. We optimize it into $O(\mathrm{len}^2)$. We know the DP before the contest, but it's super hard (and somehow unfair) to distinguish between these two solution by their constant.
 » What's the easiest way to solve M?
•  » » 14 months ago, # ^ | ← Rev. 2 →   You just take the intersection of halfspaces from the library and that's it ¯\_(ツ)_/¯ /sAt the start you ensure that $x_1 •  » » » You definitely should share your library XD •  » » And here is my clean code: https://ideone.com/baWvxN  » Is there a link to an official contest? It is being said that the contest is CCPC finals. •  » » No. It was held by a offline domjudge server. •  » » » All the contest material can be accessed via http://github.com/ftiasch/ccpc-final-2020  » 14 months ago, # | ← Rev. 3 → LOL problem B is a troll. Is it intended to solve the$n = 4$case or the whole problem without using memory? •  » » No. The model solution consumes$O(m)$memory. •  » » Ok i now can solve the whole problem with$O(1)$memory  » What was the point of including IMO 2019 P5 (problem E)? Shortlist contains the formula for the number of operations for general string  » How to solve K? •  » » Calculate$f(0)$with prefix function. For$k > 0$it's easy to see that$f(k)$equals either$k + m$or$f(p(k))$, where$p$is prefix function of$s\$.
 » How to solve B?
•  » » If n > 1 then x divides b, you can check all pairs (x, b) (there is at most 1 corresponding a). If n = 1 then if k = 1 answer is 2m(2m + 1), otherwise 0.