A chain cut week

The Sep 11 - Sep 17 week had its contests on the weekend. On Saturday MemSQL Start[c]UP has returned to Codeforces after a three-year absence with Round 1 of its third edition (problems, results, top 5 on the left, my screencast, analysis). moejy0viiiiiv was 25 minutes faster than everybody else to solve all problems, and made sure to protect his lead with a few challenges. Congratulations on the win!

The round had a few nice problems, but let me highlight problem F: there are many contestants taking part in a competition, and top c will be awarded with t-shirts. There are n available t-shirt sizes (n<=200000). Each contestant has indicated one of two things: either they need a t-shirt with some concrete size, or they need a t-shirt with one of the two concrete adjacent sizes. More precisely, for each size i we know the number a_i of contestants (up to 10⁸) that need a t-shirt of size i, and the number b_i of contestants (also up to 10⁸) that need either a t-shirt of size i or a t-shirt of size i+1. What is the minimal number of t-shirts we need to buy in order to be able to give t-shirts to top c contestants, no matter which ones end up in top c?

Apart from being an interesting problem in general, it's a great example for this recent discussion about stories in problem statements. I think that here the t-shirt and contestant story actually makes the problem statement really easy to understand and think about, while a completely formal mathematical statement would be hard to parse.

On Sunday the new season of the Open Cup started with the Grand Prix of Romania (problems, results, top 5 on the left). Team Past Glory did not show any signs of slowing down and won convincingly by a problem — well done! The great performance and second place of the Seoul National U 2 team was a great surprise, and even more so given that this is a different team from the one that earned gold medals at the last ICPC World Finals for Seoul.

Problem L of this contest showed that we can still find new games with non-trivial solutions in a very simple setup: two players have a sequence of 50000 integers, and alternately take numbers from either end of the sequence. When all numbers have been taken, each player computes the bitwise xor of their numbers, and the one with a higher bitwise xor wins. Who will win?

And right after the end of the Grand Prix, Codeforces held its Round 434 (problems, results, top 5 on the left, analysis). The battle for the first place was quite tight. Congratulations to kmjp who came out on top by a mere 25 points!

In my previous summary, I have mentioned a hard TopCoder problem: you are given 50 attractions in a city. You will visit exactly one attraction per day. Each attraction can be visited either in the morning, costing a_i, or in the evening, costing b_i. Every time you visit an attraction in the morning after visiting another attraction the previous evening, you pay an extra cost c. Every time you switch from evening to morning, you pay an extra cost d. Additionally, you are given a directed graph of restrictions — a set pairs of attractions that constrain the order of visits: in each pair, the first attraction must be visited before the second one. What is the minimal cost to perform all visits?

First of all, let's split our visits into groups: a group of morning visits, then a group of evening visits, then a group of morning visits, and so on (we need to consider two cases based on whether the very first visit is in the morning or in the evening). Since we only pay extra costs when we switch groups, the total cost depends on the number of groups and on the assignment of visits to groups, but not on the order of visits within each group.

Now let's try to build a network in which a cost of a cut would correspond to the total cost of the visits, so that we can solve our problem with the minimum cut algorithm. For each attraction, let us build a chain of vertices, with all chains having the source and sink as start and end respectively. A chain for one attraction looks like: s->v₁->v₂->..->v_n->t. Let's add infinite capacity edges going backwards in the chain, to guarantee that any finite cut separates some prefix of this chain from the rest. The size of this prefix will correspond to the number of the group that this attraction belongs to, and thus the capacity of the edges should be alternating a_i and b_i: if the vertex belongs to an even-numbered group, the corresponding edge will contribute a_i to the total capacity of the cut, and otherwise b_i, just as we need.

In order incorporate a restriction "p must be visited before q" into our network, we will add infinite capacity edges from the vertices of the chain for p to the corresponding vertices of the chain for q. This guarantees that with any finite cut, the position we cut the chain for p will be the same or earlier than the position we cut the chain for q.

Finally, in order to incorporate the morning/evening switching costs, let us add an extra attraction that must be visited after all others, and set up the capacities on its chain not as alternating a_i and b_i, but rather as 0, c, c+d, 2c+d, 2c+2d, ...

The finite cuts in the resulting network correspond to valid ways of visiting the attractions, and the capacity of the cut is equal to the total visit cost, so now we just need to find the minimum cut. Also note that we have built our network using two relatively standard building blocks: infinite edges can give us constraints on the cut, and a chain of vertices with infinite backwards edges implements a choice from several alternatives with specific costs.

Thanks for reading, and check back soon!