10891 - Game of Sum
Moderator: Board moderators
-
- Experienced poster
- Posts: 110
- Joined: Tue May 06, 2008 2:18 pm
- Location: CSE-DU, Bangladesh
- Contact:
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.
-
- Experienced poster
- Posts: 110
- Joined: Tue May 06, 2008 2:18 pm
- Location: CSE-DU, Bangladesh
- Contact:
Re: 10891 - Game of Sum
All the test cases from this thread:
Correct output:
Hope this helps...
Code: Select all
2
7 -2
3
2 7 3
5
1000 -1000 -1000 1000 1000
9
-823 912 -345 100000 867 -222 -991 -3 -40000
7
-23 35 -12 100000 99234 -86123 -3245
8
-23 35 12 100000 99234 -86123 -3245 -1
47
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 7
48
-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 7
22
91 56 -23 45 87 -65 45 -45 78 23 -20 -41 17 -54 51 51 94 -62 -74 -42 76 -76
18
92834 -95461 15911 -56189 6369 -80545 31811 51263 30076 68867 -36905 -32499 -59799 334 -82991 46636 -98741 -66601
1
-129
20
-35463 -88121 4362 -94457 86235 83680 72686 6003 93069 -2015 -10436 2139 93162 -30380 19067 76335 -78941 48620 -55887 15679
17
19335 97643 11468 86267 -79718 -59584 12129 52642 -86575 62307 -11545 -52658 72377 39986 74850 -1992 -86928
5
-91883 -97793 -54567 -64714 -98624
43
98473 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 -31614
50
1 -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 -50
50
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 1 -1
50
1 -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 -312
50
-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 45
34
1 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 -3
4
9 100 -1 8
50
-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 -6
50
-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 2
3
-100 -10 10
1
1
50
1 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 -10
6
6 4 3 -5 -8 -8
5
1 5 20 2 -1
48
1 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 8
5
-2147483648 2147483647 -2147483648 2147483647 -2147483648
5
2147483647 2147483647 2147483647 2147483647 2147483647
4
4 -10 -20 7
4
1 2 3 4
4
-20 8 -1 -2
6
15 -16 17 18 -19 13
1
654654
0
Code: Select all
9
12
1000
139395
116356
116381
108
73
364
93092
-129
443781
323860
-14747
102465
117
6
408
655
33
116
60
210
100
1
70
18
29
114995
2147483646
10737418235
7
10
25
28
654654
You should not always say what you know, but you should always know what you say.
-
- Experienced poster
- Posts: 147
- Joined: Mon Jun 07, 2010 11:43 am
- Location: University Of Dhaka,Bangladesh
- Contact:
Re: 10891 - Game of Sum
Nice problem
. Take a number and call the recursive function for rest of the array. A will try to maximize the difference,B will do the opposite. I used 3state dp.

UVa stats: http://felix-halim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
Re: 10891 - Game of Sum
Why do you need 3 states? Can be easily solved with 2....nvm ac is ac.
But yeah quite awesome problem....enjoyed solving it 10891 FTW
But yeah quite awesome problem....enjoyed solving it 10891 FTW

You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson