Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip

Problem Statement:
Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip

Summary:
An integer array A of size n <= 5000 has entries which ranges from 1 to 5000. We pick disjoint segments of the array such that for each segment S:
1. If i in S, then any j s.t. a[j] == a[i] must also be in S
2. The score of S is computed as the XOR of its elements
Goal is to maximise the sum of scores of the chosen segments.

Solution:
I like this problem. This is solvable using a dynamic programming approach.

Codeforces Good Bye 2014 Problem F - New Year Shopping

Problem Statement
500F - New Year Shopping

Solution:
A pretty tough problem which solution employs a very clever divide and conquer strategy. Learnt cool stuff :D.

Let's suppose that all the items are already sorted by \(t_i\) in increasing order. We know that item i will be available in the time segment \([t_i,t_i+p-1]\). Suppose that for each time \(T\), we know which are the segments that contain \(T\), i.e. the set of i such that \(T \in [t_i,t_i+p-1]\).

Codeforcees Round 283 Div. 2 Problem E - Distributing Parts

Problem Statement:
496E - Distributing Parts

Solution:
This is more for self-reference, I suggest you read the official tutorial on Codeforces for a better discussion on this problem.

This problem is a bipartite matching problem: match smaller "job" segments into bigger container "worker" segments, where each worker segment has certain capacity. If we model each segments as vertices, then we have a graph with \(V\) vertices. This problem cannot be solved efficiently using maxflow algorithm, since V can be very huge, hence there must be some greedy idea behind it. And as I learnt from the editorial, the idea is to consider both jobs and workers in increasing order of their lower bounds. In this iteration, we keep track of a set S of workers that we have encountered, which has the following invariant:
For all i, by the time we reach i-th segment, the lower-bound of this segment is always bigger or equal to any lower bounds of segments in S.

Hence if the i-th segment we are facing is currently a job segment, we just need to find a worker segment in S that has a bigger upper bound than that of the job segment. If there are multiple choices, we must choose the lowest one available. I think this choice can be proven to yield optimal matching by exchange arguments.

If the implementation of S is done by using RB tree, the running time of this algorithm will be \(O(V\lg{V})\).