Codeforces 564A problem

#1

Is there any alternative video. sound is in this video is very low

#2

hi @ashwani225 please use a volume booster extenstion on your browser

#3

Hey can you provide me question link

#4

@ashwani225 https://codeforces.com/contest/1172/problem/A

please mark your doubt as resolved in case of no further queries :slight_smile:

#5

Please can you explain the logic in simpler way due to sound problem I am unable to get it

#6

@ashwani225 https://chrome.google.com/webstore/detail/volume-booster/ejkiikneibegknkgimmihdpcbcedgmpo use this volume booster, the sound will become clear.
If you are using some other browser you can look for a voume booster extenstion for that

#7

I have used that but then also voice is not much clear. I think there may be some problem with my laptop also. so if you explain this then it will make lot of help .

#8

@ashwani225 You can use the CB mobile app if there is a problem with your laptop. Logic for the problem:

The idea is that if you want to place a particular card at the bottom of the pile, you need to have it in your hand beforehand. The other major point to notice is that you’ll have to place all the cards upto card n in a sequential manner. If you miss any 1 card from the sequence (cause you don’t have it), you’ll have to place and pick all the cards again (this time some different placing and picking pattern) until you reach at the same position and now you have the required card in your hand.

Another point to notice is that worst case would be to place all the zeroes in the sequence and pick all the n cards. After at most n operations, you have all the card from 1 to n in your hand, and you need more n operations to place it in a sequential manner.
So 2*n is the worst case scenario, i.e, when you have all the blank cards in your hand and the cards in the pile are arranged in descending order.

We’ll use the idea of binary search here. If the pile can be arranged in x operations, it can definitely be arranged in more than x operations. We need to find out the min value of x such that we are able to build the pile in x operations.

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.

If this can be done using x operations, we’ll check for operations lesser than x(using binary search)

Here check this submission https://codeforces.com/contest/1173/submission/55422470

So we are doing binary search basically on how many blank cards we have to play, that can be from 0 to n(in the worst case), because by then you will have all cards in your hand. Then an additional n moves to place the cards in hand in pile in order

#9

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.