With a little tricky maths, it's possible to calculate "the number of Hamiltonian cycles that use set S of forbidden edges". Using inclusion- exclusion we can combine these values to get "the number of Hamiltonian cycles that use any forbidden edges".
http://en.wikipedia.org/wiki/Inclusion-exclusion_principle Glancing at the first few submissions on the scoreboard, this seems to be the general approach that people took. -Chris On Sep 20, 5:02 pm, rajatag12 <[email protected]> wrote: > Any ideas on how to solve the large input case? > > I downloaded correct solutions from the scoreboard, but couldnt > understand the approach completely. Could not find any discussion or > Contest analysis on the problem too. > > thanks. > > - Rajat. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
