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
-
inproblem
- New poster
- Posts: 4
- Joined: Fri Oct 29, 2004 9:52 pm
Post
by inproblem » Mon Aug 08, 2005 3:37 am
hi, Can anyone(who got Ac) help me abt 10891? Can u tell me how to proceed to solve the problem?
And I am afraid abt 10892 that i wont solve it within given time.

So pls show the way to solve it
-
Abednego
- A great helper
- Posts: 281
- Joined: Tue Sep 10, 2002 5:14 am
- Location: Mountain View, CA, USA
-
Contact:
Post
by Abednego » Mon Aug 08, 2005 9:19 am
What does the phrase "consecutive numbers" mean? Does that mean that the numbers themselves are consecutive (like "1, 2, 3" or "6, 5, 4"), or does it simply mean that they are consecutive inside the array?
Also, could anyone please explain why the answer to the first test case is 7?
If only I had as much free time as I did in college...
-
Abednego
- A great helper
- Posts: 281
- Joined: Tue Sep 10, 2002 5:14 am
- Location: Mountain View, CA, USA
-
Contact:
Post
by Abednego » Mon Aug 08, 2005 9:30 am
Nevermind. I figured it out.
Code: Select all
Player A takes 7.
Player B takes 4 and -10.
Player A takes -20.
If only I had as much free time as I did in college...
-
shamim
- A great helper
- Posts: 498
- Joined: Mon Dec 30, 2002 10:10 am
- Location: Bozeman, Montana, USA
Post
by shamim » Mon Aug 08, 2005 9:42 am
I think it's the other way,
that is player A takes 4,
player B takes 7,
player A takes -10
player B takes -20,
so player A has -6 and player B has -13 ( diff. of 7).
-
oulongbin
- Learning poster
- Posts: 53
- Joined: Sat Jul 10, 2004 5:57 pm
- Location: Shanghai China
Post
by oulongbin » Mon Aug 08, 2005 2:57 pm
sorry,i don't very agree with you.
if you are right,i can do this:
A takes 7;
B takes 4;
A takes -10;
B takes -20;
then A is -3 and B is -16;
the answer is 13 greater than 7.
i don't know why the correct is 7.
-
jdmetz
- New poster
- Posts: 25
- Joined: Fri May 27, 2005 5:23 pm
- Location: Ann Arbor, MI USA
Post
by jdmetz » Mon Aug 08, 2005 3:48 pm
shamim is correct. Abednego's method gives an answer of -7, not 7.
oulongbin, both players play to get the maximum difference, so if A takes 7, B will take 4 and -10, leaving A with -20 so that B wins with -6 vs. -13. B wouldn't let A pick between -10 and -20 when B could have taken the -10 leaving A with the -20.
-
Abednego
- A great helper
- Posts: 281
- Joined: Tue Sep 10, 2002 5:14 am
- Location: Mountain View, CA, USA
-
Contact:
Post
by Abednego » Mon Aug 08, 2005 6:04 pm
Yes, you're right. I should not solve problems late at night. I did get it AC on first try though. :-)
If only I had as much free time as I did in college...
-
dispanser
- New poster
- Posts: 18
- Joined: Wed May 01, 2002 4:12 pm
- Location: Jena/Germany
-
Contact:
Post
by dispanser » Mon Aug 08, 2005 11:58 pm
cool. I couldn't figure that test case out until reading this thread. However, my program got AC during the contest. That's the magic about dynamic programming. You don't know what it does, but it eventually solves all your problems.
-
mohiul alam prince
- Experienced poster
- Posts: 120
- Joined: Sat Nov 01, 2003 6:16 am
- Location: Dhaka (EWU)
Post
by mohiul alam prince » Tue Aug 09, 2005 12:15 pm
Hi
in problem 10892
- I have solved this problem by this way
- first i have stored all factor's of the given number
- then a n square loop to find out the LCM Cardinality.
- if two factor's lcm is N then i have increased my counter variable.
- then just print the counter variable.
and in problem 10891 is a game theory problem
- you can solve this probem by using memoization.
Thanks

MAP
-
oulongbin
- Learning poster
- Posts: 53
- Joined: Sat Jul 10, 2004 5:57 pm
- Location: Shanghai China
Post
by oulongbin » Tue Aug 09, 2005 3:09 pm
jdmetz wrote:shamim is correct. Abednego's method gives an answer of -7, not 7.
oulongbin, both players play to get the maximum difference, so if A takes 7, B will take 4 and -10, leaving A with -20 so that B wins with -6 vs. -13. B wouldn't let A pick between -10 and -20 when B could have taken the -10 leaving A with the -20.
thank you very much!
i know the problem.

-
Towhid
- New poster
- Posts: 38
- Joined: Wed May 28, 2003 5:30 pm
- Location: Bangladesh
-
Contact:
Post
by Towhid » Sun Aug 14, 2005 8:54 am
Can someone provide some I/O for the this problem? My DP solution is getting WA.

From 0 to 0
-
jagadish
- Learning poster
- Posts: 90
- Joined: Mon Feb 16, 2004 8:53 pm
- Location: Bangalore INDIA
Post
by jagadish » Sun Aug 14, 2005 12:54 pm
try these :
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
0
Output :
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
if u can think of it .. u can do it in software.
-
ibrahim
- Experienced poster
- Posts: 149
- Joined: Mon Feb 07, 2005 10:28 pm
- Location: Northern University, Bangladesh
-
Contact:
Post
by ibrahim » Sun Aug 14, 2005 9:19 pm
Anbody can explain the algorithm (DP). I am not getting the right process.

-
misof
- A great helper
- Posts: 430
- Joined: Wed Jun 09, 2004 1:31 pm
Post
by misof » Sun Aug 14, 2005 9:41 pm
ibrahim wrote:Anbody can explain the algorithm (DP). I am not getting the right process.

Simple
For each segment of the input sequence you want to compute the result of the given game.
Note that after the first move of player A they are playing exactly the same game on the rest of the sequence, player B starts.
Example: If the value of player A's move is 4 and the result of the game on the rest of the sequence is 7, the result of the whole game is 4-7=-3.
-
jdmetz
- New poster
- Posts: 25
- Joined: Fri May 27, 2005 5:23 pm
- Location: Ann Arbor, MI USA
Post
by jdmetz » Mon Aug 15, 2005 3:26 pm
Towhid wrote:Can someone provide some I/O for the this problem? My DP solution is getting WA.

Do you deal with overflow?
Input
Code: Select all
5
-2147483648 2147483647 -2147483648 2147483647 -2147483648
5
2147483647 2147483647 2147483647 2147483647 2147483647
0
Output