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 1676. Mortal Kombat

hint
Posted by svr 21 Jan 2009 14:05
Using O(n^2) transitive closure in bipartite
Graph was successful.
Re: hint
Posted by Al.Cash 26 Jan 2009 21:30
Does your solution use Hall's theorem?
Re: hint
Posted by svr 26 Jan 2009 21:57
May be. If it is Hall's.
Now it is mine:edge (ra,rb) can precence in
some assigment solution if and only if
1)it's begining ra achievable by alternating path's with
respect to some given matching from it's end rb.
OR
2) Some free vertex achievable from rb.

Edited by author 26.01.2009 22:01
Re: hint
Posted by Al.Cash 28 Jan 2009 01:10
Your statement is quite simple to prove and it seems very useful for this problem.
But don't you need to build some matching before applying it?
Then the algorithm's complexity is O(N^2*M), which is much slower then O(N^2) mentioned before))
Re: hint
Posted by svr 28 Jan 2009 09:26
I said about complexity of submethod and
not about integral complexity.
 i.e. about nonstandard part of algo.