711 - Dividing up

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

bigredteam1994
New poster
Posts: 2
Joined: Fri Dec 14, 2001 2:00 am

711 - Dividing up

Post by bigredteam1994 » Fri Dec 14, 2001 10:01 am

//@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- C)*i;
sum2 = sum2 + C*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;

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 -j >0)
{
A[j] = A[j] - i;
A = A - j;
}
}
}
done = false;
for(i =1; i <= 6 ; i++)
C =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;
}

}


//@end_of_source_code

novice
New poster
Posts: 3
Joined: Tue Jan 07, 2003 10:51 pm

711

Post by novice » Sat Jan 18, 2003 11:47 am

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);
sum+=a*(i+1);
if(a)
c[r++]=a*(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;


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];

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

if(!nCr)
break;

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

}

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

printf("\n");


}


}

/* @END_OF_SOURCE_CODE */

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

711 Dividing up - What's wrong with my reasoning?

Post by little joey » Sun Sep 07, 2003 10:53 pm

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 :D
Last edited by little joey on Mon Sep 08, 2003 1:17 pm, edited 1 time in total.

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Mon Sep 08, 2003 6:35 am

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 :wink: ) to check whether reduced_sum/2 could be found there...

I hope I helped you. :)

Bye.
Andrey.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Sep 08, 2003 9:52 am

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 :cry:

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Sep 08, 2003 12:31 pm

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_ :oops:

Moral: always test your assumptions with simple cases.

itspeter
New poster
Posts: 4
Joined: Wed Dec 18, 2002 4:44 pm

711 Dividing up Math Proof ?

Post by itspeter » Thu Jan 22, 2004 6:39 am

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>6)
input = 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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

711 - any tricky test cases?

Post by minskcity » Tue Mar 23, 2004 8:11 am

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
New poster
Posts: 1
Joined: Fri Jan 07, 2005 7:29 pm

711

Post by whyworryin » Fri Jan 07, 2005 7:38 pm

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
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

Post by tat tvam asi » Thu Jan 13, 2005 2:05 am

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

711

Post by serur » Wed Apr 26, 2006 8:05 am

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.
Last edited by serur on Fri Aug 14, 2009 7:31 pm, edited 1 time in total.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Apr 26, 2006 10:33 am

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Wed Apr 26, 2006 2:10 pm

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Wed Apr 26, 2006 2:44 pm

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?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Apr 26, 2006 2:53 pm

No, that is not correct.
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).

Post Reply

Return to “Volume 7 (700-799)”