×

Easy

# PREREQUISITES:

Combinatorics, Fast Expontiation

# PROBLEM:

Given an integer N, count the number of permutations that is increasing up to a certain point then deceasing after that.

# EXPLANATION:

## finding the formula

considering that this problem is requiring us to count something and that the constraints on N is very high this will hint us that the solution will be probably using combinatorics

let's say that we have an empty array of length N and we want to put the numbers from 1 to N in this array and satisfy the problem requirements, now let's say we want to add the number 1, we have N ways to put this number on the array but if we notice that we should not make 3 consecutive numbers such that the one in the middle is the minimum number among these 3 numbers then we will know that we cannot put the number 1 on any cell except the first and the last cells, because otherwise the number 1 will be in the middle of two bigger number eventually. So in conclusion we have only 2 possible ways to put the number 1, since we have put it in a border cell then we can imagine that we have an array of length N-1 and now we want to put the number 2, again for the same reasons we have two ways and so on, until we want to put the number N we will only have 1 way instead of 2, so we have N-1 number that have 2 ways to put, so by multiplication rule of combinatorics the answer is 2N-1, finally we should subtract 2 from the answer because permutations 1 2 3 4 .... N and N N-1 ... 3 2 1 should not be counted. we also should treat the case N=1 alone because those two permutations become the same so we should subtract 1 instead of 2

to sum up, the answer is 2N-1-2 for all N>1 and 0 for N=1

## algorithm for calculating the formula

an O(n) algorithm for calculating the formula would get the score of only the first sub-task so we need a faster way to compute it, fortunately there's O(log n) algorithm for it which is called "Exponentiation by squaring", you can find details about it here "https://en.wikipedia.org/wiki/Exponentiation_by_squaring"

the algorithm works by observing that 2N = 2N/2 * 2N/2 if N is even, in this case we only need to recursively calculate 2N/2 once then squaring it. if N is odd it's very similar, we have 2N = 2(N-1)/2 * 2(N-1)/2 * N so we only need to recursively calculate 2(N-1)/2 then square it then multiply it by N

since we always divide N by 2 then this algorithm takes only O(log N) steps

pseudo code:

power2(int N){
if(N==0){
return 1
} else if(N is even){
int H=power2(N/2)
return H*H
} else {
int H=power2((N-1)/2)
return H*H*2
}
}


# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

194824
accept rate: 12%

19.3k348495534

@kingofnumbers

Can you please explain the logic of subtracting 2 in more detail I couldn't understand.

Why we cannot include this. 1 2 3 4 .... N and N N-1 ... 3 2 1

(05 Dec '16, 11:33) 2★

 0 @kingofnumbers Can you please explain the logic of subtracting 2 in more detail I couldn't understand. Why we cannot include this. 1 2 3 4 .... N and N N-1 ... 3 2 1 answered 05 Dec '16, 11:32 2★arpit728 683●12●51 accept rate: 10%
 0 @arpit728 we can not include 1,2,3,...,N and N,N-1,...,3,2,1 because in these two permutations there is no i exists that satisfies the given condition, as the first one is strictly increasing and the next one is strictly decreasing. answered 05 Dec '16, 12:05 5★srd091 1.6k●1●11 accept rate: 42% 2 @srd091 Thanks. (05 Dec '16, 14:46) arpit7282★
 0 @kingofnumbers Can we see the way to find the answer in some other way i.e. can't we not take it as a sum of combinations like this :  (n-1)C(1)+(n-1)C(2)+ .... + (n-1)C(n-2)  If wrong , why? answered 17 May, 20:00 2★u_117_a 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,010
×3,408
×768
×150
×86
×10

question asked: 04 Nov '16, 19:41

question was seen: 3,596 times

last updated: 17 May, 20:00