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

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 am

Post by Deno » Thu Nov 03, 2005 8:36 am

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

Code: Select all

deleted
Last edited by Deno on Thu Nov 03, 2005 4:33 pm, edited 1 time in total.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » 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.
Where's the "Any" key?

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 am

Post by Deno » 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?

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » 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
Where's the "Any" key?

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 am

Post by Deno » 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?

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » 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.
Where's the "Any" key?

Deno
New poster
Posts: 21
Joined: Fri Sep 19, 2003 8:24 am

Post by Deno » Sun Nov 06, 2005 5:54 pm

:) Thank you

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

10032 WA

Post by mohsincsedu » 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!!!!

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » 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"
Where's the "Any" key?

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Post by mohsincsedu » Fri Sep 01, 2006 10:41 am

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

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

I do not understand...................
Amra korbo joy akhdin............................

Charles Miller
New poster
Posts: 2
Joined: Sat Oct 28, 2006 5:51 pm

10032 WA

Post by Charles Miller » 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?

Charles Miller
New poster
Posts: 2
Joined: Sat Oct 28, 2006 5:51 pm

Post by Charles Miller » 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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » 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

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

10032 (cont'd)

Post by Darko » 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

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

Post by pineapple » Fri Dec 01, 2006 3:12 pm

Code: Select all

ACed
Last edited by pineapple on Mon Apr 23, 2007 10:18 am, edited 4 times in total.

Post Reply

Return to “Volume 100 (10000-10099)”