Help 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*