Shayan's blog

Codeforces Round 978 (Div. 2) — Video Tutorial
By Shayan, 23 hours ago, In English

Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.

2022A — Bus to Pénjamo

Video

2022B — Kar Salesman

Video

2022C — Gerrymandering

Video

2022D1 — Asesino (Easy Version)

Video

2022E1 — Billetes MX (Easy Version)

Video

2022E2 — Billetes MX (Hard Version)

Video
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
22 hours ago, # |
  Vote: I like it -17 Vote: I do not like it

Second comment XDDD

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

    Thank to this contest which give me a chance to CM qwq

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

      Congra XD

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

      you are so strong！！

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

Third Comment xDDDDD

→ Reply
»
21 hour(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Oh! nice. Contest was at 1AM IST. Most Cheaters from India could not have participated.

→ Reply
»
21 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hard D2, but really amazing.

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

Is the n limited to 69 people in D1, because it says the limit of n<=10^5?

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

hey,can anyone provide me the problems of same type of b,c and d here?i would be grateful

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

B was a very bad problem.

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

To all those who are downvoting this blog, please understand that this is not the official editorial and this guy had nothing to do with the preparation of the problems to be used for the round.

→ Reply
»
18 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

any ideas for D2 anyone ?

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

For solving D2, you gotta make three key observations:

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

For B, I'm taking the max x elements from the array and choosing them (subtracting them by the minimum of this subarray), sorting the array again and then repeating until all elements are zero. It's failing at some 294th testcase, why?

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

    Consider n = 3, x = 2 and the Elements {2, 2, 2}

    According to your approach you would remove (seconds, third), (seconds, third), (first), (first) giving you an answer of 4.

    Whereas you can pair up (first, second), (first, third) and (second, third) giving you ans answer of 3.

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

      So what actually is the issue in the logic?

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

        Issue is, you do not want to make a number 0 when you can decrement other numbers. This is done to ensure that you keep as many different models as possible to choose from. The brute force logic will be to keep sorting the array, taking largest x (or all if count is less than x) non-zero elements of the array and decrement them by 1. This needs to be repeated until all elements become 0. Obviously this will give TLE as array elements can go upto 10^9.

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

        Issue is that the pairing logic its in the update rule you are taking maximum X elements and then removing minimum of these each step.

        You logic works like this for {2,2,2}

        Take {2,2} and make it {0, 0}

        Now we have {2, 0,0} then -> {1, 0, 0} then -> {0, 0, 0}

        But if we look at one decrement at a time take {2,2} in the first pairing decrease it by 1, {1,1} now the maximum 2 elements are {2,1} instead of {1,1} which will end up giving the right answer.

        Your logic implicitly assume that the maximum elements don't change during the min(max k elements) operations, but if you work this out as shown above then you can see that they do change. So you would have to change your algorithm to account for that.

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

I thought for a few hours and believe that I've got a perfect proof for problem B. But the comment section is too small and I can't write it down.

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

    I also want know about your proof!.

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

      Hell. I discovered that my proof is almost identical to the video tutorial. But, anyway, the proof framework for this problem is very advanced. You should try to play with it a bit.

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

    Bro thinks he's Pierre de Fermat lol.

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

indeed a good contest and problem c was nice. cheater count was significanlty less, maybe because most of the cheaters were sleeping

→ Reply
»
14 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Got stuck at B, luckily I solved D1 very quickly so I didn't lose points. At least I learned something new, cool problems!

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

Shayan Why do we need to remove edge in E2 ?

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

People are saying that problem B is quite a famous and standard prob. Can someone suggest some sources where I can make myself familiar with more of these famous and standard problems? Thanks!

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

    its just greedy, We just get the maximum as it should be different cars, then divide by the given limit X, add 1 if remainder. I dont think its even a standard problem. If so, i would also like to know how.

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

      Watch Shayan's Stream. He says that it is a famous prob. Many in the comments were also saying the same.

      → Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is text editorial :(

→ Reply
»
10 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

nice problemset, thankyou

→ Reply