PROBLEM LINK:
DIFFICULTY:
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 “Exponentiation by squaring - Wikipedia”
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.