All submissions for this problem are available.
Aishwarya likes experimenting with various things. Once she was taught about the data structure stack in her 10th grade. Amazed by it, she took a sequence of numbers from 1 to N and tried to generate various permutations of it, by using a stack. She did this by randomizing push and print operations followed by a series of pop operations in the end, over the original sequence by scanning it from left to right. She defined a permutation of a sequence called Stack Generatable Permutation(SGP) as a permutation of a sequence which can be generated by the above procedure. Then it came to her mind, how to figure out quickly whether a permutation of a sequence is an SGP or not and how many SGPs starting from a number K can be obtained from a sequence of numbers ranging from 1 to N where 1<=K<=N. You as a nerd are requested to help her.
For example , take N=6 i.e. the sequence 1,2,3,4,5,6. Now consider its permutation 2,4,6,5,3,1. This is an SGP as this can be generated by the following operations, going from left to right:
push 1 => print 2 => push 3 => print 4 => push 5 => print 6 => pop 5 => pop 3 => pop 1
You can consider print as an operation resulting from pushing a number to the stack and immediately popping it out.
The input consists of two parts. In part 1 of the input, the first line contains the number of test cases T1, after which T1 test cases follow. Each test case begins with a line containing numbers N and K separated by a single space, where the next K lines(sub-testcases) contains various permutations of the sequence 1 to N where each number in the permutation has a space following it. After T1 test cases are done the next line contains the number T2 after which T2 test cases follow for the second part of the problem. Each test case in the second part contains two space separated numbers N and K in the first line following which next K lines(sub testcases) contain any one of the numbers between 1 and N.
For each test case in the first part of the problem, for each sub test case output 1 in a single line if the permutation is an SGP else output 0. For the second part for each sub test case output the number of SGPs starting from the given number followed by a new line.
- 1 ≤ T1,T2,N,K ≤ 50
Input: 3 4 3 1 2 3 4 3 2 1 4 2 4 3 1 3 1 1 2 3 6 1 2 4 6 5 3 1 2 4 2 2 3 3 1 1 Output: 1 0 1 1 1 2 1 2
3 2 1 4 is not an SGP because POP operations must be done in the end only
|Time Limit:||0.178082 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.