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

×

Editorial for SUMNCR - PELT2019

Problem setter: aditya10_

Problem Code: SUMNCR

Difficulty: Easy-Medium

Prerequisites: Observation, Implementation

Explanation: If k is even then m1=0,m2=0,... mk=0 so ans=0
If k is odd and at least one n is even then ans=1.
else for each element we have to calculate the minimum mi for which nCmi is even. ans= min(minM1 , minM2 ..... minMk) where minMi= minimum value of mi for which nCmi is even

To calculate the minimum value of m for which nCm is even -

We can write nCr as (n(n-1) ...(n-m+1)) / (2.3.4...m)
Let spn=sum of power of 2 in numerator
spd=sum of power of 2 in denominator.
We have to find minimum value of m for which spn > spd.

We have to find this minimum k . Let us write the maximum power of 2 which divides each number .

[2-3] - 1,0
[4-7] - 2,0,1,0 or (2,0)(1,0)
[9-15]- 3,0,1,0,2,0,1,0 or (3,0)(1,0)(2,0,1,0)
[16-31]- 4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0 or (4,0)(1,0)(2,0,1,0)(3,0,1,0,2,0,1,0)

We can see that it follows a pattern. Each range being calculated using previous ranges.

We can try to find the answer for some values of n from the above pattern by comparing n-1 with 2 , n-3 with 4 , n-5 with 6 .... n-k+1 with k in terms of maximum power of 2. We have to find this minimum k. You can observe from above that this minimum value will always be a perfect power of 2.

So now we only have to compare n-1 with 2 ,n-3 with 4, n-7 with 8, n-15 with 16...... in terms of maximum power of 2.
Let x= 2^y where y>=1
The minimum value of x for which (n-x+1)% 2*x = 0 is the answer.
If this minimum value is greater than n than answer is -1.

Author's Solution: click here
Tester's Solution: click here

asked 11 Jan, 18:44

panik's gravatar image

5★panik
1166
accept rate: 7%


We can also use lucas theorem to prove it.

link

answered 12 Jan, 01:26

abhayps's gravatar image

5★abhayps
421
accept rate: 0%

Instead one can observe that for any number , nCi would be even if i is equal to power of 2 raise to first unset bit in binary representation of the corresponding number.

For instance(n = 13) , binary representation is 1101 , i would be equal to 2.

But for n = 7 , suitable i does not exist.

link

answered 12 Jan, 00:08

nikesh48's gravatar image

5★nikesh48
363
accept rate: 20%

Why is r in nCr always a power of 2 for getting nCr as an even value?

link
This answer is marked "community wiki".

answered 12 Jan, 20:51

v1a9r9u8n's gravatar image

4★v1a9r9u8n
32
accept rate: 0%

wikified 13 Jan, 00:37

because only at these value there is a chance of the power of 2 in numerator can overtake power of 2 in denominator

(13 Jan, 16:39) panik5★
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:

×1,648
×814
×212
×10
×4
×2

question asked: 11 Jan, 18:44

question was seen: 261 times

last updated: 13 Jan, 16:39