10891 - Game of Sum

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

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Aug 17, 2005 3:44 pm

My AC code doesn't handle overflow as a special case..

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Post by Towhid » Sat Aug 20, 2005 7:53 am

Matched all the I/O given by jagadish
At last got ac just changing my INF from 2e50 to 1000000000000000. :o
Don't know what happened :(
From 0 to 0

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Post by Towhid » Sat Aug 20, 2005 7:54 am

Matched all the I/O given by jagadish
At last got ac just changing my INF from 2e50 to 1000000000000000. :o
Don't know what happened :(
Well, thanks a lot........
From 0 to 0

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Wed Aug 24, 2005 12:53 pm

10891 is a simple DP

You can cut the digits down from left side or right side
and count the diffence between two players by turns

I got ac by this way

the dp should be O(n^3)

rasel4all
New poster
Posts: 3
Joined: Sat Sep 10, 2005 6:55 pm

10891 - Game of Sum

Post by rasel4all » Mon Sep 12, 2005 2:24 pm

I have already read that one. But I did not understand. I need some brief descriptio. to solve this one. So please anyone can give me any good hints to solve this one. Thanks.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Sep 12, 2005 3:43 pm

Did you notice that if you try to find a winning strategy for a given game state, all of the previous moves that have been made up to that point don't matter?

Knowing this, note that at any point, there are only 2n-1 possible moves. And how many possible game configurations are there? If there aren't too many, can you compute them all?
If only I had as much free time as I did in college...

rasel4all
New poster
Posts: 3
Joined: Sat Sep 10, 2005 6:55 pm

Post by rasel4all » Mon Sep 12, 2005 8:14 pm

Can u explain by using some sample data. Please

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Sep 12, 2005 8:28 pm

Suppose your input is

Code: Select all

4 -20 8 -1 -2
Then n=5 is the length of the sequence.
You have 2n-1 = 9 possible moves:

Code: Select all

take 4
take 4 -20
take 4 -20 8
take 4 -20 8 -1
take 4 -20 8 -1 -2
take -20 8 -1 -2
take 8 -1 -2
take -1 -2
take -2
In each of these cases, your opponent will be left with a sub-array (a piece of the original array). Then your opponent will make a move, and you will get a smaller sub-array. Then you make a move again, etc. until nothing is left.

How many different sub-arrays of the original 5-element array are there? If you think about it for 10 seconds, you will see that there are 16 (including the sub-array of length 0). In general, an array of length n has n(n+1)/2+1 sub-arrays. Each of them corresponds to a game situation. So if n is at most 100, then there are fewer than 100000 possible game situations.

Now note that if you start with a sub-array of length X and make a move, then you will get a sub-array of length smaller than X. Suppose that you already know how to solve this probem for sub-arrays of length smaller than X. To solve it for a sub-array of length X, you should just try to make all of the possible moves and pick the one that gives the best value, assuming that your opponent knows how to play optimally after that.

Finally, use induction to get from X=0 up to X=n. Does this make any sense?
If only I had as much free time as I did in college...

rasel4all
New poster
Posts: 3
Joined: Sat Sep 10, 2005 6:55 pm

Post by rasel4all » Tue Sep 13, 2005 11:12 pm

Thank u very much. I got it now. Thanks again for your help.

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

10891 - Game of Sum

Post by DP » Sun Aug 13, 2006 11:36 am

Code: Select all

accepted
Last edited by DP on Sun Aug 13, 2006 4:25 pm, edited 1 time in total.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: help me...10891

Post by Martin Macko » Sun Aug 13, 2006 3:40 pm

DP wrote:can someone tell me why i am getting TLE?
i did memorization for this problem but still TLE. :(
Here is my code:
I don't know why you are getting TLE, but anyway you code is wrong. Try the following input:

Code: Select all

6
15 -16 17 18 -19 13
0
The correct output is:

Code: Select all

28
But your answer is 35.

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Sun Aug 13, 2006 4:24 pm

thnx a lot. Martin. :)

beno
New poster
Posts: 1
Joined: Wed Feb 10, 2010 11:17 am

Runtime Error on Problem 10891 - Game of Sum

Post by beno » Wed Feb 10, 2010 11:23 am

Hi, it's the first time I submit the solution to the online-judge on Problem "10891 - Game of Sum". But the "Runtime Error" result really confused me since I can get the correct solution of the sample input. Here is my code, hope someone can give me a tip. Thank you.

Code: Select all

#include <iostream>
#include <fstream>
#include <cassert>

using namespace std;

#define MAXLEN 1000

int bet[MAXLEN];

/* return maximum sum of subsequence in sequence arr 
* @param	arr		sequence to search 
* @param	n		size of sequence
*/
int maxSubseqSum(int seq[], int n);

int main(void)
{
	int n, total;
	ifstream fin("e.in");

	assert(fin);

	while (fin >> n) {
		if (n == 0) break;

		for (int i = 0; i < n; i++)
			fin >> bet[i];

		total = maxSubseqSum(bet, n);
		cout << total << endl;
	}

	return 0;
}

int maxSubseqSum(int seq[], int n)
{
	int sum, maxsum;

	assert(n >= 0);

	maxsum = sum = seq[0];
	for (int i = 1; i < n; i++) {
		if (sum < 0)
			sum = 0;
		sum += seq[i];

		if (maxsum < sum)
			maxsum = sum;
	}

	return maxsum;
}

smithdwsn
New poster
Posts: 4
Joined: Mon May 24, 2010 8:50 pm

Re: Runtime Error on Problem 10891 - Game of Sum

Post by smithdwsn » Tue May 25, 2010 3:15 pm

I think you should recheck this part of your code. In that, there is some mistakes.
int maxSubseqSum(int seq[], int n);

int main(void)
{
int n, total;
ifstream fin("e.in");

assert(fin);

while (fin >> n) {
if (n == 0) break;

for (int i = 0; i < n; i++)
fin >> bet;

total = maxSubseqSum(bet, n);
cout << total << endl;
}

return 0;
}

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10891 - Game of Sum

Post by kbr_iut » Thu Jun 10, 2010 1:55 pm

polone wrote,
the dp should be O(n^3)
mine is O(N^2)
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Post Reply

Return to “Volume 108 (10800-10899)”