Qingyu's blog

By Qingyu, history, 3 years ago, In English

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

  • Vote: I like it
  • +100
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with problem N in Div2? Isn't is a pretty straight forward bin search?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it +58 Vote: I do not like it

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, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Could you please elaborate, how you came up with the formula for $$$f[a] [b]$$$?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

      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, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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, # ^ |
      Vote: I like it +53 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G and J?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it +13 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +3 Vote: I do not like it

What's the easiest way to solve M?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    You just take the intersection of halfspaces from the library and that's it ¯\_(ツ)_/¯ /s

    At the start you ensure that $$$x_1<x_2$$$ etc. by possibly negating these.

    Let us define an octant as a part of space satisfying $$$x \ge a, y \ge b, z \ge c$$$ for some (a, b, c). You express this intersection through incl-excl principle on 8 octants, so the task is reduced to computing the volume of the intersection of this tetrahedron with one octant. However this tetrahedron is an intersection of an octant with a halfspace, so we may as well first intersect these two octants to get another octant and now we just need to compute the intersection of one octant with that halfspace. This is easily doable if we compute lengths of sides of resulting tetrahedron what is done by moving our point in each of 3 directions and computing ratios of some determinants.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You definitely should share your library XD

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And here is my clean code: https://ideone.com/baWvxN

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a link to an official contest? It is being said that the contest is CCPC finals.

»
3 years ago, # |
Rev. 3   Vote: I like it -64 Vote: I do not like it

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, # |
  Vote: I like it +23 Vote: I do not like it

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, # |
  Vote: I like it +8 Vote: I do not like it

How to solve K?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.