562 - Dividing coins

[Revenger]

I wonder why this code gets WA Can anyone help me?

[pascal]Program p562;

Const MaxV = 500;
MaxN = 100;

Var Inf : Array[0..MaxN*MaxV]of Integer;
T,tt : Integer;
N,i,j : Integer;
Sum : Integer;
W : Array[1..MaxN]of Integer;

begin
Read(T);
for tt:=1 to T do begin
for i:=0 to 50000 do Inf:=0;
Read(N);
for i:=1 to N do Read(W);
Sum:=0;
Inf[0]:=1;
for i:=1 to N do begin
for j:=0 to Sum do
if Inf[j]=1 then
Inf[j+W]:=1;
Sum:=Sum+W;
end;
j:=Sum;
for i:=0 to Sum do
if Inf=1 then
if Abs(Sum-2*i)<j then
j:=Abs(Sum-2*i);
Writeln(j);
end;
end.[/pascal]

[zsacul]

Try this:

inp:
1
4
1 9 990 10

out:
970

[Revenger]

Thank you very much! I've found my mistake

[Ghost77 dimen]

The problem of partition is difficult to me.

I used D.P. to slove it ,and I took 0.547 seconds.

But it is too slow to solve some similar problem like this.

Would anybody like to share the faster algorithm with me?

Thanks a lot.

[Shahid]

i solved it using o.200 sec and i laso use DP. i think the faster solutions also use DP, but going ahead of time by tweking their codes...........
so i also eager to know is there any faster algorithm then DP..

[Ghost77 dimen]

Do you have done problem 307,711,and 10364.

In my viewpoint, they are partition problem as 562.

But only 562 and 711, I know how to deal with by D.P.

However, my algorithm seem that it is too slow to get Accept of them.

Only succeed in 562.

An freshman of programming needs your help.

[Shahid]

i think 562 is partition by 2 problem...but in case of 10364 it is a partition by more i.e. partition by 4 problem. and as far i assume DP is good for the fast type of problems.

i solved 10364 using recursive procedure. you have to keep good bound checking to avoid time limit exceed.

if anyone knows how to solve 10364 using DP, i am very much interested to know about it.

[Ghost77 dimen]

Hi ,shahid.

I think your algorithm for 10364 is backtracking.

But the time may be too long to solve the problem 307.(Just assume)

In this sutiation, which algorithm is more faster?

By the way, how large is the range of the variable

,"long long int", in gcc.

And is it a variable except "double" in C++ is as large as "long long int"?

(I can't declare long long int in C++)

[Dominik Michniewski]

long long int is 64-bit integer
if you use Visual C++ by Microsoft, you can get the same range in integer using __int64 but you must change all __int64 to long long int before submit problem )

Best regards
Dominik

[rjhadley]

562
My first instinct was that partitioning into 2 parts as equally as possible doesn't seem too hard. But the straightforward greedy solution doesn't work. Consider this greedy method:
1) Sort the coins in descending order
2) Build up two lists, say A and B, by considering each coin in turn. If total value of A < total value of B then add it to list A, else add it to list B.

e.g. for 6, 4, 2, 1 the algorithm goes
1) A: 6 B:
2) A: 6 B: 4
3) A: 6 B: 4, 2
4) A: 6, 1 B: 4, 2
and yields the correct solution in this case.

But for 6, 5, 5, 2, 2 the algorithm goes
1) A: 6 B:
2) A: 6 B: 5
3) A: 6, 5 B: 5
4) A: 6, 5 B: 5, 2
5) A: 6, 5 B: 5, 2, 2
and yields a difference of 2 which is wrong since A: 6, 2, 2 B: 5, 5 gives a difference of 0.

Greedy in this case fails for the same reason it fails in the 0-1 Knapsack problem. So it seems that Dynamic Programming is the way to go since this problem isn't sufficiently general.

711
On the other hand, this is sufficient general that Dynamic Programming is not necessary. Since there are only 6 possible values a (somewhat big) if statement can give the correct result. i.e. Consider the parity of each type of value (i.e. reduce mod 2) and handle the special cases, such as 1 0 1 0 0 0 is false but 3 0 1 0 0 0 is true.

10364
Backtracking is the way to go (but it has to be done very carefully to get the proper runtime). Perhaps dynamic programming will work, but the straightforward try of building a table of the possible sums and checking if 1/4 * total, 1/2 * total, 3/4 * total are all in that table is misleading. i.e. Consider 5, 5, 5, 4, 11, 3, 3, 4. The table will have 10 (5 + 5), 20 (4 + 5 + 11), 30 (4 + 5 + 5 + 5 + 11) but the stick of length 11 makes it impossible to place in a side of length 10.

307
I haven't tried this one yet, it looks harder than 10364 but the methodology should be similar.

[Ghost77 dimen]

Thanks for your help.

But still something I am confused with , 711 have a lot of special cases.

As you said , my method to solve the problem before is seperating them

into two piles , and then handle them with some tips.

But still some case without consider , like follows:

1 2 3 4 5 6

0 3 2 0 0 0

In my tips , it would be ignored.(And still some mistakes like that.)

So the program comes to very ugly if I want to handle all special cases.

Or your tips is more clear. May I get a hint , thanks a lot.

[rjhadley]

Yes, the result will be very "ugly", but it will also be very fast (at runtime - if you want fast coding time, just adapt your solution to 562).

I haven't had time to code up my solution, it's all in my head! I can give you a few pointers though. If you have more questions or want to see my solution (I'll finish it this weekend sometime) then please send me a private message. (Since this is suppose to be a discussion about 562).

1) Consider the parity of the number of marbles of each type. The reasoning is that the even "part" can easily be split into two sets of equal value. This leaves 64 cases (2^6), 32 of which have an odd total value and the result is false for these.

2) Store the parities using the bits of a integer, parities.

Code: Select all

parities & 0x01 // parity of number of marbles of value 1
parities & 0x02 // parity for value 2
parities & 0x04 // parity for value 3

etc.
This will make the code more concise and simpler.

3) Some of the solutions, say odd parities for only 3, 2, 1, have trivial solutions that split evenly, namely 3 and 2 + 1 = 3 in this example. Of the 32 remaining cases, 18 (or so) fall into this category.

4) We can be smart and rather than have 18 if clauses, we can simplify (same idea as Karnaugh maps). i.e. Of the 32 cases with even totals, all with both 3 and 2 having odd parities fall in the category mentioned above. So with one check (parities & 0x06) we can handle 8 cases at once!

5) That leaves 14 cases...these are the difficult ones...I need to give more thought into a simple, reusable method. With your example above, only 2 has an odd parity. We have currently assigned one 2 and one 3 to each person and have one 3 left. We can swap person A's 2 with person B's 3 for a change of in values of 1 to each person. A is +1 and B is -1 for a total value difference of 2 (which is the value of the unassigned marble). The remaining 2 gets assigned to B and the values are equal and all the marbles are assigned! To describe this more generally, consider x := <half the total of the unassigned marbles>. We need to find a set of marbles assigned to person A and a set assigned to person B whose difference is x. If such sets exist then the result is true, otherwise the result is false. This isn't too hard to code up, but it might be a bit "ugly".

[Alexander]

Some topics of this board is talking about DP in this problem.
But what's wrong with this simple algorithm?
It's working well with all my tests...

[pascal]program task562;
var
P,N,i,j,t : integer;
l,r : longint;
a : array[1..101] of integer;
begin
readln(P);
while P>0 do begin
dec(P);
readln(N);
for j:=1 to N do begin
read(a[j]);
end;
readln;
for i:=N-1 downto 1 do
for j:=1 to i do
if a[j]<a[j+1] then begin
t:=a[j];
a[j]:=a[j+1];
a[j+1]:=t;
end;
l:=0;
r:=0;
for i:=1 to N do begin
if l<r then inc(l, a)
else inc(r, a);
end;
writeln(Abs(l-r));
end;
end.[/pascal]

[junjieliang]

Try this:
2 48 48 49 49 50 50

You can divide them equally into (2 + 48 + 49 + 49 = 148) and (50 + 50 + 48 = 148). But your program outputs 2

[Alexander]

Wow! Thanks... Really, it isn't so easy!!!