NOVICE43 - Problem 3

no tags 

 

When I first learned backtracking I made a program to find all the permutations of the English alphabets in lexicographically increasing. Filled with elation I showed the program to Rohil. Rohil being someone who likes to do stuff off the league was not impressed and gave me the following variation of the problem help me to solve the problem:
You have to find the number of permutations of length N(1<=N<=12) such that at whenever an alphabet say($) appears in the permutation all the alphabets smaller than $ should have appeared before it at least once. An alphabet is smaller than another if it appears before the other in the English alphabet. ‘a’ being the smallest and ‘z’ being the largest. For example when N=2 then aa,ab are the only valid permutations and ba,bb is invalid since in ba all the alphabets smaller than b have not appeared at least once before it. See example for further clarification.

When I first learned backtracking I made a program to find all the permutations of the English alphabets in lexicographically increasing. Filled with elation I showed the program to Rohil. Rohil being someone who likes to do stuff off the league was not impressed and gave me the following variation of the problem help me to solve the problem: 

You have to find the number of permutations of length N(1<=N<=11) such that at whenever an alphabet (say 'c' ) appears in the permutation all the alphabets smaller than 'c' should have appeared before it at least once. An alphabet is smaller than another if it appears before the other in the English alphabet. ‘a’ being the smallest and ‘z’ being the largest. For example when N=2 then aa,ab are the only valid permutations and ba,bb is invalid since in ba all the alphabets smaller than b have not appeared at least once before it. See example for further clarification.

Input

Line 1: T(no. of test cases)

Line 2: n1

Line 3: n2

Output

Line 1: no. of such permutations of length n1

……

…..

Example

Input:
2
2
3

Output:
2
5
Explanation for N=3, the possible permutations are:
abc
aba
abb
aab
aaa

hide comments
sagar_june97p: 2019-06-14 16:53:42

AC in one go.!!
Answer fits int well.

megumitadokoro: 2018-04-02 16:06:43

Basically, there are 11 possible values of n, which means you can do the backtrack. Or you can precalculate the answer and get AC in O(1).

anubhawiiitu: 2017-12-15 12:40:06

Answer for n=11 will be 6785**

Last edit: 2017-12-15 12:40:28
ssunitk: 2017-05-12 11:55:30

@Mahesh_Chandra_Sharma why its showing tle...with n^2, or O(11*11), infact it is showing tle also when i am storing the value of ans for all n=11 and then just using that array to output could u check my submissions
19389256 or 19389286 or 19389375 or 19389405

akshayvenkat: 2016-07-05 20:05:20

what are the permuations for N=4 ? can someone list them out please?

Anant Upadhyay: 2015-09-13 17:20:33

easy!

:.Mohib.:: 2015-06-07 15:06:42

Easy one.. ;)

cenation: 2014-12-16 08:53:07

easy ..........

Levon: 2014-03-24 17:49:49

@technophyle
no

technophyle: 2013-06-22 03:25:59

The answer for N=11 is 6785**


Added by:Mahesh Chandra Sharma
Date:2011-03-01
Time limit:0.379s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:NSIT Noivce contest #4