10032  Tug of War
Moderator: Board moderators
Re: 10032 (cont'd)
I tried this problem (Tug of War) really hard both in Java and C++.
I did not manage to get ACC in UVA i.e. here (at least not yet).
http://icpcres.ecs.baylor.edu/onlinejudge/
But I got ACC here (problem ID is 110805  (0.56 secs) in Java ACC)
http://www.programmingchallenges.com/
just by submitting once and I submitted the
same Java code I tried already on UVA a lot of times.
I don't know but there's something suspicious about this problem in UVA.
Maybe the two input files are different,
I mean file here
http://www.programmingchallenges.com/
is different maybe from file there
http://icpcres.ecs.baylor.edu/onlinejudge/
I am not sure.
But it is very very difficult to get ACC in Java in UVA (on 10032)
http://icpcres.ecs.baylor.edu/onlinejudge/
I am pretty sure about that.
I did not manage to get ACC in UVA i.e. here (at least not yet).
http://icpcres.ecs.baylor.edu/onlinejudge/
But I got ACC here (problem ID is 110805  (0.56 secs) in Java ACC)
http://www.programmingchallenges.com/
just by submitting once and I submitted the
same Java code I tried already on UVA a lot of times.
I don't know but there's something suspicious about this problem in UVA.
Maybe the two input files are different,
I mean file here
http://www.programmingchallenges.com/
is different maybe from file there
http://icpcres.ecs.baylor.edu/onlinejudge/
I am not sure.
But it is very very difficult to get ACC in Java in UVA (on 10032)
http://icpcres.ecs.baylor.edu/onlinejudge/
I am pretty sure about that.
Re: 10032 (cont'd)
I think PC still has the original input file. It changed a few times on UVa, they added cases to break certain types of solutions.
Re: 10032  Tug of War
Could someone having an Accepted program please
verify this I/O below? Thanks a lot in advance.
(Additional Note #1: the question posed above
is now obsolete/outdated).
Additional Note #2: This I/O below is
from an Accepted program already so I hope
it can be useful as a reference from now on.
INPUT
OUTPUT
verify this I/O below? Thanks a lot in advance.
(Additional Note #1: the question posed above
is now obsolete/outdated).
Additional Note #2: This I/O below is
from an Accepted program already so I hope
it can be useful as a reference from now on.
INPUT
Code: Select all
25
1
10
2
100
1
3
2
200
2
4
2
100
1
1
18
1
1
2
2
2
2
3
3
4
4
5
5
6
6
7
7
54
8
82
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
10
20
30
40
50
60
70
80
9
1
101
107
82
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
10
20
30
40
50
60
70
80
9
1
101
106
82
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
10
20
30
40
50
60
70
80
9
1
101
106
82
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
10
20
30
40
50
60
70
80
9
1
101
106
82
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
10
20
30
40
50
60
70
80
9
1
101
106
82
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
10
20
30
40
50
60
70
80
9
1
101
106
82
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
10
20
30
40
50
60
70
80
9
1
101
106
82
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
10
20
30
40
50
60
70
80
9
1
101
106
82
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
10
20
30
40
50
60
70
80
9
1
101
106
82
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
10
20
30
40
50
60
70
80
9
1
101
106
3
100
90
200
15
10
3
3
3
3
3
1
1
1
1
1
12
13
14
15
1
50
5
444
120
100
100
100
6
1
1
2
21
1
1
91
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
5
5
5
5
5
100
92
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
5
5
5
5
5
3
80
10
80
1
1
1
1
7
7
7
7
10
8
2
2
3
2
3
3
80
3
18
88
2
2
2
2
1
1
3
3
4
5
6
7
8
4
5
6
7
OUTPUT
Code: Select all
0 10
1 100
4 200
3 101
52 70
481 482
486 486
481 481
481 481
481 481
481 481
481 481
481 481
481 481
481 481
190 200
42 42
0 50
320 544
4 23
141 144
134 134
38 84
12 86
52 104
Last edited by Sedefcho on Sun Mar 22, 2009 5:12 pm, edited 6 times in total.
Re: 10032  Tug of War
Here is my output
Code: Select all
0 10
1 100
4 200
3 101
61 61
481 482
486 486
481 481
481 481
481 481
481 481
481 481
481 481
481 481
481 481
190 200
42 42
0 50
320 544
4 23
142 143
134 134
38 84
12 86
52 104
Re: 10032  Tug of War
Is this from an ACC program ?!
Your output for the 5th test case is wrong, no?
Here we need to form 2 groups of 9 people each.
And in one of the groups we cannot have total weight
which is less than: 70 = 54 + 1 + 1 + 2 + 2 + 2 + 2 + 3 + 3.
So the best we can achieve in this case is to have 70 in the first
group and whatever weight remains goes to the second group.
And your program gives 61 61 as an answer?!
How come?
Your output for the 5th test case is wrong, no?
Code: Select all
18
1
1
2
2
2
2
3
3
4
4
5
5
6
6
7
7
54
8
And in one of the groups we cannot have total weight
which is less than: 70 = 54 + 1 + 1 + 2 + 2 + 2 + 2 + 3 + 3.
So the best we can achieve in this case is to have 70 in the first
group and whatever weight remains goes to the second group.
And your program gives 61 61 as an answer?!
How come?
Re: 10032  Tug of War
By the way there's one more test case where our outputs differ.
And I also cannot agree with your output there. The test case is below.
Here we have 91 numbers/weights, one number/weight is 100, 45 of the numbers are 1s. And the others are visible below.
So apparently we cannot make the sum in one of the groups less/smaller than 100 + 44 times * 1 which equals 144.
And so I don't know why your program gives 142 143 as an answer.
Please correct me if I am missing something.
And I also cannot agree with your output there. The test case is below.
Here we have 91 numbers/weights, one number/weight is 100, 45 of the numbers are 1s. And the others are visible below.
So apparently we cannot make the sum in one of the groups less/smaller than 100 + 44 times * 1 which equals 144.
And so I don't know why your program gives 142 143 as an answer.
Please correct me if I am missing something.
Code: Select all
91
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
5
5
5
5
5
100
Re: 10032  Tug of War
Yes, now I am quite sure my outputs above are correct.
I finally got ACC on this problem and I am quite
happy now due to the unusual approach I used.
Actually I wanted to prove to myself that it is possible
to get ACC in this way on this hard problem.
1) I run a genetic (heuristics) algorithm (I optimized only the obvious parts of it).
2) After the genetic algorithm completes, I run a short greedy algorithm just
to find out whether there are any obvious (nearby) improvements to the
(possibly suboptimal) solution found by the genetic algorithm.
And in fact, the step 2) proved crucial for getting ACC.
Another crucial thing is to print one \n and
not two \n\n after the last test case
I guess this post cannot be considered a spoiler.
Good luck to all who are (or will be) working on this problem.
I finally got ACC on this problem and I am quite
happy now due to the unusual approach I used.
Actually I wanted to prove to myself that it is possible
to get ACC in this way on this hard problem.
1) I run a genetic (heuristics) algorithm (I optimized only the obvious parts of it).
2) After the genetic algorithm completes, I run a short greedy algorithm just
to find out whether there are any obvious (nearby) improvements to the
(possibly suboptimal) solution found by the genetic algorithm.
And in fact, the step 2) proved crucial for getting ACC.
Another crucial thing is to print one \n and
not two \n\n after the last test case
I guess this post cannot be considered a spoiler.
Good luck to all who are (or will be) working on this problem.
Re: 10032  Tug of War
I'm sorry for wrong output but my program got ACC. I think that some of tests cases are not present in judge test script.
Re: 10032  Tug of War
Yes, sure, no problem, I just wanted to clarify which outputs are logically
correct. And yes, the inputs I posted are mostly generated by myself, I have
no idea what the I/O on the judge is. But I think the judge data is pretty
strong, it's hard to get ACC on this problem (in my impression).
correct. And yes, the inputs I posted are mostly generated by myself, I have
no idea what the I/O on the judge is. But I think the judge data is pretty
strong, it's hard to get ACC on this problem (in my impression).
Re: 10032  Tug of War
Hmmm, I don't think I'm using a DP solution but can anyone point out why my solution might not be correct. Or supply a test case where my code fails.
Basically, I assign the first N/2(integer division) people to team_a, the rest to team_b(if N is even a perfect split, if N is odd the smaller team will be team_a). Then I calculate the difference between the two teams. Then I compare how the difference between the two teams would change if I swapped two members. When I find the optimal swap I do so, and then recheck until no swaps are performed. Worst case there are 100 people, 50 per team. No more than half of a team can be wrong. So there's at most 25 swaps, each swap check requires comparing every one of the 50 people on team_a to the 50 on team_b, so 2500 compares per swap check, 25 max swaps is a total of 62500 compares. So the program executes rather quickly even in the worst case. I've tried to keep the code as modular as possible to keep it understandable. Let me know if I should add comments to explain anything I'm doing.
I've tested against all of Sedefcho input and all of my output matches what's listed. I must be missing some edge case.
Basically, I assign the first N/2(integer division) people to team_a, the rest to team_b(if N is even a perfect split, if N is odd the smaller team will be team_a). Then I calculate the difference between the two teams. Then I compare how the difference between the two teams would change if I swapped two members. When I find the optimal swap I do so, and then recheck until no swaps are performed. Worst case there are 100 people, 50 per team. No more than half of a team can be wrong. So there's at most 25 swaps, each swap check requires comparing every one of the 50 people on team_a to the 50 on team_b, so 2500 compares per swap check, 25 max swaps is a total of 62500 compares. So the program executes rather quickly even in the worst case. I've tried to keep the code as modular as possible to keep it understandable. Let me know if I should add comments to explain anything I'm doing.
I've tested against all of Sedefcho input and all of my output matches what's listed. I must be missing some edge case.
Code: Select all
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef vector<int> vec;
typedef vector<int>::iterator iter;
typedef struct
{
iter a;
iter b;
} optPoint;
void process_case(void);
void get_start_teams(int,vec &,vec &);
double get_total_weight(vec &);
void solve(int,vec &,vec &,double &,double &);
optPoint find_best_swap(vec &,vec &,double,double);
int main()
{
int numCases=0;
cin>>numCases;
for(int i=0;i<numCases;++i)
{
if(i!=0)
{
cout<<endl;
}
process_case();
}
return 0;
}
void process_case(void)
{
int numPeople=0;
double total_a=0;
double total_b=0;
vec team_a;
vec team_b;
cin>>numPeople;
get_start_teams(numPeople,team_a,team_b);
total_a=get_total_weight(team_a);
total_b=get_total_weight(team_b);
solve(numPeople,team_a,team_b,total_a,total_b);
cout<<(int)min(total_a,total_b)<<' '<<(int)max(total_a,total_b)<<endl;
}
void get_start_teams(int numPeople, vec &team_a,vec &team_b)
{
int weight=0;
for(int i=0;i<numPeople;++i)
{
cin>>weight;
if(i<(numPeople/2))
{
team_a.push_back(weight);
}
else
{
team_b.push_back(weight);
}
}
}
double get_total_weight(vec &v)
{
double rval=0;
for(iter i=v.begin();i!=v.end();++i)
{
rval+=(*i);
}
return rval;
}
void solve(int numPeople,vec &team_a,vec &team_b,double &total_a,double &total_b)
{
bool swaps=true;
optPoint optimum;
while(swaps)
{
swaps=false;
optimum=find_best_swap(team_a,team_b,total_a,total_b);
if(optimum.a!=team_a.end() && optimum.b!=team_b.end())
{
total_a=total_a(*optimum.a)+(*optimum.b);
total_b=total_b(*optimum.b)+(*optimum.a);
if(total_a!=total_b)
{
swaps=true;
}
swap(*optimum.a,*optimum.b);
}
}
}
optPoint find_best_swap(vec &team_a,vec &team_b,double total_a,double total_b)
{
double ratio_diff;
double opt_diff=1;
optPoint rval;
rval.a=team_a.end();
rval.b=team_b.end();
for(iter j=team_a.begin();j!=team_a.end();++j)
{
for(iter k=team_b.begin();k!=team_b.end();++k)
{
ratio_diff=( (*j)(*k) )/(total_a  total_b);
if(ratio_diff<1 && ratio_diff>0)
{
if(abs(ratio_diff  0.5) < opt_diff)
{
opt_diff=abs(ratio_diff  0.5);
rval.a=j;
rval.b=k;
}
}
}
}
return rval;
}
Re: 10032  Tug of War
I am working on the UVa problem 10032  Tug of War, where I'm given the time constraint of 3 seconds to solve the problem. I have pasted the criteria for the problem below.
A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. 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.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The first line of input contains n the number of people at the picnic. n lines follow. The first line gives the weight of person 1; the second the weight of person 2; and so on. Each weight is an integer between 1 and 450. There are at most 100 people at the picnic.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Your output will be a single line containing 2 numbers: the total weight of the people on one team, and the total weight of the people on the other team. If these numbers differ, give the lesser first.
Sample Input
1
3
100
90
200
Sample Output
190 200
My way of doing it is ordering the list of numbers from smallest to largest, and then taking the 2 largest numbers from the list and putting them in groups P and Q. Whichever group is smaller, we add to it a larger number from the original list. Whichever group is larger, we add to it a smaller number from the original list. This keeps going until there are no numbers left in the original list. Simultaneously, we are also keeping track of the number of people in each group, so that no group gets larger than the other by more than 1. I didn't go with a complicated way of doing the problem. This way seems to be fast enough from the test cases that I have tried. I used one of the 25 test case examples earlier in this thread, and it ran in 3 seconds on my laptop, which I have to think that the online judge might run a little bit faster.
My code is here
I don't know why, but the automatic grader tells me I am exceeding the time limit, which one of the possibilities there is an infinite loop. I can't seem to make it error out with any of the test cases I have been able to come up with. If there is anyone out there that can find a test case that does this, or can point out where I have made a mistake, I would be greatly appreciated.
Thanks
Aaron
A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. 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.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The first line of input contains n the number of people at the picnic. n lines follow. The first line gives the weight of person 1; the second the weight of person 2; and so on. Each weight is an integer between 1 and 450. There are at most 100 people at the picnic.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Your output will be a single line containing 2 numbers: the total weight of the people on one team, and the total weight of the people on the other team. If these numbers differ, give the lesser first.
Sample Input
1
3
100
90
200
Sample Output
190 200
My way of doing it is ordering the list of numbers from smallest to largest, and then taking the 2 largest numbers from the list and putting them in groups P and Q. Whichever group is smaller, we add to it a larger number from the original list. Whichever group is larger, we add to it a smaller number from the original list. This keeps going until there are no numbers left in the original list. Simultaneously, we are also keeping track of the number of people in each group, so that no group gets larger than the other by more than 1. I didn't go with a complicated way of doing the problem. This way seems to be fast enough from the test cases that I have tried. I used one of the 25 test case examples earlier in this thread, and it ran in 3 seconds on my laptop, which I have to think that the online judge might run a little bit faster.
My code is here
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <iostream>
using namespace std;
int n, m, a, b, c, d, low, hi, turn, p[2], q[2], z[100] = {0};
void BubbleSort()
{
int i, j, flag = 1; // set flag to 1 to start first pass
int temp; // holding variable
int numLength = m + 1;
for(i = 1; (i <= numLength) && flag; i++)
{
flag = 0;
for (j=0; j < (numLength 1); j++)
{
if (z[j+1] < z[j]) // ascending order simply changes to <
{
temp = z[j]; // swap elements
z[j] = z[j+1];
z[j+1] = temp;
flag = 1; // indicates that a swap occurred.
}
}
}
return; //arrays are passed to functions by address; nothing is returned
}
/*
*
*/
int main(int argc, char** argv) {
cin >> n; //read in how many test cases
for(int i = 0; i <n; i++)
{
cin >> m; //read in how many persons
for(int j = 1; j <= m; j++)
{
cin >> z[j]; //read in the weight of the persons and put them in an array
}
BubbleSort(); //sort the persons
low = 1;
hi = m;
p[0] = 0;
p[1] = 0;
q[0] = 0;
q[1] = 0;
if(m == 1) //in case there is only 1
{
p[0] += z[m];
p[1] ++;
}
else
{
while((hi  low) >= 0) //while there are still people left
{
if((p[0] == q[0]) && ((hi  low) >= 1)) //case where the two ropes are equal
{
p[0] += z[hi]; //add the heaviest person to p
p[1] ++;
hi ; //subtract the heaviest person
q[0] += z[hi]; //add the heaviest person to q
q[1] ++;
hi ; //subtract the heaviest person
}
else if((p[0] > q[0]) && ((hi  low) >= 1)) //case where p>q
{
p[0] += z[low]; //add the lightest person to p
p[1] ++;
low ++; //take out the lightest person
q[0] += z[hi]; //add the heaviest person to q
p[1] ++;
hi ; //subtract the heaviest person
}
else if((p[0] < q[0]) && ((hi  low)) >= 1) //case where p<q
{
p[0] += z[hi]; //add the heaviest person to p
p[1] ++;
hi ; //subtract the heaviest person
q[0] += z[low]; //add the lightest person to p
q[1] ++;
low ++; //take out the lightest person
}
else if((hi  low) == 0) //case where there is an odd number of people
{
if(p[0] < q[0])
{
p[0] += z[hi]; //add the heaviest person to p
p[1] ++;
hi ; //subtract the heaviest person
}
if(p[0] > q[0])
{
q[0] += z[hi]; //add the heaviest person to q
q[1] ++;
hi ; //subtract the heaviest person
}
}
}
}
if(p[0] < q[0]) //print statements
{
cout << p[0] << " " << q[0] << endl << endl;
}
else
{
cout << q[0] << " " << p[0] << endl << endl;
}
}
return 0;
}
I don't know why, but the automatic grader tells me I am exceeding the time limit, which one of the possibilities there is an infinite loop. I can't seem to make it error out with any of the test cases I have been able to come up with. If there is anyone out there that can find a test case that does this, or can point out where I have made a mistake, I would be greatly appreciated.
Thanks
Aaron

 New poster
 Posts: 2
 Joined: Mon Nov 01, 2010 6:47 am
Re: 10032  Tug of War
Aaron, bubble sort is super slow. You can just use the sort method that is in algorithm.h Also the method you use is an approximation algorithm, it won't work for all cases. I came across this test case that broke my similar algorithm
Input:
Output:
Input:
Code: Select all
1
8
120
111
111
101
20
11
11
1
Code: Select all
243 243

 New poster
 Posts: 18
 Joined: Sat Nov 20, 2010 7:44 pm
Re: 10032  Tug of War
I used backtracking to this problem, but i get a TLE!!!,,,can i do more fast my code???
Code: Select all
#include<stdio.h>
#define max 150
int queremos,n,v[max],sum,sum2;
void subset(int indice,int llevamos,int p[])
{
if(llevamos==queremos){ int suma=0; //Queremos=ElementosDeseado
for(int i=0;i<queremos;i++){ //P es el resultado
suma+=p[i];
}
if((sumsuma)<(sumsum2)){ sum2=suma;}
return;
}
for(int i=indice;i<n;i++){ //n=ElementosTotal
p[llevamos]=v[i];
subset(i+1,llevamos+1,p);
}
}
int main()
{
int casos,flag=0; scanf("%d",&casos);
while(casos){ if(flag>0){puts("");}
int num,id=0,aux[max]; scanf("%d",&num); sum=0;
while(num){
scanf("%d",&v[id]); sum+=v[id]; id++;
} n=id; queremos=id/2; sum2=0;
subset(0,0,aux);
int var=sumsum2; flag++;;
if(var<sum2) printf("%d %d\n",var,sum2);
else printf("%d %d\n",sum2,var);
}
return 0;
}
Re: 10032  Tug of War
Think about dp( knapsack ) where the capacity of the knapsack is ( total weight of all people ) / 2 . Hope this helps

 New poster
 Posts: 18
 Joined: Sat Nov 20, 2010 7:44 pm
Re: 10032  Tug of War
firts i think in the snakpsack,,,but the problem say "numbersTeamAnumbersTeamB<=1 "...how i can chance to algorithm of snapsack???