Collection of problems that have no solve in OpenCup contest, or no upsolve in snarknews camp.

If a problem had both appeared in OpenCup and camp contests, OpenCup rules are applied. (ex: 67, 71, 73).

Sometimes snarknews recycles some old problems from his archive. They may not appear even though they have no upsolve. I believe snarknews decides this arbitrarily. For example, 41 is an old Japanese problem.

• 2 ~ 3: Ptz 2019 Winter
• 5 ~ 11: Bytedance Winter Camp 2019
• 13 ~ 23: GP of Bytedance, China, Baltic Sea
• 29: Moscow Pre-Finals 2019
• 31: GP of Daejeon
• 37 ~ 41: Discover Singapore 2019
• 43 ~ 53: Moscow International 2019
• 59 ~ 73: GP of Xian, Kazan, Warsaw (not in chronological order)

Lol. I got AC in 73 in 13.115s/15s by resubmitting the same TL code. Just try for several times.

Also, for some reason the model solution (from the same handout) passes this testcase, but gives a worse answer for another:

1
13 -36 364 843 562

Oh, nice... I think good idea is to write Snark on telegram.

For anyone wondering, it looks like that test case is $$$n = 0$$$ and $$$x_0 = 0$$$ (the 0-polynomial). We should either change the problem statement to allow $$$x_n = 0$$$ if $$$n = 0$$$, or we should drop the case.

19: Maintain set of vertices $$$A$$$ such that $$$\bigoplus_{v \in A} f(v) \neq \bigoplus_{(v, u): v \in A, u \in V \setminus A} g((v, u))$$$. Initially $$$A = V$$$. On each step we split $$$A$$$ in 2 almost equal parts and ask about each of them. Either one of them also satisfies the condition or we get a "complex" contradiction of the form $$$\bigoplus_{e \in E_1} g(e) \oplus \bigoplus_{e \in E_2} g(e) \neq \bigoplus_{e \in E_1 \bigtriangleup E_2} g(e)$$$. If we never get a complex contradiction we end up with $$$A$$$ containing a single vertex and since all degrees are small, we can find the contradiction naively. To deal with complex contradiction we need a uniform way to calculate $$$G(E_1) = \bigoplus_{e \in E_1} g(e)$$$. We can do it in segment tree style: split $$$E$$$ in 2 halves $$$E_L$$$ and $$$E_R$$$, let $$$E_{1L} = E_1 \cap E_L$$$ and $$$E_{1R} = E_1 \cap E_R$$$, calculate $$$G(E_{1L})$$$ and $$$G(E_{1R})$$$ recursively and let answer be $$$G(E_{1L}) \oplus G(E_{1R})$$$(actually since we don't have $$$\oplus$$$ it should be $$$(G(E_{1L}) \wedge !G(E_{1R})) \vee (!G(E_{1L}) \wedge G(E_{1R}))$$$ but let's just use xors to make formulas shorter). Now our complex condradiction will look like this: $$$((G(E_1) \oplus G(E_2)) \oplus G(E_3)) = (((G(E_{1L}) \oplus G(E_{1R})) \oplus (G(E_{2L}) \oplus G(E_{2R}))) \oplus (G(E_{3L}) \oplus G(E_{3R}))) = 1$$$, where $$$E_1 \bigtriangleup E2 \bigtriangleup E3 = \emptyset$$$. We ask about $$$((G(E_{1L}) \oplus G(E_{2L})) \oplus G(E_{3L}))$$$ and $$$((G(E_{1R}) \oplus G(E_{2R})) \oplus G(E_{3R}))$$$. If one of them is $$$1$$$ we can use recursion, otherwise we ask about $$$G(E_{iL})$$$ and $$$G(E_{iR})$$$, treat them like variables and ask about all intermediate values in formulas $$$(((G(E_{1L}) \oplus G(E_{1R})) \oplus (G(E_{2L}) \oplus G(E_{2R}))) \oplus (G(E_{3L}) \oplus G(E_{3R})))$$$, $$$((G(E_{1L}) \oplus G(E_{2L})) \oplus G(E_{3L}))$$$ and $$$((G(E_{1R}) \oplus G(E_{2R})) \oplus G(E_{3R}))$$$, since there surely will be a contradiction.

37: The number of (123)-avoiding permutations is Catalan number which gives the idea that the function might be P-recursive. And it turns out to be true. So you need any polynomial solution. This paper explains $$$O(n^2)$$$ dp for $$$m = 1$$$ which can be generalized for $$$m$$$ up to $$$3$$$.

37: First note that there are no increasing sequences of length 4, as then $$$m \ge \binom{4}{3}$$$. We'll count the number of 123-sequences by the middle element.

For $$$m = 0$$$, it's a well known result that the number of 123-free permutations is the Catalan sequence (you can see this by considering the path $$$(i, \min(a_1,\ldots, a_i))$$$). The number of non-inversions is given by https://oeis.org/A008549.

For $$$m = 1$$$, consider the unique middle element $$$a_j$$$. Then, it has one one number greater afterwards ($$$a_k$$$), and one number smaller before ($$$a_i$$$). We can think of this as gluing together the two 123-free permutations $$$(a_1, a_2, \ldots, a_{j-1}, a_k)$$$ and $$$(a_i, a_{j+1}, \ldots, a_n)$$$ at their bottom-most/right-most and top-most/left-most elements, with the requirement that the bottom and right elements are distinct (and symmetric for the 2nd). You can compute this using PIE on the $$$m=0$$$ case and FFT to combine.

For $$$m = 2$$$, you can do something similar; either there's one middle-point with 2 above and 1 below (or vice versa), and you glue together 2 123-free permutations excluding those sharing bottom/right points, or there are 2 middle points, and you treat it as gluing an $$$m=1$$$-permutation to a $$$m=0$$$-permutation.

For $$$m=3$$$, it's more of this casework, but it works out similarly; your middle points are $$$1\times 3$$$, $$$1 \times 1 + 1 \times 2$$$, or $$$1 \times 1 + 1 \times 1 + 1 \times 1$$$.

Overall, it's a lot easier to code if you have good polynomial-manipulation book code.

61: Find the smallest edge on the outer face. Let it be $$$e$$$ Look at its inner face: each min-cut uses either 0 or 2 edges on that face. It's easy to notice that we can always make one of those edges to be $$$e$$$. This means that we can decrease capacity of $$$e$$$ to 0 and increase capacities of all other edges on that face by the same amount, and all min-cuts will stay the same. Repeat this process until there are no more cycles. Congrats, we have built Gomory-Hu tree of the graph! Now on tree the problem can be easily solved with Kruskal's algorithm.

23: Find a source $$$s$$$ and sink $$$t$$$. They should be unique. Find all paths from $$$s$$$ to $$$t$$$. They should have lengths $$$n, n-1, ..., k+1$$$, where $$$k$$$ is length of the suffix link of $$$t$$$. The first edges on each of those paths correspond to first, second, ..., $$$n-k$$$-th symbols of the string. We don't know the last $$$k$$$ symbols, but they can be determined uniquely if we knew the suffix link of $$$t$$$. So we check all possible suffix links, build a string and check that graphs are isomorphic. You need to check all vertices as different strings can produce the same graph with different suffix links.

Yes, you should use the usual definition. I fixed the statement after the contest, but the old statement was used.

In one of the problems a few years ago connectedness of a graph was defined as "every vertex has an adjacent edge" xD. Fortunately it didn't matter to my solution.

71 is from GP of Kazan, you can read its editorial.

7 is problem D from AtCoder World Tour Finals 2019, you can find the editorial here.