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 ?

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

siddharths067's gravatar image

1★siddharths067
7927
accept rate: 4%

edited 07 Jan '16, 22:30

There's also a simple enough graph side of things.

(26 Dec '16, 22:16) teracoder2★

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

link

answered 08 Jan '16, 00:25

animesh_f's gravatar image

6★animesh_f ♦
8831422
accept rate: 9%

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

(08 Jan '16, 07:53) siddharths0671★

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.

link

answered 04 Jan '17, 11:23

shreyasnn1's gravatar image

2★shreyasnn1
1048
accept rate: 10%

edited 04 Jan '17, 15:33

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.

link

answered 04 Jan '17, 17:36

shaunak27's gravatar image

1★shaunak27
21
accept rate: 0%

thanks!!!!

(04 Jan '17, 18:59) shreyasnn12★
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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