Today I'm kicking off a new series on maximum flows on my YouTube channel Algorithms Live!. The first episode is already available and I've discussed some of this idea in a blog post. The series will focus on flows without costs and will cover both the algorithms and patterns of problem.
I'll be interspersing the episodes with some guest episodes to keep things interesting. One will be with Errichto, though we are still working out the details as he has been travelling for TCO and Hacker Cup. That episode will cover educational streaming and an interesting problem he wrote. Another episode will be with a Looking for a Challenge? author.
This post is to mostly gather topic ideas for the flow series and to collect questions to ask some of the future guests in the episodes. What problems/ideas would you like to see covered in the flow series? What questions would you like to see answered by the future guests?
A few patterns I remember from days of starting out flow are running flow with binary search on some parameter to find, say, the maximum k for which some process depending on k terminated properly (i.e. it would terminate properly iff the max flow on some graph was equal to x, so you can binary search on k while running flow). BAPC 2016 J is an example.
Another common trick that I would also notice is duplicating the vertices of a given graph to simulate timesteps. BAPC 2014 A is an example problem.
One problem I remember that uses both of these tricks is ECNA 2013 E.
I encountered a problem in a recent edu round, which requires converting it to a min-cut problem. I can reduce it to a classic problem similar to this one.
However, I didn't see other types of problems that can be reduced to min-cut, and want to know if they actually exists. I will be glad if they are mentioned in the future episodes.
By the way, I am a big fan of
. It is one of the very few places where proof is emphasized. Thank you for your good episodes!
One of my first ERs featured another problem which can be stated as min-cut.
There is also a very cool problem from Intel Code Challenge, and another problem from ER which was inspired by it.
I am actually interested in problems like two last ones. Are there any other examples on this technique?
This year's North American ICPC rounds also had a very basic min cut problem Cops and Robbers. In fact, it's nearly identical to an old German problem The King of the North.
https://www.spoj.com/problems/COCONUTS/
https://www.spoj.com/problems/MOBIVINA/