PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Longest increasing subsequence, Greedy
PROBLEM:
Given array A, determine the maximal possible longest common subsequence over all pairs of longest non-increasing and longest non-decreasing subsequences of A.
EXPLANATION:
Let P and Q be some longest non-increasing and longest non-decreasing subsequences of A respectively.
Claim: The longest common subsequence of P and Q can not contain two different numbers (that is, all terms of the LCS are the same).
Proof
Assume the contrary.
Then there exists some a,b\space(a\ne b) in the LCS. WLOG, let a<b.
If a appears before b in the LCS, since the LCS is a subsequence of P, a appears before b in P, a contradiction to the non-increasing property of P.
We can similarly show contradiction for the case where a appears after b.
Thus proved.
From the above claim, it is obvious that if the optimal LCS is comprised of integer x, then the number of times x occurs in both P and Q should be maximum (while still being some longest non-increasing and longest non-decreasing subsequence, respectively).
If c_x and d_x represent the maximum number of times x occurs over all P and Q respectively, the answer is then equal to
How do I compute these values?
We only discuss the steps to compute array c, since d can be computed in a similar fashion.
Let I[i] be the length of the longest non-increasing subsequence (from left to right) of A with A_i as it’s last term. Also, let IC[i] be the maximum number of times elements with value A_i can occur in this subsequence.
Similarly, let D[i] be the length of the longest non-decreasing subsequence (from right to left) of A with A_i as it’s last term. Let DC[i] be the maximum number of times elements with value A_i can occur in this subsequence.
Both these arrays can be computed in O(N\log N) each, using a slightly modified version of the longest increasing subsequence algorithm.
Then, the longest non-increasing subsequence that contains A_i has length I[i]+D[i]-1 (the -1 is because element A_i is double counted), and the maximum number of times elements with value A_i can occur is equal to IC[i]+DC[i]-1.
Finally (this step is important, since selecting A_i might not give the longest possible non-increasing subsequence of A), if I[i]+D[i]-1 is equal to the length of the longest non-increasing subsequence of A, update
TIME COMPLEXITY:
Calculating array c and d takes amortized O(N\log N), and calculating the answer from this takes O(N), making the total time complexity
per test case.
SOLUTIONS:
Editorialist’s solution can be found here.
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters