711 - Dividing up

[bigredteam1994]

//@begin_of_source_code
/*@JUDGE_ID: 15976FM 711 C++*/

#include<istream.h>

int A[8];
bool B[8];
int sum1, sum2;
bool done;
int C[8];

void check()
{
int i;

sum1 = 0;
sum2 = 0;

for( i =1; i<= 6; i++)
{
sum1 = sum1+ (A[i]- C[i])*i;
sum2 = sum2 + C[i]*i;
}
if(sum1 == sum2)
{
//cout<< " changed"<< endl;
done = true;
}
}

void BackTrack( int k)
{
int i;
int j;

for(i = 0; i <= A[k]; i++)
{
if(!done)
{
C[k] = i;
if( k == 6)
{
//for(j =1; j <=6; j++)
// cout << C[j]<< ' ';
//cout << endl;
check();
}
else
BackTrack(k+1);
}
}
}

int main()
{
int i;
int j;
int l = 0;
for(i=1; i<=6 ;i++)
cin>>A[i];

while(A[1] != 0
|| A[2] != 0
|| A[3] != 0
|| A[4] != 0
|| A[5] != 0
|| A[6] != 0)
{
l++;
if(l != 1)
cout << endl;
cout << "Collection #" << l << ':' << endl;
for(i = 1; i <= 6; i++)
{
for( j = i +1; j <= 6; j++)
{
while(A[j] -i >0 && A[i] -j >0)
{
A[j] = A[j] - i;
A[i] = A[i] - j;
}
}
}
done = false;
for(i =1; i <= 6 ; i++)
C[i] =0;
BackTrack(1);


if(done)
{
cout<< "Can be divided."<< endl;
}
else
cout<< "Can't be divided." << endl;


for(i=1; i<=6 ;i++)
cin>>A[i];
}

}


//@end_of_source_code

[novice]

Is ther anykind person who can overview my solution and then find my faults.??

here i give my code in C:

/* @BEGIN_OF_SOURCE_CODE */

#include<stdio.h>

void main()
{
int a[6],b[6],sum,i,j,k,l,c[6],r,s,p,d;
long nCr;

p=0;

while(1)
{
sum=0;
r=0;


for(i=0;i<6;i++)
{
scanf("%d",&a[i]);
sum+=a[i]*(i+1);
if(a[i])
c[r++]=a[i]*(i+1);
}

d=0;


if(!sum)
break;

printf("Collection #%d:\n",++p);

if(sum%2)
{
printf("Can't be divided.\n\n");
continue;
}

sum/=2;

for(k=1;k<r && d==0;k++)
{
nCr=1;

for(i=0;i<r;i++)
b[i]=i;


for(i=r,j=1;i>k;i--,j++)
{
nCr*=i;
nCr/=j;
}

while(nCr--)
{

s=0;

for(i=0;i<k;i++)
s+=c[b[i]];

if(s==sum)
{
printf("Can be divided.\n");
d++;
break;
}

if(!nCr)
break;

for(i=k-1;i>=0;i--)
if(b[i]!=r-k+i)
break;
if(i>=0)
{
b[i]=b[i]+1;
for(j=i+1,l=1;j<=k;j++,l++)
b[j]=b[i]+l;
}
}

}

if(!d)
printf("Can't be divided.\n");

printf("\n");


}


}

/* @END_OF_SOURCE_CODE */

[little joey]

After getting lots of WAs on all kinds of groovy algorithms, I decided to code it out as simple as possible. The comments almost 'mathematically' proof my algorithm, but ... still WA.

What is wrong?

[pascal]{$MODE DELPHI}

program p711;
{WA after WA. Confirmed:
- no runtime error
- all numbers >= 0
- total number of marbles <= 20000
- algo is fast enough: WA in 0.008 sec}

{SPOILER DELETED}

{whenever there are 5 balls with value 4, there must be one hand
with 3 of them. we can replace these 3 by 2 balls with value 6}
while (n4>4) do begin
n4-=3;
n6+=2;
end;

{SPOILER DELETED}

end.[/pascal]

Sorry for the long code, it will be removed when I get AC

[Andrey Mokhov]

Hello, little joey!

I looked through your program very carefully, and I think that your approach of reducing the number of marbles with more 'heavy' ones is correct. But I think the next part is too complicated. Perhaps it is right but I advise you to simplify the part. You can reduce the number of 6-marbles as well. I did it the following way:

Code: Select all

if (n6>20) n6=20+n6%2;


After that you may find all possible sums (after such reduce there won't be so many ) to check whether reduced_sum/2 could be found there...

I hope I helped you.

Bye.
Andrey.

[little joey]

Thanks Andrey for your quick response.

That was my original approach too, but got so many WAs on that, that I decided to spell out the most simple algo I could think of. After adjusting the above code with your suggestion, I still get WA

Can you, or anyone else, please email your AC win32 executable to [EDIT: no spam please ] ? So I can run some tests with random data and check the output format?

Thanks in advance,

-little joey

[little joey]

Thanks for the exe, Andrey.
Guess what: I ran both programs against a testset of one million randomly generated input sets. Both outputs are exactly the same...

Then I systematically ran all inputs from 10 10 10 10 10 10 down to 0 0 0 0 0 0, and discovered my error! My conclusions about the 4-ball were wrong: 1 0 1 6 0 0 will be reduced to 1 0 1 3 0 2. While the former is _not_ evenly divisible, the latter _is_

Moral: always test your assumptions with simple cases.

[itspeter]

Hi ,
I was wandering can some one give the math proof of 711's reduce method..
I have saw someone 's code write like the follows :
for (i=0;i<6;++i)
if (input[i]>6)
input[i] = 6 + ((input -6)%2);

And he say that the proof is because any two pair of the number's gcd is at most times 6..
etc : (5,6) = 30 , 5*6 = 30...

But I'm doubt the correctness of this reduce method..

[minskcity]

Can anybody provide me with "difficult" test cases for this problem??

my algorithm using:
123*1's = 63*1's + 1*60's; 1's < 119;
234*2's = 54*2' + 3*60's; 2's < 59;
so on...

[whyworryin]

hi!!
i dont know why i keep getting wrong answer. can anyone help me please.
my algo is if there are 4 1-valued marbles they are equal to 2 2-valued marbles. and if 4 2-valued marbles they are equal to 2 4-valued marble and 4 3-valued marbles= 2 6-valued marble
12 5-valued marble=4 6-valued marbles

then i find all possible sums and if the reduced_sum/2 can be achieved then i print can be divided else no. I have attached my source also . plzzzzzz help me .


#include<iostream>
using namespace std;
int main()
{
int n1,n2,n3,n4,n5,n6,i,j,k,l,m,n,test;

int cnt=1;
while(1)
{
cin>>n1>>n2>>n3>>n4>>n5>>n6;
if(n1==0&&n2==0&&n3==0&&n4==0&&n5==0&&n6==0)
break;
long sum=n1+n2*2+n3*3+n4*4+n5*5+n6*6;
if((n1*1+n2*2+n3*3+n4*4+n5*5+n6*6)%2==0)
{
n2+=2*(n1/4);
n1%=4;
n4+=2*(n2/4);
n2%=4;
n6+=2*(n3/4);
n3%=4;
n6+=4*(n4/6);
n4%=6;
n6+=10*(n5/12);
n5%=12;
sum/=2;

for(i=0;i<=n1;i++)
{
for(j=0;j<=n2;j++)
{
for(k=0;k<=n3;k++)
{
for(l=0;l<=n4;l++)
{
for(m=0;m<=n5;m++)
{
for(n=0;n<=n6;n++)
{
if(i*1+j*2+k*3+l*4+m*5+n*6==sum)
{

cout<<"Collection #"<<cnt++<<":"<<"\nCan be divided.\n";
goto next;
}

}
}
}
}
}
}
cout<<"Collection#"<<cnt++<<"\nCan't be divided.\n";
}
else
{
cout<<"Collection#"<<cnt++<<"\nCan't be divided.\n";
}
next:
;
}
return 0;
}



thanks in advance.

Pradeep

[tat tvam asi]

hi,
consider the collection : 4,1,0,0,0,0.
write a program that solves the problem
without reducing and compare the results
on random generated data.
good luck.

[serur]

This problem is similar to question "Luggage" somewhere here in UVa, but when applying widely-known DP strategy that worked there (and in may-may other places) I got TLE in "Dividing Up". So your explanation was of great moment to me.
I see that in reducing counters of n1, n2, n3 you reasoned in terms of Dirichlet principle (or whatever else it's called):

"If nm+1 objects are placed into n boxes, then some box contains more than m boxes",

but my question here:
Why it is that we can not reduce n4, for instance, to 5, this way:
if (n4==5) => (there are at least 3 in one hand ) => (we can replace 3 4-balls by 2 6-balls)?
Of course it's too great a hint, but am I right that in reducing n3 to 3 we replace 2 3-balls by 1 6-ball?

Thank you.

[little joey]

The problem asks wether it is possible to divide the balls in two sets with equal amounts of points. We can characterise every possible collection of balls according to this divisibility by saying it is 'divisible' or 'non-divisible'. Now in reducing the number of balls in a particular set by replacing some low valued balls by a smaller number of higher valued balls, we have to make sure that the 'divisibility' of the set doesn't change.

When replacing 3 1-balls by 1 1-ball and 1 2-ball: (n1=3, n2=0) -> (n1=1, n2=1), the divisiblity of the set doesn't change (the divisibility of both sub-sets is 'non-divisible').

On the other hand, if we have a subset of 5 4-balls, the divisibility is clearly 'non-divisible', the divisibility of a subset of 2 4-balls and 2 6-balls, however, is 'divisible', so the reduction (n4=5, n6=0) -> (n4=2, n6=2) is invalid.

About your last question:
The reduction (n3=2, n6=0) -> (n3=0, n6=1) is invalid, but the reduction (n3=3, n6=0) -> (n3=1, n6=1) is valid.

Hope it helps.

[serur]

Well, I understand now how to reduce 1,2,3-marbles. And perhaps for 4-marbles it's clear too.
Can't understand how you reduced 5-marbles down to 10. What I did is this:
{n5=12,n6=0}={n5=0,n6=10}, and {n4=10,n5=0}={n4=0,n5=8}
(where "=" means equivalence in your terms of "divisible"/"not divisible").
Still WA.

Thank you.

[serur]

And after reducing the first 5 types we can also reduce the number of 6-marbles to the number C which should be choosen according to the following :
6*C >= 5*n[5]+4*n[4]+...+n[1],
where n[5],...,n[1] are our reduced counters;
Am I right?

[little joey]

No, that is not correct. [I AM RESPONDING TO YOUR PREVIOUS POSTING]
The case of 10 4-balls: the only thing you can be sure of, is that one hand contains at least 5 4-balls, but you don't know how the remaining 5 balls are divided between the hands. You could replace 5 4-balls by 4 5-balls: (n4=10, n5=0) -> (n4=5, n5=4), but then you would violate the divisibility constraint.

The case of the 10 5-balls is also incorrect.

About the last reduction in the previous posting:

the reduction (n3=2, n6=0) -> (n3=0, n6=1) is invalid for two reasons:
1. it violates the divisibility constraint, as stated above;
2. you can't be shure both 3-balls are in the same hand (either Marsha's or Bill's).

the reduction (n3=3, n6=0) -> (n3=1, n6=1) however is valid for two reasons:
1. both states are 'non-divisible';
2. because there are 3 balls, you can be sure one hand has at least 2 balls.

(I took what you called 'Dirichlet's Principle' for granted in my previous posting).