n0sk1ll's blog

Codeforces Round #910 (Div. 2)
By n0sk1ll, history, 3 weeks ago, In English

Hello, Codeforces!

ELDRVD and I are glad to invite you to Codeforces Round 910 (Div. 2), which will start on Nov/19/2023 17:35 (Moscow time). You will be given 6 problems and 2 hours to solve them.

The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially.

All problems are invented and prepared by ELDRVD and me. Special thanks go to Sofija06 and NemanjaSo2005, our two most dedicated testers. We would also like to honor:

We are looking forward to your participation!

UPD1: The score distribution is $$$500 — 1250 — 1750 — 1750 — 2000 — 2500$$$.

UPD2: Editorial

UPD3: Congratulations to the winners!

  1. hitonanode
  2. Rubikun
  3. femboy-wannabe
  4. potato167
  5. Golovanov399
  6. A_G
  7. AmazingTalker_Frank
  8. Geothermal
  9. StarSilk
  10. Farhod_Farmon

UPD4: Also, congratulations to the Div. 2 winners!

  1. femboy-wannabe
  2. Top2Greece
  3. hoiii
  4. KaiAngel
  5. Nguyen_Mai_Huong
  6. lunchbox
  7. bobbilyking
  8. q_x_j
  9. supercambrian
  10. MeGustaElArroz23
  • Vote: I like it
  • +183
  • Vote: I do not like it

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

910 Sounds good! :)

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

As a tester,the problemset is breath-taking!Hope you enjoy the round :)

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

As a tester, I recommend you to participate, I had fun testing the round and hope you'll also enjoy it!

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

NemanjaSo2005 orz

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

As a tester, I enjoyed the round. Nice that my friends did 2 rounds in a short amount of time (900 was also by my friends). Maybe I should join them?

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

this round is clashing with world cup final

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

What is the score distribution among the problems?

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

As a tester, I recommend you to participate, I had fun testing the round and hope you'll also enjoy it!
PS.911 Round is coming！

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

hope i could calm down and focus on the problems

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

    hope i could calm down and focus on the problems

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

      5 questions were solved during the contest... It seems like you were able to calm down and focus on the problems :)... welcome to pupil

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

Good luck everyone.

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

As a tester, you know what I did

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

Hope to get green after that one

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

How can I change utc in codeforces?

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

Am very excited for this round.

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

expecting very less Indian participants

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

As a first-time problem setter, I hope you enjoy the problems and orz to all testers and participants!

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

Excited to reach cyan after this round!

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

I feel like Kapil Sharma in “Kis Kisko Pyaar Karoon”, as I have to juggle between a Codeforces contest, a cricket world cup final, and an end semester exam. Still trying to find my fourth one.

Life got no chill!!

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

contest cancel karaao

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

Happy Men's Day :)

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

Scoring distribution when?

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

Sunday rounds are best!!!

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

n0sk1ll Could you remind me the name of that legendary game on your profile picture?

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

hope to reach cyan today

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

Dammnnnn score distribution :⁠-⁠!

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

Interesting score distribution. C = D = 1750. Hope not to lose CM)

GL everyone!

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

I will win Codeforces Round #910!

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

I hope this game goes well

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

are codeforces mirrors down? m3.codeforces.com? dont seem to be working

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

Participation is less due to ICC CWC Final

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

ummm.. who else sacrificed this round to watch the ICC world Finals... xD.

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

The authors of this wonderful round, I really hope that you will never do such cool tasks again

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

completely unbalanced round, all there is to say.

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

why it gives wrong answer on test 3 ?? ~~~~~ int n; cin >> n ; vector < int > arr ( n + 1 ) ; for ( int i = 1 ; i <= n; i++ ){ cin >> arr[i] ; }

int ans = 0 ; 
 int last = arr[n] ; 
 for ( int i = n - 1 ; i >= 1 ; i-- ){ 
     if ( arr[i] <= last ) {
        last = arr[i] ; 
        continue ; 
     }


     int cnt = 0 ; 
      while ( true ) {
         int left = arr[i] / 2 , right = ( arr[i] + 1 ) / 2 ; 



         if ( right <= last  ){
            last = left;
             cnt++;
             ans += ( 1 << cnt ) - 1;
            break;
         }


         arr[i] = ( arr[i] + 1 ) / 2;
         cnt++;

     }


 }

 cout << ans  ;

~~~~~

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

    Perhaps the answer exceed the upper bound of int?

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

      code'output : 1 0 4 9

      it should be 3 instead of 4 which is wrong on testcase 3 , wonder why ?

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

        Oh, for the third sample input, i.e., 3 2 1? Split the 2 into 1 + 1. Then split 3 into 1+2, splitting this 2 further into 1+1. Final array is [1, 1, 1, 1, 1, 1] with three operations in total.

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

    Here is a test case that fails:

    3
4 12 5

    Your code outputs 4, but the optimal answer is 2. Split the 12 into 8+4, then split the 8 into 4+4, so the final array is [4, 4, 4, 4, 5]

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

Not good problem $$$C$$$. Solve in $$$3$$$ min, but debugging output format $$$30$$$ minutes:) $$$ABDE$$$ are cool, thanks!

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

Please, either get better at balancing problems or don't host contests at all. This is the 2nd time this has happened.

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

    every time i am close to reach cyan this thing happens i am really frustrated

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

      Honestly, in situations like these I just read all of the problem statements, and thankfully C was a casework problem so I just put an hour into it and solved it, if you really want to become cyan I'd recommend you wait for div.3 rounds.

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

Solved DE but failed to solve BC....

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

Wow, problems are actually incredible bad)

Why so unqualified testers? That's the questing...

A: Ok problem. And the last one tbh.

B: It's just unfathomable hard. Some observation maybe or just random greedy solution, as far as i can see... Didn't get it.

C: Statement is barely readable. Why are we coloring edges??? It is just too hard to visualize. It would be much more interesting if we were coloring cells and not the edges.

Other problems: Didn't even read due to unfathomable B and C.

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

    same thing happened A is nice and easy to think but I can't think B lol but many people solved it some of my friends did it within 10 minutes idk why I couldn't :(

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

    I agree that B is too hard for Div2 B. Other things you said is just skill issue (or maybe you are too exhausted to think as you used to).

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

      I agree, B is harder than usual Div2 B

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

      Disagree. Maybe i am not the smartest person ever lived, but one i know for sure. I can solve more than 1 problem in div2, if the problems are prepared nicely

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

    Hi, can you provide more feedback about the problems and their solutions? I want to improve as a problem-setter.

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

    Yeah I found C super annoying (output format doesn't help either) but I found E quite nice on the other hand.

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

cringe

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

My worst round ever:( Spent all the time debugging.

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

Is it just me or has the problem B already occurred somewhere in this exact form?

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

it was really bad

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

spending all the time trying to debug :(

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

I'm confident that i've seen problem B and D within the last six months in some codeforces contest.

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

Good bye hopes of getting cyan

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

div2 with div1 problems

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

we need more competitions from the person with the color blue. cringe

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

Should have just named problem C Good colorings to add it to the collection of annoying coloring problems.

Also I think E shouldn't be worth 2000 points, one observation is enough to solve the problem on the spot.

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

thanks bro now i finally reached cyan

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

Messed up this contest so bad lmao

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

Problems themselves are very good(especially I like this kind of B,C,D,E), and score distribution is also good. But only hard D2B destroyed the experience for many contestants... This kind of downvote is so sad...

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

    Highly agreed. The people who are complaining are just pathetic.

    D2B is a super fun problem actually (although I didn't solve it during the contest). It is true that it may appeared in leetcode rounds before. But again, do CPers really care about leetcode? I am pretty sure most people haven't seen it before.

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

      it doesnt matter do cpers leetcode or not (by the way they do). This problem has its editorial published and this is unfair

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

        cry about it

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

        Life is also unfair, maybe you shouldn`t participate either? Sorry,just a joke, but seriously, when preparing problemset, do you think it is easy to look through 10k+ different tasks in order to create something new? In my expirience,this collision may happen sometimes, but it happens quite rarely.

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

          I can understand how testers and coordinators missed it, but when a problemsetter presents a contest with 2/6 problems having already appeared on codeforces, it seems suspicious and is usually not appreciated in the community

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

            What is the second one? I am not quite familiar (D is actually not present, because the trick that solves D cannot be used to minimize the function)

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

            To be quite honest I believe there is a very solid argument for making the round unrated, and I can base it on my own experience in contest. I read B, and immediately recalled the "Extreme Extension" problem as I already mentioned above. So I had the idea, then 3 minutes of debugging later I got AC. Now, to be fair when I first read Extreme Extension a few weeks ago the greedy algorithm for one subarray popped into my head about ten minutes later, but still — I was able to breeze through today's B about ten minutes faster than I should have. The low solvecount is quite odd in light of this collision, but those who did recall Extreme Extension or the leetcode problem or whatever and who are generally not good enough to solve B would suddenly get a huge rating boost for getting top 2000, which I don't find very fair.

            Also I'm expecting +84 delta so I'm not saying this out of annoyance.

            Edit: why is it rated?

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

      Dude, https://codeforces.com/problemset/problem/1603/C

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

      I'd say it's even more unfair if most people haven't seen it before and only few people gain advantages, comparing to the problems that most people have seen it before.

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

When my internet goes down right before the contest that's a sign XD

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

B is same as https://leetcode.com/problems/minimum-replacements-to-sort-the-array/description/ D is almost same as https://codeforces.com/contest/1513/problem/F how?

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

why this is wrong for the first test case in problem C ?

YES
R B R B 
B R B R 
R B R B 
B R B R 
R R B R B 
B B R B R 
R R B R B .
→ Reply
»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

A very unbalanced contest

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

MAKE THIS ROUND UNRATED MikeMirzayanov

the same problem as problem B -> https://leetcode.com/problems/minimumreplacements-to-sort-the-array/description/

almost the same problem as problem D -> https://codeforces.com/contest/1513/problem/F

We can understand if only one problem is the same as some problems from the past, but having two is not fair. I'm also certain that problem C was a copy of some problem from the past.

UPD: https://codeforces.com/problemset/problem/1603/C one more proof, thanks Golovanov399

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

    The trick that solves D cannot be used to minimize the function, so it's not copied

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

    "I'm also certain that problem C was a copy of some problem from the past."

    proofs?

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

    As Huyum_nik_fan pointed out, 1603C (the harder version of problem B) was also solved by one of the authors: 133683209, so it cannot simply be an unintended coincidence.

    Note that solving 1603C requires solving the easier subproblem of this round's problem B, whose solution is elaborated in detail in the editorial for 1603C, so the authors should certainly have been aware that those who have solved 1603C or even just viewed its editorial (and can find it again with some searching after recalling it) would have an unfair advantage here.

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

Ya'll are mad that similar problems have appeared before, yet D was solved by less than 1k official participants during the contest, and B was solved by less than 3k participants (this is D2B we are talking about that usually gets solved by over 5 thousands of people).

Either get better at problem solving or get better at googling problems.

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

The link of old D question https://codeforces.com/contest/1513/problem/F, but only there minimum,in this contest maximum

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

    The trick that solves D cannot be used to minimize the function

    you'd better to do some research before commenting)

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

      In this context, I think it's in the other way around. The key point is whether the trick that solves past F can solves this D.

      The key observation for D is to reduce it to segment overlapping problem. After the reduction, it's just simple min/max trivial steps.

      And this observation is exactly the same as the "observation 3" in the tutorial of past F.

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

    If you've found same problem, why didn't you solve the problem ?))

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

Finally reach cyan :)

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

Can anyone help me debug this Solution for A ?

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

Man. Problem B turned out to be so easy, but I wasted all my time debugging solution for C.

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

I'm not really a fan of F, it took me ~10 mins to get the solution and ~45 mins to code it. The idea is sort of nice but the lengthy implementation sort of kills it. (Disclaimer — tbf this might be due to my trash implementation skills).

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

what a bad contest

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

Amazing I had +102 in this round

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

I forgot about this round, thanks to the cricket worldcup final.

India lost, round misses double pain!

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

Ngl, I've solved that similar to B leetcode problem before and I had the advantage of recalling an approach from https://leetcode.com/problems/maximum-of-absolute-value-expression/ similar to D. Feels like I didn't deserve purple from this round.

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

Problem D looks familiar with a Problem before,but i forget what is it infact,both two problems are analyzed by segment and calculate the contribution but i forget what problem is that=<

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

"Note that "1 A" and "3 A" are also correct one-operation solutions."--- Thanks for adding this line in 1st problem statements. I was confused first. It's make the Question clear. Without this line the problem is hard. But, after adding this line the problem became very easy.

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

Absolutely two (1, 2) equal problems on codeforces. What happened to this platform?

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

https://leetcode.com/problems/minimum-replacements-to-sort-the-array/ Problem B is found on leetcode. This is unfair !

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

Problems were pretty nice, but C sucked (that's just my bias though because it was hard for me haha)

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

LOL, I straight up copied my solution for B from leetcode. Zero code changes required. Not sure how was it not flagged out during testing, it was a relatively recent problem.

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

When we have solution? :))

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

I'm on the list!

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

Good luck everyone!

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

fking bfs

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

Thanks for the round! problem E was quite interesting, and DF are kind of standard-ish but it is still good enough :)

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

I solved problem E immediately after the contest. I realy dissapoint about it. I could get about 69 rating, but i get only 2. But contest was really nice. Problem C and D is very interesting, and problem E fits it's position very well. Thanks to @n0sk1ll and @ELDRVD for this time spent.

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

how can someone with higher initial rating and lower contest ranking than me get more plus rating points than me??

→ Reply