Editorial for Carnival Game
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
This problem can be solved with dynamic programming. First, define to represent the
board on the
layer for
, or the
bucket on the
layer for
.
Define to be minimum cost to reach
. Note that the ball can come from either
or
. Define the cost
to be
if
is
R
or if
is
L
. Similarly, define the cost to be
if
is
L
or if
is
R
. This extra cost is due to the fact that if the left/right board on the previous layer does not direct the ball to the current board, we will have to flip it so that it does.
Our general transition goes something like this:
Now, to find the maximum , we can simply take
where
.
However, how do we know exactly what boards we flipped throughout the course of our calculation?
The answer is to store the optimal paths taken in a backtracking array. Say is
if the ball came from
, or
if the ball came from
on some optimal path to
. This can be calculated while we fill the
matrix. If our maximum
happens when the ball lands in the bucket at index
, we can start our backtracking from
and move upwards to
or
depending on the state of
.
If at any time, we move in some direction that contradicts the movement that the ball would have had if it landed on in the original input, we add
to the list of flipped boards, which we output after we are done backtracking.
Comments