## 10891 - Game of Sum

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

Moderator: Board moderators

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

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

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

Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh

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

Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh

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)
polone
New poster

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

### 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.
rasel4all
New poster

Posts: 3
Joined: Sat Sep 10, 2005 6:55 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?
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

Can u explain by using some sample data. Please
rasel4all
New poster

Posts: 3
Joined: Sat Sep 10, 2005 6:55 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 4take 4 -20take 4 -20 8take 4 -20 8 -1take 4 -20 8 -1 -2take -20 8 -1 -2take 8 -1 -2take -1 -2take -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?
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

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

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

### 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.
DP
Learning poster

Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh

### Re: help me...10891

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
`615 -16 17 18 -19 130`

The correct output is:
Code: Select all
`28`

But your answer is 35.

Martin Macko
A great helper

Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

thnx a lot. Martin.
DP
Learning poster

Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh

### Re: 10891 - Game of Sum

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

kbr_iut
Experienced poster

Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH

### Re: 10891 - Game of Sum

@kbr_iut, I am very much eager to no how did you solve it in O(n^2). I can not think of any way faster than O(n^3). Which dimension did you reduce?
You should not always say what you know, but you should always know what you say.
zobayer
Experienced poster

Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh

### Re: 10891 - Game of Sum

All the test cases from this thread:
Code: Select all
`27 -232 7 351000 -1000 -1000 1000 10009-823 912 -345 100000 867 -222 -991 -3 -400007-23 35 -12 100000 99234 -86123 -32458-23 35 12 100000 99234 -86123 -3245 -1477 7 7 -7 7 -7 80 7 7 7 -7 7 -7 -7 7 -7 7 -7 7 -7 -7 7 -7 -7 -7 7 7 7 -7 7 -7 7 -7 7 7 7 -7 7 -7 7 -7 7 -7 -7 7 -7 748-7 -7 -7 -7 -7 7 7 -80 7 -7 -7 -7 -7 7 -7 -7 -7 -7 7 7 -7 -7 -7 7 7 7 -7 7 -7 -7 -7 7 -7 -7 7 7 7 -7 7 -7 7 7 7 7 7 7 7 72291 56 -23 45 87 -65 45 -45 78 23 -20 -41 17 -54 51 51 94 -62 -74 -42 76 -761892834 -95461 15911 -56189 6369 -80545 31811 51263 30076 68867 -36905 -32499 -59799 334 -82991 46636 -98741 -666011-12920-35463 -88121 4362 -94457 86235 83680 72686 6003 93069 -2015 -10436 2139 93162 -30380 19067 76335 -78941 48620 -55887 156791719335 97643 11468 86267 -79718 -59584 12129 52642 -86575 62307 -11545 -52658 72377 39986 74850 -1992 -869285-91883 -97793 -54567 -64714 -986244398473 41866 71129 -65936 -42626 9194 -46718 96921 -45613 47677 -8763 54634 -47259 -71448 9918 22666 -32711 -21692 40207 -2017 -23040 -86083 77809 15472 30718 -39085 -87911 54827 -41686 -28354 37203 6548 -74184 -3043 -43961 -95189 1238 -22002 93507 63546 32527 -42778 -31614501 -2 -3 -4 -5 -6 7 -8 -9 -10 -11 -12 13 -14 -15 -16 -17 -18 19 20 -21 -22 23 24 25 26 -27 28 -29 -30 31 32 33 34 -35 36 37 38 -39 -40 41 -42 -43 -44 -45 -46 -47 -48 -49 -50501 1 -1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 1 -1501 -2 -3 -4 5 -6 -7 -8 -9 11 11 11 -11 -11 111 -11 -11 11 11 11 -11 -11 11 -11 -11 11 -11 11 11 11 112 -312 312 123 -123 -123 123 -123 -123 -123 -123 -123 123 -123 -123 -123 123 -231 -31 -31250-1234 -1233 -12 312 -32 23 434 12 -312 -45 -1234 1233 -12 -312 32 -23 -434 -12 312 45 -1234 1233 12 312 32 23 -434 -12 312 -45 -1234 1233 -12 312 32 -23 -434 -12 312 -45 -1234 -1233 12 -312 -32 -23 -434 -12 312 45341 2 -3 -3 3 -3 3 3 -3 3 3 3 -3 3 -3 3 3 -3 3 3 -3 3 3 3 3 3 -3 -3 3 3 3 3 -3 -349 100 -1 850-1 -2 -3 4 5 -6 -7 8 -9 -8 7 66 5 4 3 -4 5 -6 7 8 -9 -8 -7 -6 6 -5 -4 5 -6 -3 -4 -4 -5 -6 -3 -4 -5 -6 3 -4 -5 6 -3 4 -5 6 3 4 5 -650-1 -2 3 -4 -5 -6 7 -8 9 10 -1 2 3 -4 5 1 -2 -3 -4 -65 -67 -2 3 -4 -7 2 3 4 6 6 -7 2 3 4 -7 78 8 82 2 3 -4 7 -2 2 34 -4 6 -7 -3 23-100 -10 1011501 2 -3 -4 5 6 7 8 9 -10 -1 2 3 4 -5 -6 -7 -8 9 10 1 2 3 -4 5 6 7 8 9 10 -2 -4 -3 -5 4 6 -7 -5 -6 10 2 -5 -4 -3 -4 -5 6 -7 -9 -1066 4 3 -5 -8 -851 5 20 2 -1481 2 3 -4 -5 -6 -6 7 8 767 -765 111 76576 -5 64 654 64 -7 7657 -76575 64 -65 6454 -64 -654 -65464 7 -5435 65 -746 -7 546 -7 654 7 -5435 -547 6 6 7 -6547 7654 -6 754 -54353 -65 -7 85-2147483648 2147483647 -2147483648 2147483647 -214748364852147483647 2147483647 2147483647 2147483647 214748364744 -10 -20 741 2 3 44-20 8 -1 -2615 -16 17 18 -19 1316546540`

Correct output:
Code: Select all
`91210001393951163561163811087336493092-129443781323860-147471024651176408655331166021010017018291149952147483646107374182357102528654654`

Hope this helps...
You should not always say what you know, but you should always know what you say.
zobayer
Experienced poster

Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh

PreviousNext

Return to Volume CVIII

### Who is online

Users browsing this forum: No registered users and 1 guest