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 formulaconsidering 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 N1 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 N1 number that have 2 ways to put, so by multiplication rule of combinatorics the answer is 2^{N1}, finally we should subtract 2 from the answer because permutations 1 2 3 4 .... N and N N1 ... 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 2^{N1}2 for all N>1 and 0 for N=1 algorithm for calculating the formulaan O(n) algorithm for calculating the formula would get the score of only the first subtask 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 2^{N} = 2^{N/2} * 2^{N/2} if N is even, in this case we only need to recursively calculate 2^{N/2} once then squaring it. if N is odd it's very similar, we have 2^{N} = 2^{(N1)/2} * 2^{(N1)/2} * N so we only need to recursively calculate 2^{(N1)/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:
SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 04 Nov '16, 19:41

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 N1 ... 3 2 1 answered 05 Dec '16, 11:32

@arpit728 we can not include 1,2,3,...,N and N,N1,...,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

@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 :
If wrong , why? answered 17 May, 20:00

@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 N1 ... 3 2 1