I need help to understand the concept of this “Nauuo and Cards” problem. Because I’m kinda lost in the middle of this video. So I would like to converse with someone who knows the problem very well.
Thank you.
Nauuo and Cards- Greedy Concept
Hey @Kinjal 
I would suggest you to drop a mail at [email protected]
And tell all the issues you are facing during this course. Happy to help
Bhaiya, my doubt is that I’m struggling to understand the concept of this problem so I need TA support to guide or help me to solve this problem. There is nothing to do with coding blocks support on that.
You’re not helping, you don’t even get my doubt. It’s a problem from codeforces and it’s a div 1 problem. And, I’m not getting the concept of this problem so I need help from TA Support. Now, if you understand what I’m trying say.
I am really sorry @Kinjal , I actually merged two doubts and gave you this reply. Just give me some time , I will send you a detailed explanation as soon as possible. Just be a little patient
Okay. FYI, I have been trying to understand the crux of this problem from past 2 days and I haven’t understand yet, how to solve it. I have some basic doubts to clear on this problem so I seek for an assistance to which I can talk to.
Okay, first give me your explanation on this problem.
I was typing for the same, just have patience cause I will give you detailed one
Okay bhaiya…
My first doubt is, If Nauuo, the girl in this problem do one operation,
“In one operation she can choose a card in her hands and play it — put it at the bottom of the pile, then draw the top card from the pile”
Is it mean that the two operation bound to happen together or we can do that individually?
Two operations: 1. take the top card from the pile and put it on her hands.
2. put a card from her hands to the bottom of the pile.
So read this comment quite carefully @Kinjal,
the aim of this problem is to tell the number of operations that Alice can perform to achieve a configuration where pile is i increasing order.Right?
So Alice has n cards in an array a[] and n cards in an array b[] and it’s assured to you that every elements from 1,n is present in either array a[] or array b[] (this is for sure).
So the operation you are allowed to perform is that:
pick one element from top of the pile and add it into array a[]
and then pick some other element from array a[] (not the top element from pile) and insert it into bottom of the pile. Such that you can attain increasing order in pile.
It means that when alice takes a card from top of the pile and add it into the array a[] it’s one operation and the second operation will be , when alice picks Biggest element from that array and add it into bottom of that pile as resultant pile should be in increasing order from top to down.
Now tell me is it clear till now?
Yeah and I need to verify that both array a[] and b[] have fixed size n and both array has mixed of zero and non-zero elements. Right!!
And, both the operation occurs in parallel, right!!
okay bhaiya, go on…
So now you tell me , how will you approach this problem?
So it means that to store n elements in the array b[] at the end will be like this:
b[1]=1,
b[2]=2,
…b[n]=n, at the end.
or, b[0]=1,b[1]=2…b[n-1]=n, at the end.
And, that’s my task. I guess.
Sanyam Bhaiya told me on the video about applying binary search which either return 0 or 1 for every element [0 to n] but I don’t know how and why.
My brute force approach will be, first take all the non zero elements move to the array a[] so that array a[] looks like a[0]=1, a[1]=2, a[2]=3,… a[n-1]=n and array b[] has all the zero elements.
After, all the non zero elements in the array a[] and all the zero elements in the array b[], now I will have “move” operation will be like,
a[0] -> b[n-1] where, a[0]=1 and shift b[n-1] element to b[n-2] and place a[0] element to b[n-1]
a[0] <- b[n-1] where, b[n-1]=0 and place it to a[0]
and these 2 move operation will happen for 0 to n times.
See it’s not necessary that the order of your array a will be like this a[0]=1, a[1]=2, a[2]=3,… a[n-1]=n it can be in any order , but your approach when you use brute force will always give you an answer of 2*n , whereas you have to tell minimum operations not maximum. Brute force is no doubt will be the ideal approach. Okay so if it’s tough for you to understand the code, why don’t you dry run it. As it will clear all of your doubt.