You are not logged in. Please login at to post your questions!


CPERM - Editorial







Combinatorics, Fast Expontiation


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


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 ""

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){
        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


Can be found here.


Can be found here.

This question is marked "community wiki".

asked 04 Nov '16, 19:41

kingofnumbers's gravatar image

6★kingofnumbers ♦
accept rate: 12%

edited 16 Nov '16, 13:43

admin's gravatar image

0★admin ♦♦


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) arpit7282★


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

arpit728's gravatar image

accept rate: 10%

@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

srd091's gravatar image

accept rate: 42%




(05 Dec '16, 14:46) arpit7282★

@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

u_117_a's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 04 Nov '16, 19:41

question was seen: 3,596 times

last updated: 17 May, 20:00