Alternating PermutationsProblem code: SNCK03 |
All submissions for this problem are available.
[Problem Idea : Varun Jalan]
You are given K indices, A[1], A[2], ... , A[K].
A[1] < A[2] < ... < A[K].
A[1] = 1 and A[K] = N.
A permutation of the numbers between 1 and N is called valid if :
The numbers in the permutation between indices A[1] and A[2] (inclusive) form an increasing sequence, the numbers in the permutation between indices A[2] and A[3] (inclusive) form a decreasing sequence, those between A[3] and A[4] (inclusive) form an increasing sequence and so on.
Count the number of valid permutations.
Input:
There will be multiple test cases. The first line contains the number of test cases T. There follow 2*T lines, 2 lines for each test case. The first line for each test case contains the numbers N and K. The second line contains K space seperated numbers, ie. A[1] to A[K].
Output:
Output T lines, one for each test case. All answers should be output modulo 1000000007.
Constraints :
T <= 111
2 <= N <= 20000
2 <= K <= 22
K <= N
A[1] < A[2] < ... < A[K].
A[1] = 1 and A[K] = N.
Time Limit : 20 seconds.
Sample Input :
3 3 3 1 2 3 4 3 1 3 4 10 6 1 2 5 7 8 10
Sample Output :
2 3 6166
Note :
For the first test case,
(1 3 2) and (2 3 1) are the valid permutations.
For the second test case,
(1 2 4 3), (1 3 4 2) and (2 3 4 1) are the valid permutations.
| Date: | 2009-11-13 |
| Time limit: | 20s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions 
I am not able to sign in from
in second test case 'k' no.
6166 permutations for 6
6166 permutations for 6 numbers? only 720 permutations are possible...
@ Shitij You need to sign in
@ Shitij
You need to sign in from your team account.
The second test case is
The second test case is correct.
There are K=3 indices given and the line following it contains the indices values.
For k=2,shouldn't the 2nd
For k=2,shouldn't the 2nd permutation be (1 4 3 2) instead of (1 3 4 2) ??
behen ke lode english seekh
behen ke lode english seekh phir humse question kar vaiyo madar chode bhosdi kay........!!!!!!!!!
behen ke lode english seekh
behen ke lode english seekh phir humse question kar vaiyo madar chode bhosdi kay........!!!!!!!!!
the max indice A[K]=N
the max indice A[K]=N possible is 20,000...does that mean that the max length of the permutation is 20,000 !
@ BBDNITM You have to output
@ BBDNITM
You have to output your answer modulo 1000000007
For k=2,shouldn't the 2nd
For k=2,shouldn't the 2nd permutation be (1 4 3 2) instead of (1 3 4 2) ??
what is meant by modulo
what is meant by modulo 1000000007
@arun garg : divide the count
@arun garg : divide the count by 1000000007 and take the remainder. thats the answer.
@ random : are you refering
@ random : are you refering to the 2nd test case ?
yup....for 2nd case
yup....for 2nd case 1(increase)->4 (decrease)-> 3
instead of what is given 1(increase)->3(increase)->4..
@ random I think the given
@ random
I think the given sample output is correct for the second case you mentioned.
(1 3 4 2) makes sense as 1, 3, 4 is an increasing subsequence in indices [1..3]
and 4, 2 is a decreasing subsequence in indices [3..4]
Can someone change our
Can someone change our display name from my email address to our actual team name, "Audrey Horne"?
I can't do it with "Edit Profile".
Thanks,
Frank
Can someone change our
Can someone change our display name from my email address to our actual team name, "Audrey Horne"?
I can't do it with "Edit Profile".
Thanks,
Frank
cc
cc