Marbles

hi ! does this prblm require numbers to be calculated in array form or int64 can work ?
thanx

@Kushagra - i think it fits 64bit integer is sufficient.

M nt gerttin wht is gng wrong... wen i run it on my machine code gives correct results..

but m gettin WA

yes...it works fine with int64. :)

hi admin, can you tell me whats goin wrong with my code..
getting correct solution when i am running code on my machine

You can't. You'll need to figure out what kinds of input could cause your program to crash yourself.

You might get a runtime error if you are going wrong with the way you take input. You might want to check that.

Look at the limit on N and K.

The answer will fit in a 64bit integer, but the intermediate values while calculating the answer might not. Are you taking care of that?

It can still cause overflows. You might want to use assert() to check if you are overflowing the limit for integers.

actully i canged  long to long long so that it will support the output  but still i am getting wrong answer and i am able to get answers in my system please help me

Yes it is a function in the C library. Did you use assert to check if you are getting negative answers?

CodeChef shows wrong answer status to my submission. It would be really helpful if which case failed could be shown with the status. The code is working fine in my system. Under what circumstances does one get wrong answer? I have included some checks and caught some exceptions too. Can this lead to wrong answer?

You get wrong answer if you don't produce an output file exactly like the judges output file.

You'll have to figure out why yourself, that is the point of problems like these :)

This my first time here. So sorry if this question is naive. Doesn't the input come from command line arguments using "public static void main (String[] args)" and we print the solution in console itself. Do I have to use any file?

@Vaibhav No, you read input from stdin and output your answers to stdout.

Hi,

I am getting NZEC error when I submit the solution in Ruby. My program runs fine on my system which has ruby 1.8 , Can some one help .

You are probably not taking input in accordance with the input specs.

hey guys , i m getting compiler error . although i compiled in java(netbeans jdk5) and there it was working correctly

Please check the FAQ and the Sample Solutions

Hi Team,

I write a solution for this problem in Visual C++ platform using only ansi c++ library. I am pretty sure that it will compile and run on linux g++ library. I ran it for given test cases. It gave correct result. But when I was submitting it shows wrong result.

My guess there is some problem in my logic.

Can I get some more test cases or if you permit I can start discussion about my logic.

Eagerly waiting for your response.

Thanks

Sure, you can use our forums to discuss your approach and ask questions.

Hi Aniruddha,

Thanks for your kind response.

I will place my approach tommorrow.

Before that one non-technical but very essential question.:-)

Can I make my profile invisible to everybody?

more specifically the email-id.

Your email id is not visible to anyone but the admin.

Thanks Aniruddha.

My Approach:

It is very simple.As order or permutaion is not been cosidered, number of possiblity/case rohit have had is the

summation of kCi * (diff-1)C(i-1) for i=2 to min(k,diff)

+ kCi for i=1

or 1 if n=k

nCr stands for combination of r element from n distinct element.

My logic is number of way i distinct marble can be selected from k distinct type * number of way i-1 marble placed diff-1 place(except 2 terminal place)

The solution giving correct result for both test case.

Hi All,

I am waiting for your valuable comments.

Thanks

How are you calculating nCr? If you don't do this in a clever way, you could end up with overflow (even though the final result fits in a 64 bit integer.)

Hi Stephen,

I am calculating the loop=min(n,r)

then upto loop calculating the numerator and denomerator (both long).

then return num/deno

Don't you think that would be larger than the value a long long could store in some cases?

Hey Anuradha,

On my box it is showing me time < 1 sec but still on portal it's saying time limit exceeded :(

It's Aniruddha and not Anuradha.

The time limit is for all the 100 test cases combined. Plus, the system on which the judge runs might be slower than the system on which you are running the code.

Hi Aniruddha,

I am using long long

Hi Stephen,

I am optimising the combination calcualtion.

But still I am getting wrong answare

You can't be optimising it well enough. It is very easy for intermediate calculations to overflow a long long if you don't do it correctly.

Hi Stephen,

I am calculating combination by below mentioned method.

long

k)

{

1;

loop=((n-k)<k)?(n-k):k;

result=n-loop+1;

temp=result;

i=2; i<=loop; i++)

{

)(result*(++temp)/i);

}

result;

}

I don't think there is any chance to overflow.

I changed

result=(long)...

to

result=(long long)...

but still getting the wrong answare.

Can any one please help me

Hi all,

I am retyping my combination calculation again.

long long combination(int n, int k)

{

if(n==k) return 1;

int loop=(n-k)<k?(n-k):k;

long long result=n-loop+1;

int temp=result;

for(int i=2; i<=loop; i++)

result=(long long)(result*(++temp)/i);

return result;

}

Is there any chance to overflow??

Is it always necessary for temp to be divisible by 'i' ?

result is multiplication of i consecutive number. so it is always divisible by i.

Hi Aniruddha,

I tried steps by splitting

result*=(++temp);

result/=i;

but still it is not working

Hi Aniruddha/stephen/all,

Do you find any flaw.

I am waiting for your comments.

Make sure that at any iteration you are not overflowing the limit. For e.g. consider 99C94. You start off with result = 95. This is divisible by 5 but you don't do this till the last loop. For higher values, these calculations in between could overflow the limit and you will end up getting a wrong answer.

hey .. can u plz tell if the case n=88885 k=6 would work even for the correct solution ??

The answer for that case is much greater than a 64 bit integer, so a correct solution does not need to give the correct answer for that case. Some correct solutions might, others might not.

Hi,

I need to know the input for which it is failing.

my first time in here.

Thanks

You're meant to figure that out yourself. Try coming up with some useful test cases.

hi!!!

as i'm solvin problems on cc, i'm not gettin how this execution time works, k consider these two solutions

http://www.codechef.com/viewsolution/1475 : admin's solution tht has perfect timing.

http://www.codechef.com/viewsolution/143304 : my solution!

well the logic is same but then y is there a diff of .7s... i mean i smaller diff can be accounted for multiple assignments and stuff like tht... or am i missin sumthin big?

TIA

Simple. You use cin/cout. These are extremely slow methods of getting input / writing output.

oh i c... Thanks a lot :) hey jus curious here, where can i get such kinda info abt time taken by such methods? or is every programmer supposed to know it by default!!!

One is supposed to know that cin,cout are much slower than scanf() , printf()

I m using this function to find out ncm...but everytime its showing wrong answer... Please help me out...I am using dev c++

long double func(long double n,long double k)
{
long double z;
if(k==0)
return 1;
z=(double)n/k*(func(n-1,k-1));
return z;
}

@Aniruddha...Its giving correct result on my machine but its showing wrong anser when I submit it...My submission ID is 148252..Pls see to it

"You can assume that this number fits into a signed 64 bit integer."

There are some inputs which will produce answers which need not fit into 64 bit integers, so those inputs will not be given?

That is exactly what that sentence says, yes.

Getting a time limit exceeded on this..

def perm_calc(n,k):
if n==k:
print 1
return
if k==1:
print 1
return
n=n-k
numr=range(n+1,n+k)
divr=range(2,k)
i=2;
for x in numr:


res = reduce(operator.mul,numr)
print res

Any suggestions?

will it be OK if i use long long int for output??

on my pc i'm getting this output

1000000 4

166665666668499999

is this correct?

"For each test case print the number of possibilities that Rohit would have had.
You can assume that this number fits into a signed 64 bit integer."

Please read the problem statement carefully.

@thanks Aniruddha ... thats not the way im taking input ... have a look on this

scanf("%d",&t);
while(t > 0){
scanf("%d%d",&n,&k);
printf("%ldn",marb(n,k));
t--;
}

i think it should give the desired output format...

%ld is a 32 bit integer.

I have written a function whick calculates (n)C(k) ... But for calculating the exact value i have use floating point numbers ... so i am using a long double ... the function returns a long double ... is it wrong to do so ... is it constrained that my function should return a long long integer ??

You won't be able to calculate the exact value with floating point numbers, they aren't accurate enough. You need the exact answer.

thanks @stephen got it :)

Hi chef

My code is working fine on my machine .. but is giving a WA when submitted :(

I've taken care of the intermediate value overflows mentiioned in the above comments

could you please tell me the problem with my code ?

http://www.codechef.com/viewsolution/154145

@Aniruddha or @stephen...

I have done this problem by recursion ...by it shows time limit exceeded while submitting in codechef....

please see my code and suggest some alternative or any improvement...

http://www.codechef.com/viewsolution/156322

...................

please reply soon.

Hello admin;

http://www.codechef.com/viewsolution/163417 Keep getting 'wrong answer'. Tried lots of possible test cases. Could you comment on where the problem could be? Hope i am outputting correctly i.e. n after every result.

Thanks.

Please ignore last post. Had an issue with overflow from variable types i was using.

Hi,

Has there ever been a successful submission in Java?  I am trying to submit a solution in Java which works perfectly fine on my boxes and is highly performant with use of cache, but fails on CodeChef's boxes with the message "Time Limit Exceeded" when I try to submit my solution (ofcourse, via web interface).

Cheers,

Naga

Yes. My solution was accepted in 0.44 seconds.

Have you considered a test case where k or n-k in your program is very large, yet the answer is very small?

(Also, the HashMap in your program is only going to slow things down, not speed things up. The chances of it ever helping are very low since it is unlikely a factorial is ever needed twice; so you are only losing time using it.)

Thanks for the hint.  I now have a successful submission in Java with 0.29 seconds.

Regards,

Naga

please have a look at my problem,

m getting a TLE, i tried two ways,

to calculate n-1 C r-1

1) multiplying from a range a to range b but with divide and conquer and everytime diving the result from one of the 2..r-1 by keeping a track of used numbers. i guess this must be slow

2) i tried with the iteratiosn = n-k<k?n-k:k. and every time i start with the high end of i and divide by gcd. if possible can anybody give a hint

inline ui combination(unsigned long long n,unsigned long long k)
{
if(n==k) return 1;
int loop=(n-k)<k?(n-k):k;
unsigned long long result=n-loop+1;
unsigned long long a=result;
ui prod=1;
for(int i=loop; i>=2;i--)
{
result=result*(++a);
ui b=gcd(result,i);
result/=b;
prod*=i/b;
if(result%prod==0)
result=result/prod;
}
return result;
}

I am very frustrated now :|

Could tell me what wrong i am doing ??

Code is pasted below,

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
*
* @author Prajot Naik
* @version 1.0 Problem code: MARBLES
*/

public class Main {

/**
* @param args
* @throws IOException
*/

public static void main(String[] args) {
BufferedReader stream = new BufferedReader(new InputStreamReader(
System.in));
int t = 0;
try {
t = Integer.parseInt(stream.readLine());
if (t > 100) {
return;
}
} catch (Exception e) {
return;
}
long[][] inpArr = new long[t][2];
for (int i = 0; i < t; ++i) {
try {
inpArr[i][0] = Long.parseLong(stream.readLine()); // n
inpArr[i][1] = Long.parseLong(stream.readLine()); // k
} catch (Exception e) {
System.out.println("Input Too Large to store");
inpArr[i][0] = 0;
inpArr[i][1] = 0;
continue;
}
}
for (int i = 0; i < t; ++i) {
System.out.println(nCr(inpArr[i][0], inpArr[i][1]));
}

}

/**
*
* Calculating nCr
*
* @param n
*
* @param r
* @return
*/

private static double nCr(long n, long r) {

if (n == 0 || r == 0) {
return 0;
}
if (n == r) {
return 1;
}
if (1 > r || n < r || n > 1000000) {
return 0;
}
return factorial(n, r);

}

/**
*
* Calculating factorial
*
* @param x
* @param y
* @return
*/
public static double factorial(long x, long y) {
double retX = 1;

long i = (x - y >= y) ? (x - y + 1) : y + 1;
long j = (x - y >= y) ? (y) : (x - y);

for (; i < x || j >= 1; --j) {
retX = (i <= x) ? retX * i : retX;
retX = (j >= 1) ? retX / j : retX;
}
return retX;
}
}

Hi I am getting runtime error after submitting my solution while it runs perfectly fine at my end with whatever test cases I tried with.

My solution is posted here...
http://www.codechef.com/viewsolution/223990

I would appreciate if anybody can guide me in this regard about what am I doin wrong?

I have been getting Runtime Errors (No other info) for this problem for quite some time. I'm using Python 2.5 and I'm trying my best to ensure that size of the numbers does not get out of hand. I tried submitting my solution to the corresponding problem  in SPOJ and recieved a Runtime Error (NZEC) on Python 2.5 and an AC on Python 2.6.2. The solution is not ideal (takes 0.21 seconds), but nevertheless runs without errors (possibly due to automatic bignum conversion in Python 2.5+) Any ideas if that is why I continue to get runtime errors here? My approach is definitely not naive, I maintain 2 lists numerator_list and denominator_list and keep picking values from denominator_list and multiplying with denominator (and performing division using fractions.gcd) till num < den, at which time I multiply in a number from the numerator_list. My number size only really gets out of hand when i have exhausted the denominator_list.

Hi Admin,

Can you please look into my last submission and let me know what is wrong with it. It is not causing overflow as BigInteger is used, but somehow I am getting a Wrong Answer message.

Thanks,

Bikash

http://www.codechef.com/viewsolution/243926

please

can anyone tell me whats wrong with this code.Its throwing a wrong answer,but I don't see anything wrong in the logic.

Thanks

anyone

please see my previous comment

An unsigned long can only store a 32 bit integer; the problem says you will be dealing with 64 bit ones. A double isn't precise enough to deal with integers of that size either.

please can anyone suggest anything?

I'm getting a TLE

http://www.codechef.com/viewsolution/245045

I'm not able to find the difference in cases with large outputs and that of small ones.

Anyone help.

see my code in previous post, I improved it

Although i solved question in less than 0.15 , i am looking for a better algo for factorials (basicaly fr nCr) or for caluclating last few digits for such a number . Can any guide me in right direction ?

@prajot I don't know if you've found some answers yet, I thought I'd point out some (not all) things I see you'd overlooked in that code:

1) nCr where r=0 is always 1; there is exactly 1 way to choose nothing out of a bag of n items.

2) Division loses precision, even when using doubles (not all real numbers can be represented in bits, even when in range).

3) Did you mean to iterate over i as well as over j?

pls help me

i am new on codechef so can anyone tell me how we are gtng the desired result just the mathematics part

http://www.codechef.com/viewsolution/309839

This is my solution to this one.

I just used brute force approach with some tiny optimizations.

I calculated nCk directly from the formula containing n!

but i did it tricky enough to get accepted!

it was not working on my comp bt when i submitted the ans it was right yipeee!!

can any one help me out in explaining how 475020 comes.

Can anyone plz explain why we are taking (n-1)C(k-1).

As in 30 7, why is the ans 29C6.

@ambuj:If you look at the fomula i.e x1 + x2 +x3 + x4 .......+xk = n. where x1,x2,x3.........,xn>=1.

so formula is (n-1)C(k-1) not nCk......

i think it's enough...........to clear your doubts

its giving WA for this one:

http://www.codechef.com/viewsolution/408221

its working perfectly fine on my computer and the algorithm is also optimal... please help

i downloaded some of the top correct solutions and cross checked my answers and there isn't any discrepancy

between any of the answers. still i am getting WA ..

thanks alot to pakhi

the simple fact posted by him that n consecutive nos product is divisible by n is the crux of the problem

Plz figure out if am doing correct as i am getting time limit exceeded

http://www.codechef.com/viewsolution/410603

Also tell about "long long int" or 64 bit integer and other things that are different from turbo c

plz somebody reply !!!!!!!!!!!

does somebody listen here?

@Gaurav: You should not use so much iteration . You are using pre computations for ncr but it is increasing time not decreasing as it has to call recursive function until it is less than or equal to that value for which you already have computed ncr.