10032 - Tug of War

[Deno]

Thanks for your suggestion...
this time I am getting a prenstation error...

Code: Select all

deleted

[Solaris]

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

[Deno]

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

I got PE even if I put
cout<<sol<<' '<<totalw-sol<<endl<<endl;
Why?

[Solaris]

The outputs of two consecutive cases will be separated by a blank line.

It means that there will be no blank line after the last test case

[Deno]

I got accepted now!! Thank you sooo much!

By the way, how did other people approach this problem?
How could they solve the question within 1 sec?

[Solaris]

DFS with some prooning and an array like yours to check for the repeatation of combination is a good method to solve this problem.

[Deno]

Thank you

[mohsincsedu]

Hi all............................

I got Acc in 562 but WA in 10032

Why................................???

Here is my code:

Code: Select all

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


#define MAXCOINS 102
#define MAXCENTS 455
#define MAXSUM MAXCOINS * MAXCENTS


int nway[MAXSUM + 1];
int ncoins, value, sum;

void main()
{
	int test, i, j, min,m,first,flag=1;

	scanf("%d", &test);
	while (test--)
	{
		memset(nway, 0, sizeof(nway));
		nway[0] = 1;

		sum = 0;
		m = -1;

		scanf("\n%d", &ncoins);
		for (i = 0; i < ncoins; i++)
		{
			scanf("%d", &value);
			sum += value;

			for (j = MAXSUM - value; j >= 0; j--)
				if (nway[j])
					nway[j + value] = 1;
		}

		m = min = 3000;
		first = 0;

		for (i = 0; i <= sum; i++)
			if (nway[i] && abs(2 * i - sum) < min)
			{
				min = abs(2 * i - sum);
				if(min<m)
				{
					if(i>sum/2)
					{
						first = i - min;

					}
					else
						first = i;
					m = min;
				}
			}

		if(!flag)
			printf("\n");
		flag = 0;
		printf("%d %d\n", first,first+m);


	}

}

Thanks in Advanced!!!!

[Solaris]

Hello Mohsin,

Its true that 562 and 10032 are quite similar problems, but they are not identical. You should put more attention to the following lines of the problem description

the number of people on the two teams must not differ by more than 1

For the following input:

1
5
500
100
100
100
100

Your code gives "400 500" where my AC program gives "300 600"

[mohsincsedu]

Hello Solaris............

Plz give me some ideas....................

I do not understand...................

[Charles Miller]

Hi, I am new to this thing here, however, I am in college and our class uses these as challenges per say. Now, I am trying to solve 10032, and it gives me correct output for all the test cases that have been provided so far on the subject, however, I am sure there are still some special test cases that it is not passing. Anyone possibly know what other cases could it not be passing?

here are the ones it passes

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

Any possible other cases?

[Charles Miller]

well, tried a different algorithm, but now I keep on getting MLE, so does anyone possibly have any type of ideas they can give to possibly save me some memory here and there. Any help is appreciated.

[sclo]

well, tried a different algorithm, but now I keep on getting MLE, so does anyone possibly have any type of ideas they can give to possibly save me some memory here and there. Any help is appreciated.

Consider using stl's hash_map, or making your own hash tables to store the values.
Most of the values are not needed, that's why hashing works to avoid MLE.

The algorithm is the obvious DP, do the DP recursively, and a little pruning is needed to avoid TLE. In order to see how to prune, sort the input first.

I managed to get it down to 0.055 secs

[Darko]

Well, Carlos locked that thread in Bugs and Suggestions, so I will respond here (where it's not very likely he'll see it )

Anyway, as I've said, input for this problem is 30Kb long, so I don't understand why Java programmers had to optimize their codes to compensate the time expense. I think it's only a coincidence that they got AC.

Well, I thought the same, but I tried this problem last night:
http://acmicpc-live-archive.uva.es/nuev ... php?p=2825
My l*m^2 solution in Java timed out. But when I recoded it in C - it got accepted in ~2secs. It's not I/O, because it has a ~32kb file (as 10032) and I read the whole file in Java before processing. There might be some overhead because I use Strings (and they are objects in Java), but I use them just to build a graph, comparing them as I do in C (as arrays).

I have no idea what makes Java solution time out in that case and C solution pass. I ran both of them on our Linux server, they run in about the same time. C is faster (~3x) if I use -O2, but I doubt judge uses any optimization. And keep in mind that Java that I ran was interpreted, not compiled like on UVa.

I was looking forward to the new judge and new Java, but it doesn't look like it is going to happen any time soon.

Darko

[pineapple]

Code: Select all

ACed