10891  Game of Sum
Moderator: Board moderators
10891  Game of Sum
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.

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
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 2n1 possible moves. And how many possible game configurations are there? If there aren't too many, can you compute them all?
Knowing this, note that at any point, there are only 2n1 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...

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
Suppose your input is
Then n=5 is the length of the sequence.
You have 2n1 = 9 possible moves:
In each of these cases, your opponent will be left with a subarray (a piece of the original array). Then your opponent will make a move, and you will get a smaller subarray. Then you make a move again, etc. until nothing is left.
How many different subarrays of the original 5element array are there? If you think about it for 10 seconds, you will see that there are 16 (including the subarray of length 0). In general, an array of length n has n(n+1)/2+1 subarrays. 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 subarray of length X and make a move, then you will get a subarray of length smaller than X. Suppose that you already know how to solve this probem for subarrays of length smaller than X. To solve it for a subarray 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?
Code: Select all
4 20 8 1 2
You have 2n1 = 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
How many different subarrays of the original 5element array are there? If you think about it for 10 seconds, you will see that there are 16 (including the subarray of length 0). In general, an array of length n has n(n+1)/2+1 subarrays. 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 subarray of length X and make a move, then you will get a subarray of length smaller than X. Suppose that you already know how to solve this probem for subarrays of length smaller than X. To solve it for a subarray 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...
10891  Game of Sum
Code: Select all
accepted
Last edited by DP on Sun Aug 13, 2006 4:25 pm, edited 1 time in total.

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: help me...10891
I don't know why you are getting TLE, but anyway you code is wrong. Try the following input:DP wrote:can someone tell me why i am getting TLE?
i did memorization for this problem but still TLE.
Here is my code:
Code: Select all
6
15 16 17 18 19 13
0
Code: Select all
28
Runtime Error on Problem 10891  Game of Sum
Hi, it's the first time I submit the solution to the onlinejudge 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;
}
Re: Runtime Error on Problem 10891  Game of Sum
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;
}
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;
}

 Experienced poster
 Posts: 103
 Joined: Tue Mar 25, 2008 11:00 pm
 Location: IUTOIC, DHAKA, BANGLADESH
 Contact:
Re: 10891  Game of Sum
polone wrote,
mine is O(N^2)the dp should be O(n^3)
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................
It is more tough to become a good person.
I am trying both...............................