P.V.Sekhar's blog

Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
By P.V.Sekhar, history, 3 weeks ago, In English

Hello Codeforces!

We are thrilled to invite you to participate in Codeforces Round 976 (Div. 2) and Divide By Zero 9.0, hosted as Divide By Zero 9.0 by The Programming Club, Indian Institute of Technology Indore (IIT Indore). The contest will take place on Sep/29/2024 18:35 (Moscow time).

UPD: The contest time has been updated to Sep/29/2024 18:35 (Moscow time), which differs from the previously announced schedule. Please take note of this unusual timing and adjust your plans accordingly.

You will have 2 hours to solve 6 exciting problems.

The round will be rated for participants with a rating below 2100.

Problem Setters:

The problems for this round have been authored by nishkarsh and me.

Acknowledgements:

We would like to extend our heartfelt thanks to:

Score Distribution (Div. 2):

  • 500 — 750 — 1250 — 1500 — 2000 — 2750

We hope you enjoy the problem set and have a great time solving!

Good luck to all participants!

Update: The editorial is here

  • Vote: I like it
  • -315
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to solve till C in this and get close to specialist

→ Reply
»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

very nice score distribution, looking forward to the contest

→ Reply
»
3 weeks ago, # |
  Vote: I like it +62 Vote: I do not like it

As a tester, I forgot when I tested this 💀

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

Big thanks to the problem setters nishkarsh and P.V.Sekhar

→ Reply
»
3 weeks ago, # |
  Vote: I like it +58 Vote: I do not like it

clashes with AtCoder

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

    For most div 2 participant, AGC isnt even rated, so that works out.

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

    Thank you for the notice. Somehow I though the AtCoder round is the usual 2h long. We've moved the round to avoid the clash.

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

Why did the Contest begin 1 hour early?

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

fire

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

Almost lost hope. Will try to be pupil in this one.

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

    wishing luck

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

    Some people like me might say that Codeforces isn’t for you. But don’t lose hope—keep pushing forward and keep grinding.

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

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

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

I thought Divide "By Zero 9.0" is a competition. but, it turn out to be a IIT Indore programming club. Excited to take participant in a contest presented by indian programmers.

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

Hope to solve till E in this round and get to Master.

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

    E might be easy since it's score is just 2000, we have to aim for AK (or if F is too hard then speed will matter). Good Luck!

    UPD : Well you are too close. Solving till E will probably suffice (rather we should talk about rank, so top 200).

    UPD 2 : My predictions actually worked, but this is still generally not correct.

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

      Stop confusing score distribution with problem rating. Not sure why this is becoming a common misunderstanding as of recently. The last contest's blog had 3 comments trying to compare div. 2 and div. 1 score distributions as if they are problem ratings.

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

        HaccerKat orz

        → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        If you compare div2 contest's E problems, they usually have score >=2500. Last contest, E had score 2000, and you can see how many people solved it.

        And I did not referred it to problem difficulty (at least not directly). Meanwhile, it's true that, more the score, more the difficulty (according to the setter).

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

          I would like to bring out this blog for reference. Scores are not supposed to be compared between different contests, but instead only within a contest. I brought up problem rating because that is the metric combined with speed + penalty that strongly determines a contest performance. There is likely some correlation between rating and score, but from what I have seen it is weak enough to make predictions unreliable. This is especially true for div. 1 or combined rounds.

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

            If we can't compare scores from different contests, then I agree with you. Thanks for clearing my misconceptions.

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

As a participant i wish i will reach Specialist

→ Reply
»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

As a participant i wish i will reach Expert

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

Seeing score distribution seems the problem set will be easy. Good luck everyone.

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

    Score distribution only says how difficult are the problems relative to each other, not how difficult they are relative to other problems on the platform, so you can't really make a prediction like this.

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

Why are contests recently

→ Reply
»
3 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

well I guess this one's timing balanced out last one's

→ Reply
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope to get a positive delta in this contest!

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

How many problem exist regarding binary strings?

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

    id say binary strings arent too rare, if youre interested in the topic i can link you some problems with them i solved

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

I'm really excited to move up the ladder this time. Thanks to your efforts for this contest!

→ Reply
»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

hype hype

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

I really want to participate in this race, but this race time will make me sleep an hour later, and I can't accept it

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

    Maybe you can take a nap from 22:00 to 23:00 (UTC+8)

    You are Chinese so I used UTC+8

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

nishkarsh sir orz

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

hope full solve to get im xd

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

IIT 's never disappoint.

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

nishkarsh orz

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

As a participant I wish to reach pupil!

→ Reply
»
3 weeks ago, # |
  Vote: I like it +47 Vote: I do not like it

No t-shits ;_;

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

Hope everyone except me reach newbie in the contest!

And I reach Tourist in this contest!

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

Why the time of recent rounds are so strange?

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

Technoblade never dies

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

Hope to have enjoying participation

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

mathforces

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

Indians as always are making the worst possible contest.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

maybe you meant to write div 3 in the announcement?

→ Reply
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

nice div2

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

Damn this contest humbled me

→ Reply
»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

baler problem diche

→ Reply
»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Perhaps E should be swapped with D? I think it’s a little bit classic.

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

    Yeah I was a bit surprised a straightforward DP works (at least passed pretest). Thought it may need some optimizations.

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

I think it nice math contest, I enjoyed the proving and solving.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

shit contest.

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

indians == mathforces .

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

Great contest. Is it only me that felt C is is easier than B ?

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

    C, D, E < B for me during contest lol

    B took ~25 mins to solve while C, D and E took 20, 10 and 20 respectively.

    Spoiler
    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    since i knew that every perfect square is having odd divisors, i could do B easily, but C took me much of time for implementation and trying to figure out all cases

    also i have seen the exact B question but only difference is the question had asked to find how many bulbs would be off at end

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    C is not easy to prove. B is pretty obvious.

    → Reply
»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

I hate this problem set :)

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

what's the reason of making TL of D 2s?

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

how to solve F?

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

jeez louise D was tricky to code

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

Speedforces :)

I really feel like there really should have been a problem between E (750+ solves) and F (~20 solves).

E just require you to realize one fact which is fairly standard ($$$x \oplus x = 0$$$) and then code knapsack while F seems to require far more thinking.

So if you have a slow start of contest you have practically no ability to recover since D and E are far more code heavy than thinking heavy.

(disclaimer: This might just be salt due to having a serious skill issue on B)

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

    You don't need to know $$$(x \oplus x = 0)$$$ for E to code the knapsack? You just need to know xor of two numbers $$$< 2^i$$$ is $$$< 2^i$$$. Also, E isn't code heavy at all.

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

      Oh yeah, I'm dumb, I complicated the implementation in an attempt to "improve" the complexity.

      → Reply
»
3 weeks ago, # |
  Vote: I like it +150 Vote: I do not like it

I am sorry, but I think this was one of the lowest quality div2s in recent times. I'll elaborate:

A: not like standards for div2A are very high, but this is just very lazy.. and probably repeated for 1e9+7-th time

B: this is just knowledge-check (or google skills check) problem, with very classic and repeated setup

C: this is actually on border of being okay, but still nothing new, and there are like 1e9+7 very similar problems with same idea (just restore answer bit-by-bit)

D: this is also somewhat okay, though not very interesting

E: just way too classic, compilation of two well-known ideas: look at the xor bit-by bit, and expanding brackets in f^2 + apply linearity of expected value to consider each summand separately, with nothing else.

F: if problem asked just to find f(n^k, d) i think it would be pretty nice, but easy, like 1800* at most. and transition from this version to prefix-sum is just straight-up application of algorithm which is way too hard for div2 level (prefix sum of multiplicative function). very weird problem.

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

    Is B actually binary search? Had to code a quick program to show me the pattern there.

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

      i did with binary search, but i think it can also be solved like quadratic equation and little bruteforce (though im not sure). core idea is that there are $$$n - \lfloor \sqrt{n} \rfloor$$$ lamps that will be still on

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

        I hopelessly submitted the one to bruteforce on x, given that (a+1)^2 — a^2 = 2a + 1 so in total there are 2a ones inbetween zeroes. Shit.

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

      Basically all the bulbs which are perfect square, would be switch off in the end, so basically there are n - sqrt(n) numbers that would be switched on. So for smallest n you have to perform binary search with the condition that n - sqrt(n) should be >=k

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

      very bad at casework and implementing but basically if n+sqrt(n)< (the smallest perfect square larger than n) it is n+sqrt(n), otherwise n+sqrt(n)+1

      took half an hour to implement

      i am bad at this

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

      After reading the problem I knew I had to do binary search but I was missing points resulting in 5 wrong answers

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

    how to solve D? is it related to gcd?

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

      Notice that $$$d_i \le 10$$$.

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

        i mean i did, so there are 10 unique modulos, but i just couldnt figure out how to merge and stuff, and i got really confused

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

          (Assuming you fixed your numbers into range $$$[0, n-1]$$$ instead of $$$[1, n]$$$).

          Basically, you can group all triplets with the same $$$(a_i \mod d_i, d_i)$$$ tuple, and start treating all elements in the form of $$$a_i \mod d_i + k \cdot d_i$$$ as a line. Merge that line using prefix sums and a little bit nitpicks.

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

            I feel my solution for problem D is slightly easier to implement: for each $$$d$$$, maintain a union-find for the furthest index we can jump(processed by previous operations), and jump when possible 283622874

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

              Oh yeah, true there. I was a bit overdoing myself with the prefixes.

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

      for each point $$$i$$$ you have to check is there and edge between $$$i$$$ and $$$j$$$ such that
      $$$max(1, i - 10) <= j < i$$$

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

    I agree, I felt I knew close to the full solution as soon as I opened each of the problems for A-E.

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

    Fyi E has an even simpler (and more braindead implementation) approach than yours.

    1. Just realize $$$x \oplus x = 0$$$, so the value $$$x$$$ only contributes if it occurs an odd number of times.

    2. Knapsack to find these "odd" probabilities in $$$O(n)$$$.

    3. $$$a_i \leq 1024$$$, so just do Knapsack to find the probability of each $$$f(S)$$$ (worst case $$$~2 \cdot 10^7 ops$$$).

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

      oh true, I overlooked it (the instinct to expand the brackets in the expectation of square is too strong), thanks

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

    For E you can also dp for the probability of each resulting xor value and just calculate directly.

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

    I agree completely, also something to note on E : it is even more classic than you put it as, because you can just code the trivial n * 1024 dp which comfortably passes without optimizations.

    I am sad that this is the impression indian rounds leave for people....

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

How should I solve problem b. What Skills do I need to learn to do it?

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

    binary search

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

      how can we check the number of bits set at some n for that large value of k?

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

    I just wrote a bruteforcer, it is a stupid problem.

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

    it's binary search, notice that only perfect squares are turned off in a range.

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

      Thank you so much. I was over thinking about primes :(

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

        I did also at first, but after noticing each index is affected by the number of its divisors, the solution became straightforward.

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

Why was dsu giving tle, on test case 7 in D, is there any way to speed up this? and avoid using DSUs?

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

    If you naively used a DSU, you would have to merge at worst O(n) elements for one operation. Since you have m Operations, you can have up to O(n*m) Merges, which is way too slow.

    There are a lot of approaches to solve the problem, but the main observation is that $$$d_i \leq 10$$$. Based off that you could store for each element the last element to update and the merges that you would still need with a specific value of d. Thus, you only need to store how long the updates have to go back for each d, which means that for all elements, you have at most 10 merges backwards. For a merge just use the dsu to merge with the other element and update the amount of updates for the prior element if neccessary.

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

      cool, thank you!. Would try to upsolve this question.

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

    To speed up you can use 10 dsu (for each d).283663343

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

solution for this contest

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

hell B was such a pain problem man it gave me existential crisis.

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

https://oeis.org/search?q=2%2C3%2C5%2C6%2C7%2C8%2C10%2C11&language=english&go=Search

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

    To be honest, this is not a big deal since the observation was easy enough to make anyway. And if you didn't make it, you could just write a brute force to print the numbers that don't have an even number of divisors and you would realize instantly that they are the square numbers.

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

How to solve B ? I tried binary search the n, such that n — sqrt(n) is greater than k, but failed in pretest 8.

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

    I got WA on pretest 8 twice. Then I replaced sqrt by sqrtl and got AC

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

    should be like this

    mid — n>=mid/(mid-n) + (mid%(mid-n)==0?0:1)

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

    Try binary search to find sqrt(n) otherwise after getting n through binary search as you have done manually check by incrementing n when is n-sqrt(n)>=k

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

    $$$sqrt(n)$$$ is not accurate enough for $$$10^{18}$$$, you will pass pretests (and hopefully systests) if you use $$$sqrtl(n)$$$.

    The safest approach is to binary search on the value of $$$y = \lfloor \sqrt{x} \rfloor$$$ as $$$y \cdot y \leq x$$$. I was too lazy to do that in contest, lets see if the risk pays off :).

    Submission: 283590674

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

bruh this can't be C solution, I kept thinking for 30 minutes because I thought it can't be that easy. and this B solution wasn't proven for me, but looked correct.. for the output it would be a combination of 0+2+0+4+0+6+0+8 right? I tried to divide (n+1) by 2 and then it would be the closest result for the rule of (x*(x+1))/2 but got WA on pretest 3

→ Reply
»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

never cook again

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

Just Another Math/Speed forces

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

Help problem A TLE on pretest 1 although runs instantaneously locally: 283575473

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    while(n >= k){
    ans++;
    n = operate(n, k);
}
ans += n;
    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks got it. Although it should still pass pretest 1 right ? Or am I wrong in thinking pretest 1 == samples ? Got so baffled by tle that didn't even think anything else.

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

    Possibly you missed the case when k==1, and directly output n, as there might be issues with division with 0 which would give TLE/Runtime Error. Also its kind of like writing n in the base k, and finding the set bits of it

    → Reply
»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

WTF was this E

→ Reply
»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

my B one line solution

int x = sqrtl(n + sqrtl(n));
cout << x + n << endl;
→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone discuss B and C approach.

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

    for C, iterate over bits and check if its possible to make the difference of the 2 bits of the first expression equal to the second expression. there are a few cases, and theyre pretty simple to figure out. for B, binary search, and also try to find out for a certain range how many bulbs will be turned on

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

      I just tried c^d and b^d otherwise solution doesn't exist. It was a throw but passed the prestests

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

can someone help me in figuring out why this ac's? I stress tested and added the line else if(inB && inC) a |= (1ll << j); and if(ans != -1 && ((ans | b) - (ans & c) != d)) ans = -1; and someone got ac

link

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

Should have just headed straight to oeis when seeing problem B. Just a find-a-formula problem which only involves keep guessing it until it is right...

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

    Well for what it's worth, I did solve it without guesswork. Bulb $$$x$$$ is on if it's flipped even number of times. Every factor of $$$x$$$ flips it. So "good" bulbs are those with even number of factors.

    Represent $$$x$$$ as its prime factorization, $$$p_1^{n_1}\cdot p_2^{n_2} \cdots p_m^{n_m}$$$. Number of factors of $$$x$$$ is $$$(n_1 + 1) \cdot (n_2 + 1) \cdots (n_m + 1)$$$ (we have $$$n_i + 1$$$ choices for which power of $$$p_i$$$ to include in each factor)

    It's easier to find bad bulbs — they have odd number of factors, so $$$n_i + 1$$$ must be odd $$$\forall i \in [1, m]$$$. So $$$n_i$$$ must be even $$$\forall i \in [1, m]$$$. Which is a roundabout way of defining a square number. So bulbs with square indices are bad.

    I agree that it's guessable, but also liked arriving at the solution, which probably will cost me some rating. Anyway, I'm sure someone with better maths can solve it much faster.

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

    Generate more samples either by hand or with brute force program and find pattern, that's how I did this problem and that's how I solve most of problems that are not obvious.

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

      Yeah this is exactly what I did too and I am quite sure if I did input it in oeis, it would be a much faster solve (Extra important in a contest situation)

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

I tried to solve E first and got Time limit Exceeded by using O(N * 1024). After that, I optimize a lot and when the contest finished, I read other's solution, I see that they just add ios_base::sync_with_stdio(false) :(

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

3 contests se downfall ho raha hai :(

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

Am I mistaken or do the authors actually allow a $$$O(N \times 1024)$$$ solution for problem E?

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

Man, these problems are just so bad.

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

only if in C had something to do with carry also ;(

an initial impression made me think of the case (0,1,1) and (1,0,0) (bits of b,c,d resp.) had something to do with carrying a bit over, had this covered in code and when stress tested it found that this is not the case T_T

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

it is too hard,harder than all div 2 I have participate in. perhaps I am not qualified to these div2s

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

Poor contest, people had WA's in C before the announcement was made.

the limit of a<=2^61 wasn't specified earlier, i think, the wa's before announcement should be compensated.

eg.- a python user might not face the problem of overflow, for which the constraint was made.

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

why doesn't this work for B : https://mirror.codeforces.com/contest/2020/submission/283599697

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

came with the idea for C but cant implement it properly any hints??

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

    each bit is independent in this equation

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

    a=b^d

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

      what's the proof?

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

        1) We can solve for each bit independently. 2) Let's analyze all possible cases for some fixed bit position i: 1. If b's i-th bit is equal to d's i-th bit, we may not set a's i-th bit, it will not make our answer worse. 2. If b's i-th bit is 1 and d's i-th bit is 0, (a&c)'s i-th bit must be set, therefore a's i-th bit must also be set. 3. If b's i-th bit is 0 and d's i-th bit is 1, we have to set a's i-th bit to set (a|b)'s i-th bit. By using this analysis, we can claim that if there exists some a, for which (a|b)-(a&c) = d holds, then a = b^d will also be an answer.

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

Mathforces is crazy

→ Reply
»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Literally the worst B i have ever seen

→ Reply
»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

I thought this was a nice contest with very nicely written problems. Thanks!

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

    So do i, man. It really encourages me to learn more about number theory.

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

For C I've just checked if c^d could be the answer. But it's hard for me to prove it.

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

my worst contest i am pretty bad at maths

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

Did I the only one to solve C by using Digit Dp ?

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

    I solved E using digit dp 😔 we should think more before start programming.

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

And this is exactly why i skip indian and chinese rounds. Questions are so unoriginal invloving mostly math and pattern recognition.

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

I knew that solving n-sqrt(n)=k for n will give me the right answer. I solved it too using basic quadratic math + flooring at the end, and it was actually giving me the correct answer but I don't know why it is failing the pretests. Can someone please tell me why????

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

    maybe u missed the ones when ur answer was a perfect square, the code i made gave me answers like 36, but the real answer was 35 since 35 is smaller and the problem asked the smallest answer.

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

      So basically I should've just checked till what range ans-i is possible. CP can be so cruel!!

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

very strong samples lol

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

Lol, B was binary search? I solved it without binary search: 283591395

→ Reply
»
3 weeks ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

Unlike other more complicated solutions, my approach to the C problem is simple:

def solve():
    b, c, d = map(int, input().split())
    a = (b | d) - (c & d)
    print(a if (b | a) - (c & a) == d else -1)

t = int(input())
for _ in range(t): solve()
→ Reply
»
3 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Multitest on F. Just why?

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

For problem B: Safe way to calculate sqrtl(num) ?

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

I hate the fact that B solution is just about old Ted-Ed riddle: https://www.youtube.com/watch?v=c18GjbnZXMw

→ Reply
»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

i think e is easier than c :(

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

    isn't that expected value problem ? any good source for expected value problem or learning way too ?

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

      Errichto's blogs and videos.

      Sums and Expected Value series

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

        will try vai.. but my main problem is, after so many try, I'm still noob in DP. still trying tho :(

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

          I'm not sure there's a trick. What I do is read the tutorial and try to solve it after the contest if there's any problem that I thought could be solved but actually wasn't.

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

I don't know why my div2A solution wrong 283639751? Can you guys give me some anti testcase please?

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

    Check out my solution.

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

i have no idea what the hell happened but I couldn't even solve problem A in this contest even after knowing the logic within literally 30 seconds of reading the problem, it's the most simple form of a greedy problem. i think i should have just moved on to B instead of trying to fix problem A the whole 2 hours, it was dumb on my part :(

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

    I saw it as writing n in base k. If k = 1, answer is just n.

            int ops = 0;
 
        while(n > 0){
            ops += n % k;
            n /= k;
        }
    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      this solution looks absolutely wild, great work. i also realized the k=1 edge case after i kept getting memory overflow errors

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

The fact that I realised about even and odd factors of a number have impact on turning on a bulb but still couldn't realise about perfect squares hurts me more.

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

    I asked ChatGPT: "What natural numbers have odd number of factors?" And It answered perfect squares and then problem is solved :)

    I didn't participate in this contest but if I had, would that consider cheating?

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

      I mean many people go to some kind of websites to find patterns. So it's ok. But I only search for syntax and func in cpp documentation or implementation of some ds.

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

need div 3 or div 4 to recover from the damage this contest has done to me

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

All the authors / testers have too much IQ, so missed what the average caveman would do for problem E.

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

For C question instead of doing for 62 bits seperately u can do this

int x=b^c,y=c^d;

int a=x|y;

if(a|b — a&c ==d) cout<<a<<'\n'; else cout<<-1<<'\n';

→ Reply
»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Love this contest, got WA because I used sqrt() instead of sqrtl() in B, and WA in C because I shifted (1 << i) instead of (1LL << i).

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

Thanks

→ Reply
»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem E

My Submission on compiler c++17 TLE but on c++23 1468 ms and I am add this problem to mashup the my solution took time 6749ms on c++17

TLE 283653307 AC 283661649 Please adjust the time limits for this problem and rejudge it

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it 
   int ans=0;
    while (n > 0)
    {
        int ank = 1;

        int l = floor(log(n) / log(k));
        int j = pow(k, l);
        n -= j;
        ans++;
    }
    cout << ans << "\n";
}

whats wrong with my code ? 283581784 I think there's a precision error in the log division . I'm not sure, though. and also is there a way to solve it using log or we have option to use only while loop to compute ?

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

DSrinath MikeMirzayanov

I found this account suspicious regarding the use of AI or cheating. The codes submitted are significantly larger, and there is a noticeable difference in variable naming and coding style compared to previous submissions.

In today’s contest:

We can see he used a.begin(), a.end(), whereas in previous submissions he used all(). He used vector<int> this time, whereas he previously used vi. Additionally, he opted for for(...) instead of fr() as he had done before.

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

P.V.Sekhar i would like to draw your attention towards an issue with the Problem B: [problem:https://mirror.codeforces.com/contest/2020/problem/B], i found a user with an accepted solution: [submission:https://mirror.codeforces.com/contest/2020/submission/283584670], and when i am trying to submit this solution again, i am getting wa on 8th test!! WOW! now codeforces is based on luck??

Please look into this. My submission link: [submission:https://mirror.codeforces.com/contest/2020/submission/283668692]

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

Same code different results (╥﹏╥)

C++17: 283654614

C++20: 283666208

P.V.Sekhar nishkarsh

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

For problem B I have submitted the same code twice. -One in C++17 (GCC 7-32) (submission link: https://mirror.codeforces.com/contest/2020/submission/283669977) -Another in C++20 (GCC 13-64) (submission link: https://mirror.codeforces.com/contest/2020/submission/283669075). For te first one I got accepted but got wrong ans for the second one. why??

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

    Because in 20 C++ sqrt returns double. And at 17 — long double This type is bigger. To do this, 20 C++ has sqrtl

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

My submission for problem B failed in Java on test case 8, idk what went wrong! It matches the approach in the editorial.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I've got a technical issue.

Is it normal if a submission (https://mirror.codeforces.com/contest/2020/submission/283590461) still has the status "Preliminary tests passed", even if the system testing is completed?

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

for question d why is disjoint set giving tle for me

→ Reply
»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

D is an easier version of the problem from Polish OI: https://szkopul.edu.pl/problemset/problem/oNnWY6ZuzzhvG-jCmijiXkIk/site/?key=statement

→ Reply
»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

I think E is too easy for Div2.

There is only one simple DP algorithm for this problem.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

What's the meaning of using Min_25 sieve instead of euler sieve? Does this mean that the usage of technology is the most important thing for a good problem? I can't understand why this problem appears on a CodeForces Round.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

I'm gonna leave a bit of feedback here.

Overall it felt like the problemset requires too little observation and most of the part was about knowing a few well-known mathematical facts (except for problem D). The reason why many people felt that it's too math-heavy is because the problems were very friendly to math people who studied very little about problems in computer science, but has great knowledge in the math theory itself. Apparently, it is likely that you'll see these problems in math classes:

  • A: It's only about knowing how to represent a decimal number in base $$$k$$$.
  • B: The core of the problem was to know that only perfect squares have odd number of divisors, which is quite a well-known fact. The rest was just about finding a non-error-prone way to implement it.
  • C: Constructing the truth table was enough.
  • E: Because the authors did not know that a $$$1024n$$$ solution existed, it became a very typical DP problem. This solution is quite trivial and involves very little math. However, reading the editorial, the intended solution is quite math-heavy — it was about knowing that linearity of expectation applies here and so that we can calculate each resulting bit independently.
  • F: I couldn't solve this, but watching other people discussing, it looks like a very typical but difficult math topic with a specific way to achieve acceptable time complexity. I heard that using a well-made template reduces the actual solution into like 5 lines.

The statements were short and clear, but it was because that these problems can indeed be expressed as just one-line math equation. I'd love to see problems that require a bit more interesting observations next time.

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

https://mirror.codeforces.com/contest/2020/submission/283654441

Can someone please help why this is failing?

→ Reply
»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

SHITY CONTEST

→ Reply
»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

I don't know how can I use min25 to pass F, because of T<=10000.

I can construct a test that T=10000, n=100000 at all, in this case my solution can't pass because 10000*100000^0.75 is too large and my constant is a little big.

You can see my submission here 283699912.

I don't think T<=10000 is an appropriate constraint.

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

i hate this E. thought it would never run O(2e8) in 4 seconds.

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

In B question ,first I was submitting on C++ 20 compiler it was giving wrong answer on test case 8. Which after contest same code I submitted on C++ 17 compiler it worked. Anyone please explain.Also yesterday got -47 due to this issue

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

I just got TLE on prob E 9 times, today I resubmit my first code and got AC??

→ Reply
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Is the Frequency of Contests on this site very low? I don't see any scheduled contests.

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

Well...it looks like we're continuing to go down

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

i'm so bad:((

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

Why did blog get so many downvotes? First time I'm seeing a contest blog with these many downvotes tbh. In fact first time seeing a contest blog with downvotes in general

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

    probably since the contest wasn't very high quality. The only good problem was D

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

      I think there is no special in D(though it is tagged bruteforce)

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

The problem C was easier if done by simple bitwise operations. I tried this. ll ans=b^d; if(((ans|b)-(ans&c))==d) cout<<ans; else cout<<-1;

I think that this was much easier than the solution in the editorial. :P

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

I liked your intention of using "Number Theory" concepts in problems(esp. in F). But, as I have seen, the problems with the blend of concepts in mathematics and critical logical solving are in previous Codeforces Div. 2 (which I participated in).

I support you to continue setting some interesting problems in the future despite the downvotes count.

Fun Fact: I have a -70 delta in this contest, though I got the idea for B in 2-3 min. and C in 15-20 min. which was affected due to my inefficient coding at that time. I love Number Theory ;)

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

Also, I notified that there are similarities in my solution for this contest and also if there was any unintentional exposure of my code (perhaps through public IDEs or similar platforms), it was not deliberate, and I apologize for any misunderstanding. The code idea and algorithm is so clear, this make some solutions make a similarity there are more than 30k participants in this contest and this for sure will lead to similarity and similarity of thinking in creating the algorithm. In the last, take the suitable action and what you see will be correct do it, but don't block my account for little unawareness.

Thank you

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

Hi P.V.Sekhar , nishkarsh, I received below message from Codeforces Round 976 (Div. 2) and Divide By Zero 9.0 Attention!

Your solution 283631407 for the problem 2020D significantly coincides with solutions shrey_gta/283612481, Isaac_Netero/283631407. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I do not know shrey_gta, and i did not share my solution to anyone I used the following document for the DSU function. https://takeuforward.org/data-structure/disjoint-set-union-by-rank-union-by-size-path-compression-g-46/

if u can look into this matter, it will be helpful. thank u

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

int solve()
{
    int n,m;
    cin>>n>>m;

    map<int,vector<pi>> hash;
    while(m--)
    {
        int a, d, k;

        cin>>a>>d>>k;

        hash[d].push_back({a,k});
    }
    auto conv = [&](vector<pi> &vec,int d)->vector<pi>
    {
        sort(all(vec));
        
        vector<pi> ans;

        int sz = vec.size();

        for(int i=1;i<sz;i++)
        {
            int &a = vec[i].first , &k = vec[i].second;

            int &pa = vec[i-1].first , &pk = vec[i-1].second;

            if(a != pa)
            {
                if(((a - pa) % d) == 0)
                {
                    int lt = a + k*d;
                    int prev_lt = pa + pk*d;

                    if(prev_lt >= a)
                    {  
                        k = (a + k*d - pa) / d;
                        a = pa;
                    }
                    else 
                    {
                        ans.push_back({pa,pk});
                    }
                }
                else 
                {
                    ans.push_back({pa,pk});
                }
            }
        }


        ans.push_back({vec.back().first , vec.back().second});

        return ans;
    };

    for(auto &itr : hash)
    {
        itr.second = conv(itr.second,itr.first);
    }

    DSU dsu(n);

    for(auto &itr : hash)
    {
        int d = itr.first;

        vector<pi> &vec =  itr.second;

        for(auto &it : vec)
        {
            int a = it.first , k = it.second;

            for(int i=1;i<=k;i++)
            {
                dsu.unite(a - 1,a + d*i - 1);
            }
        }
    }

 
    int ans = dsu.countComponents();

    return ans;

}

Can anyone help me debug my solution to D problem? (WA at test 2)

I have merged APs with common terms and differences and then used classic DSU.

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

how

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

    I did not share my code with anyone and did not copy code from anyone, maybe we have the same way of thinking but I did not share or copy code!

    You do indeed have the same way of thinking, since you're the same person.

    During contests you submit as many times as it takes for you to get solve a problem from bkdn24.__hide...

    ...and then conveniently submit the same code (with some useless variable name changes that makes you feel smart and undetectable) from bkdn24.ntth

    In case you are too dumb to realise, this is cheating. Stop crying and do better.

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

orz

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

In 2020B - Brightness Begins,

What is special about test case 854258779689358055?

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

    There are 854258779689358055 numbers before854258780613619263 which are not perfect square. Then why this is not the answer?

    https://ideone.com/wEfOYM

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

      There are 854258779689358056 numbers rather than 854258779689358055 before 854258780613619263 that are not perfect squares (as the number itself should also be included).

      → Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why is this disliked alot?

→ Reply