Shayan's blog

Codeforces Round 978 (Div. 2) — Video Tutorial
By Shayan, 6 weeks 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
  • +39
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

Second comment XDDD

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

Nice contest,but didn't have chance to take part in it.

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

Hard D2, but really amazing.

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

B was a very bad problem.

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

    So true. It seemed like only those who were already aware of the greedy algo could solve it.

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

any ideas for D2 anyone ?

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

For solving D2, you gotta make three key observations:

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

    Dang, I was so close to getting it :(. Thanks for the solution though!

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

    How about n=3?

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

      for n = 3, the minimum number of queries is actually 4. This is the only case where you have to ask > n queries. For every n > 3, you can solve it with atmost n queries.

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

      So what actually is the issue in the logic?

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

      got it

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

    I also want know about your proof!.

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

      ??

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

    Bro thinks he's Pierre de Fermat lol.

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

Where is text editorial :(

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

nice problemset, thankyou

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

So，how can I see the text version of the solution？

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

did author forget about the text tutorial?

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

D2 is really interesting I think though I didn't participate

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

I am not unable to understand how the solution of question B works :(

→ Reply