|
|
back to boardHelp wanted on 1035!! As far as I can see the problem has relatively small percent of the difficulty, but I can't think of the way I should walk the pattern by means of minimal number of threads.. Is the problem only a DFS (and if it is how should it be done) or there is something else? Thank you. Re: Help wanted on 1035!! You need some graph theory and common sense to solve it. Basically after you do the logic the problem breaks down to simple bfs/dfs and counting degrees. The idea comes from the problem of decompossing graph to a minimum amount of paths which is solved by some simple logic - you should be able to prove it yourself. Hint - it has something to do with Euler ... Re: Thanks. Got AC (at last!!!!) Very tricky problem. Re: Help wanted on 1035!! Posted by svr 3 Jan 2009 17:47 Helpfull to have math invariant(which right for every algo) I think that answer=Nc+Ndb/2 where Ndb- sum of disbalances of vertices of grid's graph. and Nc- number of alternating loops which unreached from disbalanced vertices by alternating pathes. But can't go far then test 8. AC 0.031 now.Idea is right. It taken 3 days to convert idea in quick algo. Edited by author 04.01.2009 10:13 |
|
|