i did not understand the approach to this problem. i looked at editorial on codeforces but still couldn’t understand. Can someone please provide a detailed explanation ?
Greedy approach in " Nauuo and cards " problem from codeforces
did you get the concept of upper bound?
that the answer would never exceed 2n.
(if not, its not that difficult, see the number of zeroes she has = the number of non zero entries in pile. so whenever she get a nonzero entry from top, she will put a zero on bottom. and whenever she get a 0 from top, it will be replaced by 0 until all the elements in the pile are 0. this will take max n steps, ie one iteration of whole pile. now pile has all 0’s and she has all non zeros. so she can put the numbers in the order in the pile which will take another n steps. which means max of 2n steps)
now you know upper bound is 2n. and min answer can be 0 when pile is already arranged as required. so you can apply binary search.
but how to apply it. how to write check function that decides the movement to first half or second half. right?
think about some examples and try to solve them manually.
you will realize that in most of the cases, to arrange the numbers, you need to put all the numbers from 1 to n in the pile from bottom. means after some steps, you need to form your solution from bottom.
say after x steps you decided to form solution. then after x step you must have 1 in your hand to put it in bottom. then after x+1 steps you must have 2 in your hand to put it in bottom(if you don’t have a 2, you will put another number and sequence will be disturbed which will cost you another iteration and that will result in more than 2n solution), so after x+2 step, you must have 3 in your hand and so on…
so your answer is x+n(you decided after x step and n step to form solution.)
in the check function of binary search, you need to verify that after x+i steps , you must have i in her hand.(what is x? in binary search you always decide the solution as mid, so n+x = mid, x = mid-n).
how to know if we have i at x+i step? so you just need to check where is i in the pile initially, say it is at distance d, then replace everything with 0 as discussed earlier, after d steps you will have i, and if d<=x+i, you will have i at x+ith step.
now watch the video again and try to code it yourself.
thanks
5 Likes
I have seen the video after reading your explanation.But can you give some pseudocode for the problem for better understanding and writing the code correctly. @gauravshukla789
it is highly recommended that you try writing the code yourself, then if you have trouble in your code, I will help you in fixing that.
give it a try, its not that hard, you just need to write check() function of binary search.
thanks.