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

# | User | Rating |
---|---|---|

1 | Benq | 3796 |

2 | tourist | 3722 |

3 | Radewoosh | 3719 |

4 | ecnerwala | 3578 |

5 | ksun48 | 3462 |

6 | Um_nik | 3456 |

7 | maroonrk | 3445 |

8 | jiangly | 3431 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 207 |

2 | awoo | 186 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

5 | Radewoosh | 177 |

7 | -is-this-fft- | 176 |

7 | maroonrk | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 171 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/16/2021 05:40:31 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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}$$$

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]$$$?

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$$$.

Now, $$$f(a, b)$$$ is the number of paths of length $$$(n + 1)$$$ from $$$1$$$ to $$$a + b$$$. Consider one of such paths.

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.

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.

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?

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

octantas 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.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

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.