Nope. Imagine for a moment that the insert cost is 2 and the maximum
allowed difference for smooth arrays ('m') is 20. We'd like to
calculate Solve(6, 10), and we're on the delete step.Now let's say Solve(5, 10) is 125, and Solve(5, 100) is 80. Now you'd think that, during the delete phase, we should consider all [0-255] numbers, so that we end up deleting + inserting our way from 100 down to 10, which requires inserts: 80, 60, 40, 20, 10, so that'd be 10 extra penalty points for inserting, for a total of 80 + 10 = 90 points; that's cheaper than simply using Solve(5, 10) and not inserting anything, as that would cost 125. However, the above scenario can't happen; if Solve(5, 10) is 125 and Solve(5, 100) is 80, where m is 20 and insert cost is 2, our algorithm is broken. The cheapest way to get to the first 5 numbers 'smoothed' with the final number being 10 is easily provable to be no more than 90, therefore Solve(5, 10) can't be 125. Regardless, even if you do loop through [0-255] for final_value (which certainly can't do any harm!), your program should still complete the large set inside of a minute. NB: Caveat, I figured out 1A-B about a minute after time ended, so I didn't actually program it. Possibly my reasoning is flawed. On May 22, 9:32 pm, Chris Carton <[email protected]> wrote: > > 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%2bunsubscr...@googlegr > > oups.com> > > . > > 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 > athttp://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.
