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 -~----------~----~----~----~------~----~------~--~---
