I want a proof or a counter example

[..]

I just solved problem 711 in 0.04s by this algorithm:

mod 10 on number of each kind of marbles
then use DP to check if it can be divided in half.

But I can't find a proof or a counter example to show that this algorithm is theoretically correct for this problem. Can anyone help me?? Thanks a lot!!

[cyfra]

Hi!

I am not sure if I understood your solution, but what would you do for test:
11 0 3 0 0 0

Dividing is possible and as I understood you would do mod 10 on this and have :
1 0 3 0 0 0

which has no solution..

Am I right or not ?? ( because I am not sure if this is your method)..


Good Luck

[..]

Oh~~~~~~~~~
Yes, I miss this example. Thanks!

Then can anyone tell me if there is good algorithm to solve this problem?
I know this problem is NP-Complete, but is there any reduction to decrease the runtime of DP?

[..]

Thanks a lot!!

[Dominik Michniewski]

I'm stuck with this problem.
I think about cyfra's tests and passed it.

My algorithm is:
1. reduce number of marbles modulo 8. I think that is correct, because smallest common multiply of any number from set {1,2,3,4,5,6} is at most 6, but exist cases (i.e. 0 0 0 0 6 5) on which this reduction fails. I think that reduction modulo 8 is safe.
2. use backtracking to check all combinations - if I arrive half of sum of rest marbles I stop.

Result => WA in 0.002 s.
Could anyone help me ? Counter examples will be nice. Any advices too

Best regards
DM

[Per]

Well, in the spirit of cyfra's test:

9 0 3 0 0 0

Solution is obvious, but if you reduce mod 8, there is no solution anymore. I don't think any "mod k" strategy works, I think you'll always be able to find similar cases.

[Dominik Michniewski]

OK, thanks Per ...
So how can I reduce number of marbles to check ? I think, that it's backtracking problem or I'm wrong ?

Best regards
DM

[Per]

Backtracking is slow, it's better to use DP.

But you still need to reduce the marbles somehow. Hint (for how I did it, there are probably other ways): note that, for instance, if you have 5 marbles of value 2, and 10 marbles of value 4, it's basically the same as having 25 marbles of value 2 and none of value 4, since you can construct the same set of values with them. Note that you actually get more marbles, but it's easier to see what you can do with them, since they're all of the same kind.

[Sedefcho]

I cover the test cases here and I am pretty sure my algorithm is
logically OK.

Can someone with an ACC program post here several (10-15)
test cases.

It would be nice if there're also some larger numbers
in these cases. Small numbers are also ok as long as they reveal
some BUG

[Sedefcho]

DP vs. Backtracking

I fixed my WA problem, now I have a TLE as I use
backtracking in the second part of the algorithm
( after reducing the counts n1, n2, ... n6 ).

Actually after reducing these counts I get a sequence
6,6,...6, 5,5... 5, 4,4,...4, 3,3..., 3, 2,2,...2, 1,1...1
( I use a sorted array here ).

The count of the elements equal to 6 is n6.
The count of 5's is n5.
The count of 4's is n4.
The count of 3's is n3.
The count of 2's is n2.
The count of 1's is n1.

Note that n1<=3, n2<=5, n3<=7, n4<=9, n5 <=11 .

And I have n6 <= 21 ( the n6 is more special than the others ).

We can even make it n6<=20 , I think but this will change
nothing in the performance of my program as it will
just mean one element less in my
Sorted Array ( see the sequence above ).

We have these limitations for n as we have reduced
the n numbers ( i = 1,2,3,...6 )
in the first part of our algorithm.


So I create an ARRAY of n1 + n2 + ... + n6 elements and using
backtracking I am trying to find if it could be divided into
two sub sets the which have equal sums ( of their elements ).

So now ...
How can I substitute the backtracking with DP here ?!
Or after the first part of the algorithm you take
a completely different approach ?

[Sedefcho]

Hi all,
I know now what DP method can I use here.

But after I have changed my backtracking algorithm
to a DP algorithm I got WA again ( with the backtracking
I had TLE ).

So can someone give some test cases now pls.

[little joey]

Are you shure your reduction schemes are correct?
In my schemes n1<3, n2<3, n3<3, n4<11, n5<11.

For the n1<3 part: whenever there are three 1-balls, there must be at least 2 in one hand, so we can replace these two by one 2-ball.
I can't see a scheme that reduces n4<=9, but you might have found one.

[Sedefcho]

My reduction method has proved to be wrong.

Now I try to do it without any reduction and using DP algorithm
but I get TLE ( quite logical ).

Can you explain me in more detail the reduction method
which I must implement.

[little joey]

It's hard to give more hints without giving the whole problem away, but I'll try.
If you follow my reasoning for reducing the number of 1-balls, then it boils down to something like while(n1>2){n1-=2;n2++;}, which can of course be done more efficiently. Similar reasonings can be used to reduce n2 and n3. For n4 and n5 I used a slightly different reasoning which reduces them whenever they are bigger than 10, but I'm sure you can do that yourself.
So in the end you are left with a maximum of 26 balls with values 1 to 5, the rest are 6-balls. Now you have to divide these max. 26 balls between Alice and Bob (or whatever they're called) and also divide the 6-balls between them so that they have equal amounts of points.

Hope you get it.

[Sedefcho]

Below is the part of my code which dreduces the counts N1...N6.

"chastno" means " result of the division "
"ostatak" means " remainder of the same division "

Apparently there's a logical error in it. I get WA although
the program is now fast.

The last part ( which reduces N6 ) could be made even more effective
by replacing the constant 200 with a smaller one.
I have put there 200 just to make sure the
logical error does not come from there.

Can u tell me where my error is ?

Code: Select all

    private static void reduce(){
        int chastno = 0;
        int ostatak = 0;

        // replace 1's with 2's
        chastno = n[1] / 2;
        ostatak = n[1] % 2;
        if (chastno>=0 && chastno % 2 != 0){
            chastno--;
            ostatak += 2;
        }
        n[1] = ostatak;
        n[2] += chastno;

        // replace 2's with 4's
        chastno = n[2] / 2;
        ostatak = n[2] % 2;
        if (chastno>=0 && chastno % 2 != 0){
            chastno--;
            ostatak += 2;
        }
        n[2] = ostatak;
        n[4] += chastno;

        // replace 3's with 6's
        chastno = n[3] / 2;
        ostatak = n[3] % 2;
        if (chastno>=0 && chastno % 2 != 0){
            chastno--;
            ostatak += 2;
        }
        n[3] = ostatak;
        n[6] += chastno;

        // replace 4's with 6's
        chastno = n[4] / 3;
        ostatak = n[4] % 3;
        if (chastno>=0 && chastno % 2 != 0){
            ostatak += 3;
            chastno--;
        }
        n[4] = ostatak;
        n[6] += 2*chastno;

        // replace 5's with 6's
        chastno = n[5] / 6;
        ostatak = n[5] % 6;
        if (chastno>=0 && chastno % 2 != 0){
            ostatak += 6;
            chastno--;
        }
        n[5] = ostatak;
        n[6] += 5*chastno;


        int throwAwayN6 = n[6]-200;

        if (throwAwayN6 >=0 ) {
            if (throwAwayN6 % 2 == 1) {
                throwAwayN6--;
            }
            n[6] = n[6] - throwAwayN6;
        }



    }