You can solve this problem by using a dynamic programming approach. Just take a look at the Contest Analysis to see two possible solutions :-)
http://code.google.com/codejam/contest/dashboard?c=agxjb2RlamFtLXByb2RyEAsSCGNvbnRlc3RzGIL6AQw#s=a&a=3 On Sat, Aug 22, 2009 at 11:24 PM, AzizulGafur<[email protected]> wrote: > > Hello Group ! > I have been trying to solve the "Endless Knight" Problem > ( > http://code.google.com/codejam/contest/dashboard?c=agxjb2RlamFtLXByb2RyEAsSCGNvbnRlc3RzGIL6AQw#s=p3 > ) > > I solved it without much effort but as you can guess > the solution is a dumb Non-polynomial-time solution. > My solution was tree-based solution with the complexity > roughly being 2 to the Power (H or W). > > I was wondering if this problem has an actual polynomial time > solution. > In other word, has anyone been able to solve it in polynomial time? > > You are welcome to post the whole solution or just a "YES" or "NO" > > > > -- Luiz Ribeiro http://luizribeiro.org/ --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
