Four Melodies
Contest: Educational Codeforces Round 24
Difficulty rating: 2600
Tags: flows, graphs

Author note: I think some of you might remember the problem "Two Melodies" from Eductational Codeforces Round 22. Now it's time to make it a bit more difficult!

Alice is a composer, and recently she had recorded two tracks that became very popular. Now she has got a lot of fans who are waiting for new tracks.

This time Alice wants to form four melodies for her tracks.

Alice has a sheet with n notes written on it. She wants to take four such non-empty non-intersecting subsequences that all of them form a melody and sum of their lengths is maximal.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Subsequence forms a melody when each two adjacent notes either differ by 1 or are congruent modulo 7.

You should write a program which will calculate maximum sum of lengths of such four non-empty non-intersecting subsequences that all of them form a melody.

Input format:
The first line contains one integer number n (4 ≤ n ≤ 3000).

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 105) — notes written on a sheet.

Output format:
Print maximum sum of lengths of such four non-empty non-intersecting subsequences that all of them form a melody.

Constraints:
Time limit: 5.0 s
Memory limit: 1024.0 MB

Note:
In the first example it is possible to compose 4 melodies by choosing any 4 notes (and each melody will consist of only one note).

In the second example it is possible to compose one melody with 2 notes — {1, 2}. Remaining notes are used in other three melodies (one note per each melody).

Example input:
5
1 3 5 7 9

Example output:
4

Example input:
5
1 3 5 7 2

Example output:
5

Editorial:
Let's build a directed graph where vertices represent notes and a directed edge comes from vertex i to vertex j iff i < j and ai and aj can be consecutive notes in a melody. Now we have to find four longest vertex-disjoint paths in this graph.
This problem can be solved with mincost k-flow algorithms. We build a network where each vertex of the graph is split into two (let's denote the vertices that we obtain when we are splitting some vertex i as vi, 1 and vi, 2). Then each directed edge $$\vec{i} \rightarrow \vec{j}$$ transforms into a directed edge from vertex vi, 2 to vertex vj, 1 in the network, the capacity of this edge is 1, and the cost is 0. Also we add directed edges from the source to every vertex vi, 1 and from every vertex vi, 2 to the sink (they have the same characteristics: capacity is 1, cost is 0). And for each i we add a directed edge between vi, 1 and vi, 2; these edges actually represent that we are using some note in a melody, so their capacities are also equal to 1, and their costs are  - 1. The answer to the problem is equal to the absolute value of minimum cost of 4-flow in this network.
The bad thing is that the network is really large. So we have to use some advanced mincost algorithm here.
Model solution uses Dijkstra's algorithm with Johnson's potentials to find augmenting paths of minimum cost. We set a number p(v) for each vertex v of the network (these numbers are called potentials). Then we modify costs of the edges: if some edge $$\vec{i} \rightarrow \vec{j}$$ had cost ci, j, now it's cost is {c'}i, j = ci, j + p(i) - p(j). It's easy to prove that if some path from vertex v to vertex u was the shortest one between these vertices without modifying the costs with potentinals, then after modifying it will also be the shortest between these vertices. So instead of looking for an augmenting path in the original network we can try looking for it in a network with modified edges. Why? Because it is always possible to set all potentials in such a way that all costs of edges will be non-negative (and we will be able to use Dijkstra to find the shortest path from the source to the sink).
Before looking for the first augmenting path, we calculate potentials recursively: p(source) = 0, p(v) = min{p(u) + cu, v} (we check all u's such that there is an edge $$u \rightarrow v$$ in the network). The network is acyclic before we push flow, so there is always a way to calculate these potentials with dynamic programming. Then each time we want to find an augmenting path, we run Dijkstra's algoritm on modified network, push flow through the path we found and modify the potentials: new potential of each vertex v becomes p'(v) = p(v) + d(v), where d(v) is the distance between the source and vertex v in the modified network (and we found this distance with Dijkstra). When we have found four augmenting paths, we are done and it's time to evaluate the cost of the flow.