There is a more verbose explanation of that problem here: http://www.necessaryandsufficient.net/2008/08/google-code-jam-ugly-numbers/
<http://www.necessaryandsufficient.net/2008/08/google-code-jam-ugly-numbers/>Hope that helps. On Sat, Sep 12, 2009 at 8:23 AM, TripleM <[email protected]> wrote: > > 1. The provided solution does do the opposite of that which is > mentioned in the analysis, but that makes no difference whatsoever. dyn > [i][x] will end up counting things equal to -x mod 210, which is > exactly the same when x=0 which is the only one you want. > > 2. Because if x=3, cur=5, and sgn=-1, (x + sgn*cur)%MOD = -2. Adding > an extra MOD makes it always positive. > > On Sep 12, 5:07 am, Bey <[email protected]> wrote: > > Hi, > > I was trying to follow the solution to the 2008 problem Ugly Numbers > > in Round 1C. I understand that it ought to be a Dynamic Programming > > solution. Also, x % 210 and y % 210 tell you (x+y)%210 and (x-y) % > > 210. However, I hope someone can help me with the following: > > > > 1. If the operation before character 'j' was '+', shouldn't the update > > be dyn[j-1][(x-d)%210] rather than the other way round? > > > > 2. Why is there a +MOD in the line > > dyn[j+1][(x+sgn*cur+MOD)%MOD] += dyn[i][x]; > > > > Note: I am following the solution from the Contect analysis athttp:// > code.google.com/codejam/contest/dashboard?c=32015#s=a&a=1 > > > > Thanks! > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
