rui_er's blog

Codeforces Round 942 (Div. 1, Div. 2) Editorial
By rui_er, history, 2 weeks 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
  • +91
  • Vote: I do not like it

»
2 weeks ago, # |
← Rev. 2   Vote: I like it +111 Vote: I do not like it

too math, downvoted...

→ Reply
»
2 weeks ago, # |
  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 weeks ago, # |
  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 < 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 weeks ago, # |
← 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 weeks ago, # ^ |
      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 weeks ago, # ^ |
      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 weeks ago, # ^ |
    ← 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
  • »
    »
    11 days ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    orzorzorz

    → Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

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

#include "bits/stdc++.h"
#define int long long

signed main() {
    int tt; scanf("%lld", &tt);
    while (tt--) {
        int n; scanf("%lld", &n);
        char c[n]; scanf("%s", &c);
        std::string s(c);
        int cntU = std::count(s.begin(), s.end(), 'U');
        if (cntU % 2 == 1) printf("YES\n");
        else printf("NO\n");
    }
}
→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Inadequate char array length.

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

      Thanks!

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

      but why? its size is n

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

        You need a \0 (which is $$$0$$$ if you convert it to int) to tell the language that a C-type string ends here. So you'll need extra space.

        → Reply
        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          ok thanks! i will never use char[], scanf, printf

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

Whoa did not expect the solution to B would be so simple

→ Reply
»
2 weeks ago, # |
  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 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I've tried, but its making solution too much complex bcz of such input: 1 1 1 2 2 2 3 3 3

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

    Here 258928208

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

      can you explain please?

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

        Here curr is storing the minimum value all the elements can reach and rem stores the remaining operations after that minimum value is reached. Every element in priority queue I am comparing with previously reached value and calculating whether it possible to reach next top of priority queue value with remaining k.

        → Reply
»
2 weeks ago, # |
← 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 weeks ago, # ^ |
      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 weeks ago, # ^ |
        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 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Thanks a lot for the explanation!

        → Reply
      • »
        »
        »
        »
        10 days ago, # ^ |
          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
        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            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
  • »
    »
    13 days ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

    → Reply
»
2 weeks ago, # |
  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 weeks ago, # |
  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 weeks ago, # |
  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 weeks ago, # ^ |
      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 > fulls$$$ (and purchase $$$r$$$ distinct $$$a_i <= fulls$$$) at any end of full permutations to form additional permutations of $$$1..n$$$.

    258906139

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

      I used binary search on k, I sorted array just ,

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

      how will you arrange for this test case 2 3 2 how will you add the extra 2 ?

      → Reply
»
2 weeks ago, # |
← 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 weeks ago, # ^ |
      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 weeks ago, # ^ |
        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 weeks ago, # ^ |
        ← 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 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Cool that it fits in time

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

            Well, i am sure that it is less than O( nlog^3 n), but i don't know what it is exactly.

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

          Can you elaborate on your approach?

          → Reply
          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
            ← 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 < \frac{g^2}{c}$$$ (otherwise $$$a$$$ won't be positive).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                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 weeks ago, # ^ |
        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 weeks ago, # ^ |
          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
»
2 weeks ago, # |
  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 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        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 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Nice maths training contest

→ Reply
»
2 weeks ago, # |
← 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 weeks ago, # |
← 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 weeks ago, # |
← 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 weeks ago, # ^ |
      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 weeks ago, # ^ |
        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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It was (mid-a[i]) so it overflowed ... Damn I am stupid

        → Reply
  • »
    »
    2 weeks ago, # ^ |
      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 weeks ago, # ^ |
        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
      • »
        »
        »
        »
        3 days ago, # ^ |
          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 weeks ago, # ^ |
        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
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      2 3 1 2

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

→ Reply
»
2 weeks ago, # |
  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 weeks ago, # |
  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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

B2

https://qr.ae/pswyHC

→ Reply
»
2 weeks ago, # |
  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 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Very good math problems and fast editorial. Thanks!

→ Reply
»
2 weeks ago, # |
  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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Take a look at the codeforces catalog. There people much smarter than me have posted the exact thing you are looking for.

    From resources to guides on how to improve and tutorials on specific topics and even stuff on mindset and attitude.

    https://codeforces.com/catalog

    → Reply
»
2 weeks ago, # |
← 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 weeks ago, # |
← 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wish I could become as good as you to even come up with that complexity of the problem.

    → Reply
»
2 weeks ago, # |
  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 weeks ago, # ^ |
      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 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you please explain why this case has answer 3? I can only simulate the answer is maximum 2, no matter how much I try. Thank you.

      1

      6 0

      1 2 1 2 1 1

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

        You can arrange them like this:

        2 4 1 3 5 6 2 4

        then you get [1, 6], [2, 7], [3, 8] as valid subarrays

        → Reply
»
2 weeks ago, # |
  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 weeks ago, # ^ |
      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
  • »
    »
    10 days ago, # ^ |
      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 weeks ago, # |
  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 weeks ago, # ^ |
      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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah i just found the problem with my code

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

    NVM it was actually signed integer overflow! :(

    → Reply
»
2 weeks ago, # |
  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 weeks ago, # |
← 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 weeks ago, # ^ |
      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 weeks ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Yeah, that's right. But the good thing is that I don't have to solve any equation. Just let matrices do it!

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

I still need to practice,my math is very poor...

→ Reply
»
2 weeks ago, # |
  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 weeks ago, # |
  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<k} c_i x^i$$$, thus we have $$$v = \sum_{i<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 weeks ago, # ^ |
      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
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Solution này dùng ma trận của ánh xạ tuyến tính á. Nếu bạn học Đại Số Tuyến Tính ở chương trình ĐH rồi thì sẽ biết cách dùng này.

      → Reply
  • »
    »
    2 weeks ago, # ^ |
      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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, thanks for pointing that out

      → Reply
  • »
    »
    10 days ago, # ^ |
    ← 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
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I mean for the specific $$$T$$$ in this problem, it holds

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

        Thank you very much. This problem is hard, even when you have a good understanding of Linear Algebra and found that $$$(T-I)^n = 0$$$ due to the Cayley-Hamilton theorem, that will just not enough, let alone proving that $$$T-I$$$ is nilpotent. You need to find the nilpotent degree of $$$T-I$$$, that is the smallest value of k such that $$$(T-I)^k = 0$$$ and come up with $$$k \leq \log n$$$ is not that easy at all. Also an inexperienced coder like me can stumbled on my dumb question above :)))

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

    After reading your solution, I had difficulty in computing coefficient $$$c_i$$$ so I have changed my approach to the following:

    Instead of computing $$$c_i$$$, I used Taylor Series here:

    $$$ \begin{aligned} x^{-m}&= 1 + -\frac{m}{1!}(x-1) + \frac{m(m+1)}{2!}(x-1)^2+\ldots\\

    &\equiv 1 + -\frac{m}{1!}(x-1) + \ldots +(-1)^{k-1}\frac{m(m+1)\ldots(m+k-2)}{(k-1)!}(x-1)^{k-1} \mod (x-1)^k \end{aligned} $$$

    So we have

    $$$ T^{-m} = 1 + -\displaystyle\frac{m}{1!}(T-I) + \ldots +(-1)^{k-1}\frac{m(m+1)\ldots(m+k-2)}{(k-1)!}(T-I)^{k-1}. $$$

    We can set $$$k=20$$$ because $$$\log n \leq 20$$$. But if $$$m$$$ is large, then it's likely that we will get integer overflow even when using long long because the last coefficient can be up to $$$\displaystyle\frac{(10^9)^{20}}{20!}$$$ . So we have to compute these coefficient according to their modulo. That triggers another problem, we have to compute the inverse of $$$i$$$ modulo $$$998244353$$$ for all $$$i=\overline{1,19}$$$, since $$$998244353$$$ is a prime number, we can write a program to get all of them easily, that is

    // inverse[i] is the number x that x*i equiv 1 mod 998244353

vector<ll> inverse = {0 ,1, 499122177, 332748118, 748683265, 598946612, 166374059, 855638017, 873463809, 443664157, 299473306, 272248460, 582309206, 460728163, 926941185,
865145106, 935854081, 939524097, 720954255, 105078353};

    And I got accepted. Here is my solution

    259730338

    → Reply
»
2 weeks ago, # |
  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 weeks ago, # ^ |
      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 weeks ago, # ^ |
        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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what is | in D1 and D2 stand for?

→ Reply
»
2 weeks ago, # |
  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 weeks ago, # ^ |
    ← 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 < 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://codeforces.com/blog/entry/126124). I studied it today.

    → Reply
  • »
    »
    2 weeks ago, # ^ |
      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 weeks ago, # ^ |
        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 weeks ago, # ^ |
          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 weeks ago, # |
  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 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Update rank too late !

→ Reply
»
2 weeks ago, # |
  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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain how we get p<d?

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it 
      It is show in editorial that gcd(p+q, q) = 1. 
Therefore (p+q)%d == 0. 
(p+q)%d = 0; 
p+q = (x*d)
we get min value of p+q at x = 1.
p+q >= d
we know, p >= 1 && q >= 1.
Therefore, p < d
      → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain the deletion part?

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

      k=gcd(a,b) p=a/k,q=b/k -> gcd(p,q)=1

      gcd(p+q,q)=gcd((p+q)-q,q)=gcd(p,q)=1

      so q is useless in this fraction, and you can delete it.

      → Reply
»
2 weeks ago, # |
  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 weeks ago, # |
  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 weeks ago, # |
  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 weeks ago, # ^ |
      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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand the DIV 2 C tutorial at all. Is it just me?

→ Reply
»
2 weeks ago, # |
  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 weeks ago, # |
  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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So once you have got the number of full segments let them be=temp. Now, traverse the input array and make all elements (which are less than temp) equal to temp. and reduce k accordingly. Now if still k>0 then traverse array again and increase all elements equal to temp by 1(why 1? because greedily we just want more no. of elements greater than temp). let no. of elements to be added be num=0. And finally traverse array again and if a[i]>temp do num++. seems a bit complicated lol but you can go through the code 258983345

    → Reply
»
2 weeks ago, # |
  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://codeforces.com/contest/1972/submission/258899009

→ Reply
»
2 weeks ago, # |
  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 weeks ago, # ^ |
      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 weeks ago, # |
← 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 weeks ago, # ^ |
      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 weeks ago, # ^ |
      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 weeks ago, # |
  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 weeks ago, # |
  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 weeks ago, # ^ |
      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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

oh shit! What have I done? I thought Alice would win if both the number of facing up coins and the number of total coins were odd. I submitted the code using this logic and received a penalty. Had I knew the number of facing of coins being odd is enough for Alice to win the game, it would have been accepted.

→ Reply
»
2 weeks ago, # |
← 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://codeforces.com/contest/1967/submission/258991320

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

For div 2 D1 why kd≤⌊n/d⌋+1 ?

→ Reply
»
2 weeks ago, # |
  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 weeks ago, # ^ |
    ← 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 weeks ago, # ^ |
      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
    • »
      »
      »
      13 days ago, # ^ |
        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
      • »
        »
        »
        »
        13 days ago, # ^ |
          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
        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            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 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain the problem I have?

I use Code::Blocks for competitive programming and yesterday I submitted the code (258902555) with error 'out of bounds', but in Code::Blocks it worked correctly unlike system showed that there is the wrong answer on one of the tests of first pretest, so I was confused and decided to rewrite code on Python.

Why didn't it show that there is the error and, moreover, worked without error and I got different answers in Code::Blocks and testing system?

→ Reply
»
2 weeks ago, # |
← 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 weeks ago, # ^ |
      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 weeks ago, # |
  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 weeks ago, # |
  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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    p=(kd−1)q implies that gcd(p, q) >= q (maybe even gcd(p, q) = q), then q = gcd(p, q) = 1.

    If q = 2, then p = (kd — 1) * 2, so gcd(p, q) = 2.

    → Reply
»
2 weeks ago, # |
  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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I see my mistake, you are not dividing by the inv_fact[d] everytime, and the inv[d] is actually not the inverse factorial, it is 1 / d.

    → Reply
»
2 weeks ago, # |
  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 weeks ago, # ^ |
    ← 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
    • »
      »
      »
      10 days ago, # ^ |
        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
      • »
        »
        »
        »
        7 days ago, # ^ |
        ← 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
        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            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
          • »
            »
            »
            »
            »
            »
            7 days ago, # ^ |
            ← 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
»
13 days ago, # |
  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
  • »
    »
    12 days ago, # ^ |
      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
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In D2, Why does $$$gcd(p, q) = 1$$$ implies $$$q = 1$$$?

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

        It doesn't in D2. In D1, it's because $$$q|p$$$.

        → Reply
»
12 days ago, # |
  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
»
10 days ago, # |
  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
  • »
    »
    8 days ago, # ^ |
      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
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2/ D2, How this formula enumerate each (p,q), in the solution of editorial? min(n/(a+b)/a,m/(a+b)/b);

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

    From the editorial you see that p + q | d, so d/(p+q) must be an integer. Furthermore, p and q must be coprime and less than sqrt(n) and sqrt(m) respectively.

    For each valid couple (p, q) how many values of d satisfy that d/(p+q) must be an integer? d = a / p <= n / p and d = b / q <= m / q. Therefore d can assume values from 1 to min(n/p, m/q). How many of these are multiple of p + q? floor(min(n/p,m/q)/(p+q)).

    → Reply
»
8 days ago, # |
  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
  • »
    »
    7 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The condition $$$b⋅gcd⁡(a,b)│a+b$$$ is equivalent to (p+1)=kd so (p + 1)/d must be an integer. Since q=1, d=b=gcd(a, b), therefore d has the same range as b: from 1 to m.

    For each possible value of d, we can count how many couples (a, b) satisfy the condition (p + 1)/d=k. Since p=a/d<=floor(n/d), p + 1 <= floor(n/d)+1. So (p + 1)/d can assume values from 1 to (floor(n/d)+1)/d. How many are them? (floor(n/d)+1)/d.

    We need to subtract one at the end because for p = 0 and d = 1 we get (p + 1)/d = 1 but that's not ok because p must be greater than 0.

    → Reply
»
43 hours ago, # |
  Vote: I like it 0 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