Kita's blog

Codeforces Round #866 problem C
By Kita, history, 22 months ago, In English

Hey guys

if anyone wanted a video editorial for today div2 problem C I made one and posted onto youtube

Video

Thank you!

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

Comments Comments (2)
| Write comment?
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you explain a bit more about the (mex+1 < number of elements) in the array?
Thanks

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

    Hey! so you can keep a list of what numbers you need to increase the mex and if you have just one more you need, you can change a number into the number you need and you are done right? for example 0 1 2 3 4 5 100 => you want MEX 6, you have 0-5 so all you need is 6, so change the 100 to 6

    but that relies on you having something to change. for example 0 1 2 3 4 5 => you want MEX 6. You have 0-5 so all you need is 6, but you can't change anything else to get a 6 because that means you lose one of the 1-5.

    So, you have to check whether you have sufficient number of elements to get your mex+1. If you have < k elements in an array, you can't have MEX of k. So, you need to check if the number of elements is > mex+1, otherwise you can't achieve mex + 1.

    Hope this helps!

    → Reply