> > In the deleting section > > // Try deleting > best = Solve(pixels[1 to N-1], final_value) + D > > shouldn't we loop over all possible values of final_value??? >
I'm not very good at the dynamic programming stuff but after thinking about that solution for a while I think I understand it. The Solve function *must* return an answer in which the value of the final pixel is final_value. That is the basis of the DP algorithim. Then the caller loops through all possible final_values calling Solve each time to gets the minimum cost, i.e the caller is doing something like: min( (Solve(pixels, final_value) for final_value in [1 to 256]) ) On Sat, May 22, 2010 at 9:18 AM, shahansad kollaparambath < [email protected]> wrote: > Hi every one.. > > i am having trouble understanding the solution given for problem B of round > 1A. > > The code given at the contest analysis is. > > int Solve(pixels[], final_value) { > if (pixels is empty) return 0 > > // Try deleting > best = Solve(pixels[1 to N-1], final_value) + D > > // Try all values for the previous pixel value > for (all prev_value) { > prev_cost = Solve(pixels[1 to N-1], prev_value) > > move_cost = |final_value - pixels[N]| > num_inserts = (|final_value - prev_value| - 1) / M > insert_cost = num_inserts * I > best = min(best, prev_cost + move_cost + insert_cost) > } > return best > > } > > > In the deleting section > > // Try deleting > best = Solve(pixels[1 to N-1], final_value) + D > > shouldn't we loop over all possible values of final_value??? > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<google-code%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
