Doubt in editorial | Problem - Marbles

#1

Problem link : https://online.codingblocks.com/app/player/158115/content/165260/5093/code-challenge



Editorial code: https://ide.codingblocks.com/s/402951



Why do we have below condition in the code?

if (n - r < r - 1)
{

r = n - r + 1;

}



Where does the loop condition
i >= n - r + 1

come from?


As the solution is n-1 C k-1 or n-1 C n-k , why can’t we simply loop from 1 to n-k or k-1?

#2

Yup this is correct

so we check if n-k < k-1 then update k as n-k+1

Because either it will result in integer overflow or since we are using integer division it may result in proper division

N-1CK-1 == (N-K+1)! / (K-1)!

#3

Ok I know that N-1CK-1 = (N-1)! / ((K-1)! * (N-K)!)

How did you derive this N-1CK-1 == (N-K+1)! / (K-1)! ? Can you please explain?

#4

OH SORRY , my bad
(N-1)! / (N-K)! == ( N-1) * (N-2) * …*(N-K+1)

SO N-1CK-1 == ( N-1) * (N-2) * …*(N-K+1) / (K-1) !

1 Like
#5

Thank you. It is clear now.
But I have another question.
How the division ans/(n-i) is equivalent to ans/(k-1)! ?
How do I know the loop runs for (k-1)! times?

#6

Hey @thirumeni.m07
Run

		for (ll i = n - 1; i >= n - r + 1; i--) {
			cout<< (n - i)<<" ";
		}

Also

it runs for k-1 times
(n-1) - (n-r+1) +1 == r-1

1 Like
#7

Sorted bro. Thanks for your time :smile:

1 Like
#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.