OJ Board

Posted: **Thu Nov 03, 2005 8:36 am**

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

deleted

Posted: **Thu Nov 03, 2005 3:43 pm**

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

Posted: **Thu Nov 03, 2005 4:34 pm**

Solaris wrote:
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?

Posted: **Thu Nov 03, 2005 8:25 pm**

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

Posted: **Thu Nov 03, 2005 11:08 pm**

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?

Posted: **Fri Nov 04, 2005 5:43 am**

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

Posted: **Sun Nov 06, 2005 5:54 pm**

Thank you

Posted: **Sat Nov 19, 2005 12:18 am**

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!!!!

Posted: **Sat Nov 19, 2005 2:42 pm**

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"

Posted: **Fri Sep 01, 2006 10:41 am**

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

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

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

Posted: **Sat Oct 28, 2006 5:55 pm**

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?

Posted: **Tue Oct 31, 2006 7:39 pm**

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.

Posted: **Fri Nov 10, 2006 2:42 am**

Charles Miller wrote: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

Posted: **Sun Nov 12, 2006 8:23 pm**

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

Posted: **Fri Dec 01, 2006 3:12 pm**

Code: Select all

ACed

OJ Board

10032 - Tug of War

10032 WA

10032 WA

10032 (cont'd)