themaskedhero's blog

Problems with application of a popular algorithm but with smaller complexity
By themaskedhero, history, 8 years ago, In English

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.

  • Vote: I like it
  • +24
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Here are two MST problems similar to the one you posted
http://code-festival-2016-qualb.contest.atcoder.jp/tasks/codefestival_2016_qualB_c
http://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_g

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

Here's a max-flow problem of the type you want:

724E — Goods transportation

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Another max-flow example: 704D - Captain America

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Two well-known dp problems where you should decrease the number of states to get AC.
http://mirror.codeforces.com/contest/729/problem/F
http://mirror.codeforces.com/group/jx70Vs2WZm/contest/101064/problem/L

→ Reply