CodeChef is a non-commercial competitive programming community
Login
Username (New User? Signup) Password (Forgot Password?)
Signup
Login or
Signup with
Connect
Note
  • Publicize your achievements on your Facebook Wall.
  • Challenge your friends or ask them for help.

Site Navigation

  • PRACTICE
    • Easy
    • Medium
    • Hard
    • Challenge
    • Peer
  • COMPETE
    • February Long Contest
    • January CookOff
    • January Long Contest
  • DISCUSS
    • Wiki
    • Forums
    • Blog
    • Twitter
  • COMMUNITY
    • CodeChef Meetups
    • Campus Chapters
    • Host your Contest
    • User Groups
    • CodeChef TechTalks
    • All Educational Initiatives
    • Event Calendar
  • HELP
    • Frequently Asked Questions
    • FAQ for problem setters
    • Problem Setting
    • Ranks
    • Tutorials
  • ABOUT
    • About CodeChef
    • Team CodeChef
    • Press Room
    • CodeChef Financials
    • CodeChef Sponsorships
    • CEO's Corner
    • Contact Us
    • About Directi
Home » Compete » Codechef Campus Snackdown » Alternating Permutations

Alternating Permutations

Problem code: SNCK03

  • All Submissions

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: 20

s
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


  • Submit

Comments

  • Login or Register to post a comment.

I am not able to sign in from

Shitij @ 21 Nov 2009 07:09 PM
I am not able to sign in from my USITHawks account correctly. When I (or my team mates) try the site shows us to be signed in from some other account........please fix it asap, coz we'll not be able to make submissions till then......

in second test case 'k' no.

STL_Tweakers @ 21 Nov 2009 07:38 PM
in second test case 'k' no. of elemnts in an array are 3 then how '1 2 3 4' came in it voilates the value of k as it should have 3 elemnts and permutation formed are of 4 elemnts

6166 permutations for 6

socialcoders @ 21 Nov 2009 07:43 PM

6166 permutations for 6 numbers? only 720 permutations are possible...

@ Shitij You need to sign in

admin @ 21 Nov 2009 08:06 PM

@ Shitij

You need to sign in from your team account.

The second test case is

admin @ 21 Nov 2009 08:12 PM

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

random @ 21 Nov 2009 08:34 PM

For k=2,shouldn't the 2nd permutation be  (1 4 3 2) instead of (1 3 4 2) ??

behen ke lode english seekh

busted @ 21 Nov 2009 08:57 PM

behen ke lode english seekh phir humse question kar vaiyo madar chode bhosdi kay........!!!!!!!!!

behen ke lode english seekh

busted @ 21 Nov 2009 08:57 PM

behen ke lode english seekh phir humse question kar vaiyo madar chode bhosdi kay........!!!!!!!!!

the max indice A[K]=N

BBDNITM @ 21 Nov 2009 09:22 PM

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

admin @ 21 Nov 2009 09:29 PM

@ BBDNITM

You have to output your answer modulo 1000000007

For k=2,shouldn't the 2nd

random @ 21 Nov 2009 09:34 PM

For k=2,shouldn't the 2nd permutation be  (1 4 3 2) instead of (1 3 4 2) ??

what is meant by modulo

arun garg @ 21 Nov 2009 09:48 PM

what is meant by modulo 1000000007

@arun garg : divide the count

syco @ 21 Nov 2009 10:23 PM

@arun garg : divide the count by 1000000007 and take the remainder. thats the answer.

@ random : are you refering

syco @ 21 Nov 2009 10:38 PM

@ random : are you refering to the 2nd test case ?

yup....for 2nd case

random @ 21 Nov 2009 10:40 PM

yup....for 2nd case 1(increase)->4 (decrease)-> 3

instead of what is given 1(increase)->3(increase)->4..

@ random I think the given

bigred @ 21 Nov 2009 10:57 PM

@ 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

AudreyHorne @ 21 Nov 2009 11:06 PM

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

AudreyHorne @ 21 Nov 2009 11:26 PM

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

code easy @ 23 Feb 2010 07:04 AM

cc

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

Programming Competition Fetching successful submissions
Directi Go for Gold
CodeChef is a global programming communityCodeChef hosts online programming competitions
CodeChef is a non-commercial competitive programming community
  • About CodeChef
  • About Directi
  • CEO's Corner
  • C-Programming
  • Programming Languages
  • Contact Us
© 2009 Directi Group. All Rights Reserved. CodeChef uses SPOJ © by Sphere Research Labs
In order to report copyright violations of any kind, send in an email to copyright@codechef.com
CodeChef a product of Directi
The time now is:
CodeChef - A Platform for Aspiring Programmers

CodeChef was created as a platform to help programmers make it big in the world of computer programming. At CodeChef we work hard to revive the geek in you by hosting programming contests on a monthly basis. We also aim to have training sessions and events related to online programming for programmers around the world. Apart from providing a platform for programming competitions, CodeChef also has various tutorials and forum discussions to help those who are new to the world of computer programming.

Practice Section - A Place to hone your 'Computer Programming Skills'

Try your hand at one of our many practice problems and submit your solution in a language of your choice. Our judge accepts solutions in over 35+ programming languages. Online programming was never this much fun! Receive points, and move up through the CodeChef ranks. Use our practice section to better prepare yourself for the multiple programming competitions that take place through-out the month on CodeChef.

Compete - Monthly Programming Contests and Cook-offs

Here is where you can show off your computer programming skills. Take part in our 10 day long monthly programming contests and the shorter format Cook-off programming contests. Put yourself up for recognition and win great prizes. Prizes worth up to Rs.20,000 and $700 are up for grabs every month along with lots more CodeChef goodies.

Discuss

Are you new to computer programming? Do you need help with algorithms? Then be part of CodeChefs Forums and interact with all our programmers love helping out other programmers and share their ideas.

CodeChef Community

As part of our Educational initiative, we give institutes the opportunity to associate with CodeChef in the form of Campus Chapters. Hosting online programming competitions is not the only feature on CodeChef. Be a part of the CodeChef community through CodeChef meetups and techtalks. You can also host a programming contest for your institute on CodeChef and be a guest author on our blog.

Domain Name Registration, Web hosting, and Website Design provided by BigRock.com