369 - Combinations

[Picard]

if you correct that small mistake i mentioned in hank's source, you will get an accpeted (by the online judge) example.

[hank]

Ok, people, there's something REALLY wrong about this problem. I tried tons of different approaches, and I got more W.A.'s than I can remember. But, for each one of them, I couldn't find one single test case for which my solution was wrong.

Anyway, my last desperate attempt was to use a Big Integer data type to calculate. So I did. The main part of the program appears below:

...
void main()
{
int n, m, M, i;
TBigNumber *c = (TBigNumber *) malloc (sizeof(TBigNumber));
TBigNumber *aux = (TBigNumber *) malloc (sizeof(TBigNumber));

scanf("%d %d", &n, &M);
while (n)
{
m = (M > n / 2) ? n - M : M;
InitNumber(c, 1); /* initializes c with "1" */
for (i = 1; i <= m; i++)
{
InitNumber(aux, n - i + 1);
BigMul(c, aux, c); /* multiplies c and aux, result in c */
}
for (i = 1; i < m; i++)
{
InitNumber(aux, m - i + 1);
BigDivMod(c, aux, c, aux); /* divides c by aux, result in c, remainder in aux */
}

printf("%d things taken %d at a time is ", n, M);
for (i = 0; i < c->Size; i++)
printf("%d", c->Digits);
printf(" exactly.\n");
scanf("%d %d", &n, &M);
}
free(c);
free(aux);
}
...

In this last version, I didn't use any trick - it was straight from the formula. It just CAN'T be wrong, I've used this same Big Integer structure lots of times, it is 100% correct. Is there anyone who got "accepted" in this problem and would be willing to send me a text file in the form

<value of N> <value of M> <right answer>

so I can check my program one last time before shooting my computer?

Thanks in advance,

Rodrigo

PS: I won't use your file to create a huge look-up array , I just wanna know what's wrong.

[CORRECT!!]

(intput)
100 90
100 50
99 40
100 6
20 5
18 6
0 0

(output)
1591253560
445776180
445776180
1192052400
15504
18564


(THE TEST DATA WHICH SOMEBODY TOLD ME IS CORRECT)

[hank]

if you correct that small mistake i mentioned in hank's source, you will get an accpeted (by the online judge) example.

#include "stdio.h"
void main()
{
unsigned long n,m,c,t;
while(scanf("%lu %lu",&n,&m)==2){
unsigned long i,j; long double cc=1;
if(n==0&&m==0)break;
t=m;
if(n-m<m) m=n-m;
for(i=n,j=(unsigned long)1;j<=m;i--&&j++)
{
cc *=(long double)i;
cc /=(long double)j;
}
c=(unsigned long)cc;
printf("%lu things taken %lu at a time is %lu exactly.\n",n,t,c);
}
}





BUT I STILL GOT W.A.
WHY?

[Picard]

it's interesting, it gets accpeted for me, maybe the mailer breaks a string or the problem number is wrong. i have no other idea

btw 100 50 and 99 40 have a result of much greater as 2^32

[hank]

it's interesting, it gets accpeted for me, maybe the mailer breaks a string or the problem number is wrong. i have no other idea

btw 100 50 and 99 40 have a result of much greater as 2^32

Great!I got accpeted!!

thanks!!

[Rodrigo]

Picard, my man , thanks! You're right, the mail program was messing up long lines. I finally got this problem and other one I was working on this weekend to get accepted.

I no longer want to shoot my computer. I'm just pissed with Yahoo Mail.

Rodrigo

[ithamar]

I dont know why i am having problems with this problem. I use the same code that i use in problem 530 and here doesnt work (The only change is that i use BigInt instead of long). Do u know some border cases that i should take care of.

My program works this way with this input:

Code: Select all

100 0
100 things taken 0 at a time is 1 exactly.
100 50
100 things taken 50 at a time is 100891344545564193334812497256 exactly.
100 49
100 things taken 49 at a time is 98913082887808032681188722800 exactly.
100 51
100 things taken 51 at a time is 98913082887808032681188722800 exactly.
100 90
100 things taken 90 at a time is 17310309456440 exactly.
100 10
100 things taken 10 at a time is 17310309456440 exactly.
100 100
100 things taken 100 at a time is 1 exactly.
6 0
6 things taken 0 at a time is 1 exactly.
6 1
6 things taken 1 at a time is 6 exactly.
 6 2
6 things taken 2 at a time is 15 exactly.
6 3
6 things taken 3 at a time is 20 exactly.
 6 4
6 things taken 4 at a time is 15 exactly.
6 5
6 things taken 5 at a time is 6 exactly.
6 6
6 things taken 6 at a time is 1 exactly.
 0 0

Thanxs ind advance for your help

[ithamar]

I got accepted.

I change my code to use long instead of BigInt thiws way it works. I compare the answer of my two programs and they are exacly the same when the answer fits in long but obviously the result is incorrect when not.

From this i can deduce that the input contains a C(n, k) that doesnt fit in long because that way my program with BigInteger would be correct. So the judge is accepting pragrams that give incorrect answers to the problem and reject the programs who give CORRECT answer to all cases. I dont see the logig behind of this, anybody can explain me?

To the people that is trying this problem. When you are asked the
C(100, 50) you should answer 183430866638381299 instead of the CORRECT answer that it is 100891344545564193334812497256

[Adrian Kuegel]

No, I dont think that the input/output is incorrect. I used double, and my answers should be more precise than wanted, although for 100 50 i get
1008913445455641700000000000000, which is obviously wrong, so this can't be part of the input file

[ithamar]

The point is that when I give my program a better precision capacity, I get a wrong answer, but when I give "enough" precision it gets accepted... the only possible logical conclusion is that they have an input case for which the "promised precision" is not enough...

This is not right.

[Adrian Kuegel]

I don't know where your error is, but it is a bug in your program. I just send in a program with my bigInteger routines using a precision of 100 digits, and I got Accepted. And I know my routines are correct, I used them for a lot of programs.

[ithamar]

ok.

I am going to double check my BigInt routines. If you get accepted with BigInt then is my mistake.

Thanxs anyway.

[Doodge]

Can anybody find a mistake in this source? I can't but it gets WA.

[c]// Combinations
#include <iostream.h>
#include <math.h>

int n, k;
int ilprim;
int prim[25];
int ilp[25];
int testno=0;

void gen_smart()
{
int pri, i, j;
prim[0]=2;
prim[1]=3;
ilprim=2;
i=5;
while (i<100)
{
pri=1;
j=0;
while (j<ilprim && (prim[j]<=int(sqrt(i))) && pri)
{
if (i%prim[j] == 0) pri=0;
j++;
}
if (pri)
{
prim[ilprim]=i;
ilprim++;
}
i+=2;
}
}

void addprim(int from, int to, int what, int w)
{
int left=from, right=to, s;
int found=0;
do
{
s = (left+right)/2;
if (prim[s]==what) found=1;
else if (prim[s] < what) left = s+1;
else if (prim[s] > what) right = s-1;
} while (left <= right && !found);
if (found)
ilp[s]+=w;
}

void add(int begin, int end, int change)
{
int i, j, l, pri;
for (i=begin; i<=end; i++)
{
j=0;
pri=1;
while (pri && (prim[j]<=int(sqrt(i)))) // Check if it's prime
{
if (i%prim[j] == 0)
pri=0;
j++;
}
if (!pri) // It's not prime so add it prime divisors
{
j=0;
l=i;
while (l>1 && prim[j]<=i/2)
{
while (l%prim[j] == 0)
{
l = l/prim[j];
ilp[j] += change;
}
j++;
}
}
else // If prime then add it
addprim(0, ilprim, i, change);
}
}

void calculate()
{
int quant=1;
for (int i=0; i<ilprim; i++)
if (ilp)
quant*=int(pow(prim, ilp));
cout << n << " things taken " << k << " at a time is " << quant << " exactly.";
}

int main()
{
gen_smart();
while (cin >> n >> k && (n || k))
{
if (testno) cout << '\n';
for (int i=0; i<ilprim; i++) ilp=0;
add(n-k+1, n, 1);
add(2, k, -1);
calculate();
testno++;
}
return 0;
}[/c]

[jura]

why do i get WA?

[pascal]program comb(input,output);
var m,n,i,j:byte;
popis:array[1..100,1..2] of boolean;
umnozak:longint;
begin
repeat
readln(n,m);
if (n=0) and (m=0) then halt;

for i:=m+1 to n do
begin
popis[i,1]:=true;
end;
for i:=1 to n-m do
begin
popis[i,2]:=true;
end;

umnozak:=1;
for i:=m+1 to n do
begin
umnozak:=umnozak*i;
popis[i,1]:=false;
for j:=1 to n-m do
begin
if popis[j,2] then
begin
if (umnozak div j=umnozak/j) and
(umnozak > j) then
begin
umnozak:=umnozak div j;
popis[j,2]:=false;
end;
end;
end;
end;
write(n,' things taken ',m,' at a time is ',umnozak,' exactly.');
until (n=0) and (m=0);
end.[pascal][/pascal][/pascal]

[jhonny_yang]

#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include <io.h>
#include <fcntl.h>

long arr[100],bagi[100];

int main()
{
long n,m,z,temp,k,i,jlh,j,ada,kd,zz,mm,kri;
unsigned long kk;

while (scanf("%d %d\n",&n,&m)!=EOF){
if (n==0&&m==0)break;

for (i=0;i<100;i++)arr=0;

kd=m;
z=n-m;

if (m>z){
temp=z; z=m; m=temp;
}

i=0;
for (k=z+1;k<=n;k++){
arr[i++]=k;
}

jlh=i;

k=0;
for (i=m;i>=2;i--){
ada=1;
for (j=0;j<jlh;j++){
if (arr[j]%i==0){
arr[j]=arr[j]/i;
ada=0;
break;
}
}
if (ada){
kri=i;
for (zz=2;zz<=kri;zz++){
if (kri%zz==0){
for (mm=0;mm<jlh;mm++){
if (arr[mm]%zz==0){
kri=kri/zz;
arr[mm]=arr[mm]/zz;
--zz;
break;
}

}
}
}
if (kri>1)
bagi[k++]=kri;
}
}

ada=1;
for (i=0;i<k;i++){
ada*=bagi;
}

kk=1;
k=1;
for (i=0;i<jlh;i++){
kk=k*=arr;
if (kk>=2147483648){
printf("Detected Error ");
break;
}
}
printf("%d things taken %d at a time is %ld exactly.\n",n,kd,(long)(k/ada));
}

return 0;
}
//@END_OF_SOURCE_CODE

What is my Error ?