Problems with application of a popular algorithm but with smaller complexity

Revision en1, by themaskedhero, 2016-12-02 11:02:26

I have been looking for problems in which the solution looks at a famous algorithm, and applies it to the problem at hand. However, because of some special property of the problem, the algorithms complexity is reduced. An example is USACO 2016 February Platinum Fenced In (http://usaco.org/index.php?page=viewproblem2&cpid=625). The problem involves applying Kruskals algorithm in a clever way.

I was wondering if someone has more examples of these kinds of problems, specifically ones that use MST or max flow algorithms.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English themaskedhero 2016-12-02 11:02:26 601 Initial revision (published)