Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

rui_er's blog

By rui_er, history, 7 months ago, In English

久别无恙, Codeforces!

We are glad to invite you to take part in Codeforces Round 942 (Div. 1) and Codeforces Round 942 (Div. 2), which will start on Apr/30/2024 17:35 (Moscow time). You will be given 6 problems and 2 hours and 30 minutes to solve them in both divisions. Some problems will be divided into two subtasks.

The problems were authored and prepared by N_z__, wyrqwq, yinhy09 and me rui_er.

We would like to thank:

Score distribution:

  • Div. 2: 500 — 750 — 1500 — (1000 + 1500) — 2500 — 3500
  • Div. 1: 750 — (500 + 750) — 1250 — 1750 — (1750 + 1000) — 3500

We hope you'll like the problemset!

UPD: Congrats to the winners!

Div. 2:

  1. 3_m
  2. RinaRin
  3. eightniko
  4. liumohan
  5. golomb

Div. 1:

  1. tourist
  2. jiangly
  3. jqdai0815
  4. gamegame
  5. Kevin114514

Editorial is out.

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

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

Hope to get postive delta!

»
7 months ago, # |
Rev. 3   Vote: I like it -16 Vote: I do not like it

Looking forward to this high-quality contest.

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

rui_er!

»
7 months ago, # |
  Vote: I like it -10 Vote: I do not like it

As not a tester,I don't know how this round is like.

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

As a problemsetter, hope you have fun!

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

    As another problemsetter, Good Luck.

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

      As a person who read three body problem, hope to solve three problems.

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

        As a person who will be reading the problems, hope to solve four problems. GL&HF

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

          As a person who read three body problem, hope to solve three problems.

»
7 months ago, # |
Rev. 3   Vote: I like it -26 Vote: I do not like it

How hard will this round be? They are known to create hard problems. :/

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

So sad that I can't participate this contest, GLHF

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

    I think you will get upvoted if you mention the fact that you are also a team member of us.

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

Hope for high-quality problems!

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

As a tester,

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

As a tester, I tested

»
7 months ago, # |
Rev. 2   Vote: I like it -84 Vote: I do not like it

I hope this is a perfect competition.

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

As a tester,I also tested :)

GLHF!

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

I am curious about why this contest changed into div1,div2. I remember it was div1+div2 until yesterday.

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

    The sponsor is not available.

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

      What’s the reason to prefer separate rounds over a combined round?

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

        So you can't increase rating by beating div2 people.

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

        Certain div1 people have replied to me with "so i dont need to solve 2 more trivial problems"

        Doesnt make sense to me because it takes 5 mins but ok

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

          As far as I know, separate rounds are just the default for historical reasons. I think there is no big difference between separate and combined rounds (i.e., just those 5 minutes).

          [maybe having separate rounds instead of combined rounds also affects the rating system? I have no data about that]

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

            If this was a combined round, maybe hack and FST would not have occurred in Div1-D.

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

    Clearly,this will make it more difficult to increase the rating.(

»
7 months ago, # |
  Vote: I like it -56 Vote: I do not like it

QP

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

As we all know, cute rui_er is a kind of ruler.

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

OMG ruler round

She always come back

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

orz wyrqwq

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

rui_er!!!

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

As a tester I don't know what to comment.

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

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

     This is what I acknowledged from Algodoo marble races, so the figure above actually disobeys the rule in Algodoo.

    Purple HSL: [270, 100, 100]

    Violet HSL: [300, 100, 50]

    And, more astonishing, violet belongs to Team Pink, not Team Purple. If we change "L" of violet to 100, we will obtain magenta, which definitely belongs to Team Pink.

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

I like violet :D

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

Good luck & have fun to all participants!

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

Hope I can reach IGM lol

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

As a tester, hope you enjoy the problems!

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

as a Minecraft lover , I hope there is Minecraft in the tutorial

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

SpeedABforces

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

As a non Tester me happy ;)

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

Spent one hour just to realize that the answer for B is long long :v

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

I got AC for problem E one minute after the contest. I enjoyed the problems, thanks

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

As a participant, I will do my best and use all heuristics I know

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

I became CM in today's edu, where shall I register? div 1,2?

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

    Maybe you can register Div.2 now and take part in Div.2.

    Like changzhou, became Master but got negative delta in Div.2 :(

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

It would be cool to continue the tradition with photo of authors and coordinator:)

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

In Edu, many solutions to problem A, including mine, are hacked, because of set.

How is it possible? The time complexity is $$$O(t*n*(n-1)/2*4*log(4)) = O(5*10^7)$$$ which should not work longer, than 2 seconds.

I have solved ABCDE, and would become a master, if my solution to A wasn't hacked :(

Hopefully my solutions will not get hacked in this round.

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

Was the div2 registration intended to close this quickly? Almost 20 hours to go and "registration completed".

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

    Registration completed means u have successfully registered to participate in the contest, that doesn't mean that registration has ended for all.

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

      Oh, I don't recall clicking Register on that edition for some reason xD, must have done it before the announcement or something.

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

orz rui_er

»
7 months ago, # |
  Vote: I like it -14 Vote: I do not like it

久别无恙, Codeforces!

»
7 months ago, # |
  Vote: I like it -12 Vote: I do not like it

nutella, not LGM, testing.

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

Why did div1+2 collapse into div1,2?

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

I wish high rating to participants. Best of luck everyone.

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

GL&HF! Hope for high rating!

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

wow CN Round! Hope I can return home on time :D

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

Seeing "You" in legendary grandmaster colour felt so heartwarming even though I might never get there.

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

Wish get blue!!!!!

»
7 months ago, # |
Rev. 2   Vote: I like it -44 Vote: I do not like it

Wow,Chinese round!

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

Yet another Chinese round!

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

why this c is so difficult

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

    Going for D1 first before C might be a wise choice, because of its lower point value.

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

As a tester,I look forward to becoming Master.

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

may be in this contest I become a pupil or not. lets see!

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

Hope to get violet purple

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

just want to know what does the score distribution (1000 + 1500) mean?

two problems or something else?

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

I have participated in edu round yesterday and rating still not changed yet, If i participated in this round, my rating will change depending on my old rating?

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

    the rating will depend on updated rating of yesterday's contest.

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

Hope everyone will not get stuck in A, B and C.

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

If this round is hard I will be angry

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

As a Participants and who will enjoyed the problemset, I hope the problemset will be good :)

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

as a tester, hope you enjoy this round. This is certainly a very interesting round and I personally enjoyed it a lot, hope you guys have fun!!!!

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

My first ever Div 1!

»
7 months ago, # |
  Vote: I like it -60 Vote: I do not like it

希望可以解决一个题

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

As a problem writer who wrote rejected problem proposals, GL&HF to everyone!

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

If you like MO this much, you could try asking these on AOPS. That way, non-mathematicians can focus on coding! Leave us some problems!!!

Worst contest I have ever seen!..

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

Can someone answer this please — The rating changes of div2 participants will be made considering the performance of div2 contestants only or the performance of div1+div2 participants combined ?

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

i spent more time thinking about B2 than any of CDE.... I even had to use OEIS as a crutch for B2 (https://oeis.org/A063647 is the number of possible $$$y$$$ for each $$$x$$$) cause im too stupid at NT

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

Tfw I spend nearly two hours sitting in one place at D2. Always feeling so close, then turning out that I got nothing.

I'd appreciate a hint.

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

can anyone help me in c, i get correct submission (using binary search ) 258901211 but get 5 wrong submission by using the end value 1e12,1e14,1e15,1e18 . can anyone say the reason why only 1e13 get accepted

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

    Same mistake I did and suffered 2 WA.

    k-=(mid-arr[i]); This will overflow. Since n is 1e5 and mid>=1e15

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

    i got accepted on 2e17. (probably 1e18 is going overflow and others are not enough , dont know)

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

cool contest! how to solve E please?

»
7 months ago, # |
  Vote: I like it +13 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we binary search on C div 2?

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

    Yep, use BS to find max of min in the list after purchase.

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

    you can BS what's the new minimum element after adding k cards

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

    Probably possible, but not necessary. You can straight-up iterate one time to distribute evenly so that we have $$$x$$$ minimum elements ($$$x \le n$$$), then iterate another time if after that $$$k$$$ is still positive.

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

    Yes, but not necessary. Wasted like an hour doing it. Then looked at implementation of top guys and felt really stupid.

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

    My approach didn't even consider BS. Just get the list sorted and then bump up the minimum with your coins to equal the 2nd lowest, then the 3rd, etc.

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

      that will work for small k, but k is too large here.

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

        Large k is not an issue: my solution

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

        Too large? I was able to optimize the step of increasing the minimum to O(1) time for a total complexity of O(n). No need to worry about the magnitude of k.

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

in div.2 D2 number of pairs(n, m) {n fixed, m unbounded} is equal to this OEIS A063647 but couldnt proceed further. did someone solve it by looking at this oeis?

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

    nah it's just some basic math deductions lol, not sure if my solution will fst tho

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

How to solve B2? The max I could reduce the problem to is that any pair $$$(a, b)$$$ must satisfy $$$((a / g) + (b / g))$$$ divides $$$g$$$ where $$$g = gcd(a, b)$$$, but I still have no clue how to actually count this faster than $$$O(n \sqrt{n} \log{n})$$$.

Also B2 >>> C in my opinion, it took me ~15-20 mins to come up with the overall approach for C while I was unable to get anywhere on B2 after 1.5hrs of thinking T_T.

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

    It should be reduced to count pair $$$(a, b)$$$ such that $$$(a+b) | b^2$$$

    You just need to prove that if $$$(a + b) | b^2$$$ then $$$(a+b) | gcd(a,b) b$$$

    It's actually enough to iterate over all factors of $$$b^2$$$ that no more than $$$b+n$$$

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

      The question is about the hard version, not the easy one

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

        Yes. I'm talking about B2. :)

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

          But if $$$(a+b)|b^2$$$ then the $$$a = 4$$$, $$$b = 4$$$ from the fourth example of B2 (which is confirmed to be a valid solution) won't work: $$$(4+4)/4^2 = 8/16 = 1/2$$$, this is not a natural number. Are you really sure?

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

            You might misunderstand the notation here.

            $$$(a + b)|b^2$$$ means that $$$b^2$$$ is divisible by $$$a+b$$$.

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

    Let $$$a=gx, b=gy$$$ where $$$gcd(x,y)=1, g=gcd(a,b)$$$. $$$(x+y)$$$ divides $$$gy$$$, let $$$gy=q(x+y)$$$ or $$$qx=y(g-q)$$$, $$$y$$$ divides $$$qx \implies y$$$ divides $$$q$$$. Let $$$q=py$$$. So $$$gy=pyx+py^2 \implies g=p(x+y) \implies p$$$ divides $$$g$$$. Also note that $$$x<n/g$$$ and $$$y<m/g$$$. This allows you to check all pairs $$$(x,y)$$$ such that $$$gcd(x,y)=1$$$ and $$$x+y = g/p$$$ by iterating through all values of $$$p,g$$$. Overall time complexity is $$$\sum_{p=1}^{min(m,n)} \sum_{g=rp, 1<=r<=min(m,n)/p} \ min(m,n)/(rp) = \sum_{p=1}^{min(m,n)} min(m,n)/p = O(min(m,n)log(min(m,n)))$$$

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

    Here is how I solved B2

    Assume that $$$gcd(a,b)=g$$$ and let $$$a=gx$$$,$$$b=gy$$$ and $$$gcd(x,y)=1$$$. Since we need $$$g(x+y)$$$ to divide $$$g^2y$$$, we get that $$$(x+y)$$$ divides $$$gy$$$. So let $$$A=x+y$$$ and $$$B=y$$$. Here are few observations

    1. $$$A>B$$$

    2. $$$gcd(A,B)=1$$$

    3. $$$A$$$ divides $$$g$$$ giving $$$A\leq g$$$

    4. $$$gB \leq m$$$

    5. $$$g(A-B) \leq n$$$.

    Thus we get that $$$B\leq\sqrt{m}$$$ and $$$A\leq \sqrt{m}+\sqrt{n}$$$. So we can brute force on each $$$(A,B)$$$ pair which satisfies $$$1$$$ and $$$2$$$ and find the value of $$$g$$$ that ensures $$$3$$$,$$$4$$$ and $$$5$$$ by say precomputing multiples of every number.

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

    Maybe it is an easier way:

    let $$$s=a+b$$$, then $$$(a+b)|b \cdot \gcd(a,b)$$$ equals to $$$s| b \cdot \gcd(b,s-b)$$$, equals to $$$s | b \cdot \gcd(b,s)$$$.

    It meens that, for each prime $$$p$$$, let $$$p^{k_1}|b$$$ and let $$$p^{k_2}|s$$$, then $$$k_1 \ge k_2/2$$$.

    Calculate all prime factors of all integers, for each $$$s$$$, calculate the number of $$$b$$$.

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

I do really enjoyed this contest. Unfortunately, couldn't derive the formula for Div.2 D2 that would work with O($$$nlogn$$$) complexity

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

Out of curiosity, is there an easier approach than matrix expo to calculate the cumulative sums in Div1C?

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

    I solved it purely by observing the matrix. Took me a lot of time but managed to solve it using just prefix sums.

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

    It is actually a tree with depth less than $$$\log n$$$.

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

      Yes, but how do you count the number of times a node at depth $$$d$$$ is added to the current node?

      The recursive prefix sum value seems to be a linear equation of $$$d$$$ levels. I just gave up and used matrix expo to calculate the values in $$$O(\log^3(n) \cdot \log(k))$$$ time (the base matrix is just the lower triangular matrix, i.e, 1s for $$$col \leq row$$$).

      Then I just used these values along with the tree to calculate the answer.

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

        Simply write down on paper and notice that it is Pascal triangle.

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

        I strongly recommend you learn Generating Function! It is extremely useful!

        In this problem, let's write down a[1] a[2] a[4] a[8] as b[0] b[1] b[2] b[3] and see what happens if you do the reverse of $$$f$$$ in the problem statement. b will become b[0], b[1]-b[0], b[2]-b[1], b[3]-b[2]. And if we write down this array in the form of a generating function, it will be a transformation from $$$p=b_0 + b_1x + b_2x^2 + b_3x^3$$$ to $$$q=b_0 + (b_1-b_0)x + (b_2-b_1)x^2 + (b_3-b_2)x^3$$$, which turns out to be $$$q=p(1-x)$$$. If you do it for $$$k$$$ times, it will be $$$q=p(1-x)^k$$$. The coefficient of $$$(1-x)^k$$$ is simple.

        As you can see, generating function provides a clear and simple deduction towards the solution. Usually it is problem-agnostic, which means you can put anything involving counting (especially dynamic programming) into a generating function, and use math tools to solve it. You don't have to stare at the coefficients anymore. I got this solution using generating function withint 5 minutes.

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

    Yes, the $$$i$$$-th value is actually $$$\binom{k+i}{i}$$$. If you turn your head, you should try see a pascal triangle

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

      facepalm I observed the matrix of linear equations was the lower triangular matrix but somehow didn't realize this T_T.

      Thanks for the help!

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

        i did something even more stupid

        i knew $$$i$$$-th value is $$$[x^i] \frac{1}{(1-x)^k}$$$ then immediately went to do code that without thinking more 😹😹😹😹😹

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

      "if you turn your head" lol

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

      Too simple formula encourages guessing instead of solving, it is not cool.

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

Div2F is nice, implemented binary search part but couldn't to find minimum >= previous on x jumps in time.

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

I'm too bad at maths for this.. was so close to IM but now I'm back to low master cause I got hardstuck on NT lmao

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

:( :( :(

»
7 months ago, # |
  Vote: I like it -24 Vote: I do not like it

Mathforces.

Weak pretests. Maybe I can get positive delta with points earned by hacking.

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

can someone give me the submission of div2 C i checked my code at least 1000 times i couldn't find a mistake.

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

How to solve D1 div 2?

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

    First, you have to see that a must be a multiple of b. Then, it is a pretty straightforward (n+m)*log(n+m) implementation, where you iterate over all possible b and over all multiples of b.

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

    $$$a + b$$$ must clearly be a multiple of $$$b$$$. This is only satisfied when $$$a$$$ is a multiple of $$$b$$$.

    However if $$$a$$$ is a multiple of $$$b$$$, then $$$gcd(a, b) = b$$$, meaning $$$a + b$$$ must actually be a multiple of $$$b ^ 2$$$.

    So we have $$$a + b = k * b ^ 2$$$, or $$$a = k * b^2 - b$$$. So for each $$$b$$$, you can just count the number of multiples $$$k$$$ which generate valid values of $$$a$$$ in a total of $$$O(m \log m)$$$ or $$$O(m)$$$ time depending on implementation.

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

      can you help me understand how do we find that the time complexity is O(mlogm)?

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

    We are counting values of (a+b) which are multiples of b.gcd(a,b).

    e.g. (a+b) = k.b.gcd(a,b) (for some k values)

    dividing through b gives a/b + 1 = k.gcd(a,b)

    This means that a is divisible by b, e.g. let a = Xb, then gcd(Xb, b) = b

    Which reduces the problem to

    a+b is divible by b^2

    Iterate all b's, and look for how many b^2 fit beneath "maximum value of a" + the current b and sum them all up.

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

    You need to know two things for this.

    1) are you aware of "sieve of eratosthenes" ? What is the concept behind it ? What will be runtime complexity of it ?

    2) Reduce the formula



    => (a + b) % (b * gcd(a,b)) = 0, => (a + b) = k*(b * gcd(a , b) ) where 'k', is some random positive integer ( because => Right side is divisible by 'b' . So, left side also must be divisible by 'b'. => Left side, among (a + b) , 'b' is already divisible by 'b' ( obvious ) , so 'a' also must be divisible by 'b'. 1. Based on above, we know that 'a' is multiple of 'b'. Use two for loops, using sieve concept. complexity will be apprx O( n log n log n ) , considering modulo and division and multiplication occur in O(1).
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Why do you need SoE or something like that if ones just use the following piece of code?

      int count(int n, int m)
      {
          int k = 0;
          for (int b = 1; b <= m; ++b)
              k += (n / b + 1) / b;
      
          return k - 1;
      }
      
      
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Same problem can be solved in multiple ways. my approach and your approach are different.

        My solution is based on what I did during the contest, I never claimed, that it is most optimised approach xD.

        I reducing the formula, I reached an observation, that 'a' must be multiple of 'b'.

        Now, for all 'b', within 1 to m, I will traverse through all possible multiples of 'b'.


        for(int i = 2 ; i <= m ; i++) { for(int j = i ; j <= n ; j += n) { f ((i+j) % i . gcd(i,j) == 0) ans++;

        To understand the time complexity I gave an example of SoE.Hope I have explained how I solved the problem.

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

mathforces

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

Am I the only one using Mobius Inversion to solve Div.1 B2? I spent almost an hour and couldn't find simpler solution. Also C<<B2

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

    Yeah being stuck in D2 made me lost rk1(Div 2). I spent almost an hour in it :(

    Actually when you found that $$$x+y | g (xg=a, yg=b, g=(a,b))$$$, you will realize that $$$(x+y)g \le n+m$$$ and $$$x+y \le g$$$ which means that $$$x+y \le \sqrt{n+m}$$$, so you can brute force every possible (x,y) and solve the number of g in about $$$O(n+m)$$$.

    BTW how to solve by Mobius Inversion I dont know lol

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

These are some good problems 💪💪🔥🔥

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

https://mirror.codeforces.com/contest/1972/submission/258921511

Can anyone pls tell what is wrong in this code for C?

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

    use long long instend of int

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

    New Submission

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

    I think in the final output k should be min(k, remaining).

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

B2 is restarted

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

My pre-contest predictions:

  • Math
  • Data structure
  • Implementation

Seems that all my predictions are correct!!

"Thanks" for such a round to let Chinese Rounds become stereotyped!!!

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

    Exactly.

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

    TheScrasse meanwhile I want too hear your voice about these Chinese style problems. I am wondering if these math problems are interesting for you, and the round is balanced with these problems.

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

      My take:

      • The only data structure problem here is 1967F - Next and Prev.
      • All the problems up to 1967C - Fenwick Tree have almost no implementation.
      • Yes, there is a lot of maths. But I prefer an unbalanced contest rather than a contest with bad problems.
      • In this contest, $$$26$$$ problems were proposed, and I didn't just accept a random subset of $$$8$$$ problems.
      • Most testers confirmed that problems looked good. Are there so many people who don't like this round?
      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it -33 Vote: I do not like it
        • Almost every Chinese round has a hard data structure problem(except ours).
        • I agree 1A~1C have almost no implementation. Those parts are enjoyable.
        • For math problems, what i dont like is handling these abstract numbers(some visualizable operations are more exciting) and processing very carefully with the corner cases.
        • Feedbacks are from Chinese\cup LGM. Is that really useful for most Codeforces users?

        edit: how can I forget the FST of problem D? Pretests seems to have n=m.

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

          About the last point: feedback is from the testers, which cover a wide range of ratings. In this case there was no big complaint from any tester. Maybe the testers overestimate the beauty of the problems?

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

          FST on D is just me being blind, seeing $$$5$$$ generators (with two of them which weigh 7 KB) and missing $$$n = m$$$. This is the second time I miss this detail, I hope the third time does not happen :(

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

    Always math :)

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

    Is stereotyping always harmful?

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

How to solve D2 (div. 2)? I've figured that x * y / (x + y) = n means (x — n)(y — n) = n ^ 2 and was trying to iterate through n, looking at all its divisors, getting divisors of n ^ 2 from it and trying to form all valid (x, y) pairs from it. But since n can get pretty large, O(max N * sqrt(max N)) takes too long.

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

    $$$a+b | b\cdot (a,b) \rightarrow g(x+y) | g^2y\space \space(let g = (a,b) ,x = a/g , y = b/g) \rightarrow (x+y)|gy \rightarrow (x+y)|g \space \space((x+y,y)=(x,y)=1)$$$

    When you found that $$$x+y | g (xg=a, yg=b, g=(a,b))$$$, you will realize that $$$(x+y)g \le n+m$$$ and $$$x+y \le g$$$ which means that $$$x+y \le \sqrt{n+m}$$$, so you can brute force every possible (x,y) and solve the number of g.

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

please find the mistake in this. Div2 C 258921994

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

Thanks for this contest, I really liked problem $$$C$$$!

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

If you submit the code casually, you even have a good chance of passing problem B and D1.

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

A question to anyone who solved div1C: does $$$\mathcal O(n\log^2 n)$$$ solution with the restoration of the value from indexes with a lower lowbit value to indexes with bigger lowbit values work?

UPD: the question is no longer relevant.

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

is my implementation wrong or does binary searching on number of perms not work?

my logic was that if you wanted X perms than array should be [X/n, X/n, ..., X/n+1, X/n+1] with X % n of them being X/n+1.

for some reason i get WA on pretest 2 so now i sad :(

258903132 258901827

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

    oh wait its probably cuz X=0 makes my code not work... oopsie :3

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

      nevermind... i think it is still wrong

      could somebody pls help me?

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

Does my solution Can be hacked ? 258885731

»
7 months ago, # |
  Vote: I like it -37 Vote: I do not like it

Thank rui_er for giving a so easy CN Round.

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

Div. 2 B and C were literal guessforces. I spent an hour trying to find a solution to B, even wrote a brute force, then I viewed the samples and be like "Hmmmm... It's almost as if the U count is odd then Alice wins else Bob". And pretests passed... Whatever. Probably I'm just too retarded and it's actually very easy to prove.

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

    Yeah whenever you remove a coin, you always remove a U coin.

    There are three neighbour cases

    1. neighbours are both D, then U => U + 2
    2. Neighbours are both U, in which case U => U — 2
    3. One is U, one, is D, in which case U does not change.

    In all three, the parity of U does not change, so the only relevant fact is the parity of U.

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

      The problem statement says we should also remove the selected U. So it actually always changes to the opposite parity.

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

        My comment was perhaps not super clear. I refer to the parity staying invariant after you remove the first U coin, i.e. the neighbour transforms don't change parity, only the initial coin removal does

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

    i have gone mad after realizing the solution for B after spending an entire hour.

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

    The brute force also passes 258885731

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

how have so many people in Div2 solved D2?

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

what is the optimal rearrangement of the the 6th test in Div2 C test samples ?

I tried a lot during the contest to figure out what is the best rearrangement but I couldn't find it :(

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

    If you meant this testcase:

    9 7
    7 6 1 7 6 2 4 3 3
    

    Then it's as of following:

    • Add $$$a_3$$$ by $$$3$$$.
    • Add $$$a_6$$$ by $$$2$$$.
    • Add $$$a_8$$$ by $$$1$$$.
    • Add $$$a_9$$$ by $$$1$$$.

    Then we get:

    7 6 4 7 6 4 4 4 4
    

    Now, one possible arrangement might be:

    1 4 2 5 3 6 7 8 9 1 4 2 5 3 6 7 8 9 1 4 2 5 3 6 7 8 9 1 4 2 5 3 6 7 8 9 1 4 2 5 1 4 2 5 1 4
    

    ($$$46$$$ elements in total, valid subarrays are $$$[1, 9], [2, 10], \dots, [32, 40]$$$)

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

I hope there will be a plagiarism check for this Round, since apparently the solutions to Div 2 A, B, C and D1 were leaked hardly an hour into the contest.

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

    a, b, c were all brute force that even 800's can solve. I dont think it is necessary to check plagiarism for them

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

      Nope, never. Regardless of the difficulty of the question, plagiarism is a serious issue.

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

I can't call myself a mathematician anymore :(

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

Thanks for Interesting problem and positive delta~~

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

Anyone knowing in how much time aproximative the ratings will be out??

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

Why A is failing on systest?

»
7 months ago, # |
  Vote: I like it -19 Vote: I do not like it

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

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

CNOI Round 🤓👎

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

In div2 on D2 we have 588 accepted solutions. In div1 on B2(same task) we have 582 accepted solutions.

funny :)

»
7 months ago, # |
  Vote: I like it -9 Vote: I do not like it

why D1 is so easy may be some other problem can be placed at D and D2 can be a different problem

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

There seemed to be a weak pretest in C? 4000AC->3600? And I seemed to fly about 100 rank:)

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

    Yeah, also jumped a bunch of places up. But then again, you're responsible for verifying your solution even if you managed to pass the pretests.

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

    Yup. I made the upper bound on answer smaller than it actually is, giving WA on test 9. Tbh sucks going from +30 to -100 delta.

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

      How do you know your delta? C-F predictor does not seem to be showing correct values anymore

»
7 months ago, # |
  Vote: I like it -24 Vote: I do not like it

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

lol, i spent like 40 min trying to solve B, because i didn't double check examples , and i didn't read n coins on the table forming a circle

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

Could you please give me testcase of problem C div 2. I got WA but I don't know why.

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

was it rated?

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

day by day div 2 is getting harder for me :)

»
7 months ago, # |
Rev. 2   Vote: I like it +3 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

»
7 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Finally a div.1 standing with tourist rk1 and jiangly rk2! BTW, congrats to Kevin!

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

amazing problems! However math problems are a little more than I expected,which I'm not good at.

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

Why more and more gcds?They are not interesting!!!!!!!!!

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

please provide an update on when the rating will be updated?

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

I found myself waking up six times throughout the night, hoping to see my new 'Max Rating,' yet it remains unchanged even now!

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

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

Is it rated?

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

Is there any issue/delay in updating rating of this round?

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

Did anyone try to prove the solution div2 B? I think we get the pattern pretty quickly, but proving it is not intuitive. How do we prove that with induction?

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +5 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.

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

      got it thankyou.

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

      I couldn't prove it too ,just discovered the pattern through test case,but couldn't understand the gist of the problem.

      Can you tell me who will win for this case"UDU" ?

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

Was this contest unrated?

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

Over a day and wasn't rate. Why??

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

And finally, it's rated!

Spoiler
»
7 months ago, # |
  Vote: I like it +20 Vote: I do not like it

tourist is back on top againnn

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

in this contest there again those (before some of them i already mention in previous contest where they failed the system test for a problem)tried to change there code and may happen that they might be undetected so posting this (majorly they tried avoiding a bit by looking at the format of i(i+j) and just trying to be smart let them be declared as a variable instead of using directly and all the necessary loops needed in submissions of D2 div2: 258918241 258918681 258918681 258917636 258918237 258917628 258918431 258917198 258917154 Vladosiya MikeMirzayanov

»
7 months ago, # |
  Vote: I like it -10 Vote: I do not like it

《久别无恙》

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

nazmulaas2023 is my second id....on this contest..by mistake of mine i submitted my code into nazmulaas2023...that's why my code of nazmulnns2066 and nazmulaas2023 is same...unitentionally i did this...please consider..i apologise for this mistake

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

i made a mistake during the contest..i submitted C in my wrong id which is nazmulaas2023..when i realize this...i change some of the code and then submitted in my id nazmulnns2066 which i did the contest..that's my code look similar.. i apologise for my mistake..

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

sorry MikeMirzayanov, but the system declare that my 1972C submission is similar to huanjua. My explaination is we are both students come from Ho Chi Minh City and in 2015-2016 entrance exam in VNU.HCM for grade 9 there is a problem using the same binary search idea and we use the same idea. Please give me back my rating. Thanks