Igorfardoc's blog

Codeforces Round #769 (Div. 2)
By Igorfardoc, history, 3 years ago, In English

Hi, Codeforces!

Vladithur and I are pleased to invite you to our Codeforces Round 769 (Div. 2), which will be held on Jan/30/2022 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.

We would like to express our great gratitude to:

You will have 2 hours to solve 5 problems, one of which is divided into two subtasks.

The scoring distribution is 500 — 1000 — 1500 — 2000 — (1500 — 1500)

We have tried to make clear statements and strong pretests for the problems and hope you will have fun and increase your rating!

Good luck!

Also, we would like to start the trend of evaluating the round's problems. We think it will give valuable feedback to authors and make future contests better. So please, vote for each problem after the round's end.

Problem A
Problem B
Problem C
Problem D
Problem E1
Problem E2

UPD: Editorial is here.

UPD2: Congratulations to the winners!

Div. 1 + Div. 2:

  1. kotatsugame
  2. tute7627 and jiangly
  3. -
  4. I_Iove_chtholly
  5. Alan_girlfriend

Div. 2:

  1. I_Iove_chtholly
  2. Alan_girlfriend
  3. Wlxsohandsome
  4. 778
  5. i_will_be_less_than_blue
  • Vote: I like it
  • +394
  • Vote: I do not like it

Comments Comments (122)
| Write comment?
»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

As a tester, I like all problems!

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

I can say that all the problems are very interesting to solve and the authors have done a great job inventing them.

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

By the way, does dkirienko help you?

If the answer is "yes" — is it meaning that participant can solve all problems using Python? :)

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

    Even though the answer is "no", all problems can be solved using Python!

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

Is the round going to be Starcraft-themed? :P

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

Hope all of you will get good rating after this round .

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

Love the idea of per-problem feedback prompts! Although I wonder why people already started voting — are those testers or trolls? :P

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

    Some of them are testers, and some of them are trolls, I think. But, I really hope they will revote after the round.

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

      I think it would be better if you have given this feedback voting option in editorial blog instead of announcement blog, Anyway it's a great initiative.

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

        I believe there are people like me who rarely open editorials.

        They should've just added the voting section after the end of the contest by editing the blog.

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

      And some of them — I believe — has a superpower to foresee the future

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

    trollforces

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

So please, vote for each problem after the round's end.

you should have waited round to end for putting votes, now alot people will vote but forget to re-vote

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

The people who vote for the Bad problem even before they see the problem are the same people who always ruin beautiful things!

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

It is sad to see that some people have already voted "a bad problem" . Anyway, I wish everyone good luck for the contest!

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

As a tester I think there should be a section to ask for contribution.

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

Hello, I am a beginner who recently joined codeforces. Will there be a division 3 contest anytime soon? Thanks.

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

    You should try participating in div 2 as well. Because div3 is a rarer thing than div2 :)

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

    This is a normal and reasonable question, and I can't understand why there are so many downvotes. I doubt some users just downvote it blindly because there are already some downvotes and it's tempting to add more.

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

I don't understand why is it possible to evaluate problems before the round, it would be good update later , but why now?

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

    So, may be it is a good idea, but I actually do not see much of a difference, because there will always be trolls, and you will not get rid of them by moving the evaluation to the update or to the editorial. As for decent people, I think they will revote after the round, if at first they chose the wrong option.

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

nobody reads tags expect me

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

As a tester, I do read tags!

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

DELETED

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

    I think it doesn't. This contest is held on 30/1 14:35 UTC, while COCI contest #4 is held on 29/1 14:00 UTC. Correct me if I'm wrong.

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

Hope to get +69.

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

What about The people who vote for the Bad problem even before they see the problem!! what are u doing?!

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

    what if these votes came from the testers?

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

      man just count the number of testers and votes. ez math bro. Also testers should not vote. they give the writers a direct feedback.

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

I appreciate the idea of collecting the feedback regarding individual problems. But I'm getting the feel that this way of collecting the feedback might lead to a lot of false statistics. The round hasn't started yet and already you can realize some surprising data.

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

    I agree that it may collect false statistics, but regardless, it's a good step forward. Sometimes there are just bad problems, you can't deny that. And, I appreciate the effort of the authors to step forward and give chance for feedback. This says that the authors are careful and I hope we'll finally have some good problems, not just edge-case work.

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

      Indeed it is a pretty nice initiative to provide a platform for some constructive feedback wrt to problem set. I'm just suggesting some points of improvement to ensure some sort of validity in the poll results. Like opening the poll after the contest ends to begin with.

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

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

I suggest putting the voting buttons in the editorial. People should provide feedback only after they have seen the solution.

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

    After being inspired by this I think we will have a huge benefit if we can vote for every single problem after we solved it (maybe there can be some rating restriction for example rating >= 1400). Thus, every problem except its rating difficulty will also have a number that corresponds to its pleasure to be solved and whether it's a good or a bad problem. I think this way both problem solvers and authors can take advantage of this.

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

Great initiative!

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

new challenge for all contestants........good luck

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

Interesting delete line.

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

Which is more easy problem A or problem E?
I am new on codeforces. Plz tell me.

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

Good luck!

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

Wow! The authors of the round have avatars from Starcraft 2. We should participate!

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

Wowwwwwwwwwwwwwwwwww how can you add the likes?

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

as a !tester , i am here to farm contribution.

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

I am not sure the categories for evaluating problems are right. Quite often the problems I fail to solve (or fail to solve without reading the editorial) are the most interesting (best?) problems.

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

Hoping for a contest which do not contain problems like previous Div2 C

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

Good timing of the Australian Open Final, has ended 20 minutes before the contest.

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

    Unfortunatly, our compatriot Daniil Medvedev lose :(

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

Good luck everyone

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

ALL the best guys..

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

bitforces.

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

If I do multiple submissions, and all are passed then my score depends on my first submission or last submission

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

great round, loved the problems!

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

Hint for task C?

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

I have no idea why my solution to B passed pretests :OO

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

The fact that C=E1 in scoring distribution is strange for me.

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

back to mathforces :(

also thanks for very not misleading scoring of the last task

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

    More like bitforces?

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

      math includes bit and D was math also

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

        I consider them as very different things and there's very little math in D IMO.

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

Is C Ad-Hoc?

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

DELETED

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

    Which of the problems have endless corner cases?

    • A: The edge cases are literally in the samples.

    • B: No edges cases needed here since (n — 1) ^ largest bit always works.

    • C: Not sure if there is a casework soln to this, but my solution just iterates on the value the final element will take and then you just need to check the smallest value $$$\geq a$$$ that is a submask of this element. I don't think anything is casework heavy here.

    • D: My solution uses one nice observation + range queries, maybe the other solution is case work heavy which is unfortunate since range query structures shouldn't be required for a Div2D.

    • E1: No case work here, just find distances and calculate the answer using a weird sort of prefix maximums / decreasing suffix maximum.

    • E2: No clue, didn't solve it, but I doubt you're referring to this problem.

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

      There could be many different solutions for a single problem. If one takes the wrong direction, then that person might be stuck in many corner cases. I'm initially referring to my case solution for C but I'm also talking about things generally.

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

        This is interesting. One of the things I hate about myself is that I find it hard to discard an idea, so I end up checking a lot of cases and overcomplicating problems unnecessarily and most of the time I will fail anyway. Checking the straightforward editorial for C after struggling is beautiful. I don't think the 4 cases about the bit values is something to be considered painful casework. My conclusion is that, most of the time, you should blame yourself. Writing simple solutions is part of practice.

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

          Yes, you are absolutely right. It took me some time to realize the importance of avoiding getting stuck in one direction. In most cases the problem should have a clean solution which doesn't require too many cases.

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

      Why is range queries bad for div2D?

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

How to solve D without range query data structures?

Btw I really like the monotonic observation. Its such an obvious fact that as we increase the number of elements the gcd will not increase, but it really did not strike me in relation to the problem.

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

    I kept a multiset of ban positions for each indices. For instance, a suffix gcd equals to $$$3$$$ at position $$$5$$$ bans position $$$7$$$.

    When we actually update a gcd, we maintain the set. Such updates will not be many as each time at least one of the gcds lose a factor.

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

    I think the key observation is that given a[i], there can be at most around log2(a[i]) distinct gcds among gcd(a[i]), gcd(a[i — 1], a[i]), ..., gcd(a[0], ..., a[i]).

    So, combined with the monotonic observation, it's fine to maintain a partitioning of [0, i] into intervals, one for each distinct gcd. So in log2(i) time you can find the earliest position j such that gcd(a[j], ..., a[i]) is equal to its length. I guess you could also binary search but that's unnecessary.

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

      Could you elaborate on how you would generate and maintain such a partitioning though? I can think of a way to do this in $$$O(n \cdot \sqrt{max(a)} + n \cdot \log(max(a)) \cdot \log\log(max(a)))$$$ but this is too slow. I basically can't figure out how to eliminate factorization for newly added factors from $$$a_i$$$.

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

    Sqrt decomp go brr

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

There were so many submissions by unrated accounts around the same time. Were the solutions of first 4 problem leaked or something ?

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

bit operation contest. lacked variety of problems...

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

I love problem D

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

    Realized just after the contest that, replacing a for loop with while(bs) will work like magic

    Nice problem :)

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

bitforces

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

Very cool contest and interesting tasks!!!

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

Read at this bc I can't delete this comment: https://codeforces.me/blog/entry/99442#comment-882354

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

More cheat today.

@ MikeMirzayanov

we need to ban the cheat accounts,this kind of account makes imfair to cp

What's more , I find that most of accounts which submitted their code in 01:59 of E were suspect of cheat.

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

How is this wrong for E1? I maintained an Euler tour and segment tree. If I want to connect node 1 to node x. So max distance here will be max((max distance in the subtree of node x — dis[x] + i), max in the remaining tree excluding the subtree). Finally I take min ans for each x. Can someone pls give a counter example where this fails?

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

    Here is a case where your code will fail(if I have understood it correctly)

    9

    1 2

    2 3

    3 4

    4 5

    5 6

    6 7

    4 8

    8 9

    The correct answer for x = 1 is 3, but by yout logic it's 4

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

Is this even possible to create a solution for D that exceeds time limit?

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

In question B ,if we take input 6,then according to editorial solution answer will be {3 2 1 0 4 5} but the optimal ans is {2 3 1 0 4 5}.

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

    The problem asks us to minimize the maximum xor among pairs of adjacent elements. Both 3 2 1 0 4 5 and 2 3 1 0 4 5 have the same maximum xor of 0 ^ 4 = 4, so I don't think it really matters.

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

Good contest

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

During the contest when I was solving problem c, I got the intuition that we can solve this in a total of three steps in these sequence 1. either increase a or b by some amount. 2. take the OR. 3. increase the b to match the value with the second step value. Although I was not able to prove it during the contest. I submitted it just based on some gut feeling. So I just want to know is this the case with other people too? or do you guys first prove your solution and then submit it?

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

MikeMirzayanov I'm not really sure where to put this, but I received these two messages:

Attention!

Your solution 144568353 for the problem 1632D significantly coincides with solutions Weierstrass/144555583, codebuster_10/144561876, 876pol/144568353, Winterfrost/144569022, xiaoququsd/144572170, Kanheyalal/144572862, dimss/144575074, Kawaii/144576113, matouzouken/144576356. 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://codeforces.me/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.

Attention!

Your solution 144557728 for the problem 1632C significantly coincides with solutions Weierstrass/144543081, codebuster_10/144548751, Kawaii/144549603, matouzouken/144551794, Winterfrost/144556519, 876pol/144557728, xiaoququsd/144562448, dimss/144563984, Kanheyalal/144564250. 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://codeforces.me/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 wrote the code for both these submissions locally on vscode and I don't know any of the people mentioned in the message. Also, the codes don't seem that similar in the first place.

However, just to be sure, the code for 1632C is fairly short and is just a false positive. I had also submitted a couple WA submissions before this one, so its not like I copied it off of someone.

I got the code for the sparse table in 1632D from https://brilliant.org/wiki/sparse-table/, and the rest of the code is also short and is just two pointers.

(also, sorry for tagging you)

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

    Why their is positive Plag check, submissions are not even similar at all ? MikeMirzayanov Please see to it. I ran both my submissions locally and use my own template, any of the given submissions does not seem to be similar to mine at all.

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

    I also received this message, and I think our codes are completely different (I even didn't use any existing templates).

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

wow how many cheaters were removed? I should have got only +7 delta at the end of contest but now got +22

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

    SO CRAZY that one out of four accounts were cheaters in last round.

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

    I think that a good way to anti the cheater is to solve the problem faster than them. So whether they are cheating is unmeaningful.

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

In the third problem, isn't b' the same as a'|b. But, it doesn't give me the correct solution. If anyone could explain.

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

Hi I am a newbie and would appreciate some assistance here. My submission fails with verdict Wrong answer on test 2. However when I click on my submission number I can only see test case 1 which is succeeding. My question is how can I see test case 2 ?

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

    During the competition you will not be able to see private test cases. However, after the competition, you can resubmit your code and you will be allowed to see them.

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

I have a trouble understanding problem D example test case 3:

input
7
2 12 4 8 18 3 6
output
0 1 1 1 2 2 2

I expect that for prefix (2 12 4 8) we will need only 2 replacements, but it's 1 according to example

Specifically, I see two separate pairs: GCD(2, 12) = 2 and GCD(4, 8) = 2. I expect that we will need to replace one value in each pair

Can you help me?

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

    GCD(4, 8) = 4. And we can change this prefix into 2 5 4 8.

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

Hi MikeMirzayanov, My id has been hacked and someone has submitted fraudulent copied solutions from my account. They have even changed the email address of the account to something random and I can't even recover it. I am sending this message from an existing session. Dm'ed you the details. Please help.

→ Reply