snarknews's blog

New Year Prime Contest and New Year Blitz Contest 2020
By snarknews, history, 5 years ago, In English

Traditionally, SnarkNews runs two New Year Contests.

The New Year Blitz Contest (Multiple Language Round) will start at 18:00 31.12.2019 and ends at 06:00 01.01.2020 Moscow Time. Contest consists of 12 problems. Some of those problems are based on problems, used at official or training contests in 2018. Contest rules are based on the ICPC system with two important modifications.

  1. Penalty time is calculated as distance between time of first successful submit for the contestant on this problem and 0:00:00 01.01.2020, i.e. successful submissions at 23:50:00 31.12.2019 and at 0:10:00 01.01.2020 will both have penalty time 10 minutes (600 seconds).

  2. Multiple Language Round rule: If for the first successful submit for the contestant on the some problem was used the programming language, which was never used by this contestant in his previous first successful submits on other problems, contestant receives language bonus: his summary penalty time is decreased by 100 minutes (6000 seconds). Note that different implementations of the same language are counting as same language, i.e. Java 6 and Java 7 are both counted as Java, C++ 32 bit and C++11 64 bit both as C++. Additionally, C and C++ are counted as same programming language.

Contest will be running on Yandex.Contest system. Link for registration and participation.

16'th Prime New Year Contest will start at 23:00 30.12.2019 and finish at 23:59 10.01.2020 Moscow time. Traditionally, Prime New Year Contest consists of problems, which were presented at team programming contests in 2019 and never solved on the contest. For the Prime New Year contest plain ICPC rules are used.

Idea of Prime Contest was first implemented by Andrey Lopatin and Nick Dourov at Summer Petrozavodsk training camp at 2003; in Russian word "Prostoj" used in meanings "prime" and "easy", so, contest was called "Prostoj contest" but was composed of extremelly hard problems, numbered with prime numbers (2,3,5 etc). Since then such a numeration is traditionally used for contests, consisting of very hard problems only.

Contest will be running on Yandex.Contest system. Link for registration and participation.

Both contests have English statements. Registration is open till the end of the contest.

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

Comments Comments (33)
| Write comment?
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Yes! My favorite contest is back!!

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

This was fun :) Will there be solutions released in the future?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you have the sources of the Prime Contest problems? I'm just a bit curious.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +58 Vote: I do not like it

    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)
    → Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

On problem 67, I got TL by the source which got AC in upsolving the original OpenCup contest. I resubmitted the code, but the running time was almost the same, so I believe it's not due to the volatility of the judge environment. I also resubmitted to the original contest and got TL.

So here's my question: Did the judge environment or test data change? Well, I'm just too lazy to optimize my code, but I'll be glad if I can hear from you.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I though these were going to be impossible but I actually got one :O

How do you get a flag next to your name?

→ Reply
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Are tests to problem 3 (Aloha) correct? snarknews zimpha

I and Swistakk have both WA on test 5. We got hold of this test (from Petrozavodsk handouts), and it seems that one of the answers isn't optimal.

Extracted testcase (file #5, testcase #389)
Expected answer
Our answer + solution

Could you please look into it?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

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

    Extracted testcase (file #5, testcase #382)
    Model solution out
    Our out, the same as the expected answer in the test suite
    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +62 Vote: I do not like it

snarknews Would this be possible to extend this contest by something like a week? This year there are 21 problems which is very many and contest itself is pretty short. Last year there were 26 problems but it lasted to 23rd January and in previous years there were not more than 13 problems I think. Moreover I completely forgot about this contest this year and mnbvmar reminded me about it just yesterday, so I missed half of it and I have two busy days before its end :(.

→ Reply
»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I think the test data for task 47 (Zayin and Dirichlet) is incorrect, I have an assertion that $$$x_n \ne 0$$$, as guaranteed in the input, but it's failing on test 17. Does anyone have a copy of the test data to check? snarknews?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 19 and 37?

I have absolutely no clue about 19 even after an extensive amount of thinking — 50 queries limit sounds just absurdly tiny.

And how about 37? The limits suggest I should immediately copy-paste FFT from my library, but what next? I found some formulas counting just the number of good permutations (and a lengthy paper proving them). Maybe this problem works in a similar way?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    37
    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +68 Vote: I do not like it

      Here's a closed form for $$$N \ge 3$$$. You can find these by doing the problem analytically with the generating function of Catalan numbers.

      $$$ \begin{align*} f_0(N) &= -2 \cdot 4^{N-1} - 10 \binom{2N-1}{N-1} + 7\binom{2N+1}{N} - \binom{2N+3}{N+1} \\ f_1(N) &= -6 \cdot 4^{N-1} + 8 \binom{2N-3}{N-2} - 4 \binom{2N-1}{N-1} + 90 \binom{2N+1}{N} - 118 \binom{2N+3}{N+1} + 44 \binom{2N+5}{N+2} - 5 \binom{2N+7}{N+3} \\ f_2(N) &= -118 \cdot 4^{N-2} + 14 \binom{2N-3}{N-2} - 102 \binom{2N-1}{N-1} + 140 \binom{2N+1}{N} - 467 \binom{2N+3}{N+1} + 854 \binom{2N+5}{N+2} - 550 \binom{2N+7}{N+3} + 143 \binom{2N+9}{N+4} - 13 \binom{2N+11}{N+5} \\ f_3(N) &= -452 \cdot 4^{N-2} - 16 \binom{2N-5}{N-3} + 64 \binom{2N-3}{N-2} - 286 \binom{2N-1}{N-1} + 96 \binom{2N+1}{N} + 1368 \binom{2N+3}{N+1} - 834 \binom{2N+5}{N+2} - 2661 \binom{2N+7}{N+3} + 3488 \binom{2N+9}{N+4} - 1618 \binom{2N+11}{N+5} + 330 \binom{2N+13}{N+6} - 25 \binom{2N+15}{N+7} \end{align*} $$$
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        Wow, very cool! As this problem author, I am very surprised that it is solvable like that.

        Also, now we finally have proof that the sequence is P-recursive ;)

        (Are you happy ko_osaga? :P).

        → Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

So I guess no extensions and no correct tests to Aloha for us ;__;

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 23 and 61?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

mnbvmar aid Is the problem statement for 23 (Beautiful Automaton) incorrect? The definition the problem gives for suffix automaton is "the minimal DAG such that all substrings of S are the paths from the root", while the standard definition is "the minimal finite-state automaton such that all suffixes are the accepting strings". They differ on a string like "abbb": the first definition (as written) should produce

5 5
1-a->2
2-b->3
1-b->3
3-b->4
4-b->5

while the standard definition gives

7 7
1-a->2
2-b->3
3-b->4
4-b->7
1-b->5
5-b->6
6-b->7
Accepting: 1, 5, 6, 7

The difference is essentially because you can't pick a set of accepting states in the first DAG to make it a suffix automaton. The first definition applied to s+"$" should be roughly equivalent to the second.

The problem statement specifies the first, but it looks like test 6 is the second graph and expects "abbb". Is the problem statement incorrect?

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

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

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

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

How to solve 7 and 71?

→ Reply