10032 - Tug of War

[Salmin Sultana]

is my algorithm correct?
need some input&output.

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

int n;
int a[105];

void input()
{
int i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a);
return;
}
void work()
{
int temp,i,j,k,p1,p2,t1,t2,man1,man2,test;

scanf("%d",&test);

for(k=0;k<test;k++)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a);
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a<a[j])
{
temp=a;
a=a[j];
a[j]=temp;
}
}
}

p1=a[0];
man1=1;
p2=a[1];
man2=1;

for(i=2;i<n;i++)
{
if(man1==man2)
{
t1=abs(p1+a-p2);
t2=abs(p2+a-p1);

if(t1<t2)
{
p1+=a;
man1++;
}
else
{
p2+=a;
man2++;
}
}
else if(man1>man2)
{
p2+=a;
man2++;
}
else if(man2>man1)
{
p1+=a[i];
man1++;
}

}
if(p1<p2)
printf("%d %d",p1,p2);
else
printf("%d %d",p2,p1);
}
}
int main()
{
work();
return 0;
}

[sohel]

Instead of posting your code.... try to describe your algorithm......
in this way the thread becomes more interesting and helpful.

And if posting the code is a must then you should use C++ tagging option.

[Salmin Sultana]

is my algorithm correct?
need some input&output.

at first i sorted the iputs.entered 1st man in group1&2nd man in group 2.
kept track for man in 2 groups with man1&man2 variable.
then for every next input checked if there is equal man in 2 groups.
if man number is equal then checked in which group i shuold enter the
man such that the difference will min.
if number of man is not equal(graeter by one) then i will push the man
in the group where man no. is less.

[cpp]
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int n;
int a[105];

void input()
{
int i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a);
return;
}
void work()
{
int temp,i,j,k,p1,p2,t1,t2,man1,man2,test;

scanf("%d",&test);

for(k=0;k<test;k++)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a);
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a<a[j])
{
temp=a;
a=a[j];
a[j]=temp;
}
}
}

p1=a[0];
man1=1;
p2=a[1];
man2=1;

for(i=2;i<n;i++)
{
if(man1==man2)
{
t1=abs(p1+a-p2);
t2=abs(p2+a-p1);

if(t1<t2)
{
p1+=a;
man1++;
}
else
{
p2+=a;
man2++;
}
}
else if(man1>man2)
{
p2+=a;
man2++;
}
else if(man2>man1)
{
p1+=a[i];
man1++;
}

}
if(p1<p2)
printf("%d %d",p1,p2);
else
printf("%d %d",p2,p1);
}
}
int main()
{
work();
return 0;
}[/cpp]

[Tomislav Novak]

Hello.

I'm trying to solve dynamic programming problems on UVA and I'm stuck on problem 10032, Tug of War.

My code is basically the same as for 562 (Dividing Coins), plus the part that checks whether the difference between number of people in each team is at most 1.

Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.

If I've understood the problem correctly, then if the number of people is even, both teams will always have equal number of member, and if the number of people is odd, the difference will always be 1.

The algorithm I use: enumerate all possible weights for the first team using dynamic programming (similar to the knapsack problem) and save the number of people needed to achieve this weight. Then loop through all possible weights where the difference between number of members is at most 1, at find the one where the difference between weight_of_all_people - weight_of_people_in_team_1 is minimum.

Here's what my program outputs for following test data:

Code: Select all

2

4
100
200
300
600

5
100
200
300
400
500

Code: Select all

500 700

700 800

[c]
#include <stdio.h>
#include <limits.h>

#define MAXPEOPLE 100
#define MAXWEIGHT 450
#define MAXSUM MAXPEOPLE * MAXWEIGHT
#define MAX(A, B) ((A) > (B) ? (A) : (B))
#define MIN(A, B) ((A) < (B) ? (A) : (B))
#define ABS(A) ((A) < 0 ? -((A)) : (A))

struct
{
int pos, pic;
} weights[MAXSUM + 1];

int ncases, npeople, sum;

int main()
{
int i, j, w, min, result;

scanf("%d", &ncases);

while (ncases)
{
scanf("%d", &npeople);

for (i = 1; i <= MAXSUM; i++)
{
weights.pos = 0;
weights.pic = INT_MAX;
}

weights[0].pos = 1;
weights[0].pic = 0;

sum = 0;
for (i = 0; i < npeople; i++)
{
scanf("%d", &w);
sum += w;

for (j = MAXSUM; j >= w; j--)
if (weights[j - w].pos)
{
weights[j].pos = 1;
if (ABS((weights[j - w].pic + 1) - npeople) < weights[j].pic)
weights[j].pic = weights[j - w].pic + 1;
}
}

min = INT_MAX;
for (i = 0; i <= sum; i++)
if (weights.pos && ABS(2 * weights.pic - npeople) <= 1)
if (ABS(2 * i - sum) < min)
{
min = ABS(2 * i - sum);
result = i;
}

printf("%d %d\n", MIN(result, sum - result), MAX(result, sum - result));

if (ncases > 1) printf("\n");
ncases--;
}

return 0;
}
[/c]

Help of any kind is appreciated.

Tomislav

[Tomislav Novak]

I finally managed to find out why I'm getting WA, but I still can't fix it (i get TLE or MLE).
Consider this test data:

Code: Select all

1

4
100 
50
50
200

If one team has weight 100, then it can consist of only one man (the one with weight 100) or two men with weights 50. So, weight 100 can be achieved with 1 or 2 people.
[c]
weights[j].pic = weights[j - w].pic + 1;
[/c]
This is the part of my original source where I update the number of people that can be contained in a team of weight j as a number of people in team j - w (where w is weight of man i) plus one. However, I should here consider all numbers off people j - w can contain (both 1 and 2 in previous example).

Code: Select all

struct
{
  int pos, pic;
} weights[MAXSUM + 1];

If i change pic (pic = number of men...) to an array, then i have to add two more loops: one that checks all ways weight j - w can be made, and one that checks if some way is already saved in pic array (so I don't add duplicates).

This is obviously too slow and results in a TLE. If I add another boolean array the i get MLE.

How can I efficiently consider all ways weight j - w can be achieved when computing weight j?

Please help!

[Minilek]

consider a greedy approach that starts off with two teams of people and continuously modifies the teams until they can't be made better.

i proved to myself this works and (falsely) proved to myself it was fast and got AC in 0.000. now that i see a flaw in my proof that this algorithm is fast, can anyone explain to me why it really did end up being so fast?

thanks.

[tan_Yui]

I got WA too....
Could anyone give me some more I/O ?
Following is I/O which I prepared.

Input :

7

3
100
90
200

12
1
2
3
4
5
6
6
5
4
3
2
1

4
1
5
5
9

10
9
1
1
1
1
1
1
1
1
1

4
400
200
100
100

1
77

6
1
3
2
4
3
5

Output :

190 200

21 21

10 10

5 13

300 500

0 77

9 9

And, I have a question about this :

INPUT
400
200
100
100

output
500 300

I think the right output is 300 500 because

If these numbers differ, give the lesser first.

Is my idea wrong?

Thank you.

[tan_Yui]

Hello, I got WA again and again....
I want help to solve problem 10032.
Could anyone answer me my questions which posted above?

Thank you.

[jeu blanc]

Salut!

I've tried to solve "Tug of War" several times, but the Judge just doesn't believe, my solution is correct...

I need either more testcases or somebody who would review the code I've added after this posting, please.

Thanks a lot!
Greetings,
Tarek.


___________

I've just found the first mistake in the algorithm I used by myself.
Updated source-code follows:
______________________

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

int main(int argc, char *argv[])
{
int testCases;
int numberOfPeoples;
int peoplesWeight[100];
int teamA;
int teamB;
int balanceFactor;
int differenceA;
int differenceB;
int i;
int j;
int temp;
int index;

(void) scanf("%d", &testCases);

while (testCases) {
testCases--;

for (i = 0; i < 100; i++) {
peoplesWeight = 0;
}

(void) scanf("%d", &numberOfPeoples);

for (i = 0; i < numberOfPeoples; i++) {
(void) scanf("%d", &peoplesWeight);
}

for (i = 0; i < numberOfPeoples; i++) {
for (j = 1; j < numberOfPeoples; j++) {
if (peoplesWeight[j-1] < peoplesWeight[j]) {
temp = peoplesWeight[j-1];
peoplesWeight[j-1] = peoplesWeight[j];
peoplesWeight[j] = temp;
}
}
}

teamA = teamB = 0;
balanceFactor = 0;
teamA += peoplesWeight[0];
teamB += peoplesWeight[1];

for (index=2; index < numberOfPeoples; index++) {
if (balanceFactor == -1) {
teamB += peoplesWeight[index];
balanceFactor++;
}
else if (balanceFactor == 1) {
teamA += peoplesWeight[index];
balanceFactor--;
}
else {
differenceA = (teamA + peoplesWeight[index])-teamB;
differenceB = (teamB + peoplesWeight[index])-teamA;

if (differenceA < differenceB) {
teamA += peoplesWeight[index];
balanceFactor--;
}
else {
teamB += peoplesWeight[index];
balanceFactor++;
}
}
}

if (teamA > teamB) {
temp = teamB;
teamB = teamA;
teamA = temp;
}

printf("%d %d\n\n", teamA, teamB);
}
return 0;
}#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
int testCases;
int numberOfPeoples;
int peoplesWeight[100];
int teamA;
int teamB;
int balanceFactor;
int differenceA;
int differenceB;
int i;
int j;
int temp;
int index1;
int index2;

(void) scanf("%d", &testCases);

while (testCases) {
testCases--;

for (i = 0; i < 100; i++) {
peoplesWeight = 0;
}

(void) scanf("%d", &numberOfPeoples);

for (i = 0; i < numberOfPeoples; i++) {
(void) scanf("%d", &peoplesWeight);
}

for (i = 0; i < numberOfPeoples; i++) {
for (j = 1; j < numberOfPeoples; j++) {
if (peoplesWeight[j-1] < peoplesWeight[j]) {
temp = peoplesWeight[j-1];
peoplesWeight[j-1] = peoplesWeight[j];
peoplesWeight[j] = temp;
}
}
}

teamA = teamB = 0;
balanceFactor = 0;
teamA += peoplesWeight[0];
teamB += peoplesWeight[1];
index1 = 2;
index2 = numberOfPeoples-1;
while (index1 < numberOfPeoples && index1 <= index2) {
if (balanceFactor == -1) {
if (teamB < teamA) {
teamB += peoplesWeight[index1];
balanceFactor++;
index1++;
}
else {
teamB += peoplesWeight[index2];
balanceFactor++;
index2--;
}
}
else if (balanceFactor == 1) {
if (teamA < teamB) {
teamA += peoplesWeight[index1];
balanceFactor--;
index1++;
}
else {
teamA += peoplesWeight[index2];
balanceFactor--;
index2--;
}
}
else {
differenceA = (teamA + peoplesWeight[index1])-teamB;
differenceB = (teamB + peoplesWeight[index1])-teamA;

if (differenceA < differenceB) {
teamA += peoplesWeight[index1];
balanceFactor--;
index1++;
}
else {
teamB += peoplesWeight[index1];
balanceFactor++;
index1++;
}
}
}

if (teamA > teamB) {
temp = teamB;
teamB = teamA;
teamA = temp;
}

printf("%d %d\n\n", teamA, teamB);
}
return 0;
}

[jaredjohnson]

1

11
10
3
3
3
3
3
1
1
1
1
1

Should give:

15 15

[tan_Yui]

Thank you for your reply, jaredjohnson !
I try to check my code again after I return to my home town.
My code might output wrong answer '12 18' instead of '15 15'.

Best regards.

[Md. Afsar Uddin(SUST)]

Following Program is Accepted:

#define SIZE 100
#define MAX 450

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

char c[SIZE / 2 + 1][SIZE / 2 * MAX + 1];
int n, weight[SIZE + 1];

int main(void)
{
int i, j, k, min, sum, test_case;

scanf(" %d", &test_case);

while(test_case--)
{
scanf(" %d", &n);

for(i = 0, sum = 0; i < n; i++)
{
scanf(" %d", &weight);
sum += weight;
}

memset(c, 0, sizeof(c));
c[0][0] = 1;

//Generating the weight-sum of all combinations.
//'c[j]' will be '1' if it's possible to make weight 'j' with 'i' persons.
for(i = 0; i < n / 2; i++)
{
for(j = 0; j <= i * MAX; j++)
{
if (c[j])
{
for(k = 0; k < n; k++)
c[i + 1][j + weight[k]] = 1;
}
}
}

for(i = n / 2, j = 0, k = n / 2 * MAX, min = sum; j <= k; j++)
{
if (c[j] && abs(sum - 2 * j) < abs(sum - 2 * min)) min = j;
}

if (min < (sum - min)) printf("%d %d\n", min, sum - min);
else printf("%d %d\n", sum - min, min);

if (test_case != 0) printf("\n");
}

return 0;
}

But this give me following input/output

Input:

3

4
1
1
3
7

6
1
1
1
1
11
3

6
10
1
1
2
3
3

Output:

6 6
9 9
9 11

But correct output should be:

4 8
5 13
8 12

[Sedefcho]

Below I give all test cases I have tested my program with.

This program still gets WA although the answers seem OK.

Could someone who has an ACC program

1) verify them

2) give me more test cases if all my answers for these test
cases are correct


INPUT

Code: Select all

16

4
10
22
99
13

3
100
90
200

3
200
90
100

4
100
90
101
200

4 
100 
200 
300 
600 

5 
100 
200 
300 
400 
500

4 
100 
50 
50 
200

4
400 
200 
100 
100

11 
10 
3 
3 
3 
3 
3 
1 
1 
1 
1 
1

3 
100 
90 
200 

12 
1 
2 
3 
4 
5 
6 
6 
5 
4 
3 
2 
1 

4 
1 
5 
5 
9 

10 
9 
1 
1 
1 
1 
1 
1 
1 
1 
1 

4 
400 
200 
100 
100 

1 
77 

6 
1 
3 
2 
4 
3 
5 

OUTPUT

Code: Select all

35 109

190 200

190 200

201 290

500 700

700 800

150 250

300 500

15 15

190 200

21 21

10 10

5 13

300 500

0 77

9 9

[Deno]

I am getting TLE even though I use DP.
My run time is (number of people * number of people/2 * total weight/2)
I use a boolean array
"array[3][100]=true" means it is possible to have 3 people with total weight=100.

Does it sound right?

How do people approach this problem?

Thank you

(should I attach my code?)

[Solaris]

number of people = 100
maximum weight = 450

My run time is (number of people * number of people/2 * total weight/2)

In worst case your complexity comes : 100 * 50 * 22500 = 112500000

I dont think its an acceptable solution. Think about looping through only those weights that has been achieved in the previous levels ... not all possible weights.