Nanako's blog

By Nanako, 22 months ago, In English

1770A - Koxia and Whiteboards

Idea by m_99

Hint 1
Hint 2
Hint 3
Solution
Code (m_99)

1770B - Koxia and Permutation

Idea by m_99

Hint 1
Hint 2
Solution
Code (Nanako)

1770C - Koxia and Number Theory

Idea by triple__a

Hint 1
Hint 2
Hint 3
Hint 3.5
Hint 4
Solution
Code (Nanako)

1770D - Koxia and Game

Idea by m_99

Hint 1
Hint 2
Hint 2.5
Hint 3
Solution
Code (Nanako, DSU)
Code (zengminghao, DFS)

1770E - Koxia and Tree

Idea by m_99

Hint 1
Hint 2
Hint 2.5
Hint 3
Solution
Code (Nanako)

1770F - Koxia and Sequence

Idea by m_99

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution
Code (errorgorn)

1770G - Koxia and Bracket

Idea by huangxiaohua and errorgorn

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (errorgorn)

1770H - Koxia, Mahiru and Winter Festival

Idea by SteamTurbine

Hint 1
Hint 2
Preface
Solution (sketch)
Solution (details)
Code (SteamTurbine)
Visualizer (Python script)
  • Vote: I like it
  • +243
  • Vote: I do not like it

| Write comment?
»
22 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I thought I did pretty bad this contest(Problem A harder than B and C) but still managed to get a positive delta.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i was not able to solve any questions , got stuck in problem A But by this contest i will get to learn a lot for sure and will improve in next contest

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

    same :)

»
22 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

C can also be solved in O(50 * n) as for a prime to fail it should have at least 2 * p indices.(min(cnt0,cnt1,…,cntp−1)≥2). but as n <= 100 we can have p <= 50. my submission

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

    I missed that observation, I checked all primes under 1000 because it I thought it would be reasonably high enough.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, you can solve the Question with max upper bound of 25 primes since the 26th prime is 101 which can't become unavailable for x since max elements are 100

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

    n/2 = 50 is actually O(n), so this solution (O(n^2)) is not better than tutorial

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When we say an algorithm is O(n^2), it means it grows quadritically with n

    Lets take n = 1000, your algorithm will need O(500*n) then, do you see why your algorithm is still quadriatic wrt n?

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bro I realized few seconds after posting, but I think we cant delete So left it like that :(

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I misread B, I thought that the cost is sum(c), not max(c). Somehow I still got AC.

»
22 months ago, # |
  Vote: I like it +31 Vote: I do not like it

I loved the problems of this contest. They were enjoyable to solve. Still amazed...

»
22 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Why the constraint for $$$n$$$ in problem C is too low? Since the complexity is $$$O\left( \dfrac{n^2}{\log n}\right)$$$ why not $$$n \leq 10^4$$$?

I did an $$$O\left( \dfrac{n^4}{\log n^2}\right)$$$ that wouldn't passed with higher values of $$$n$$$

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is actually O(n * sqrt(n)) :)

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

    The author team deliberately set it as troll. We didn't mean to kill $$$O(\frac {n^4} {\log n})$$$ specially but implementations with high constant time will lead to a TLE.

    • »
      »
      »
      22 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      and the author somehow succeeded in killing pollard rho (I don't know if that's intended, though I think it should be)

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

        I see how you cheated C. Now stop putting shit here. Shit.

        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it +25 Vote: I do not like it

          proof bro? my first AC is just skipped due to resubmission. You can easily see it barely fits in TL

»
22 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Please fix the LaTeX in Solution F.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks for the reminder and it's ok now.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And for the solution of C, it should be if $$$x\equiv 0 \pmod 2$$$?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any prize in this contest for individuals ranking under 2k

»
22 months ago, # |
  Vote: I like it -8 Vote: I do not like it

ah yes of course chinese remainder theorem on third task sily me for not knowing fringe ideas on suposedly easier tasks

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    CRT is not generally considered a fringe idea.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    CRT is one of the crucial ideas you should always think about when solving a number theory related problems.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

While there are many primes up to 10^18, we only need to check for the primes up to ⌊n/2⌋. This is because min(cnt0,cnt1,…,cntp−1)≥2 is impossible for greater primes according to Pigeonhole Principle. whyy??

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

    Take prime $$$p = 53$$$ as an example, it's impossible to use only $$$100$$$ elements to fill a bucket of size $$$53$$$ and each slot has at least $$$2$$$ elements.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      elaborate for this tc plz 2 10005294,10005402

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

        Surely it's YES without checking any prime. If $$$a_i$$$ are pairwise distinct, the minimum case with answer NO is $$$n = 4$$$ as mentioned above.

        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          what about this 5 10005294,10005402,10005398,10005212,10004358 ???

          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
            Rev. 4   Vote: I like it +3 Vote: I do not like it

            For $$$p=2$$$, we get $$$\mathit{cnt}_0=5$$$ and $$$\mathit{cnt}_1=0$$$.

            For $$$p=3$$$, it's unnecessary to check because of Pigeonhole Principle. If we check it, we get $$$\mathit{cnt}_0=3$$$, $$$\mathit{cnt}_1=0$$$ and $$$\mathit{cnt}_2=2$$$. Ensuring $$$x \bmod 3 = 2$$$, we can calculate a proper $$$x$$$.

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

              so answer should be YES

              • »
                »
                »
                »
                »
                »
                »
                »
                22 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Surely for $$$x = 5$$$.

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

    If min(count(i))>=2, then sum(count(i))>=p*2, which means 2*p<=n

»
22 months ago, # |
  Vote: I like it +44 Vote: I do not like it

Problem C and D are really really amazing (and easily one of the best problems I've ever come across, the proof of C, the pigeon hole principle drives me crazy!) ! I really appreciate the authors for such amazing problems. Its a pity I wasn't able to participate :(

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    can you please explain Pegion hole principle proof ?,why only we are checking primes less than n/2. I am still stucked in that.

»
22 months ago, # |
  Vote: I like it -34 Vote: I do not like it

CRT for 3rd task?, cannot believe..trash round

  • »
    »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it +32 Vote: I do not like it

    You don’t actually need to know it, I just observed that if there were two odd and even there would always be at least two even, so modulo 2 would be present. I later expanded this idea to other prime numbers.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't get it, can you please elaborate on your intuition, I would like to know your thought process.

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        If there are two odd numbers and two even numbers, there will always be at least 2 even numbers. This is because any number you add has to be odd or even, therefore the two original even numbers will be even if an even number is added and the two odd numbers will be even if an odd number is even. This means there will be a pair divisible by 2(or gcd!=1). Now the underlying structure of this phenomenon is important. Why does this work? Well in modulo arithmetic (a+b)%m = a%m + b%m. If a is our given number, and b is what we’re adding, we can only add two distinct values (0 and 1). If the problem was simply gcd!=2, we only need to check whether there is one distinct modulo of 2. Otherwise, no matter what we add there will always be at least 2 numbers where %2==0. However, this principle itself is not only restricted to 2, it can be done for any number. For our purposes, we only need to check prime numbers although it’s not necessary to find out which prime number to check. Since n == 100, the maximum number we need to check is 50(since there needs to be at least 2 in each spot for it to fail). The main intuition came from the fact that n is reasonable small, so the solution must involve checking all the number in the array in terms of their modularity rather than gcd or other measures on the elements since the elements themselves can be quite large.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    You don't need to implement the algorithm of CRT. It's just used to promise the existence of such x. In fact many contestants got AC by intuition.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the transitions in dp for G ?

»
22 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone clear my doubt? In problem C, suppose that I have checked the remainders upto p primes , and I got such x, which satisfies the given condition( I constructed this x from first p primes where p is greater than largest element in the set). Now, how can I say that the solution I got will not contain any multiple of primes which is greater than pth prime when every element is different. I didn't get proper intuition here, so I didn't proceed afterwards :( any help will be highly appreciated.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By solution, I mean final state of array, that is (a1+x,a2+x....)

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

    A intuitional sketch explanation is, for a large enough prime $$$p$$$, we can always find a proper value $$$\mathit{offset}$$$ so that none of $$$a_i + \mathit{offset}$$$ will be multiples of $$$p$$$.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is this ai ai+x or is it the initial ai, (here x is same as how I constructed x using first p primes).

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        the initial.

        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But, after choosing that offset, still I may find some different x, and after addig this x to ai+ offset, I still cant say that there is no multiple of such large p.

          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            The final $$$x$$$ is derived by merging many of $$$\mathit{offset}$$$ with Chinese Remainder Theorem, instead of summing up. So primes won't affect each other.

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

              Now, how can you we say that this new x is not giving two multiples of primes, which are greater than the primes from which I constructed this x. It will be very helpful if this is explained in the editorial.

              • »
                »
                »
                »
                »
                »
                »
                »
                22 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Maybe I didn't really get your point, so I hope it can be helpful to take this case as an example. When we list equations accordingly, just like:

                $$$ x \equiv 1 \pmod 2 \\ x \equiv 2 \pmod 3 $$$

                . We will able to calculate a proper value like $$$x = 5$$$ using CRT. When we continue to add more equations for larger primes, the calculation is still possible as long as adding valid equations is possible.

              • »
                »
                »
                »
                »
                »
                »
                »
                22 months ago, # ^ |
                Rev. 3   Vote: I like it +17 Vote: I do not like it

                The $$$x$$$ isn't constructed by merging the congruences of primes $$$p \le n$$$, but $$$p \le \max |a_i - a_j|$$$ over all $$$1 \le i < j \le n$$$ (i.e. the largest difference between any two values in the array). We just know that for any $$$p > n$$$ there has to exist some remainder $$$r$$$ such that $$$a_i \equiv r\ (mod\ p)$$$ doesn't appear at all. That's why we don't need to calculate them.

                We don't need to check any primes $$$p > \max |a_i - a_j|$$$ since for two values $$$a_i + x,\ a_j + x$$$ to both be divisible by some prime $$$p$$$, we would also need their difference $$$|(a_i + x) - (a_j + x)| = |a_i + x - a_j - x| = |a_i - a_j|$$$ to be divisible by $$$p$$$ which is not possible if $$$p > \max |a_i - a_j|$$$.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  22 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Why x need to be constructed by only p<= maxabs(ai-aj), suppose that I have constructed such an x in this way, and I will see the array (a1+x, a2+x,.... an+x). Now, I can guarantee that no two of them hve a common factor of p for all primes <= max(ai-aj). How can I comment on p> max(abs(ai-aj)), I mean how can you say that there doesnt exists 2 multiple's of p>max(abs(ai-aj)) in the array (a1+x,a2+x...an+x). Hope you got my doubt...

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

                  I updated my original comment to show this. Message me privately if you still don't understand this.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  22 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Thank you very much for the solution.

            • »
              »
              »
              »
              »
              »
              »
              22 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Just a little question, why is the cost mentioned in Hint 1 of problem B 2n instead of n only?

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

                If $$$k = 1$$$, the cost of the section which only has the value $$$n$$$ is $$$max(n) + min(n) = n + n = 2n$$$

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  22 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  ah yeah, my brain just stopped working and just thought that it's only the max(n) only...

»
22 months ago, # |
  Vote: I like it +41 Vote: I do not like it

I think in problem E, you need to elaborate on why the probabilities attached to the vertices are independent (in fact, they are not!), otherwise the probability of a value of $$${\mathit{siz}}_{\mathit{son}}$$$ may be non-deterministic.

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

    Aren't they independent as the two components separated by the current edge have not been in contact with one another (which means every event within each component is independent to the other, and by extension the sizes and probablilities and whatnot)?

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Precisely, what he means to say is that what you've written should have been there in the editorial.

»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem A was literally mind blowing

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In C after checking for all primes <= N. After that how can we say that there will exist a number such that gcd will be 1 for every pair.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If no prime was found where every possible remainder appeared at least twice, there has to be at least one remainder for every prime such that $$$x \equiv r\ (mod\ p)$$$ works. We know that such $$$x$$$ that fits all of the congruences always exists because the Chinese remainder theorem says so. (Go to the proof-section for the proof of the theorem).

»
22 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Did anyone else miss A because they sorted array b?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved A after B,C,D with four WA's because of this.

»
22 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Why is my Python PriorityQueue solution too slow in PyPy. 187389454

In Python 3.8 it is faster: 187389600

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain why "Then there is a way to make $$$p$$$ a permutation iff there is a way to assign a direction for every edge such that every vertex has one edge leading into it. " is true in problem D's editorial?

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

    For choosing one element from $$$a_i$$$ and $$$b_i$$$, we can consider "choose $$$a_i$$$" as "edge $$$(a_i, b_i)$$$ is directed as $$$b_i \rightarrow a_i$$$".

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Solution Para-5 Line 3 , Why it min(cnt,....)>=2 ? Can someone please elaborate this line.

»
22 months ago, # |
Rev. 3   Vote: I like it +115 Vote: I do not like it

;_;

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +68 Vote: I do not like it

    Thank you very much for the round, I enjoyed it very much and will also remember it for very long as the round I reached gm! I liked the problems very much, especially problem D. The underlying idea was very cute and unexpected, I wish to see such problems more often

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why are you leaving CP?

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Graduated from university and no longer have the opportunity to participate in the ICPC, so I will not keep training for a long time anymore.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I have two questions related to editorial for Problem C.

"Yes" condition:

"every prime $$$p$$$ should divides at most one $$$b_i$$$"

Question 1: so, do I correctly understand, that, instead of checking Yes, we are checking No?

So, "No" condition is next:

There is a prime number $$$p$$$ for which there are two elements $$$a_i$$$ and $$$a_j$$$ such $$$(a_i+x)\equiv 0\text{ } (\text{mod }p)$$$ and $$$(a_j+x) \equiv 0\text{ }(\text{mod }p)$$$ for any positive integer $$$x$$$.

By subtraction two equations we have: $$$a_i \equiv a_j \text{ }(\text{mod }p)$$$.

Question 2: do we need just to check for given $$$p$$$ if two elements have same remainder modulo $$$p$$$? I mean, that if we can find such $$$p$$$ and such two elements then answer is No?

If so, then it contradicts with next statement in editorial:

If $$$\text{min}(\text{cnt}_0,\text{cnt}_1,…,\text{cnt}_{p−1}) \ge 2$$$, we output NO immediately.

Because it should be $$$\text{max}(\text{cnt}_0,\text{cnt}_1,…,\text{cnt}_{p−1}) \ge 2$$$ instead of $$$\text{min}(\text{cnt}_0,\text{cnt}_1,…,\text{cnt}_{p−1}) \ge 2$$$.

Or I am unable to understand the logic why $$$\text{min}$$$ is used instead of $$$\text{max}$$$.

  • »
    »
    22 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    $$$a_i \equiv a_j \pmod p$$$ means a slot in bucket $$$cnt$$$ is banned, but maybe other slots are still available.

    For a bucket like $$$\mathit{cnt} = [111, 222, 1, 333, 444]$$$, although $$$\max = 444$$$, we have $$$\min = \mathit{cnt}_2 = 1$$$, so we can keep $$$x \equiv 3 \pmod 5$$$ to get a proper $$$x$$$ such that "$$$5$$$ should divide at most one $$$b_i$$$" holds.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm sorry, but I don't understand...

      Consider smaller example instead of $$$cnt=[111,222,1,333,444]$$$, just $$$cnt=[2,2,1,2,2]$$$.

      Array $$$a=[5,10,6,11,7,8,13,9,14]$$$ gives such $$$cnt$$$ modulo $$$5$$$. You are saying that you can choose $$$x \equiv 3\text{ }\left(\text{mod }5\right)$$$. OK, but with $$$x = 3$$$ we have $$$b=[8,13,9,14,10,11,16,12,17]$$$. But $$$gcd(14,10)=2$$$, so, $$$x = 3$$$ is a wrong number.

      • »
        »
        »
        »
        22 months ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        This NO is caused by prime $$$2$$$ instead of prime $$$5$$$. Only if condition $$$\min(\mathit{cnt}) \leq 2$$$ holds for each prime, we output YES. For example, $$$a = [6, 12, 18, 24, 30, 36, 48, 54, 60]$$$ and $$$x = 13$$$ (if we set $$$x \equiv 1 \pmod 2$$$, $$$x \equiv 1 \pmod 3$$$ and $$$x \equiv 3 \pmod 5$$$).

        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If we are able to find a prime number such that count of any of its remainder is 1 than ans should be yes and why do we need to check for other primes?

          we are considering the cases after adding the value x. so in that sense why we need to take the modulo we assumed that we have added x but the modulo we have taken is not representing it

          I am really confused on how the solution worked

          If possible please breakdown a test case into small pieces, I tried it but got messed up

          Also please link similar problems(if any)

          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            From "We are able to find a prime number such that count of any of its remainder is 1", we can only derive that it's possible to choose a proper $$$x$$$ such that $$$p$$$ won't divide two or more of $$$b_i$$$. But we don't know if it holds for other primes.

            • »
              »
              »
              »
              »
              »
              »
              22 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Consider the test-case, n=4 a={8,9,11,13}

              if p=2 we have cnt={1,3} if p=3 we have cnt={1,1,2}

              so usnig CRT we will find the solution for x=0 (%2) x=0 (%3) || x=1 (%3) so we can get a solution as x=6 here since we can not have solution with x=1(%3) so how can we say for other cases if we only had equations(given below)a solution will exist x=0 (%2) x=1 (%3) since in above test case if we only considered these 2 equations there will not be a possible solution

              • »
                »
                »
                »
                »
                »
                »
                »
                22 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                CRT always can give you solutions as long as you input correct congruence equations. A solution for "x=0 (%2) x=1 (%3)" is $$$x = 4$$$.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How does a single slot verify we can have different values for all numbers giving different remainders.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        CRT. Different prime numbers won't affect each other.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When $$$a_1 \bmod p = a_2 \bmod p = c$$$, $$$x$$$ should not be $$$(p - c) \bmod p$$$. (Because if $$$x\equiv (p-c){\pmod {p}}$$$, just like $$$x=p-c$$$, then $$$(a_1 + x) \bmod p = (a_2+x)\bmod p = 0$$$, which means $$$a_1+x$$$ and $$$a_2+x$$$ at least have one same factor $$$p$$$ and $$$\gcd(a_1+x,a_2+x)\not = 1$$$.)

    The constraints are $$$x\not = c$$$, where $$$c$$$ is that at least there is a pair of $$$a_i$$$ and $$$a_j$$$ that meets $$$a_i \bmod p = a_j \bmod p=c$$$. So if there is one of the counts of $$$a_i \bmod p$$$ that is less than $$$2$$$, we can get equation $$$x \equiv (a_i \bmod p) \pmod p$$$. For all $$$p$$$, we can get a group of equations. Because there is no limitation on $$$x$$$, anyway we can solve one $$$x$$$ by CRT or other ways.

»
22 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Good contest but why were the samples so weak ?

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

    Too strong samples will imply correct solutions. I hope we have set it basically properly.

»
22 months ago, # |
Rev. 8   Vote: I like it +63 Vote: I do not like it
Gonna post my solution to F because some people say it is easier to understand and it does not require Kummer's theorem and Vandermonde's identity
»
22 months ago, # |
Rev. 4   Vote: I like it +15 Vote: I do not like it

This is how I solved F —

Here goes my solution to F, few people find it easier than understanding involution etc
»
22 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Chinese Reminder Theorem. -> Chinese Remainder Theorem

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for correcting and it's fixed now.

»
22 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

In $$$C$$$, I understand why for each prime $$$p$$$ there must be least one $$$0 \le v < p$$$ where $$$a_i \equiv v$$$ mod $$$p$$$ occurs at most once. I also understand that if the previous condition is satisfied, for any set of primes, for each $$$p$$$ of them we can choose $$$0 \le v < p$$$ where $$$a_i \equiv v$$$ mod $$$p$$$ occurs at most once and construct $$$x$$$ that satisfies the congruences $$$x\equiv -v$$$ mod $$$p$$$ using Chinese remainder theorem, i.e., to make every $$$p$$$ divides at most one $$$a_i+x$$$ .

But what guarantees that after choosing a set of primes we will not end up with a new prime $$$p_{new}$$$ by which some $$$a_i+x$$$ and $$$a_j+x$$$ will be divisible? and if we include $$$p_{new}$$$, what guarantees that another newer prime will not appear and continue like this indefinitely? We already know a trivial case that causes this, i.e., when we have $$$a_i = a_j$$$. But what guarantees there are no other cases that can cause this?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Instead of chosing $$$a_i \equiv v$$$ mod $$$p$$$. You should choose $$$v \equiv -a_i$$$ mod $$$p$$$. This will ensure that for each prime p, there exists atmax one such $$$a_i + x \equiv 0$$$ mod $$$p$$$ for each prime $$$p$$$.

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

      Yes I understand how we should choose the moduli for a set of primes to ensure every prime of them divides at most one $$$a_i+x$$$, but this is not my question.

      My question is why is it guaranteed that after doing this for any set of primes there will not always appear another prime that was not in the set and will divide some $$$a_i+x$$$ and $$$a_j+x$$$.

      A trivial example for this is an array of $$$2$$$ values with $$$a_1=a_2=v$$$. For any set $$$S$$$ of primes we can create an $$$x$$$ such that no prime of them divides $$$v$$$, but we will always end up with a prime that was not in $$$S$$$ and divides $$$v$$$ ($$$a_1$$$ and $$$a_2$$$). So the question is, apart from an arbitrary array with some $$$a_i=a_j$$$, what guarantees that there are no other cases that can cause this?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It looks like the answer of my question is here.

    Any prime that divides any $$$2$$$ values divides their difference as well. The difference between any $$$a_i$$$ and $$$a_j$$$ will still be the same after adding $$$x$$$ to both. This means we have an upper bound for the primes that can divide any $$$a_i+x$$$ and $$$a_j+x$$$ as long as $$$a_i$$$ and $$$a_j$$$ are different. When $$$a_i=a_j$$$, no upper bound exists as any prime divides $$$0$$$.

»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Why BenQ uses Rust for solving H in Goodbye 2022 contest? Is there any benefits over C++?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

so where can I find the Chinese tutorial

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's available now, sorry for being late.

»
22 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In Problem C you didn't use the condition "all $$$a_i$$$ are different". So why do I have to check the trivial NO? What makes the solution incorrect when some $$$a_i$$$ are the same?

This is what confuses me when I come up with this solution.

»
22 months ago, # |
  Vote: I like it +60 Vote: I do not like it

I have another idea for H. First we solve by hand for $$$p_i=q_i=n-i+1$$$, it is easy using idea for $$$n=2$$$. Now whenever $$$p_i>p_{i+1}$$$, the corresponding paths must intersect and so you can untangle them and swap $$$p_i$$$ and $$$p_{i+1}$$$. So we can just do bubble sort and do $$$O(n^2)$$$ such subroutines to modify into correct $$$p$$$. Same idea for fixing $$$q$$$.

Thanks for the contest, very interesting problems.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to prove that [n,1,n-1,2,n-2,3,n-3,4,....] is the optimal solution for B ??

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
    • the lower bound of the cost is $$$n+1$$$ (we cannot do better than that)
    • $$$[n,1,n-1,\dots]$$$ has cost $$$n+1$$$ (we hit the limit)
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem G has such a simple statement. It seems so unexpectedly hard to me.
Seems a really nice problem, gonna try it when I reach red.

»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Why is the greedy strategy for question A correct? Is there any proof of the correctness of the first solution or the second?

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

    I added a short explanation about the sorting approach — hope that helps!

»
22 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Really a nice contest for last of 2022.

»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

For E, is the expression for updating the probabilities very intuitive? I mean, mathematically, I got the expression but not sure if there is some obvious way to state that both probabilities will become (Pu + Pv)/2

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, we can consider the move operation as "swap or don't swap with both $$$\frac 1 2$$$ probability", no matter whether $$$u$$$ and $$$v$$$ are occupied or not. Therefore, $$$p_{\mathit{new}} = \frac {p_u+p_v} {2}$$$.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you prove that probability of swapping is equal to $$$1 \over 2$$$?

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        just simple case-analysis for all $$$4$$$ cases. (node $$$u$$$ / $$$v$$$ occupied or not)

»
22 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

In E, why isn't (or I just didn't see in code) $$$sum_u$$$ updated while calculating the contribution each edge gives to the final answer, when $$$p_u$$$ was changing?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because it's not changing.

    Each edge split the tree into two components, and you can see that a butterfly cannot fly from one component to the other before the operation on this edge.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please ensure that you have gotten why we claim $$$|\mathit{siz}_{\mathit{son}} - \mathit{siz}^0_{\mathit{son}}| \leq 1$$$ before think about later parts.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think the butterflies don't cross that edge.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem-C,

In the min case, cnt[i]=2 for every 0 <= i < p where p is a prime number. So, 2*P=n tends to P = floor of n/2. That is also proved by Pigeonhole principle.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem C can you find such x for yes

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is theoretically possible by using CRT as the editorial mentioned, but the result may be very large.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please explain how theoretically it is possible to use CRT?

      For some Prime P1, we need x1 to be added in the array to make at most 1 element divisible by P1, but how to find x so that at most 1 element is divisible by all primes smaller than n/2?

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        solve congruence equations like:

        $$$ x \equiv x_1 \pmod {p_1} \\ x \equiv x_2 \pmod {p_2} \\ \dots $$$
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In question C If min(cnt)<2 holds for all primes, then we can list certain congruence equations and use Chinese Reminder Theorem to calculate a proper x I don't want to go to too many details on how to find x but can someone explain why the Chinese Remainder Theorm can be used here?

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

    CRT is used to solve congruence equations, for example, CRT tell us "$$$x = 13$$$ is a solution" if we set $$$x \equiv 1 \pmod 2$$$, $$$x \equiv 1 \pmod 3$$$ and $$$x \equiv 3 \pmod 5$$$.

»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

In problem D I have considered bipartite graph from number to position, the solution is very similar actually. To verify feasibility of assignment, we check that each connected component contains the same amount of numbers and places.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, what was the intuition to set up the graph like so? I've gotten the 2 lemmas but I couldn't figure out how to set up the graph like that. If anyone can provide some insight, that would be great.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody please explain what hints towards using graph in problem D? Is there so observable pattern?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain how D problem is converted to a graph problem? Like what exactly are the edges and the vertices in the said graph? Thanks in advance :)

Following is my approach, please correct me if I am wrong (I think it would TLE anyway tbh)

I could figure out lemma 1 and lemma 2 by myself and thought that I can make a directed graph by taking the elements in array a and b as vertices and every a[i] and b[i] connected to a[i+1] and b[i+1] except the last node. Then I traverse through this graph twice and check if I can create a path with unique vertices and reach the terminal node (i.e. check if P is a permutation) one path starting from a1 and the other from b1. Every node is marked 1 if a path through the node exists or 0 other wise. Now we can check for every (a[i], b[i]):

  • if a[i] and b[i] are both marked 1 and if they are equal that means a path through both the vertices exists and any of them can be chosen during that round (i.e. c[i] can be anything so multiplying answer with n)

  • if they both are marked 1 but are not equal then c[i] can only take 2 values in that round (so multiplying answer with 2)

  • if only one of them is marked 1 then c[i] can only take that one value so multiplying answer with 1

  • else no path exists so the answer is multiplied with 0

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

2 2 109 111 119 110

for this solution Answer is 229 by editorial solution But the answer is 230

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have to apply all $$$m$$$ operations sequentially.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the logic behind only taking prime numbers upon n/2 in problem C?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    pegion hole ! for primes over n / 2 there exists an r < p where cnt[r] < 2 (cnt[x] = number of array elements that have reminder x when devided by p)

»
22 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In E, what is inv2? And why do we multiply delta by it?

UPD: Ok, inv2 means division by 2, but why do we divide delta by 2?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If we use delta, it means we apply the move operation always, no matter the direction of edges. But actually, it's randomly chosen from two directions.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, what does "if (edge != 2 * vertex) ans = 0;" this implies?

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

    Refer to the editorial (Paragraph "We can transform this into a graph problem..."). We need to check whether $$$|V| = |E|$$$ or not.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem c

given the input a = [5, 7], then [5 mod 2, 7 mod 2] = [1, 1]. 1 appears twice so the minimum multiplicity is equal to 2. Above in paragraph 3 you say print NO. if x=2,then the gcd(5+2, 7+2) = gcd(7, 9) = 1. Isn't it wrong to print no while there is an x for which gcd(a_{1}+x, a_{2}+x) = 1.

I'm probably wrong I just want someone to explain how.

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

    1 appears twice but 0 doesn't appear, so the minimum multiplicity is $$$0$$$ instead of $$$2$$$.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please post link of the classical problem mentioned in hint 1 of problem E

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide a easir explanation for problem C

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem D why edge!=2*vertex

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Scroll up the mouse wheel a few times to see.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain how the sigma pi formula came in F’s editorial and how did this helped in solving the problem. As we are not interested in number of sequences but xor of such ones. Moreover $$$\binom{ny}{x}$$$ is the solution of equation $$$t_1 + t_2 + … + t_n = x$$$ where each $$$t_i$$$ can take any value between 0 and y by Vandermode identity, then how are we ensuring that each $$$t_i$$$ is also subset of y?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We can't ensure that each $$$t_i$$$ is a subset of $$$y$$$ so we need inclusion-exclusion principle (Hint 4).

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explains why in problem C, we only consider prime number ?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, we only need to iterate through all prime numbers, then why are we checking for each number from 2 to n/2 ??

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

    checking prime numbers in $$$[2, \lfloor \frac{n}{2} \rfloor]$$$ is enough, I just got lazy to sieve prime numbers when implementing it.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi!

I am wondering, for problem C, is it equivalent to check all integers up to $$$\lfloor n/2 \rfloor$$$ instead of primes? The criterion for NO is exactly the same. And for the existence of $$$x$$$, we could also create the equations in the same way, (in which the modulo may not be pairwisely coprime, but we can always convert it to one that is), and use CRT to solve it.

Actually, I think checking integers is more essential, right?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    checking prime numbers in $$$[2, \lfloor \frac{n}{2} \rfloor]$$$ is enough, I just got lazy to sieve prime numbers when implementing it.

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      So instead of using primes upto u/2 -> how traversing all numbers upto n/2 won't change our answer ?
      I mean can you prove ?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        like if you run out slots when checking $$$6$$$, then you must run out slot when checking $$$2$$$ or $$$3$$$, so it's redundant to check composite numbers.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ok ok i got that like if 2 and 3 are dividing at most one numbers then obviously 6 will divide at most one number.

»
22 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone explain the problem D why we need to build the graph like this and why we can find the answer by assigning directions for each edge? I can't imagine how it works

»
22 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

gr8

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to get the x if it exist for Problem B by using CRT? what's the mod function?

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just read the editorial for Problem D. I think you missed a third category for the additional edge. Consider a case where a connected component of the final undirected graph is the following:

The edge 2-4 is neither a cycle edge nor a self loop edge. While the final answer will remain the same, I think clarifying this would be helpful for anybody who looks at the tutorial in the future.

Please feel free to correct me if I'm wrong.

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

    Hello! Actually, what the editorial said is, components can be categorized into two types — "cycle component" or "self-loop component", by the size of their cycles. The component in your graph is also counting as a "cycle component" although it's not only a cycle.