how binary search solves the problem…
binary search can be used to solve greedy problems how??
plz give logic and some expamle
Logic not clear
what is the increaing function in this problem?
Binary search is not the greedy aspect. Getting the answer for a particular amount of moves is the greedy part. Binary search is a generic approach, you see that the answer can lie in some range and that the answer has some property. For example in this case it is an increasing function.
What they mean by increasing function is that , if you can sort the deck with some x moves, then you can definitely sort the deck in some y moves where y>=x, and we need to find the minimum x for this.
Sir how this problem is a greedy problem?
plz help me with code of this problem.
Its greedy because for a particular amount of moves we do it greedily.
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.
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
i am clear with binary search part…
but in last paragraph
not clear with this line.
what I understood is to check for x operations if we check that indices of 1 should be <=x and then keep on increasing till the size of pile that is n… is it right?
Yeah basically x is the number of cards you choose to take in hand.So the more number of cards you pick the easier it gets. That’s all there is to it. So just find the minimum x
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.