Question - Marbles. Why does it show wrong answer? Answer is simply (n-1)C(k-1).

, ,

Link to the question - http://www.codechef.com/problems/MARBLES

#include<iostream>

#include <algorithm>

using namespace std;

int main()

{

	int i, T;

	long int j, n, k, lnMin; 

	long long int Outputs[100];

	double llnTemp=1.0;

	cin>>T;

	for(i=0;i<T;i++)

	{

		cin>>n;

		cin>>k;

		lnMin=(min(k-1,n-k));

		for(j=1;j<=lnMin;j++)

		{

			llnTemp/=j;

			llnTemp*=(n-1);

			n--;

		}

		Outputs[i]=llnTemp;

	}

	for(i=0;i<T;i++)

		cout<<Outputs[i]<<endl;

}

@s1d_3 your corrected


[1].


  [1]: http://www.codechef.com/viewsolution/3149943
1 Like

The “code” link is not working. Could you please cut-paste the whole code?

Or better, could you tell me where exactly my code has problems? I am new here. It would better help me if I understood the error and wrote the code myself!

When you do llnTemp /= j, there is a possibility that at some point llnTemp is not completely divisible by j and this results in a WA. So it is better to first multiply llnTemp by (n-1) and then divide it by j. Moreover you have to initialize llnTemp to 1.0 in each testcase. Hope you got what you needed !

1 Like

Actually I had made it double so that even if its not divisible, it would be cool. But ultimately in my final submission I made it int and used the *= first. Very sorry for the stupid error of not re-initializing llnTemp every time. Thanks for your time.