You are not logged in. Please login at www.codechef.com to post your questions!

×

# IOIPRAC INOI : What's the expected approach for Calvin's Game ?

 1 Whats the expected approach for Calvin's Game INOI 13 My approach of choosing max(forwardphase_at_i + Reverse_At_i) apparently fails.. asked 07 Jan '16, 22:21 79●2●7 accept rate: 4% There's also a simple enough graph side of things. (26 Dec '16, 22:16)

# DP Solution: Compute the following quantities

$Forward[i]$ = $Max$ $score$ $if$ $we$ $move$ $forward$ $from$ $K$ to $i$, $for$ $all$ $K <= i <= N$

$Backward[i]$ = $Max$ $score$ $if$ $we$ $move$ $backward$ $from$ $i$ to $1$, $for$ $all$ $K <= i <= N$

$Ans$ = $Max$ $(Forward[i] + Backward[i])$ $for$ $all$ $K <= i <= N$

Make sure to include the case in which you don't move forward at all.

Code

answered 08 Jan '16, 00:25

8831422
accept rate: 9%

That's very generous ,Thank You Very much, Now I know what I missed :) ^_^

(08 Jan '16, 07:53)
 1 I have a doubt. May be the doubt is silly if the input is 5 2 5 3 -2 1 1 (sample input) then we can continuously increase our score by from 3 to 1 and then 1 to 3 repeatedly (here 3 refers to the number 3 and not the third position).. I probably didnt read the question properly but pls clarify this doubt. answered 04 Jan '17, 11:23 104●8 accept rate: 10%
 1 We can only one forward phase(not move) followed by one backward phase. If you go from 3 to 1 and come back to three you have completed the forward phase and cannot go forward any more. answered 04 Jan '17, 17:36 21 accept rate: 0% thanks!!!! (04 Jan '17, 18:59)
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,181

question asked: 07 Jan '16, 22:21

question was seen: 3,114 times

last updated: 04 Jan '17, 18:59