Um_nik's blog

By Um_nik, history, 5 years ago, In English

Hello Codeforces!

Sadly there will be no OpenCup round this weekend, but instead I invite you to participate in a mirror of t.me/umnik_team Contest which will be held on Timus Online Judge this Sunday, 12 MSK. This contest was originally held on Petrozavodsk Summer Camp 2018 (if you participated in the camp, please do not participate in this contest). This is an up-to-3-person team contest with ICPC rules (one computer per team). Difficulty level is comparable to OpenCup rounds (not jqdai0815-hard, but certainly not for Div.2).

Author of most of the problems is me, with huge help from Merkurev and one problem from Kronecker.

Hope you will enjoy the contest.

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

»
5 years ago, # |
  Vote: I like it +47 Vote: I do not like it

Friendly warning that one of problems from this contest appeared on Prime New Year Contest, but I guess it's not like results of some mirror of Petrozavodsk contest are very important, so I wouldn't say that this exclude anybody from participating if he just pretends this problem doesn't exist.

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

    Absolutely correct, thanks, I half-forgot that this problem was there, probably because it is not that hard :)

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

      Which one was that?

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

        Don't look if you didn't participate in Prime New Year Contest and going to participate in the mirror.

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

        By this point I can assure you that you know something like half of problems from this contest, no point in you participating there :p

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

          Really? I don't think that this contest was published anywhere, and if I remember correctly, there were no teams from Warsaw in that camp.

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

            On University of Warsaw we usually use problems from Summer Petrozavodsk camps for internal competitions. In particular we used two of your problems yesterday :p

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

              How do you get access to them?

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

                By the courtesy of snark :)

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

                  Weird stuff, this contest is not even on opentrains :)

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

                  Being absent or being added with a two years delay on opentrains is not that uncommon ;p

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

                  I mean, weird that you have access to the contest and it's not even on opentrains. So Snark have time to send the contest to you, but don't have time to upload it to opentrains.

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

          Makes sense, thanks.

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

Is there problems pdf?

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

    You can see the statement by clicking on the problem.

    Or do you want to print it out? I can send you some version, since we changed limits in 2 problems.

»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Really hard problems QAQ

I'm surprised so few people did G, to me it was trivial, just a lot of work. Initially my code was way too slow, then I swapped binary search in baby-step giant-step to the gnu_pbds hashmap and suddenly random instances took like 1.5s. Pretty odd, I thought that binary search could never be beaten.

In C the weight of the tree is just $$$\sum_{i = 1}^{n} deg(i) \cdot i \cdot n - i \cdot (n-1)$$$ so you only need $$$E[deg(i)]$$$ for all $$$i$$$, but that seems to be pretty hard to get. Apparently sampling trees uniformly at random given degrees of nodes isn't easy, so how is counting solutions possible?

How to solve D?

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

    For D the answer is 4*a-1/3. With the power of WolframAlpha.

    First attempt
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    $$$ans=4a-\frac 1 3$$$ for $$$a \ge 2$$$

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

    Did you get accepted on G? My solution does not involve computing discrete logarithms.

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

      Yeah. I don't know any better way to get the size of the generated subgroup than to take $$$(p-1) / gcd(p-1, a_{1}, \dots, a_{k})$$$ where the values in the interval are $$$g^{a_{1}}, \dots, g^{a_{k}}$$$ for some generator $$$g$$$.

      So I used discrete logarithm to turn the input values into exponents of the generator, and multiplication into addition. Then I used the standard technique of interval GCD segment tree with addition to get the result.

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

        It shouldn’t be fast enough though... at least if p is 10^12 I don’t think this approach can pass.

        To find order of subgroup, it’s just the lcm of all order of elements as the multiplicative group is cyclic. It’s easy to maintain if you consider ratios of consecutive elements.

        EDIT: I see what you mean now, the complexity is like sqrt(p(n+q)) I guess. Still, it can be done without polynomial dependence on p.

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

          $$$p$$$ was at most $$$10^{9}$$$ in the problem

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

          When I came up with this problem, I didn't know that you can solve (add on segment, gcd on segment) with segment tree. Then I_love_Tanya_Romanova solved it with this approach during testing. Our implementation of this works about 6.5 seconds which was enough in original contest, but not in this version. Though I didn't try to optimize it, looks like very fast hashtable is the key.

          My original solution had complexity $$$O((n+q) (\log n + \log p) \log p$$$, and it works around the same time. To get lower times I did some insane optimizations, main one is this: I needed to calculate $$$O(\log p)$$$ powers of the same number in one query, and instead of doing $$$O(\log p)$$$ binary exponentiations, I did 5 or 6 layers of sqrt-decomposition-like thing, getting $$$O(k(\sqrt[k]{p} + \log p))$$$ (where $$$k=6$$$), which is 2-3 times faster.

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

    You know degree for all not_-1 vertices, and all other vertices are the same, so they have equal $$$E[deg(v)]$$$. Sum of all deg is $$$2n-2$$$, so you know $$$E[deg(v)]$$$ for all $$$v$$$.

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

    Maybe G is hard because people like me don't know what group means in mathematics?

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

      There were the definitions, right?

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

        I saw the sample and didn't scroll beyond. Sorry.

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

        It's not like you are already familiar with a concept right after reading definitions.

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

          This is true. But this problem is about the multiplicative group modulo prime number, with which participants are mostly familiar, things like existence of primitive root are known. So even if you didn't know what is group, I think you could read the definitions and understand that you are dealing with object you know.

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Help, how to solve B?

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

    let $$$A = {a_1,a_2,\cdots,a_k} $$$ (sorted by dfn)

    $$$f(x)$$$ = the sum of the weight from root to x.

    $$$ans = f(a_1) + f(a_2) + \cdots + f(a_k) - f(lca(a_1,a_2)) - f(lca(a_2,a_3)) - \cdots - f(lca(a_k,a_1))$$$

»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

How to solve A & E?

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

    A: First of all, we consider that whether a single 0 or 1 occur in the rule. Obviously, only one of 0 or 1 occur in the rule, Otherwise the answer is N or -1. Suppose there exists 0 but not 1, because it is a prefix-free system, a fact is that if W can be decoded, only if 0^k+W can be decoded. For any S, if we consider restrciting a suffix cannot be decoded, we only have to think about how to divide the prefix part. Because 0 can be decoded, and each part we devided at least contains a 1, so we can only divide into p(the number of 1s) parts. We can only create this way by connecting every 1 with the continuous 0s. Now the problem becomes finding the shortest prefix that cannot be decoded and the answer should be added by the number of 1s. We can easily find it by reversing those strings and building an AC-Automaton.

    Well, I think it is a quite good problem and also a nice contest. Many thanks to Umnik~

    PS: I actually translate this solution from my solution in Chinese written in August,2018. Maybe I miss some important details or have some mistakes.

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

    For E, $$$O(n^3)$$$ is obvious but got TLE. I guess some methods like FFT/NTT would be used to optimize it (since 40961 is a modulus of NTT). But I have no clue.

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

    E: We need to compute $$$\sum((s[i] == 0) \times C(i, x)\times C(n - i - 1, y)$$$ for each $$$x, y$$$. Fix $$$y$$$, it turns out to use FFT/NTT.

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

      Sorry, I don't understand. Fix y, then how to change it to a convolution?

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

      Could you be so kind and elaborate a bit more on how to reduce this sum to convolution? I tried to calculate $$$f(l, r)$$$ — the number of subsequences of length $$$l + r + 1$$$ with $$$(l + 1)$$$'th element being $$$0$$$. I.e. I tried to preprocess some sums and the answer for length $$$k$$$ would be calculating $$$a_l = f(l - 1, k - l)$$$ and outputting $$$\sum_{i=1}^k a_i \cdot (C(n, k) - a_i)$$$. I computed $$$f$$$ using divide and conquer and NTT that is in $$$\mathcal{O}(N^2 \log^2 n)$$$ which is too slow. Could you hint further how can one achieve $$$\mathcal{O}(N^2 \log n)$$$ if that is the intended complexity?

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it -21 Vote: I do not like it

      Good afternoon, could you please send the solution to problem 2122 with acm.timus.ru I would be very grateful to you https://acm.timus.ru/problem.aspx?space=1&num=2122&locale=en

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

Scoreboard of original contest, if anyone interested.

»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

How to solve I & F?

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

    I`ve passed F with just bruteforce from a highest weight (but I have nothing to prove it).

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

      Hmm. I did the same thing except memorizing, so it gave TLE. I was thinking that but didn't implement.

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

      Notice that there are at most two transitions for each state. ($$$W_i \ge \sum_{j<i} W_j$$$) And another upper bound is $$$w_i$$$.

      The time complexity is $$$O\left(\sum_{i=1}^{n} \min (2^{n-i},w / 2^{n-i})\right)= O(\sqrt w)$$$.

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

    I: Lucas's theorem. We need to compute $$$\sum{C(n, i)\times C(n - i, i)}$$$. Represent $$$n$$$ as $$$(a_1a_2...a_k)_p$$$. So we concern only $$$i$$$ such that its $$$p-base$$$ representation $$$(b_1b_2...b_k)_p$$$, $$$2b_i \le a_i$$$.

»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it
»
5 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

How to solve H without obvious $$$\mathcal{O}(n \log^2 n)$$$ interpolation followed by $$$\mathcal{O}(m \log^2 m)$$$ evaluation (which is too slow)?