Saksham_Sahgal's blog

By Saksham_Sahgal, history, 20 months ago, In English

Can anyone tell me how the output of Test case 3 of Problem is —

9 9 9 15 15 6 -1 -1 6 -1 -1 -1 -1 6 15

and not —

9 9 9 -1 8 6 -1 -1 6 -1 -1 -1 8 6 8

the as far as i understand — i have to perform N moves , where -

  1. Draw the topmost card from the deck. Let X be the integer written on it.
  2. Then i will find a stack of upfacing cards with the smallest integer greater than or equal to X written on and and i will put this X card into that stack .
  3. if there is not such stack then i will put this card into a new stack.
  4. if any stack has k cards i will eat that stack.

for input —

15 3 3 14 15 9 2 6 5 13 1 7 10 11 8 12 4

According to me the steps should look like —

  • 3 (new stack)
  • 3 14 (two new stacks)
  • 3 14 15 (three new stacks)
  • 3 ( 14 9 ) 15 (9 goes to stack 2)
  • (2 3) ( 14 9 ) 15 (2 goes to stack 1)
  • (2 3) ( 6 14 9 ) 15 (6 goes to stack 2)
  • now stack 2 to is eaten because it has size = 3 (therefore 6 , 14 , 9 is eaten at step 6)
  • (2 3) (5 15) (5 goes to stack 3)
  • (2 3) (13 5 15) (13 goes to stack 3)
  • now stack 3 to is eaten because it has size = 3 (therefore 13 , 5 , 15 is eaten at step 8)
  • .
  • .
  • . -and so on..

can anyone tell me where i am getting it wrong? thanks in advance

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
20 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You can go through the array and that is what you will get at the end.

3 14 15 9 2 6 5 13 1 7 10 11 8 12 4
3 2 1 -> 9
14 9 6 -> 6
15 5 4 -> 15
13 7
10 8
11
12

Imagine every value that you add to the stack becomes a representative of the stack and numbers only less than representative can go into that stack. While you add 13 to the (5, 15) stack: 13 > 5