I've seen this technique before where if you have some recurrence dp(state) = val, you can swap the state and value functions to better the complexity, and instead get dp(val) = state.

I'm looking for examples of these problems, one example is http://usaco.org/index.php?page=viewproblem2&cpid=648 .

Thanks

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.

Hi CF community,

Wanted to wish happy birthday to GlebsHP who has organized CF contests and helped the community for a while now. We really appreciate your efforts and I hope you have a nice birthday!

Hi CF Community:

Today I was solving the problem Farmcraft (http://main.edu.pl/en/archive/oi/21/far). Basically in this problem, you start at the root of a tree, and when you reach a node, you start a timer in that node(except for the root, which only starts when you visit it last). Each node has a time value t_i, and a timer in that node ends when it reaches t_i. What is the minimum amount of time for all timers to end, if you walk the tree in the optimal way.

My idea was to binary search the minimum time, and then subtract this from each node's t_i. Then, this gives the maximum time that you can reach each node. But how should I check if its possible to satisfy all maximum times. Or is there another solution?

Hi CF community!

I was thinking about some problem:

Given a string S, in each query you must reverse some substring of it. Then, at the end you must print the string. Constraints are 1 ≤ |S|, Q ≤ 10⁵ where Q is number of string reversals.

I'm now wondering about what is the offline and the online algorithms to solve this problem.

Thanks!

Hi everyone,

http://acm.sgu.ru/problem.php?contest=0&problem=304

I was solving this problem and I was unable to. I believe that this is DP, but I do not know the state. I do note that, for any gum, we can easily uniquely determine how much it will cost to take n teeth from that gum by picking greedily.

Thanks much in advance, themaskedhero

Hi all,

Today I was working on this problem. I recognize that this is a data structure problem, but I am curious on how to solve it with:

1. Segtree + lazy propagation and 2.Binary indexed tree

Thank you much in advance!