Discussion @ 1872. Spacious Office @ Timus Online Judge

Fast solution

Posted by Hallelujah 6 Apr 2013 16:41

For solving this problem I used advanced bipartite graph theory. But it work slowly(about 0.6sec). Very interesting how solve more quickly. Please, give me some hints.(My e-mail: scarlet.flower@list.ru)

Re: Fast solution

Posted by Серовиков Андрей 8 Apr 2013 19:39

Maximum matchings in bipartite graph is almost enough to solve it + some "magic" :)
Maybe maximum flow algos' works better here...
My complexity was O(V*E), 0.3sec

Re: Fast solution

Posted by Kungurtsev [Psych Up club] 3 Sep 2013 18:48

Just gredy.

Re: Fast solution

Posted by Alexey Dergunov [Samara SAU] 6 Sep 2013 11:55

Also, O(NlogN) solution exists

Discussion of Problem 1872. Spacious Office