10032 - Tug of War

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

Moderator: Board moderators

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 10032 (cont'd)

Post by Sedefcho » Thu Feb 05, 2009 6:54 pm

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.programming-challenges.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.programming-challenges.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.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Re: 10032 (cont'd)

Post by Darko » Thu Feb 05, 2009 7:58 pm

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 10032 - Tug of War

Post by Sedefcho » Fri Mar 20, 2009 3:12 pm

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

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.

poixp
New poster
Posts: 20
Joined: Mon Apr 07, 2008 11:05 am

Re: 10032 - Tug of War

Post by poixp » Fri Mar 20, 2009 3:32 pm

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


User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 10032 - Tug of War

Post by Sedefcho » Sat Mar 21, 2009 11:50 am

Is this from an ACC program ?!

Your output for the 5-th 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
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?

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 10032 - Tug of War

Post by Sedefcho » Sat Mar 21, 2009 1:25 pm

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.

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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 10032 - Tug of War

Post by Sedefcho » Sat Mar 21, 2009 6:17 pm

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 sub-optimal) 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.

poixp
New poster
Posts: 20
Joined: Mon Apr 07, 2008 11:05 am

Re: 10032 - Tug of War

Post by poixp » Mon Mar 23, 2009 2:44 pm

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 10032 - Tug of War

Post by Sedefcho » Mon Mar 23, 2009 3:20 pm

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).

kdawg
New poster
Posts: 1
Joined: Sat Oct 31, 2009 10:30 am

Re: 10032 - Tug of War

Post by kdawg » Sat Oct 31, 2009 10:48 am

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.

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

apautz22
New poster
Posts: 1
Joined: Tue Nov 02, 2010 3:38 am

Re: 10032 - Tug of War

Post by apautz22 » Tue Nov 02, 2010 4:01 am

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

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

clamhunter
New poster
Posts: 2
Joined: Mon Nov 01, 2010 6:47 am

Re: 10032 - Tug of War

Post by clamhunter » Tue Nov 09, 2010 2:43 am

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:

Code: Select all

1 
8 
120 
111 
111 
101 
20 
11 
11 
1 
Output:

Code: Select all

243 243

sir. manuel
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

Re: 10032 - Tug of War

Post by sir. manuel » Tue Dec 21, 2010 11:17 pm

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((sum-suma)<(sum-sum2)){ 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=sum-sum2;  flag++;;
            if(var<sum2)  printf("%d %d\n",var,sum2);
              else  printf("%d %d\n",sum2,var);
                         
      }
return 0;
}

asif_iut
New poster
Posts: 16
Joined: Mon Nov 01, 2010 8:08 am

Re: 10032 - Tug of War

Post by asif_iut » Wed Dec 22, 2010 8:51 am

Think about dp( knapsack ) where the capacity of the knapsack is ( total weight of all people ) / 2 . Hope this helps :D

sir. manuel
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

Re: 10032 - Tug of War

Post by sir. manuel » Sat Dec 25, 2010 12:56 am

firts i think in the snakpsack,,,but the problem say "numbersTeamA-numbersTeamB<=1 "...how i can chance to algorithm of snapsack???

Post Reply

Return to “Volume 100 (10000-10099)”