PROBLEM LINK:
Author: Tasnim Imran Sunny
Tester: Istvan Nagy
Editorialist: Lalit Kundu
DIFFICULTY:
Medium-Hard
PREREQUISITES:
dynamic programming, graphs, greedy
PROBLEM:
There are N cards placed in a row, where every card has two numbers written on it, one on the top(array A) and one on the bottom(array B). The numbers are between 1 and N(both inclusive). Every number is written on the top of exactly one card, and on the bottom of exactly one card as well.
Chef wants to rearrange the cards, such that the length of the longest common contiguous subsequence between the sequence formed by number written on top of the cards, and that formed by those written on the bottom is maximum. He can’t modify the numbers written on any card and can’t flip the cards, that is, for any card the number written on top remains at the top and the number written on bottom stays at the bottom. Find out the maximum possible length of the common contiguous subsequence.
QUICK EXPLANATION:
======================
Consider a single card as a node in the graph and then add edge between nodes i and j if A_i = B_j. In the graph built, break down cycles into chains and try to interleave these chains to form a common substring. For a set of chains, they can be interleaved only if size of each chain is either m or m+1. Traverse over variable m to calculate maximum possible answer. Answer for a certain m can be calculated via DP.
EXPLANATION:
================
Note: We’ll be using 0-indexing of arrays in this editorial.
First observation should be that these cards have permutations written on them and problems involving permutations can usually be solved using dynamic programming + bitmasks, but constraints here are high. We can guess that a polynomial solution is required.
Let’s try to think something on terms of graph. Maybe construct a bipartite graph where there are edges between two nodes if their value matches? Does it help? No, it doesn’t because two values A_i and B_i are stuck together, they can’t be moved around independently! So, why not consider a single card as a node in the graph and then add edge between nodes i and j if A_i = B_j. How does this graph look like? You can try some examples to see where are we arriving at. Let’s consider the example,
7
4 2 6 5 3 7 1
4 5 6 3 2 1 7
The graph we’ve build looks something like:
____ 1-----3
| | \ /
0____| \ /
4
____ ____
| | | |
2____| 5____6
Let’s observe the cycle with 3 edges. There are three cards with values [2, 5], [5, 3] and [3, 2]. If we place them in the same order we get
A = 2 5 3
B = 5 3 2
where substrings A[1, 2] and B[0, 1] are same. What if I put some more cards such that we get a formation of card numbers like 1-P-3-Q-4(P and Q are some other cards), now what happens? We get something like
A = 2 x 5 y 3
B = 5 a 3 b 2
Now, substrings A[2,4] and B[0,2] can be same if a == y. If we have two another cards with numbers r and s such that B_r == A_s, then we can place them instead of P and Q and our substrings will be matched. We have two such cards 5 and 6 with us.
Do you observe what is happening? Our partial sequence that gives us a common substring of length 3 is S = [1, 5, 3, 6, 4]. This happens because in the graph that we’ve built 1 and 3 are adjacent which matches values of A and B at indices S_0 and S_2 respectively. Similarly, values of A and B at S_1 and S_3 are matched because card numbers at those positions are adjacent in the graph. Again, at indices S_2 and S_4, cards which are adjacent are placed. We can complete our final sequence by adding remaining cards, before or after the current sequence but it doesn’t matter as it doesn’t contribute to the answer.
This is the main idea here. We are building a final single sequence(say S) of N card numbers in such a way that for a certain x and j, S_j is adjacent to S_{j+x}, S_{j+1} is adjacent to S_{j+x+1}, S_{j+2} is adjacent to S_{j+x+2} and so on. For that we break down cycles in chains of small lengths and then interleave multiple chain lengths to form a single sequence.
What about the criteria of length while interleaving? Can we interleave chains of arbitrary length together?
We should observe that for a certain chain all of its elements should be equally spaced(like in the above example for the chain (1-3-4) we placed them at a distance of 1 from each other). You can see that if S_0 is adjacent to S_x, then S_x should be adjacent to S_{2x} and so on. Similarly, for the element at index 1, S_1 should be adjacent to S_{x+1} and so on.
Now, here is an interesting proposition:
If in a set of chains, length of any two chains doesn’t differ by more than 1, it is possible to interleave them.
Here comes the greedy part. We know that for each element of a chain(except the last element), its next element should occur at equally spaced intervals. First, we place all chains of length m+1 and then all chains of length m and now if we build our answer by putting elements from each chain one by one, this criteria will always be satisfied(Can you prove it?).
For example, three chains are
[1, 2, 3]
[6, 7, 8]
[4, 5]
If we arrange these cards like [1, 6, 4, 2, 7, 5, 3, 8], then for each chain, its elements are equally spaced and each chain of length \textrm{len} contributes \textrm{len-1} values to the common substring(How?).
So, chains in a set should of length m or m+1. Traversing over this variable m till N and taking maximum of all the cases will give us the answer.
Consider, m=1. It is a special case because there is no next element in chains of length 1. We have to handle this case separately. We can do that very easily by placing all chains of length 1(which basically is a single card) adjacent to each other in our final solution.
The only thing now left is, for a given cycle length and a variable m, break cycle into chain lengths of m or m+1 such that (total number of nodes included in the chains - total number of chains) is maximised. We subtract total number of chains, because each chain of length \textrm{len} contributes \textrm{len-1} to the answer. For this we employ DP 
We define \textrm{DP}(i, j) as the maximum number of nodes that can be covered by chains of length j or j+1. Now, defining recurrence here is very easy:
\textrm{DP}(i, j) = \textrm{max}(j - 1 + \textrm{DP}(i-j, j), j + \textrm{DP}(i-j-1, j).
Here is the commented pseudo code:
//this array contains cycle lengths
cycle[K]
final=0
for i=2 to N:
curans=0 //answer for current value of i
for j=1 to K:
curans += DP(cycle[j], i)
final=max(final,curans)
print final
This DP array can be precomputed to reduce the complexity.
Total complexity that way would be O(N^2).
Refer to setter’s commented solution for implementation details.