satyam343's blog

Codeforces Round #965 (Div 2) C
By satyam343, 3 months ago, In English

I am the coordinator of Codeforces Round #965 (Div 2).

Let me explain the situation behind the hard Problem C.

Initially, we planned to have the following C1 and C2 in this round.

Problem C1
Problem C2

However, two days ago, a tester shared a LeetCode blog link that contained the solution to C1, though it didn't help much with C2.

As a result, we had to remove C1 from the contest.

At that point, we had two options:

  • Introduce a completely new problem as C.
  • Use the previous C2 as C.

Since finding a new Problem C proved challenging (trust me, it's very hard to come up with good, easy problems, especially when you're aiming for a specific difficulty), we decided to use C2.

Recognizing that C2 seemed harder than the usual Div 2 Cs, we took the following steps to make it easier:

  • Simplified the problem: The previous C2 required contestants to observe that there always exists an optimal distribution of elements such that there is only one element in $$$S_2$$$. We modified the problem to eliminate the need for this reduction.
  • Enhanced samples: Testers noted that the problem was still more challenging than typical Div 2 Cs. Based on their feedback, it seemed to be rated around 1600-1700. One of the main reasons many testers received WA was due to incorrect implementation of binary search. To address this, I decided to include strong samples so that such bugs could be caught during sample testing.

It seems it did not help much. I am sorry for that.

So I checked the expected rating of C in Errichto's Discord server, and it shows the expected rating to be 1752.

I don't think it is too bad for problem C. Well, recent Div 2 Cs have been quite easy, so you might argue that it was very hard for C and all that. I do agree that the gap between problems B and C was huge, and I should have done something about it. But it was quite hard to add a problem of suitable difficulty this close to the round.

Also, I prefer having an interesting, slightly unbalanced contest over a boring, balanced contest. Although it is still possible to have an interesting, balanced contest, and I will try to ensure that my future rounds, which I coordinate or author, reflect this.

Also instead of downvoting the announcement of editorial, you can downvote this blog. It is not like that upvotes matter that much, but I don't want the blog by cry to get downvoted for my decisions.

Lastly, get good and learn binary search properly.

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

»
3 months ago, # |
← Rev. 3   Vote: I like it +206 Vote: I do not like it

I just want to say, satyam343 was the most responsible and hardworking coordinator I’ve ever worked with. Ever since this flaw was discovered three days before the contest, he has worked tirelessly on salvaging whatever we can from C. Proposing a whole another problem was unreasonable since we had to come up with an idea, prepare it, and get it tested within three days. That’s basically a recipe for disaster.

Even I thought this round was going to be doomed for sure, but it was somewhat saved. I want to give huge thanks to our testers for discussing this new change with us. But at last, we did the best we can in the time we had left.

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

I think it's a good problem. I bugged for some reason but still good

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

C was tougher than usual div2C — yes! was it a good problem — yes and would've been much better at D imho (or C2 as planned prev) but yeah, nice round and cool set of problems!

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

satyam343 Orz

→ Reply
»
3 months ago, # |
  Vote: I like it -65 Vote: I do not like it
Lastly, get good and learn binary search properly.

Nice way to end whatever this is you posted :clown:

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

As a tester, I am bad at binary search, and thus found solutions that did not use binary search.

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

"I prefer having an interesting, slightly unbalanced contest over a boring, balanced contest"

Well,I think the contest was pretty interesting. I liked C :)

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

As a participant, I am not asking you to change problem set. I am fine with hard problems. But, my only ask to you is, GIVE POINTS ACCORDING TO DIFFICULTIES. . How big of change is there, if you simplly give more points to harder question ?

Today, C problem was quite difficult, and quite confusing at the same time.

If you have put efforts in making test-cases, and making entire problem-set, we appreciate it. that's why we also don't expect the last minute changes, but changing the points distribution is the least you can do, to make the contest FAIR !!!

All the best for your next problem-set. satyam343, cry.

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

    The painful of "C" problem in this round is very familiar with 961 div 2. But still can't blame all of the responsibility on the Problem Setters.

    Yep totally agree man I just hope to see a "fit" score to expect what kind of beast I'm facing and not totally ruined the problem/contest itself.

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

    Another long night, gonna lose some sleep again...

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

    score distribution is for relative difficulty and not absolute

    I do not believe the score distribution was way off

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

      Let's do basic comparision, 


      let problem = someNewProblem, problemPoints;

if ( difficulty(problem) == usualC_problem) {
    problemPoints = 1500;
} else if (difficulty(problem)  >  usualC_problem) {
    problemPoints = 1750;
} else if(difficulty(problem) < usualC_problem) {
    problemPoints = 1250;
}

      This is my logic to decide points for problem C.

      One can further argue, that what is the UsualC_problem difficulty defined as, anyone who has given descent number of rounds on Codeforces, would know that what an UsualC_problem looks like.

      Now, Please try to see, in first 45 minutes of the contest, how many Div2 people solved C problem ? ( eliminating Div-1 participants ) . Does that tell you, that problem was difficult that UsualC_problem ? For you it might not be, because you are Red, but try to put yourself in others shoes.

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

        I don't think 1500 has to be the "standard C problem score" and it should rely more on the relative ratio between problems, so when problem B has lower score then the harder problems can get less score too.

        But I do agree that the jump from 750 to 1250 wasn't nearly as enough and maybe C — D — E1 could all have like a score of 1500.

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

        Your logic is wrong. It doesn't make sense to compare point values of problems from different CF rounds, because the point values have no meaning on their own.

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

Thank you so much satyam343 for caring to write this blog and to explain the background.

I struggled a lot with C and did not get it eventually. Many thanks again to the problemsetting team cry who brought us this round! It is easy to criticise after having not that good a contest but much more difficult to create something that so many of us participated in and enjoyed.

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

Where's the LeetCode blog link? I'm interested in that.

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

    google "maximum sum of medians", it's literally the first result, and the top comment gives the answer away.

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

To be honest, although this is tougher than I thought, atleast I learn something new over this and I think you guys are trying your best to make this as balance and good as possible. Hope your future round will be improve and don't make a huge mistake like this

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

Pretty amazing Round.No complaints just need to improve my skills :)

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

Generally i think div2Cs are from 1400-1700. So while a bit tougher, I think its ok.

Personally didnt like seeing the disparity between B and C, if B was a bit tougher like 1300 ish than 900-1000 I would be fine.

But well. You make great problems, can't wait for your future rounds orz.

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

Where can you solve bin search?

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

blud fr tells you its ur fault for him making a trash problem XDD

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

Lastly, get good and learn binary search properly.

I don't get why people say this. Once you have learned binary search, you have learned it. Learning how to use it is much different, and imo using it in unique situations is very dependent on IQ.

Like if a 2200-rated div. 2 C had a tricky application of binary search, would you also say "just learn how to use binary search" and call it a day?

Btw, I don't think it was a bad problem. I like when div. 2 C is hard so I don't need to worry about div. 2 D. Anyway, I just think that your comment there is unnecessarily incendiary.

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

    Dudeee.

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

    I feel like you are trolling with this IQ nonsense.

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

      Job productivity and IQ are highly correlated, especially when the job is cognitively demanding. You might expect a correlation of r = .5, when corrected for range restriction, between IQ and performance at a cognitively demanding job.

      Codeforces is more cognitively demanding than pretty much any job out there. That is because people here like to think, and thinking is all people here do (well, except when they're commenting). Therefore, it is not unreasonable to expect a correlation greater than .5 between codeforces skill and IQ. This means that IQ accounts for at least 25% of the variance in codeforces skill. And this is a conservative estimate, too. Now I hope you can see that I'm just spitting facts.

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

Lastly, get good and learn binary search properly.

It reads as if you blame the participants instead of recognizing that this is a bad problem or maybe there are flaws in how you presented the task. You perhaps should have given the participants a few things that could help to do better rather than suggesting they were struggling simply due to a lack of skill.

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

After all that long nonsense. Then at the end, "it's your fault as a participant, you should learn binary search"

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

It's better to have only 2-3k solves on a Div2 C than 9k+ solves like the recent Div2 contests.

Yes, I also agree the rating points for this problem was not enough, but it was still a good problem, nonetheless.

People just love to blame their poor performance or inability to implement a solution on the problem-setters. There was nothing confusing or wrong with this problem.

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

    Why? Don't we have D-F to distinguish between these 9k people?

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

    You are correct. Ideally, it should go

    C — 2k

    D — 500

    E — 40

    F — 0

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

      lol, good one.

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

        Well ofc I am being serious. The point of div. 2 is for div. 1 users to flex their ability to create super hard problems on us noobs.

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

          If you haven't solved E1, just (stop being poor) learn to binary search

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

            bro you only need ABCD + decent time to get a rating over 2100. E1/E2 are overkill for us in Div2

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

              This is a div2 round. The problems should be relevant for a div2 audience, not GMs. Also, this time E1 was on the easier side.

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

                I meant to perform at a 2100 + level, the point is that one is not poor if they failed to solve E1, if they successfully solved E1, they are well on their way to being in Div1

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

The problem itself is great, it's just a poor choice for a div2 C. It's rated somewhere between 1700 and 1800 (likely closer to the latter), and thus putting it into the easy half of the contest targeted at participants up to 2100 seems slightly inappropriate.

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

    That's what I said, but Shreyan "Dominator" Ray doesn't agree to that. donno what to say ...

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

      Please get your argument straight

      I dont want to argue on whether its fine as C or not (honestly i dont care)

      Score distribution wasnt way off, judging problem difficulty from score distribution and then getting annoyed is your issue.

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

You are such a clown for the last line. Let me break what you just said here : the purpose of a problem co-ordinated at certain place is to be solved by targeted rating ranges, In this case by [upper pupils to expert], you can have good 2500 rated Binary search problem in D2C and call participants stupid cause they cant implement it? Such stupidity is unreal.

Down one hour 30 minutes in the contest C had like 900+ submissions is this expected for D2C? You fucked up bro stop being lame. And the average rating is a joke, all thanks to cheaters the average rating of normal C's are 1200 which is stupid to me they are not 1200 problems, and in last 20-30 minutes the submission of C was almost doubled which actually lowered the average. So you better acknowledge what happened here instead of making lame excuses.

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

You did not need Binary Search for C. just use nonsense greedy :)

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

So many people are divided over the last line(of the post). It is also having negative effect on the seriousness of the post

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

problem itself was cool I think, gather all concepts in single problem greedy, binary search, brute force.

just wrong score were assigned

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

can someone prove the fact that one of the two empty subsets must contain only one element? and what would be the final distribution overall, I mean like should it be the maximum element in the empty subset or it might be another element?

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

    The basic outline is as follows: sort your array, take the max and the remaining median (v_i). Now prove we can't do better. Notice that this is the largest answer with the smaller element being v_i. If there's a better answer, the smaller element must be >v_i. Therefore, we should split our array into two sets both with medians >v_i. This is, however, impossible because there aren't enough elements >v_i in the original array (follows from the definition of the median, I'm too lazy to do it here).

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

Stop running away from your responsibilities and blaming it on us.

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

    to be clear i just had to let this line out lol loved the contest.

    great problem, just some shaky scoring.

    btw i love cry i use your template everyday i added you on genshin too

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

You were supposed to use binary search?? I made a completely different solution lol that just used two pointers moving away from the median. I think it was a very cool problem

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

Thanks for the explanation.

But this line: "I prefer having an interesting, slightly unbalanced contest over a boring, balanced contest." — Is a very sketchy one. Usually balanced contests are more fun because there is a chance to solve something outside of your usual level. And such big gaps are a bit problematic.

I personally think C is good. In my, again, personal opinion, it just doesn't really fit inside the given time limit. It's may be more fun to encounter it in Olympiads/rounds with 3 to 5 hours to solve, maybe even on team events. For this Div 2, it was a killer.

*upd: given its score on the distribution, I'll repeat this again.

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

    Counter example : AGCs are hailed to be few of the best contests. They also have some of the most unbalanced distributions.

    I truly believe that in non extreme examples, interestingness is way more important in problems than difficulty balance.

    Sure you might be lucky and have a balanced but also interesting set, however thats quite rare, and to actually manage tbe balance you would have to impact interestingness in some way (either use a easier problem in some position / make a problem artificially harder etc)

    Contests are not just 1 contest and then its over. Its a continuous game and you will eventually reach the rank you deserve :)

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

      What are your thoughts on the weak pretests for this contest's problem A? In the last week's Atcoder regular contest, the first problem had a similar edge case compared to this problem that a lot of people missed initially including you. Imagine if that was a codeforces problem and it passed pretests and then FSTed? Don't you think that there should be strong pretests?

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

        i have looked at the wrong submissions, and the error is not possible to catch without knowing the error beforehand....especially with only having t <= 100 due to it being A

        I dont think this is a case of weak pretests in any ways, but stupid submissions which fail on a very small minority of cases. Do note that the test was introduced through hacks by somebody looking at other people's codes and not intentionally left out. (infact currently systests = pretests + hacks i believe in cf)

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

          I didn't realize it was introduced through hacks, then it makes sense obviously. But if it was intentionally left out, then it would have been a case of weak pretests in my opinion.

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

Thanks for a wonderful contest, but...
Editorial code for Problem C doesn't work for this valid test case

Testcase

satyam343 please look into this.

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

After all these rude and frankly unproductive comments, I would like to share my constructive feedback on this situation.

The primary issue with ratings in general is that it ignores a key component, TIME. Some problems are not necessarily hard, but due to their nature, they take a long time to solve even for high rated participants. This problem C is a good example of that. It was pointed out that the majority of solves came after the first hour. A similar thing occurred on the recent Teamscode contest, which I was a problemsetter for. This contest had way more of the long but not necessarily difficult problem types. Some problems simply have lots of small details that invite buggy code. Of course some high rated participants can process through the details much faster and are able to better avoid buggy code, but these are exceptions. The editorial may have a clean solution, but the majority may have messy implementations.

For the participant, the goal is to simply improve on implementation. However, it would be good for contest quality if this is taken seriously. If a problem is found to be taking testers a long time to solve, it should be reevalutated. Maybe shuffling the problem set for testers would lead to less bias towards earlier problems. The simplest fix is to increase the contest duration. The goal is to try to avoid these situations before it comes to late.

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

Hi, I’m the tester that found the link. I would just like to add that I also found the same problem in Google Kickstart 2022 Round D: Image Labeler.

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

    Also something interesting I just remembered, they actually had a different C1/C2 proposed earlier that had better difficulty balancing in my opinion.

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

I do not know what is the meaning of the array b, could cry give me the answer, thanks

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

Although proclem C is a little bard,but it is also a great round.Hope the round will be better!

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

The problem is great! That is one Div.2 C just slightly harder than expected.

I have a guess about the high difficulty: I have got 7 (or 6) WA2 in the contest until I got AC, and every time I found a different bug. I was astonished that such a bug-rich solution could pass the samples. Such sample isn't unusual, most of the codeforces problems have samples much weaker than this, but this problem is not so easy to code (without a bug) for coders like me. Thus, the problem is not difficult to come up with a solution, but is difficult to think through all the details in the code.

Such problem is necessary in CP. When you encounter a bug, you must find the origin of it. I believe over-debugging is not the reason to consider the problem as "too hard". However, I prefer samples of more strength, as I am novice at debugging :-)

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

Problem C was nice and I am happy to solve this in the contest

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

Satyam why are you running away from the fact that you only assigned 1250 points to C?

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

I found the binary-search solution in like 40 min after the beginning of the contest and then left due to understanding that I have no interest in debugging it for another 1 hour. IMHO, there is no need to include implementation-based tasks like that in short rounds (although the problem itself is great).

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

C was good and not so hard for its position as others claim. There have been harder C's before. Yes it was a bit heavy on the implementation side (and I fucked up since I missed an overflow error) but that aside no reason for people to complain.

The round had cool problems and a good difficulty gradient. Please set more rounds in the coming days.

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

it was a very good level problem everyone stuck on it. but i think we need more problem like that, keep woriking hard nd bring such challenging problem in upcoming contest, at the end all the best satyam343

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

I loved the problem! I just kinda failed to be greedy(until it was nearly too late)....

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

perhaps you might make a C1 like all b[i] equal to 0/1 ?

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

Nah bro whatever, C was shit.

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

Cf

→ Reply