74TrAkToR's blog

Codeforces Round #830 (Div. 2)
By 74TrAkToR, history, 2 years ago, translation, In English

Hello, Codeforces!

I am happy to invite you to my Codeforces Round 830 (Div. 2) which will be held at Oct/23/2022 13:05 (Moscow time). The round will be rated for all the participants with rating strictly less than 2100 before Oct/23/2022 10:50 (Moscow time).

The tasks were created and prepared by 74TrAkToR. I would like to thank everyone who helped me a lot with round preparation.

During the round you will need to solve 5 problems, some of which have subtasks. You will have 2 hours to solve them.

Score distribution will be announced shortly before the round.

We wish you good luck and high rating!

UPD: Score distribution: $$$750-750-(1000-1000)-(1250-1250)-3000$$$

UPD: Editorial

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

Comments Comments (107)
| Write comment?
»
2 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Sleepforces

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

Orz to gyh20 for testing twice :O

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

    Instead of writing your shit on every post , you can consider practice more. Asses everywhere.

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

      Says a newbie

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

        Not a noobie kiddo, have you heard of ALT??

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

          ALTs are prohibited by the codeforces rules

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

        Don't be so ignorant. He actually has a maximal rating of a whopping 1069 on his alt!

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

      So your first comment on codeforces is aimed at trying to roast me (which failed horribly)? Too bad.

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

        No need to roast someone with contribution <0 . Just reminding not to shit everywhere.

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

          Says a person who ranks last place with an "ALT"

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

            This one's is special, aimed at getting rating<0 ;) And one more thing, you should practice some good problems, 400 is a big number for pupil lol .

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

              Trying so hard to solve a problem, eh?

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

              Yeah I am practicing good problems you idiot

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

        I love chromate00.

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

The round will be rated for all the participants with rating strictly less than 2100.

Due to CFR #829 (as you know, the round ends 30min before this round), it seems not clear enough.
According to this comment, the round will be rated for all the participants with rating strictly less than 2100 right before CFR #829 starts, and the order of rating calculation is #829 $$$\rightarrow$$$ #830 right? (Let's make it well-defined like the problem statements so that to avoid needless troubles!)

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

there are two contests on the same day! why?

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

    Both rounds are based on on-site contests, so they have to be the same day due to on-site contests being the same day.

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

As a tester who has not yet had time to participate in the test, the current number of upvotes is 74, orzorzorz.

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

Feels like those high school exam days where you take Paper 1 and Paper 2 with 30 mins break between each other

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

As a tester, I want to get valeriu's attention.

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

At least one contest could be at usual time on that day.

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

Two contests one after another [DIV2] :)

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

It's like participating in ICPC but with a 30 min break. Nice way to prepare for ICPC orz

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

India vs Pakistan (cry emoji)

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

    Literally. Would have been great if they would have shifted at-least one of the two contest during the normal 8:05 pm IST

    (Hope emoji)

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

JEE Advanced vibes.

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

no way, two rounds in a row

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

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

The judger will be so happy during the triple system test:)

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

Please note that this contest doesn't start at a usual time. And there is also a contest (#829) on the same day.

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

Hoping to cross 2100! Good luck!

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

    I hope to cross 1600 and become expert! Good luck for you too!

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

      I hope to cross 1400. Good luck to you too

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

        I hope to cross 1200. Good luck everyone

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

Finally, I can Fall down 2 times a day!

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

    Sir You can also say that I can go up 2 times a day

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

I can't take part in the contest because I must go to school tomorrow.I'm very sad.

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

Consicutive two contest! Wasn't it better if second contest will postpone between 23rd and 29th October?

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

Hope to become specialist by doing this contest.

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

Question: what if I show a 2100-crossing performance during the earlier Round #829 and then participate in this Round #830? Will #830 get unrated for me after #829 rating adjustments?

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

    Carry in post "rated for all the participants with rating strictly less than 2100 before Sunday, October 23, 2022 at ***"

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

      So I think you will rating for both matches anyway

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

    2100-crossing performance indeed :)

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

From 3 contests on 3 consecutive days to 3 contest in 1 day, codeforces has gone wild :)

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

As a tester, my 4th goal this year was achieved.

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

    orzorzorz, you are the only Japanese among my friends on codeforces. Hope we can become good friends in the future.

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

how can we register 830 now? I cannot find it in contest

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

If my rating become more than 2100 after I take part in the round 829 and then I take part in round 830,will my rating be calculated based on the rating lower than 2100 or more than 2100?

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

Score Distribution?

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

CodeForces using largest common prefix as title for common contests? It went incorrect for today's contests.

  • Needs to be fixed
  • Seems Good
→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The most balanced round I have ever seen, grats!

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

POV: YOU'VE TAKEN PART IN THE SANEST ROUND ON CODEFORCES EVER.

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

How to solve c1?

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

    Consider what happens if we remove any element $$$a_i$$$ from the subsegment.

    • The sum will reduce by $$$a_i$$$.
    • The bits that are on in $$$a_i$$$ will be flipped in the XOR. The best case is that the xor reduces by $$$a_i$$$, which happens when all the bits in $$$a_i$$$ are on in the XOR.

    So the value of $$$f(l, r)$$$ can never be increased by removing elements, only the size of the subsegment can be reduced.

    C2s solution involves using this to realize the optimal solution will remove at most $$$\log(max(a))$$$ non-zero elements from each side since each element must disable at least 1 bit in the XOR. So you can solve it in $$$O(n \log^2(max(a)))$$$.

    I'm not actually sure what the partial solution for C1 uses, maybe fixing each possible left end and binary searching on the right end?

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

      fixing each possible left end and binary searching on the right end?

      Yes

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

Why does trying only the first 30 non-zero elements from each side WA (177636235), but 60 gets AC (177636753)? Shouldn't it be the max number of bits in a_i (i.e, 30) since any position contributes a non-negative amount to f(l, r), so we can only remove each bit at least once without reducing the max value.

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

    Picking first 31 non-zero elements is the optimum, not 30 elements.

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

By number of solves, C1/D1 must be something very obvious. Absolutely lost any shape:)

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

Felt silly writing a DFS solution for problem A after being stuck for a while but at least it passed lol 177632733

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

What is the intended solution to B? I bricked on it for way too long before just coding the overkill dp.

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

    My solution greedily flipped the first block of 1s it found while iterating and kept a variable for if everything was "flipped" or not

    Example:

    10011

    01100 (flipped = true, find next block of flipped 1s)

    00011 (flipped = false)

    2 in total

    #177620466

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

What was the process for D1? I got stuck thinking about k-mex because it felt like it would time out no matter what lol.

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

    maybe just a brute force

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

    My solution that passed pretests was just to memoize answers since the answer for a query can never reduce unless elements are deleted from the set. So next time we can just check from the memoized multiple.

    I think this probably becomes $$$O(q \log q)$$$ or something similar which is good enough to get AC, thought I didn't bother analyzing it properly, I just guessed it was something simple looking at the solve count.

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

      UPD: Sorry it was wrong

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

      I did it similarly, for a given K stored the k-mex in a map. Next time if K came up then set k-mex = max(mapped value of K, next largest multiple of k less than the current smallest non-negative element not present), and stored this in the map. But how is the complexity coming up to be O(q*logq) can you explain that?

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

        Edit: Deleted.

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

          Can you explain why the $$$k$$$-mex is updated at most $$$q / k$$$ times for each $$$k$$$? If we have alternating inserts and queries of the form $$$+ k, ? k, + 2k, ? k, + 3k, ? k, \dots$$$, we are updating the $$$k$$$-mex $$$q / 2$$$ times instead of at most $$$q / k$$$.

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

            You're right. The proof is incorrect. I believe the bound is correct though, and we need a more complicated argument. I'll think more and try to post a correct proof soon. But yeah, it's clear that the lower bound holds.

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

              Have you found the correct proof yet?

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

                I have asked a group theorist (really smart guy). Hopefully, we'll get a proof (or a counter example) soon.

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

      Oh, I was definitely overthinking it then. Need to not be blind during contests lol

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

Time limit exceeded on pretest 18, What can I say?

won't use unordered_map any more

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

ABD-forces

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

    TBH BAD-forces. Not "bad", but based on the number of submissions xD

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

In C, how to handle bits that are present in exactly 3 elements? Or if there is no need to handle them separately at all?

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

How to solve D1? By the looks of it seemed like some kind of precomputation as there were strictly no removals??

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

Spent 30 minutes on A debugging code when I realized my function to calculate if $$$gcd$$$ of an array is equal to $$$1$$$ looks like this:

int f(int n, vector<int> a) {
    int ans=a[0];
    for(int i=1; i<n; i++) ans=__gcd(rj, a[i]);
    return ans;
}
Silly mistake
→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to not be blind during contest? Even though ai = 0 is given in sample of both C1 and C2 but I still ignored and wasted too long .

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

Sad

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

I don't really understand why memorized brute force for D1 run so quickly.

Can anybody prove the time complexity?

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

    Cause if you iterated too much to calculate the answer, it means you added the element just as many times.

    Total "for loop" of all queries "?" executes asymptotically around the same number of times as addition of the elements with "+" (maybe by log times better)

    Not a strict proof but intuition though

    It reminds of range(0, n, 1) + range(0, n, 2) + range(0, n, 3) and this is supposed to be bound to n log n

    Probably it is possible to build strict proof around this

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

    I think it is to do with the number of divisors.

    Since $$$k|x$$$ and $$$\dfrac xk\le2\times 10^5$$$ i.e. $$$k\ge\dfrac x {2\times10^5}$$$, I guess the number of $$$k$$$ which satisfy these conditions is about $$$1000$$$.

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

    Your value of memoized answer will change only when you insert the memoized answer in set. So the maximum number of times your answer pointer will move in all queries is O(q)

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

A day well spent

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

The C1 is so intresting! Though I haven't solved it in contest,I really love it .

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

Can't complain as this round was based on an Olympiad, but would suggest to have fairly easier problem A in upcoming rounds so that all the actual participants are involved in rating calculation.

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

    B < A without a doubt. And I suppose a considerable amount of newbies notice the term "GCD" in the question and just abandon.

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

codeforces not geometryforces not mathforces not sleepforces not speedforces

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

Is the rating going to be calculated based on my rating after round 829 or before it?

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

This contest went well for me but first one was disaster for me ,feeling very frustrated, feeling like my career & dream is getting finished ,very sad,cp was something that I loved and it gave me some worth when started but seems like things are not going anywhere now

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

    It happens sometimes man, just hold in there. Hope it gets better for you :)

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

      people can have bad contests but the level of inconsistency that I am showing is detrimental, in first contest I did 800 perf and in the second 1600 ;the difference is 2 times, and this has been for long and I think the way I am performing and practicing I am not doing justice to my talent and I am certainly much more than just a cyan ;and my level of skill won't create any real impact or threat in national contests which is frightening; but yes as I can't give up I should quickly find ways to do well in national level & cf

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

    Well, for me a well performed contest may just mean I'm lucky. And many ups and downs of my ratings actually reflect my true level. Maybe you should focus more on what you learned from every contest rather than the ratings.

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

This round is great.when will be rating change.before rating change becomes quickly than now.i'm looking forward to rating change

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

FSTed , sad TaT.

The pretest of div1B is too weak...

Problems are great , especially div1D

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

    Ehrm, this is #830, which had Div.2 only. Maybe you are looking for #829 instead?

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

      Ohh sorry I post it at wrong place. But how can I delete it?

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

        It's fine (for now), Codeforces doesn't support deleting comments more than 3 minutes ago, so unfortunately you cant delete the comment

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

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

Minor thing: for D, when it says k-MEX is the minimum nonnegative integer, then doesn't 0 work for a lot of the test cases provided?

→ Reply