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 1721. Two Sides of the Same Coin

Help with algo please
Posted by Grigor Gevorgian 11 Oct 2009 00:58
How to solve this problem ? Flow seems not enough because of the vertexes of "anything" type.
Re: Help with algo please
Posted by wcwswswws 11 Oct 2009 21:40
Flow can solve it but there's a better way in fact.

Edited by author 11.10.2009 21:40
Re: Help with algo please
Posted by Grigor Gevorgian 11 Oct 2009 22:23
Could you tell me, please, how to construct the graph for a flow ?
Re: Help with algo please
Posted by Tbilisi SU: Gio (Away) 11 Oct 2009 23:57
you should construct bipartite graph.
for example , you have people with ranks:

2 4 6 8 10

2 , 6 , 10 - to the left side
4 , 8 - to the right side
Re: Help with algo please
Posted by Pavel Kovalenko 16 Oct 2009 23:14
I tried to use Kuhn (max pair-combination), but get WA#11. And don't know, what to do next...
Re: Help with algo please
Posted by SkidanovAlex 17 Oct 2009 00:00
You always can put all the people with skill < 2 (modulo 4) to the left part and all the people with skill >= 2 (modulo 4) to the right. Definitely, all the edges will connect vertices from different parts, so this graph will be bipartite.
Re: Help with algo please
Posted by Igor9669(Tashkent IAC) 18 Oct 2009 19:30
My algo is O(n^3),but it got TLE 11!
What is right algo here?
Re: Help with algo please
Posted by acm_tester 25 Apr 2011 00:20
My algo is O(n^2*m) and AC in 0.093
It is standart bipartite matching algo
Re: Help with algo please
Posted by xurshid_n 11 Jan 2012 13:21


 
acm_tester wrote 25 April 2011 00:20
My algo is O(n^2*m) and AC in 0.093
It is standart bipartite matching algo

I was use Hopcroft_Karp algo (from wiki) and AC. 0.031 s.
Re: Help with algo please
Posted by Michael Uskov [USU] 11 Dec 2014 13:29
SkidanovAlex wrote 17 October 2009 00:00
You always can put all the people with skill < 2 (modulo 4) to the left part and all the people with skill >= 2 (modulo 4) to the right. Definitely, all the edges will connect vertices from different parts, so this graph will be bipartite.
But why will the maximum match in this graph will be answer to the problem?
Re: Help with algo please
Posted by SergeiEgorov 22 Sep 2015 01:30
I used a Hopcroft-Karp algorithm to solve this problem and got AC in 31 ms. So, not bad :)