rui_er's blog

Codeforces Round 942 (Div. 1, Div. 2) Editorial
By rui_er, 2 years ago, In English

1972A - Contest Proposal

Hint 1
Tutorial
Solution

1972B - Coin Games

Hint 1
Hint 2
Tutorial
Solution

1967A - Permutation Counting

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1967B1 - Reverse Card (Easy Version)

Hint 1
Hint 2
Tutorial
Solution

1967B2 - Reverse Card (Hard Version)

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1967C - Fenwick Tree

Hint 1
Hint 2
Tutorial
Solution

1967D - Long Way to be Non-decreasing

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1967E1 - Again Counting Arrays (Easy Version)

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1967E2 - Again Counting Arrays (Hard Version)

Thanks A_G for discovering that E2 is possible!

Hint 1
Hint 2
Tutorial
Solution

1967F - Next and Prev

Hint 1
Hint 2
Hint 3
Tutorial
Solution
  • Vote: I like it
  • +113
  • Vote: I do not like it

Comments Comments (174)
| Write comment?
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +111 Vote: I do not like it

too math, downvoted...

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

Auto comment: topic has been updated by rui_er (previous revision, new revision, compare).

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +57 Vote: I do not like it

I don't think that this round deserves hate. div2A-D2 were all good. I say that as someone stuck on D2 for almost 2 hours. My final submission was rejected because of strict limits. However, the trick $$$p^2 \lt n$$$ can compensate for it. I find it fascinating, and I am glad to have seen it. The model code is much simpler than mine.

The downside is that all problems (the ones I attempted) had the same (math) tag. But, it is a common trend nowadays. We cannot do anything about it, so cope.

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +21 Vote: I do not like it

Well, here is the main contribution list of the writers.

Please feel free to tell us which is you favourite problem and why, and even the problems you dislike too. Meanwhile, I would also like to thank our hard-working coordinator and testers. They together made it possible for us to hold this round.

If there is a chance, we hope to meet again with better problems.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +70 Vote: I do not like it

    D1 is not mine, it was accidentally invented by the tester newb_programmer while he was solving D2.

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    I liked 2F/1D. Too hard for me to solve during round but solution nicely unfolds in several steps

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

    2F/1D is really cool. I would have been annoyed if hint 2 was the intended solution.

    Btw typo in editorial
    → Reply
»
2 years ago, hide # |
← Rev. 3  
Vote: I like it -8 Vote: I do not like it

can anyone explain, why my code is WA on test 7 (problem B)

Spoiler
→ Reply
»
2 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

is it possible to solve 2C/1A using Priority Queue? Not in $$$O(k)$$$. I din't think of binary search and now my Pupil is on the line :sob:

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

Too much time wasted for proving the solution of B

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

    but how did you prove it? that Alice wins if the number of U's have to be odd.

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

      At every turn, the parity of the total number of 'U' cards flips. This is because once we flip a 'U' card, the number of 'U' cards decreases by 1. Now since it has two neighbours , it will be either a). DD -> UU b). UU -> DD c). UD -> DU

      Either the number of U increases by 2, decreases by 2 or remains same. Since we already discarded a U card, the parity always flips. Also since the maximum number of U can be the current size of the string, we can guarantee the game will end at most after n turns. The winner of the game is the person who gets the string with only 1 U left. So we can conclude that whoever starts with odd number of U's will be the one who will get to the state where there is 1 U left, and hence will win the game.

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

        Thanks a lot for the explanation!

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

        Hey, I understand that the parity of the number of $$$U$$$'s always changes but that does not provide any rigorous proof that if the number of $$$U$$$'s is odd then Alice wins.

        I struggled a bit to provide more rigorous proof for this thing.

        (Proof by induction does not work since the number of $$$U$$$'s can increase).

        I think the main observation is that the number of $$$U$$$'s is bounded by the length of the string $$$n$$$. That means that there is a point in time where the number of $$$U$$$'s always decreases and can't increase any more.

        If you consider the number of $$$U$$$'s throughout operations it might look like this: 3 -> 4 -> 5 -> 2 -> 3 -> 4 -> ... -> some bound -> start decreasing till 1

        I would assume that the proof would work for any number of increase/decrease values as long as the parity always flips, there is an upper bound and the game will always end.

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

          The game always ends in at most $$$n$$$ moves and Alice can always make a move since the number of coins facing up is odd, so nonzero, which means that the game must end on Bob's turn.

          → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it -8 Vote: I do not like it

    Yeah,Mathematical problems are difficult to prove.I hate math.

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

weak pt. I just wrote the limit as the correct limit -1.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Could solve all the way to the problem D2. My math knowledge was useful in both task D1 & D2, however, mathforces.

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

Editorial is Little bit confusing for me.

Please can anyone verify that following approach was correct?

1)sort array use binary search, to make all all element atleast equal to X

This x will have range from min of array to max+k of array..

2)then ..make arrangement,1->n in this cycle and calculate the answer...using this x

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    You don't need binary search if you already sorted array.

    1. Find $$$fulls$$$ = number full permutations (bin search or sort + prefix sum)
    2. $$$r$$$ = remaining k
    3. add $$$a_i \gt fulls$$$ (and purchase $$$r$$$ distinct $$$a_i \lt = fulls$$$) at any end of full permutations to form additional permutations of $$$1..n$$$.

    258906139

    → Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +8 Vote: I do not like it

in div2D1 you do not have to count using math, you can naively run a for loop. The time complexity will be still $$$\mathcal{O}(n+m)$$$ for each test case. This is because, for each value of $$$m$$$ the loop will take $$$\mathcal{O}(\frac{n}{k^2})$$$ time, and $$$\sum_{k=1}^\infty{1/{k^2}}$$$ converges to $$$\pi^2/6$$$.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +9 Vote: I do not like it

    We can also notice that $$$a$$$ must be a multiple of $$$b$$$ and iterate $$$b$$$ from $$$1,2,..m$$$ and $$$a$$$ from $$$b,2b,...n$$$, then it turns into $$$O(n\log{n})$$$.

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

      Unfortunately couldn't make the same trick work for Div2D2, do you have any idea how?

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

        My solution for D2 uses same trick 258920365. Though it is O(n log^3(n))

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

          Cool that it fits in time

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

          Can you elaborate on your approach?

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

            Consider $$$g = gcd(a, b)$$$, than $$$(a + b) | b \cdot g$$$ is equivalent to $$$k \cdot (a + b) = b\cdot g$$$ (for some $$$k$$$). Let $$$a_0 = \frac{a}{g}$$$, $$$b_0 = \frac{b}{g}:$$$ $$$ \newline k \cdot a_0 \cdot g + k \cdot b_0 \cdot g = b_0 \cdot g^2 $$$

            Then dividing by $$$b:$$$ $$$ \frac{k \cdot a_0}{b_0} + k = g$$$

            Notice that $$$gcd(a_0, b_0) = 1$$$, but $$$\frac{k \cdot a_0}{b_0}$$$ is some integer, thus $$$b_0|k$$$. In other words $$$k = b_0 \cdot c$$$ (for some $$$c$$$).

            So we get $$$c \cdot a_0 + c \cdot b_0 = g$$$, it means that $$$c|g$$$. Also $$$g|b$$$. Having $$$c, g, b$$$ we can get $$$a, a_0$$$. So I used that trick to iterate over every triple $$$(c, g, b)$$$(Also you need to check that $$$gcd(a_0, b_0) = 1$$$)

            And a bit of optimization: notice that $$$b \lt \frac{g^2}{c}$$$ (otherwise $$$a$$$ won't be positive).

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

              Thanks. I wasn't thinking about $$$k=b0⋅c$$$. So I didn't solve this problem.

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

      can you explain me why a must be a multiple of b?

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

        in div2.D1 b.gcd(a,b) divides (a+b) hence b divides (a+b) , => (a+b) = k.b Then a = (k-1).b , this means b divides a

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

    Could you please explain why can we use step $$$k^2$$$ for the inner loop?

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

      Check the editorial for necessary conditions of a valid pair. My solution is just about omitting some math from it.

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

My O(n log^3 n) solution has passed the Div1B2, can anyone hack it or give a tighter complexity?

258888693

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +11 Vote: I do not like it

    your complexity is $$$O(answer * log(n))$$$ :) max answer is $$$11680996$$$

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

      Thanks.

      Is this explaination correct? "For most cases, gcd(u,i-u)=1, so we can assume the enumeration quantities approximate to the answer."

      → Reply
»
2 years ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

Nice maths training contest

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

Can anyone give me the reason why this got signed integer overflow 258927405. I have checked the code it and it is correct for other ranges,but fails here.

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +34 Vote: I do not like it

As far as I'm concerned, E is a bit classical and similar to CF837F.

Thanks anyway to this round that made me GM.

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

A different solution to div1. A, div2. C using binary search.

The answer is completely binary searchable and there isn't anything wrong with it, but it doesn't match my intuition.

Let binary search on the number of Full permutations you create, we can handle the remaining part manually with an O(n), in binary search, let's check if we can have $$$x$$$ full permutations created, to check it we can just calculate the need for that much permutation for each item and see if have more or less if we had less we just add the mid - a[i] to the want variable, it's just the matter to check if want <= k.
Obviously, l is the answer, so you know that you can create n*(l-1) + 1 full permutations, (for x permutations, we need $$$n+x-1$$$ elements).
Now let's handle the remaining value. we manually loop through all the elements and if any element had anything less than l, we just add that to the want variable, otherwise the number of permutations you can create gets increased by one(reader's exercise: Why? ).

the code: 258927507

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

    Had the exact same idea ... dont know where it went wrong ... help

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

      I think the issue with your code is that the initial high value is very high and may lead to overflow (I'm not certain how because I don't use C++ that often). If you change it to 1e13, it works just fine.

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

    Please tell me how the number of permutations is increased by one if any element is more than k pls. if k=0 and you have 2 3 2 where will you add the extra two

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

      think about how you set up the first permutation if you have some extra from one

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

        can you give a bit more hint about the construction of the answer? I am still not able to fully understand how it will always increase the number permutations by one

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

      Oh I just noticed I miss typed in the original comment
      By k I meant L sorry

      → Reply
»
2 years ago, hide # |
 
Vote: I like it -35 Vote: I do not like it

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

OMG D2...

I got: a = dp >= (p + q)p b = dq >= (p + q)q

So, I decided to sum up them and get: a + b >= (p + q)^2

Nice contest though

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +54 Vote: I do not like it

Loved the round, thank you! The best moment of the contest for me was when I started coding Persistent Segment Tree in Div.1 D (it wouldn't have worked probably) and realized that there's a cute solution with much less code! Though E1 looks like a pretty standart problem to be honest...

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

For 1972C - Permutation Counting, I first misread the problem as to find the maximum possible answer for any $$$m \le n$$$, where the subarrays form permutations of $$$[1,m]$$$. 258892957

I'm not sure if that was the right approach for the misread verison, but after realizing my mistake, simply disabling the outer loop to handle only $$$m=n$$$ case made it AC. 258896138

Would've been great for me if the problem was actually about the misread one :)

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

Very good math problems and fast editorial. Thanks!

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

I am a newbie and I intend to reach to pupil quickly.What resources should I follow to reach it and I really feel annoyed with questions like B that was asked today.I tend to spend a lot of time on such problems and many a times contest gets ended and I am unable to come up with solution.Please guide me

→ Reply
»
2 years ago, hide # |
← Rev. 4  
Vote: I like it +55 Vote: I do not like it

I like Div1E, thanks, though I couldn't make it on time...(QAQ) Here is my solution.

We can rephrase the problem as a random walk:

  • The states are $$$-1, 0, \ldots, m-1, m$$$.
  • Start at $$$b_0$$$.
  • States $$$-1$$$ and $$$m$$$ are absorbing.
  • From states $$$0, \ldots, m$$$, decrement with probability $$$1/m$$$, increment otherwise.
  • Let $$$z_i$$$ be the probability that it does not end up at $$$i$$$ after $$$n$$$ steps. The answer is $$$m^n (1 - z_{-1})$$$.

If we had infinite number of steps instead of $$$n$$$, the problem would be classical. Let $$$f_i$$$ be the probability that, starting from $$$i$$$, it is eventually absorbed at $$$-1$$$ after infinite number of steps. We have $$$f_{b_0} = z_{-1} + \sum_{0\le i\le m-1} z_i f_i$$$. It is known that $$$f_i = \dfrac{(m-1)^{m-i}-1}{(m-1)^{m+1}-1}$$$ for $$$m \ne 2$$$ and $$$f_i = \dfrac{m-i}{m+1}$$$ for $$$m = 2$$$. (Caveat: What if $$$998244353$$$ divides the denominator? It turns out no such case exists within the constraints, luckily.)

To compute $$$z_i$$$ for $$$0 \le i \le m-1$$$, we can reduce it to certain path counting and use reflection method as in the editorial. It takes $$$O(n/m)$$$ time for each $$$i$$$, thus $$$O(n)$$$ overall. (Caveat: The sum of $$$m$$$ is not bounded! We should do this only for $$$b_0-n \le i \le b_0+n$$$.)

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +47 Vote: I do not like it

Lol, I thought about the model solution to E1, but also thought "Huh? quite weird $$$O(min(nm, \frac{n^2}{m})$$$ tradeoff solution with a ton of detailed math? I'm not coding that for 1750 points! There must be some much slicker way to do this!" and that turned out to be exactly the intended solution xD... But I managed to get D instead and I wouldn't be able to do both anyway

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

Could anyone explain the output of this test case for the div2C problem?

10 9

1 9 1 2 1 5 7 5 3 3

The answer is 27 but I am only getting 26 as max.

[6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10]

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Here is an optimal solution for that test case

    • Buy 3 cards of the first and third ones
    • Buy one card for the fourth one
    • Buy two cards for the fifth one

    then you can arrange them as follows and get 27 as the maximum score:

    1 2 3 6 7 8 4 5 9 10 1 2 3 6 7 8 4 5 9 10 1 2 3 6 7 8 4 5 9 10 1 2 3 6 7 8
    → Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

I have made detailed video explanations for C and D1 Question Here are the links for anyone who wishes to watch

C : https://www.youtube.com/watch?v=ZP4HPYTWtZQ D1 : https://www.youtube.com/watch?v=cSKooXv7FKA

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

    Why didn't you mention in the comment that it's not in English? To gain some unintended view?

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it -8 Vote: I do not like it

    Why did you write I have made detailed video explanations for C and D1 Question Here are the links for anyone who wishes to watch instead of मैंने सी और डी1 प्रश्न के लिए विस्तृत वीडियो स्पष्टीकरण बनाया है, जो कोई भी देखना चाहता है उसके लिए यहां लिंक हैं?
    What drove your decision to advertise the videos in english? =)

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

can anyone help me finding what's wrong with this approach in 2/C

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Inside the binary search, you can break when tmp < 0 (clearly). Turns out, you "must" break otherwise some negative integer overflow will occur and unintentionally make tmp positive even though it should DEFINITELY be negative once tmp < 0 occurred. I got AC on your submission with this change. 258943287

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

We can also solve Div1C in $$$O(n \log^{2} n )$$$ by maintaining the generating function $$$g_{i}(x)$$$ for every position $$$1 \leq i \leq n$$$, where $$$[x^{n}]g_{i}(x)$$$ denotes the value of $$$f^{n}(a)[i]$$$ where $$$a$$$ is the array we are trying to find and $$$f$$$ is the "fenwick function" from the statement. We maintain it by processing $$$i$$$'s in the ascending order of their lowest bit and summing up the generating functions. The result can be extracted as $$$a[i] = [x^{k}]g_{i}(x)$$$.

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +46 Vote: I do not like it

I enjoyed div1C a lot, thank you! I came up with a solution different than the one mentioned in the editorial (using matrices).

Solution

And here is my submission : 258943002

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

    If i understood correctly, your solution is actually the same as the editorial solution, because if im not mistaken, the part that you calculate with matrices is exactly the same binomial coefficient mentioned in the editorial(if we solve the equations that you mentioned, to get an explicit formula).

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

How to find more problems like B which require you to make a very minute observation like it was parity of number of 'U's removed here for every possible type of move, at times it is first and last element....

Is there any way of improving in such problems which don't follow of flow of logic and just break as soon as we make an observation ... ?

I was able to solve D1 and C both but couldn't come up with B and it happens quite a lot ..

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +55 Vote: I do not like it

A brutal solution for 1C: Let $$$T$$$ be the linear operator that does the "Fenwick tree" transform, one can verify that $$$(T-I)^{k}=0$$$ for $$$k = \log n$$$. So to solve the equation $$$T^m v = a$$$, just compute the coefficient of $$$x^{-m} \bmod (x-1) = \sum_{i \lt k} c_i x^i$$$, thus we have $$$v = \sum_{i \lt k} c_i T^i a$$$. Since $$$T$$$ can be applied to a vector in linear time, this has time complexity $$$O(n\log n)$$$.

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

    I'm eager to grasp your solution; could you recommend any prerequisite resources to aid my understanding? Thanks in advance.

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

    Just a minor typo, the mod should be $$$(x-1)^k$$$, not $$$(x -1)$$$, right?

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

    I have yet to understand why the linear operator $$$T$$$, which is a $$$n\times n$$$ matrix, can be applied to a vector in linear time? That is, when we multiply a $$$n\times n$$$ matrix with $$$n\times 1$$$ matrix, the time complexity should be $$$O(n^2)$$$, right? Or have I left out something important?

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

TOOOOOO much math... But the problem attached seem good imo Ive also stuck at D1/D2 almost 2h, Im not good at algebra... Each problem was so coooool but the set was tooooooo biased...

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

    I managed to do both D1 and D2 from first using brute force on a smaller number and then finding a pattern to optimize it.

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

      Yes I've tried to do as similar method. Maybe I almost reached to answer but failed to implement it due to limited time :( my skill issue lmao

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

what is | in D1 and D2 stand for?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +25 Vote: I do not like it

It seems that there are many alternative solutions to E2. Looking through the submissions, here are some that I don't understand (and they look quite different from the editorial):

258928492 258921598 258925888 258917151

jiangly maroonrk maspy potato167 Would any of you mind explaining how your solution works? :)

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

    Let $$$path_{[0,M)}(b,i)$$$ denote the number of Dyck path from $$$(0,b)$$$ to $$$(i,0)$$$, which lies within the range $$$0 \leq y \lt M$$$. Then, we need to compute $$$\sum_i f[i] \cdot path_{[0,M)}(b,i)$$$ for some coefficients $$$f[i]$$$.

    By the reflection principle, $$$path_{[0,M)}(b,i)$$$ can be represented as $$$\sum_{b'} (\pm 1) \cdot path(b',i)$$$, where $$$path(b',i)$$$ has no restriction to the range of $$$y$$$.

    Therefore, we need to compute $$$\sum_b (0 \text{ or } \pm 1) \cdot \sum_i f_i \cdot path(b,i)$$$. So, the problem is reduced to computing $$$\sum_i f_i \cdot path(b,i)$$$ for each $$$b$$$. In other words, computing the composition $$$\sum f_i(x+x^{-1})^i = f(x+x^{-1})$$$.

    In this case, we can show that $$$f_i$$$ forms a geometric sequence (from $$$b_0$$$ to $$$N-1$$$), and $$$f(x)$$$ takes the form of $$$(\text{a sparse polynomial of degree N+1}) / 1-rx^2$$$.

    Therefore, $$$x^{N-1}f(x+x^{-1})$$$ is a polynomial of degree $$$2N+2$$$ divided by a polynomial of degree $$$4$$$, and this can be computed in $$$O(N)$$$ time.

    By the way, the composition $$$f(x+x^{-1})$$$ can be computed in $$$O(N\log N)$$$ time (https://mirror.codeforces.com/blog/entry/126124). I studied it today.

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

    My solution is almost the same as maspy's solution. The only difference is the way to compute $$$g_b=\sum_{i} f_i \cdot path(b,i)$$$. I didn't use polynomial things and directly calculated the recurrence relations for $$$g_b$$$ by considering paths.

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      I didn't use polynomial things and directly calculated the recurrence relations for ...

      Would you mind elaborating?

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it +21 Vote: I do not like it

        Let $$$g_b=\sum_{0 \leq x, 0 \leq y, x+y \leq K, x-y=b} w^{x+y} {x+y \choose x}$$$. Then consider $$$g_b-w(g_{b+1}+g_{b-1})$$$. It can be calculated in $$$O(1)$$$ time.

        → Reply
»
2 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

Can anyone explain more clearly the solution of problem E div1? I do not really understand.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Update rank too late !

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

The solution of 2D2/1B2 is pretty amazing: I couldn't believe that we can delete q of $$$(p+q)\mid qd$$$ in such an easy proof!

All in all, I think this contest is better than my last contest Educational Codeforces Round 141 (Rated for Div. 2). Thinking deeply should be the biggest feature of codeforces, that's why I prefer this round. Though in mathforces, a high quality contest is needy.

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

Enumerate $$$i$$$ from $$$1$$$ to $$$n$$$. Enumerate $$$a_i = w$$$ for $$$w$$$ from $$$1$$$ to $$$m$$$. If it is possible for $$$a_i = w$$$ after $$$k$$$ steps, $$$w \gets w + 1$$$; Otherwise, $$$i \gets i + 1$$$. If $$$i$$$ gets to $$$n + 1$$$ first, it's valid. If $$$w$$$ gets to $$$m + 1$$$ first, it's invalid.

Should it be "If it is possible for $$$a_i = w$$$ after $$$k$$$ steps, $$$i \gets i + 1$$$.; Otherwise, $$$w \gets w + 1$$$"?

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

C is one of the best and most satisfying problems I've ever seen, and D1 and D2 were also really nice as well. Thanks to authors for making a great contest!

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

can someone tell the time complexity of the code used for calculating if a pair is coprime in the solution of div-2 d2.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Seems to be $$$O(\frac{\sqrt{n} }{2} \cdot \frac{\sqrt{m} }{2} +\frac{\sqrt{n} }{3} \cdot \frac{\sqrt{m} }{3}+\frac{\sqrt{n} }{4} \cdot \frac{\sqrt{m} }{4}+\cdots)=O(\sqrt{nm}\cdot \sum _{i=2}\frac{1}{i^2})=O(\sqrt{nm}\cdot (\frac{\pi ^2}{6} -1))= O(\sqrt{nm} ) $$$

    Anyway, after contest I just tried add an extra judgement of if (gcd(a, b) == 1), and it didn't raise the time complexity too much and got AC as well.

    → Reply
»
2 years ago, hide # |
 
Vote: I like it -30 Vote: I do not like it

I cannot understand why so many people upvoted the annoucement and editorial.

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

Can someone please explain div2 C. I was able to figure out that we need to binary search for the number of full segments of [1..n] and answer would be at-least n*(full-1) + 1. But how to handle the remaining elements which can be appended to the prefix and suffix of these full segments.

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

I did brute force , and it worked for D1 , i just checked for each a and b , checked their gcd and put it in the formula , just kept increasing a by b in each iteration , that made the complexity (b)*(a/b) which is a , and it worked, didnt understand the answer given here tho :/ my submission link : https://mirror.codeforces.com/contest/1972/submission/258899009

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

in problem 2D2/1B2, how $$$gcd(p + q, q) = gcd(p, q) = 1$$$ helps in droping the term $$$q$$$ in $$$(p+q) ∣ (qd)$$$

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    I think this is done to find the max values of p and q

    since (p+q) can't divide q it doesn't contribute to find the max of p and q such that they can be used to find the solutions

    hence it is removed .

    might help

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

We also know that p≥1,q≥1,so p<d=ap≤np and thus p2<n

why should p<d?? (div 2 D2)

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

    If p>=d, then p+q>d, then d obviously can't be a multiple of p+q.

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    div 2 D2:

    a=pd,b=qd,
GCD(a,b)=d => GCD(p,q)=1
b*d=c(a+b)   ;c=constant
qdd=c(p+q)d
qd=c(p+q)
qd/(p+q)=c
since (p+q) cant divide q as gcd(p+q,q)=gcd(p,q)=1
q(d/(p+q))=c
p>=1 and q>=1
max value of (p+q) should be d in order to divide it.
to get max of p , fix q to min(1)
p+1<=d
p<=d-1
p<d
    → Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Can anyone explain why in div1C the coefficient of a_u in b_v will be the mentioned value?

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

I still don't understand why 6th testcase in Div2 C is 32. I currently can only find 31 permutations.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Buy cards so that the array becomes 7 6 4 7 6 4 4 4 4. One of the possible sequences: 1 2 4 5 3 6 7 8 9 (repeat 4 times) 1 2 4 5. Number of permutations = 9 * 4 + 4 - 8 = 32

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

My solution to 1967A — Permutation Counting using check max_element > (sum_element + k) / (number_of_elements)
https://mirror.codeforces.com/contest/1967/submission/258991320

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

In question E div2 Fenwick Tree. The editorial states that it's easy to prove that the coefficient is

Can someone walk me through it because I kept trying on my own and couldn't come up with it...

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

    In the contest I try generating the fenwick tree and try to come up with the coefficient from the result

    0 [100 0 0 0 0 0 0 0]
    1 [100 100 0 100 0 0 0 100]
    2 [100 200 0 300 0 0 0 400]
    3 [100 300 0 600 0 0 0 1000]
    4 [100 400 0 1000 0 0 0 2000]

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +7 Vote: I do not like it

    you can get a coefficient matrix like:

    1 1 1   1  1  1
1 2 3   4  5  6
1 3 6  10 15 21
1 4 10 20 35 56
...

    where row_i is k, and column_j is delta_d

    consider a_1 in b_1 to b_8

      b:  1  2  3  4  5  6  7  8
k=0:  1  0  0  0  0  0  0  0   
k=1:  1  1  0  1  0  0  0  1
k=2:  1  2  0  3  0  0  0  4
k=3:  1  3  0  6  0  0  0  10
k=4:  1  4  0 10  0  0  0  20
....

    let c_u_k denote the coefficient of a_1 in b_u in f^k(a), then c_8_k = c_1_(k-1)+c_2_(k-1)+c_4_(k-1)+c_8_(k-1), note that c_4_k = c_1_(k-1)+c_2_(k-1)+c_4_(k-1), so we have c_8_k = c_4_k + c_8_(k-1), which is a classic formulate for combination number.

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

      I understand what you're saying and I actually came up with something similar:

      for i % 2 == 0: b(k)[i] = a[i] + b(k)[i/2] + b(k-1)[i]

      for i % 2 == 1: b(k)[i] = a[i]

      but I guess I'm a bit weak in combinatorics as I still don't know how to draw the general rule. I think I have to work on that.

      But thanks a lot for explaining it <3

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

        don't take all elements at once， take 8 for example， a_4 a_6 a_7 in b_8 are the same（ dep=1 ）， and then a2 a3 a5（ dep=2， and a2 a3 in b4 is dep=1， a5 in b6 is dep=1） ， then a1 in b8（ dep=3， a1 in b2 is dep=1， a1 in a4 is dep=2）， the rule is about dep and k

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

          Oooooh, I totally get it now. Thanks a lot <3

          Dealing with the fenwick tree as an actual tree that's a first for me, nice problem indeed.

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

In the tutorial for D2 :-

Can anyone please explain how we got (p+q) | d from (p+q) | qd?

My understanding:

b * gcd(a, b) = (a + b) * k

From here we can say that a needs to be a multiple of b hence a = b*x

So, b * gcd(a, b) = (bx + b) * k

Hence as per the editorial p = x and q = 1 but then why aren't we considering q = 1 in (p+q) | d which will eventually look like (p + 1) | d?

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

    p and q are co-prime if p+q|qd if there is a common divisor between p+q and q lets call it s so now we have s*x=p+q s*y=q; subtracting them we get s*(x-y)=p which means that s divides p, but s already divides q hence it is a contradiction to the fact that p and q are co prime hence there is no such divisor hence p+q|qd----> p+q|q

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

can someone explain me how stars and bars is used in problem Div1 C. .

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

"We know q=1 because gcd(p,q)=1." how can we say that doesnt this mean p and q both are coprimes?

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

For 1967C — Fenwick Tree, I have a function that computes the inverse factorials under a modulo MOD, but I'm getting different values than the solution above? 

def factorials(n):
    fact, inv_fact = [1] * (n + 1), [0] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = (fact[i - 1] * i) % MOD
    inv_fact[-1] = mod_inverse(fact[-1])
    for i in reversed(range(n)):
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD
    return fact, inv_fact

It becomes wrong after inv_fact[3] = 166374059, compared to their calculate where inv[3] = 332748118. I've used the function above for many problems, couldn't imagine it is wrong.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

How to solve E1 using NTT?

For the $$$dp_{i,j}$$$ as mentioned, could understand that $$$dp_{i-1} \times (x^{-1}+(m-1)x^1) = dp_i$$$, but the transition has limit at -1 and m.

Does it use "circular convolution" trick (on CDQ processing) just like this AT problem?

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

    You may solve it using a D&C. When you need $$$a$$$ transforms, the $$$[a,m-a]$$$ part is easy by using a direct convolution, so you need just deal with the first $$$a$$$ terms and the last $$$a$$$ terms, and that's small.

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

      Can you elaborate on how to deal with first/last $$$a$$$ terms? I can't figure out how to deal with it in $$$\tilde O(a)$$$ time.

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

        finally figure out the details.

        supposed that it only has the lower limit at Y=-1, and do not has the upper limit, we can use the following D&C to solve it:
        * supposed that we want to calculate $$$dp_R$$$, where $$$dp_L$$$ has been finished (which was used as the input for $$$dp_R$$$);
        * let $$$len=R-L$$$, if the size of input is not greater than $$$len$$$, we just recurse it: by calculating the middle column first, and then use the middle row to calculate the right part...
        * otherwise $$$[dp_{L,len},dp_{L,sz-1}]$$$ can do a direct convolution (add the result to the last column), and the remain part (with length not gerater than $$$len$$$) just do sth as the above.

        when it has lower limit Y=-1 and upper limit Y=M, we can do some similarity:
        * when the input size not greater than $$$2len$$$, we just rucurse it;
        * otherwise use $$$[dp_{L,len},dp_{L,sz-1-len}]$$$ to do a direct convolution;
        * and the two remain parts are exactly on the situation: it has only one lower/upper limit.

        here is my implemention.

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

          Cool, I thought that algorithm can only handle the case where lower bound exist. Thank you!

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

            I did a bit of analysis on it, and it seems such algorithm can handle counting non-decreasing path with limited degree of transition polynomial $$$f$$$ (let say its degree is $$$|f|$$$) with limited adjacent difference of lower bound/upper bound (let's say $$$L_n, U_n$$$ is respective lower/upper limit sequence and $$$max(max_{i = 2}^{n}(L_i - L_{i - 1}), max_{i = 2}^{n}(U_i - U_{i - 1})) = D$$$).

            Since after we transit the "middle part" at some $$$(l, r)$$$ using direct convolution, the following called would only need to handle one bound, and this part would cost $$$O((n + m)\lg (n + m))$$$

            Then for the following part handle only one bound (let's say lower part, the analysis for upper is similar), when recurse from $$$(l, r)$$$ to $$$(mid, r)$$$ (for $$$(l, mid)$$$ its degree would be no more than the $$$(mid, r)$$$ part), it would have to handle a polynomial of degree $$$(L_r - L_l) + |f|(mid - l) \leq (r - l)(D + |f|)$$$ and do at most one convolution on it, so this part would cost $$$O(n(D + |f|)\lg (n(D + |f|))\lg n)$$$

            So the complexity of this algorithm is $$$O(n(D + |f|)\lg (n(D + |f|))\lg n + (n + m)\lg (n + m))$$$. And it would be fast enough as long as $$$m$$$ and $$$n(D + |f|)$$$ are small enough.

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

Yo guys, I am currently reading the editorial for D1. I understood everything up until this last section. I understand why we are enumerating d from 1 to m (since d is essentially just b since q is 1). I am not sure how p becomes floor(n / d). Since p * d = a, don't we have to also enumerate all a's up to n? Why are we just greedily using n (the bound for a) over all d's?

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

    $$$a=pd=(kd-1)d$$$, so we enumerate $$$a$$$ by enumerating $$$k$$$. $$$k$$$ can be any positive integer from 1 to $$$\lfloor(\lfloor n/d\rfloor+1)/d \rfloor$$$ (unless $$$d=1$$$, when 1 must be omitted), so we add $$$\lfloor(\lfloor n/d\rfloor+1)/d \rfloor$$$ to the count.

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

For E1/E2, if you work in the ring of power series modulo $$$x^{2(m+1)}-1$$$, then the number of failing $$$a$$$-sequences is the constant coefficient in

$$$(x^{-1} - x) x^{b_0 + 1} (m - 1)^{-b_0/2} \frac{m^n - (m - 1)^{n/2} (x + x^{-1})^n}{m - \sqrt{m - 1} (x + x^{-1})}.$$$

Using this together with fast exponentiation-type algorithms and FFT convolution, you can get an $$$O(m \log m \log n)$$$ method, although it doesn't seem to be faster than the editorial method unless $$$n/m$$$ is quite large.

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

I could not comprehend the solution for Div1C (Fenwick Tree). Could someone please elaborate on the solution, or suggest any resources that could aid in my understanding?

P.S.: I am familiar with the basic Fenwick Tree

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +11 Vote: I do not like it

    To calculate $$$\textrm{coefficient}\cdot a_u$$$ in $$$b_v$$$, think about how many ways $$$a_u$$$ can reach $$$b_v$$$. Say, $$$a_5$$$ can reach into $$$b_{16}$$$ via $$$b_6, b_8, b_{16}$$$. Now, the number $$$3$$$ came from the depth difference of $$$5$$$ and $$$16$$$ being $$$3$$$. And you want to cover this $$$3$$$ distance using $$$k$$$ steps, where in each step you either propagate forward or stay in place.

    If you don't know stars and bars method, a short explanation is that $$$n$$$ things can be divided into $$$m$$$ portions (where a portion is allowed to have $$$0$$$ things in it) by inserting $$$m-1$$$ separators, thus the number of ways become $$$\binom{n+m-1}{n}$$$ (treat the separators also as "things", then make any valid arrangement).

    Now, if you piece it together, using the example, $$$a_5$$$ can reach $$$a_{16}$$$ by first staying in $$$5^{th}$$$ place or propagating, in fact even staying in place for $$$k-2$$$ steps and propagating twice, or any other way. Every different choice represents a coefficient of $$$a_5$$$in $$$b_{16}$$$. This number of ways should be $$$\binom{3+k-1}{3}$$$, using $$$k-1$$$ separators between $$$3$$$ propagation actions. Replace $$$3$$$ with $$$\Delta d$$$ and you got the formula.

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

In 1967B1 — Reverse Card (Easy Version) Tutorial, I got till the point where count of values of a is floor(n/d), but after that why the answer is floor((floor(n/d)+1))/d). Can anyone explain?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

div1C can be also considered in a linear algrebra perspective. Notice each time of BIT is simply a linear operation. And it is so spartial that we can apply some optimization on it. For each index $$$x$$$, thinking the chain $$$b_1 = x, b_2 = b_1+(b_1 \text{&} -b_1), b_3 = b_2 + (b_2 \text{&} -b_2) ...$$$ (which length at most $$$O(\log n)$$$) chain.

Define

$$$ A := \begin{pmatrix} 1 & 0 & 0 & ... & 0 \\ 1 & 1 & 0 & ... & 0 \\ 1 & 1 & 1 & ... & 0 \\ ... & ... & ... & ... & ... \\ 1 & 1 & 1 & 1 & 1 \end{pmatrix} $$$

If contribution of index $$$x$$$ ($$$a_x$$$) for location at each $$$b_j$$$ ($$$a_{b_j}$$$) after $$$T$$$ round is $$$v^T = (v^T_1, v^T_2, ..., v^T_{\log n})$$$, then after one more round, it is: $$$v^{T+1} = A v^T$$$. That is, the contribution of $$$a_x$$$ to each $$$b_j$$$ after $$$K$$$ op is $$$A^K \begin{pmatrix}1 \ 0 \ 0 \ ... \ 0\end{pmatrix}$$$.

$$$A^K$$$ can be simply calculated with pre compute $$$A^1, A^2, A^4, ..., A^{2^{30}}$$$ in $$$O((\log m)(\log n)^3)$$$, and evaluate in $$$O(\log K (\log n)^2)$$$ (segmv is $$$O((\log n)^2)$$$).

Then for each index $$$b_j$$$ except first one, just have $$$b_j \gets b_j - v_j^K \times a_x$$$ as the contribution, at the end it will ends with desired answer, which is $$$O(n \log n)$$$.

Total complexity is $$$O((\log m) (\log n)^3 + n\log n)$$$

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

    Hi , I had some trouble understanding your solution , more precisely : how did you manage to make the sizes of the A and v logn , I think thats something you did with the chain optimization you mentioned but I couldnt understand that either :/ Can you explain that more elaborately.

    Thanks in advance

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

I'm not sure to understand the tutorial for 1967A — Permutation Counting because of this edge case:

Assume you had:

n = 6 and k = 0

with cards: 1 1 1 2 2 2 3 3 4 4 4 5 5 6 6 6 (that is 3 3 2 3 2 3)

then the array we will make is: 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 ; plus one 4 that we have to use. Without the 4, there are 10 permutations to this array.

However, I don't know where to place the last 4 to generate the answer 11, the answer the algorithm would give this problem: cnt = 2 (for 3 and 5) lst = 2 (because 3 and 5 both have 2) ans = n*lst - cnt + 1 = 6*2 - 2 + 1 = 11

Why is the answer 11?

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

1967B1 — Reverse Card (Easy Version)

What if I set p = 1, How should I proceed from qd | (p + q)?

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

    I can't come up with a useful bound for k if I set p = 1. Could you please help me how we can solve this considering p = 1? My understanding was that because gcd(p , q) = 1, so we can set either q = 1 or p = 1.

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

For problem Long Way to be Non-decreasing there is a simpler way to group each element without using DSU


	mroot := make([]int, m+1)
	var getroot func(i int) int
	getroot = func(i int) int{
		if mroot[i]==0{
			mroot[i]=i
			mroot[i] = getroot(getparent(i))
		}
		return mroot[i]
		
	}
→ Reply
»
23 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

.

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

Great editorial

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

cute rui_er

→ Reply
»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Found B1 to be a beautiful problem...loved the math

→ Reply