can anyone write editorial to the problem https://code.google.com/codejam/contest/189252/dashboard#s=p2 this is the problem from previous codejam. I tried to refer the eeditorial in contest analysis section, but it's to vaguely written so I didn't get it. asked 22 Apr '16, 23:00

Let us first discuss a slightly inefficient approach which is more intuitive and then move to a optimized approach. Let dp[i][j] be the number of gold coins to be used if prisoners in range [i,j] are considered. Here is a bottom up implementation for the same : Solution Complexity is The key observation to reduce both Time and memory complexity is that we do not need to save every state, only states with dp[i][j] where i and j are a prisoner or a it's neighbour or the edge(0 or P1) matter, and hence we can use a top down approach along with a map, as mentioned in the editorial there to get the code to run optimally : Optimized Solution Complexity is answered 25 May '16, 20:06

Brute force 
answered 10 Jan, 21:18
