Codeforces Round 267 Div. 2 Problem E - Alex and Complicated Task

Problem Statement:
467E - Alex and Complicated Task

Solution:
We maintain an array P and a set S, and we consider the elements from left to right:
1. If \(v = a_i\) is not in S yet, add it in and note its index. Hence S will store the index j of the first occurrence of the number \(v\).
2. Else, we set P[i] to index of j of \(v = a_i\) we stored in S.
3. If between P[i] and i there exist P[j] that is less than P[i], then the element P[j], P[i], j, and i forms one desired sequence! Store them and reset S.

Codeforces Round 267 Div. 2 Problem D - Fedor and Essay

Problem Statement:
467D - Fedor and Essay

Solution:
A pretty fun problem to solve! One thing to notice is that the replacement rule is not bidirectional, i.e. if \(x_i\) and \(y_i\) are synonyms, it only says we can replace \(x_i\) with \(y_i\), but not the other way around. So in other words, we have a directed edge from \(x_i\) to \(y_i\). Each word acts as a vertex, and hence for each vertex u, we would like to know, amongst all vertices v that is reachable from u, what is the minimum number of \(R\) and minimum length of such synonym.

Codeforces Round 284 Div.1 Problem C - Array and Operations

Problem Statement:
498C - Array and Operations

Solution:
Another interesting max-flow problem, but I think coming up with the correct model may require some level of familiarity with the concept and intuition, since the runtime complexity analysis can be a bit subtle.

The clever idea behind this problem is to consider each prime one by one. We start out with a source S and a sink T. Then since \(i_k + j_k\) is guaranteed to be an odd number, we conclude that \(i_k\) and \(i_j\) has different parity, i.e. one is odd, and another is even. So we actually have a bipartite matching task, between the odd-indexed and the even-indexed \(a_i\)s. From here, we build a graph as follows:
1. Choose a prime \(p\).
2. For each pair of odd indexed \(a_i\) and even indexed \(a_j\), we find the maximum number of times each of them can be divided by \(p\), call it n and m respectively.
3. Next, we connect S to \(a_i\), \(a_i\) to \(a_j\) and \(a_j\) to T.
4. The capacity of the edges are set as follows:
    - capacity of (S, \(a_i\)) is n.
    - capacity of (\(a_j\), T) is m.
    - and capacity of (\(a_i\), \(a_j\)) is the minimum of n and m.

TopCoder SRM 371 Div. 1 Medium - ChessMatchup

Problem Statement:
TopCoder SRM 371 Div. 1 Medium - ChessMatchup

Solution:
Just learnt Kuhn-Munkres algorithm, and tried a related problem. The problem is a straight forward modification of maximum weight perfect matching. Here is an implementation:

Codeforces Round 272 Div. 1 Problem D - Dreamon and Binary

Problem Statement:
477D - Dreamon and Binary

Solution:
A loaded DP problem.. And it features an interesting use of suffix array prefix doubling technique. The official editorial to this problem seems to be quite detailed, but somehow I find it a bit hard to understand. You may find my explanation even more confusing, but hopefully still useful.

Codeforces Round 284 Div. 1 Problem B - Name That Tune

Problem Statement:
498B - Name That Tune

Solution:
A tough problem, not only because it is a conceptually difficult problem on probability, but also coupled by the fact that the problem constrain is very, very tight. In fact I have rewrote my implementation, which all are based by the idea described in the official editorial, just to reduce constant term in the running time complexity. But a good problem nevertheless :)

DP state that works here is as follows:
Let D[i][k] be the probability of the person guessing i-th song exactly at time k seconds. The base case for D is that of D[0][0] which means guessing none of the song exactly at time 0 second.

Codeforces Round 271 Div. 2 Problem E - Pillars

Problem Statement:
474E - Pillars

Solution:
This problem has a very interesting use of segment tree in combination with DP. The DP idea is very standard: let f[i] be the maximum length of jumps using pillars from [1..i], ending at i. Then f[i] = max of f[j] + 1, for all j such that \(|h_i-h_j| \geq d\). Then what's left is to find an efficient way to find those j that satisfies the requirement, and at the same time, find the maximum f[j] amongst all such j. This is where the segment tree comes in.