Codeforces Div-1 Problem Concept

#1

So I code this problem with explanation but I need to verify my explanation that if I understood the concept right way or not.

#2

Yes the concept is applied correctly.

#3

Bhaiya, can you kindly tell me that my explanation with the code is correct or not!

#4

Yes w.r.t. that only I said, you can submit it on codeforces if you want to check that it passes the testcases or not.

1 Like
#5

Yeah, I checked with 3 test cases which was given in the problem. And bhaiya, I have read your previous explanations on this problem and you were talking about one corner case on this problem, so can you kindly elaborate that corner case of this problem?

You said like,

So this is how we check it for x operations :- If the pile can be built in x operations, x will always be greater than n(except for one corner case that I’ll discuss later). So the last n operations would be to put all the cards from 1 to n in the pile. We’ll talk about the last n operations. In the 1st operation of the last n operation (overall x-nth operation), we must be able to place the card ‘1’ in the pile. This would be possible if the occurence (index) of card ‘1’ in the array ‘b[]’ is less than (x-n) ,similarly for card 2, the index in array ‘b[]’ is less than x-n+1 and so on upto card n. We’re just checking whether we have the card in hand or not before placing.

#6

I think that the ideal case is the corner case when we don’t need to bring over all the non-zero elements from array b[] to an array a[]. Otherwise, it will take extra n operations. I think, that’s the corner case here.

#7

Sorry for the late reply. Yes that was the case.

#8

Okay!
So, when ideal case fails then surely we are applying binary search to this problem and the total minimum number of operations is required like (n+x). Right!!!
So, what is x means from your point of view?

#9

I didn’t understand , x was the cards we played out na? So we binary searched on that.

#10

yeah, x number of cards we played out from our hand i.e. from the array a[]. Right!!!
And what kind of x number of cards we played out, is it zero or non-zero element of cards?

#11

We play out Blank cards.

#12

So it means that after x number of cards played out, all the non zero elements from 1 to n will present in my hand or in array a[] and in the pile or in b[] contains all the n number of blank cards.
Right!!

#13

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.