### Qingyu's blog

By Qingyu, history, 3 years ago,

GP of Beijing is finished now. How to solve H(Nonsense) and I(Number Theory)?

• +100

 » 3 years ago, # |   0 What's wrong with problem N in Div2? Isn't is a pretty straight forward bin search?
•  » » 3 years ago, # ^ |   0 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}$
 » 3 years ago, # | ← Rev. 2 →   +58 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).
•  » » 3 years ago, # ^ |   +10 Could you please elaborate, how you came up with the formula for $f[a] [b]$?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +13 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.
•  » » » 3 years ago, # ^ |   +13 Divide one polynomial by the other polynomial. You only need coefficients of small powers, works pretty much the same as in one-variable case.
•  » » 3 years ago, # ^ |   +53 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}$.
 » 3 years ago, # |   0 How to solve G and J?
•  » » 3 years ago, # ^ |   +8 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 Unable to parse markup [type=CF_MATHJAX], and the $i$-th node of $a_1$ be Unable to parse markup [type=CF_MATHJAX]. Let the length of $a_0$ be $l_0$, and the length of $a_1$ be $l_1$. It will always be true that Unable to parse markup [type=CF_MATHJAX] and Unable to parse markup [type=CF_MATHJAX], meaning that those paths always start and end at the same node. It is also possible that Unable to parse markup [type=CF_MATHJAX], meaning that the answer is a cycle of 1s, or that Unable to parse markup [type=CF_MATHJAX], meaning that the answer is a cycle of 0s.When adding node $i+1$, by looking at the cases where Unable to parse markup [type=CF_MATHJAX] based on Unable to parse markup [type=CF_MATHJAX] and Unable to parse markup [type=CF_MATHJAX], Unable to parse markup [type=CF_MATHJAX] based on Unable to parse markup [type=CF_MATHJAX] and Unable to parse markup [type=CF_MATHJAX] and Unable to parse markup [type=CF_MATHJAX] based on Unable to parse markup [type=CF_MATHJAX], Unable to parse markup [type=CF_MATHJAX] and Unable to parse markup [type=CF_MATHJAX] you can always find a way to add $i+1$ to the answer.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +8 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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
 » 3 years ago, # |   +13 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.
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   +3 What's the easiest way to solve M?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +20 You just take the intersection of halfspaces from the library and that's it ¯\_(ツ)_/¯ /sAt the start you ensure that $x_1 •  » » » 3 years ago, # ^ | 0 You definitely should share your library XD •  » » 3 years ago, # ^ | 0 And here is my clean code: https://ideone.com/baWvxN  » 3 years ago, # | 0 Is there a link to an official contest? It is being said that the contest is CCPC finals. •  » » 3 years ago, # ^ | 0 No. It was held by a offline domjudge server. •  » » » 3 years ago, # ^ | +30 All the contest material can be accessed via http://github.com/ftiasch/ccpc-final-2020  » 3 years ago, # | ← Rev. 3 → -64 LOL problem B is a troll. Is it intended to solve the$n = 4$case or the whole problem without using memory? •  » » 3 years ago, # ^ | +10 No. The model solution consumes$O(m)$memory. •  » » 3 years ago, # ^ | -10 Ok i now can solve the whole problem with$O(1)$memory  » 3 years ago, # | +23 What was the point of including IMO 2019 P5 (problem E)? Shortlist contains the formula for the number of operations for general string  » 3 years ago, # | +8 How to solve K? •  » » 3 years ago, # ^ | +16 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\$.
 » 3 years ago, # |   0 How to solve B?
•  » » 3 years ago, # ^ |   +8 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.