n0sk1ll's blog

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

Hello, Codeforces!

BULLMCHOW and I are glad to invite you to Codeforces Round 910 (Div. 2), which will start on 19.11.2023 17:35 (Московское время). 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 BULLMCHOW 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

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. y_x_c
  9. supercambrian
  10. MeGustaElArroz23
  • Vote: I like it
  • +183
  • Vote: I do not like it

Comments Comments (147)
| Write comment?
»
12 months ago, # |
  Vote: I like it +16 Vote: I do not like it

910 Sounds good! :)

→ Reply
»
12 months 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
»
12 months 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
»
12 months ago, # |
  Vote: I like it +26 Vote: I do not like it

NemanjaSo2005 orz

→ Reply
»
12 months 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
»
12 months ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

this round is clashing with world cup final

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

What is the score distribution among the problems?

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

hope i could calm down and focus on the problems

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

    hope i could calm down and focus on the problems

    → Reply
    • »
      »
      »
      12 months 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
»
12 months ago, # |
  Vote: I like it +9 Vote: I do not like it

As a tester, you know what I did

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

Hope to get green after that one

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

expecting very less Indian participants

→ Reply
»
12 months 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
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Excited to reach cyan after this round!

→ Reply
»
12 months 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
»
12 months ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

contest cancel karaao

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

Happy Men's Day :)

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

Scoring distribution when?

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

Sunday rounds are best!!!

→ Reply
»
12 months 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
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

hope to reach cyan today

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

Dammnnnn score distribution :⁠-⁠!

→ Reply
»
12 months 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
»
12 months 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
»
12 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Participation is less due to ICC CWC Final

→ Reply
»
12 months 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
»
12 months 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
»
12 months ago, # |
  Vote: I like it +10 Vote: I do not like it

completely unbalanced round, all there is to say.

→ Reply
»
12 months 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
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Perhaps the answer exceed the upper bound of int?

    → Reply
    • »
      »
      »
      12 months 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
      • »
        »
        »
        »
        12 months 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
  • »
    »
    12 months 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
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 3   Vote: I like it -17 Vote: I do not like it

      .....

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

        Here is a failing test case:

        3
11 46 15

        Your program outputs 4, but the correct answer is 3. Split 46 into 11+11+12+12.

        → Reply
»
12 months 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
»
12 months 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
  • »
    »
    12 months 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
»
12 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Solved DE but failed to solve BC....

→ Reply
»
12 months 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
  • »
    »
    12 months 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
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I agree, B is harder than usual Div2 B

      → Reply
    • »
      »
      »
      12 months 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
  • »
    »
    12 months 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
  • »
    »
    12 months 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
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Congratulations on master you performed so good

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

        Thanks a lot! Let's see if I can stay master after this round.

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

cringe

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

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

→ Reply
»
12 months 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
»
12 months ago, # |
  Vote: I like it -6 Vote: I do not like it

it was really bad

→ Reply
»
12 months 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
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good bye hopes of getting cyan

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

div2 with div1 problems

→ Reply
»
12 months 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
»
12 months 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
»
12 months ago, # |
  Vote: I like it +17 Vote: I do not like it

thanks bro now i finally reached cyan

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

Messed up this contest so bad lmao

→ Reply
»
12 months 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
  • »
    »
    12 months 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
    • »
      »
      »
      12 months 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
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        cry about it

        → Reply
      • »
        »
        »
        »
        12 months 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
        • »
          »
          »
          »
          »
          12 months 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
          • »
            »
            »
            »
            »
            »
            12 months 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
          • »
            »
            »
            »
            »
            »
            12 months 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
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      12 months 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
»
12 months 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.net/contest/1513/problem/F how?

→ Reply
»
12 months 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.net/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.net/problemset/problem/1603/C one more proof, thanks Golovanov399

→ Reply
  • »
    »
    12 months 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
  • »
    »
    12 months 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
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    As hazzlek 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
»
12 months 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
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
  • »
    »
    12 months 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
    • »
      »
      »
      12 months 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
  • »
    »
    12 months 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
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally reach cyan :)

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

Can anyone help me debug this Solution for A ?

→ Reply
»
12 months 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
»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

what a bad contest

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

Amazing I had +102 in this round

→ Reply
»
12 months 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
»
12 months 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
»
12 months 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
»
12 months 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
»
12 months 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
»
12 months 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
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When we have solution? :))

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

I'm on the list!

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

Good luck everyone!

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

fking bfs

→ Reply
»
12 months 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
»
12 months 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
»
12 months 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