The Cool Monkeys — Gym Problem

Revision en1, by angelg, 2015-08-28 19:33:22

Hello, I've been trying to solve this problem: http://codeforces.me/gym/100733/problem/I. I tried to solve it modeling the problem as a flow network. All edges have capacity one. I build the graph twice, one for considering each tree as tree A and the other as tree B. I add M edges from the sink to the highest branches of tree A, and connect the M lowest branches from tree B to the sink. Then I connect all branches that fulfill the inequity abs(Ha — Hb) < T. But, I'm getting wrong answer in test #21. This is my submission: http://ideone.com/6sC2ek.

I would understand a TLE veredict as my solution creates a huge amount of edges about (500^2) in some cases. What would be a better solution for this problem? Is there a way to build this as a flow network and use less edges? I also tried to come up with a DP solution, but I failed to do so. Can anyone point me in the right direction?

Tags flows, gym, dynamic programming, data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English angelg 2015-08-28 19:33:22 938 Initial revision (published)