CPERM - Editorial

combinatorics
cperm
easy
editorial
fast-expo
nov16

#1

PROBLEM LINK:

Practice
Contest

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 “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.


#2

@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


#3

@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.


#4

@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?


#5

@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


#6

@srd091

Thanks.