Hints

• ||Try to first think about how you'd solve the problem if the repetition score was the same as the original one (there is no loss of points for duplicates). What about this constraint makes it impossible to translate this idea to the actual problem?||
• ||As you'd know, pretty much all graph search algorithms cannot handle non-local constraints. It can only make decisions based on the immediate nodes present. This problem however has non-local constraints... or does it? When viewed as the path taken by the skater, this is indeed non-local. But is there a way we could reposition the problem such that the constraint is no longer non-local?||
• ||Keep in mind that ~m~ is relatively small. Is there a way we could build the solution such our search algorithm will decide on the first entry to the row, as well as the return entry, at the same time?||
• ||Rather than starting at bottom row, consider starting at the top row - this is easily computable as we're just consider pairs of adjacent cells, or the same cell with the duplicate score. How could we build from this to a path starting at the second from the top? How would I need to categorise paths from the top row?||

Solution

View Solution

The trick here is that if we grow the path from the centre in both directions, then at each row, the first visit will be chosen at the same time as the second! So let us maintain a 3 dimensional dynamic programming memo, where dp[r][c1][c2] stores the maximum score path starting at row r, column c1, and ending at row r, column c2, turning around at the half-pipe. Each of these DP states then gives us 9 options for states to build off of in the row above (3 options for c1, and 3 options for c2). Then, we know whether to consider the duplicate scoring mechanism purely based off if c1 == c2. Final complexity for this solution will therefore be ~O(n \times m^2)~. @code_include[solutions/main.cpp]{rm_config: True, langs: "cpp,py"} Alternatively (and more efficiently), because the duplicate cost is always worse or equal to the original trick cost, we can model this as a min-cost-flow problem (finding a 2-flow in the graph selects two edge disjoint paths), since if we have 2 edges, one for the original trick, and one for the duplicate, min-cost flow would always take the original edge first, since it is less costly to do so. @code_include[solutions/flow.cpp]{rm_config: True, langs: "cpp,py"}