ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1035. Cross-stitch

Help wanted on 1035!!
Posted by Ivan Georgiev 24 Sep 2001 01:34
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!!
Posted by Jivko Ganev 24 Sep 2001 03:36
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.
Posted by Ivan Georgiev 28 Sep 2001 19:36
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