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

×

CPERM - Editorial

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

This question is marked "community wiki".

asked 04 Nov '16, 19:41

kingofnumbers's gravatar image

6★kingofnumbers ♦
194824
accept rate: 12%

edited 16 Nov '16, 13:43

admin's gravatar image

0★admin ♦♦
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) arpit7282★

@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

link

answered 05 Dec '16, 11:32

arpit728's gravatar image

2★arpit728
6831251
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.

link

answered 05 Dec '16, 12:05

srd091's gravatar image

5★srd091
1.6k111
accept rate: 42%

2

@srd091

Thanks.

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

link

answered 17 May, 20:00

u_117_a's gravatar image

2★u_117_a
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×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