Обсуждение @ 1872. Просторный офис @ Timus Online Judge

Fast solution

Послано Hallelujah 6 апр 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

Послано Серовиков Андрей 8 апр 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

Послано Kungurtsev [Psych Up club] 3 сен 2013 18:48

Just gredy.

Re: Fast solution

Послано Alexey Dergunov [Samara SAU] 6 сен 2013 11:55

Also, O(NlogN) solution exists

Обсуждение задачи 1872. Просторный офис