Codeforces Rockethon 2015 Problem F1 - Scaygerboss

Problem Statement:
513F1 - Scaygerboss

Solution:
Happy to solve another maximum flow problem :) The official editorial to this problem is well-written so check them out if you have not. Here I will discuss on the approach for the easier version of the problem only, as that is the max my brain can currently comprehend :D

Every maximum flow problems are interesting, and this one further reinforces that statement. Here we are to match the males and females into a cell for which each cell can be associated with at most a pair of matching. We are to find the minimum possible time for all the males and females can move to their designated cells, amongst all possible matching. Here we can use binary search to guess the minimum value, and check whether that value can result in a valid matching using maximum flow.

Codeforces Rockethon 2015 Problem D1/D2 - Constrained Tree

Problem Statement:
513D2 - Constrained Tree

Solution:
Can a problem be interesting and yet frustrating? The answer turns out to be a loud and painful Yes.. Spent 8 hours just to get this right :/

Btw the editorial to this problem is sufficiently comprehensible hence I would suggest you to read the official editorial instead of this one if you haven't done so. Otherwise, you might benefit from this :)

You are supposed to construct a tree out of a given set of relationships between the nodes on the tree, such that the pre-order and in-order labelling of the nodes agree on each other. That is a pretty confusing semantic in my opinion. And they have recursive definition.

Codeforces Rockethon 2015 Problem E1/E2 - Subarray Cuts

Problem Statement:
513E2 - Subarray Cuts

Solution:
This is another excellent problem, for which its solution demonstrates the power of dynamic programming. Unfortunately the implementation is very error prone due to the handling of edge cases (at least for me). The official editorial to this problem is also unfortunately very hard to read, partly because the TeX are not typed correctly. Anyway, here is my note about this problem.

The problem is difficult because we are presented with modulus operations. When we try to do a naive DP by keeping track of the value of \(s_j\), we will soon realize that we also need to keep track of the value for \(s_{j-1}\), which inflates the space search very badly. As it turns out, there is another way of looking into the problem which I think is very clever.

Codeforces Rockethon 2015 Problem C - Second price auction

Problem Statement:
513C - Second price auction

Solution:
This is a good problem :) The official editorial to this round is very well done and you are encouraged to check them out!

Apparently this problem can be solved using a pure mathematical approach, but I would like to describe the dynamic programming approach to solve this problem. In the editorial the author describes an \(O(N(R-L))\) solution to this problem, which requires some bounding on the states. But due to the small search space of N, I decided to write an \(O(N^3(R-L))\) solution because it is a bit more intuitive :)

Codeforces Round #290 (Div. 1 C / Div. 2 E) - Fox and Dinner

Problem Statement:
512C - Fox and Dinner

Solution:
I've always been fascinated with maximum flow problems. The author to this problem is brilliant, and his official editorial is very well written, succinct and sweet. This post is mostly for my future reference, but feel free to read through the discussion :)

We can certainly identify that this problem is a matching problem, but what exactly is the type of matching we are interested in? On the first glance it seems to require some notion of tables, in which each table must contain at least 3 elements. That sounds like a random constraint, but as it turns out, a pretty fundamental observation to this problem can leads to a very clever representation of the problem that can easily enforce the constraints described in the problem statement.

Codeforces Round #290 (Div. 1 B / Div. 2 D) - Fox and Jumping

Problem Statement:
512B - Fox and Jumping

Solution:
The idea to solve this problem is pretty simple (but the DP is not :P): Find the lowest cost combination of cards for which their greatest common divisor is 1. The official editorial has succinctly explained the DP approach in merely a few lines, check it out!

The proper DP approach is to do a bitmask on prime factors, which will give a running time of \(O(2^k N^2)\), where k is at most 9, since there can at most be 9 different prime factors in any integer less than \(10^9\). How does it work?

Codeforces Round #290 (Div. 1 A / Div. 2 C) - Fox and Names

Problem Statement:
512A - Fox and Names

Solution:
The idea to solve this problem is pretty intuitive, but I make no pretence that implementing it is easy,  as I had a lot of trouble trying to write a correct one.

First of all we represent each letter as a node in a directed graph, where a directed edge from u to v means that u has higher "rank" than v. In this problem we are required to build such graph using the strings provided. There are a lot of ways to do this, and some are more clever than the other. My one is particularly messy, but it does the job after some debugging and patience.