PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given an array F, representing the frequencies of elements 1, 2, \ldots, N.
Across all arrays A matching this frequency array, compute the maximum possible value of \min(\text{LIS}(A), \text{LDS}(A)).
Here, \text{LIS}(A) is the length of the longest strictly increasing subsequence in A, and \text{LDS}(A) is the same but for decreasing.
EXPLANATION:
We want to maximize \min(\text{LIS}(A), \text{LDS}(A)), which means we want to have both a long increasing sequence and a long decreasing sequence.
Importantly, note that \text{LIS}(A) and \text{LDS}(A) use strictly increasing/decreasing subsequences respectively - which means that only distinct elements matter.
Because only distinct elements matter, we only really care about which elements are present in the LIS/LDS; since after deciding the elements for each, we can just arrange them in ascending/descending order appropriately.
So, let’s try to decide which elements must be chosen for which sequence.
Let’s look at some element x.
- If F_x \ge 2, we have (at least) two copies of x.
This allows us to use one copy for the increasing sequence and one copy for the decreasing sequence, and these copies don’t interfere with each other at all.
This allows us to increase both the lengths of the increasing and decreasing sequence by 1, which is clearly the best we can do. - If F_x = 1, we have only one copy of x.
This copy can be used in either the increasing sequence or the decreasing sequence - but can we potentially use it in both? If we can, that would definitely be optimal.
Now, observe that it’s not too hard to use any single element in both an increasing and a decreasing sequence.
For example, the array [3, 2, 1, 2, 3] has the single element 1 appearing in both the LIS and the LDS.
However, this can only be done for one element.
Specifically, if we have two different elements, then it’s impossible for both of them to appear simultaneously in an increasing and a decreasing subsequence.
It’s not hard to see why: if we have x \lt y and x appears before y in the array, then no decreasing subsequence can contain x and y (and similarly if x appears after y then no increasing subsequence can contain them both).
Thus, among elements with F_x = 1, at most one of them can contribute to both the LIS and the LDS.
Every other such element can be present in only one or the other.
Since we’re trying to balance their lengths, it’s clearly optimal to give half of them to the LIS and the other half to the LDS.
Putting everything together, we obtain the following:
- Let c_1 denote the number of x such that F_x = 1.
Let c_2 denote the number of x such that F_x \ge 2. - We can start out with a “base” of c_2 + \min(1, c_1), since each of the c_2 elements with higher frequency can be given to both increasing and decreasing sequences; and also one element with frequency 1 can do this (if it exists).
- That leaves \max(0, c_1 - 1) elements with frequency 1.
Half of them go to the increasing sequence, the other half to the decreasing sequence.
The answer is the base plus whichever is the smaller among these two halves, i.e.c_2 + \min(1, c_1) + \left\lfloor \frac{\max(0, c_1-1)}{2} \right\rfloor
This expression can be further simplified to just c_2 + \left\lceil \frac{c_1}{2} \right\rceil.
Note that we also need to actually prove that this bound is attainable by constructing a valid array, but that’s not too hard.
Once the elements participating in the increasing/decreasing subsequences have been decided, do the following:
- If there are to be no common elements (which happens when c_1 = 0), the two subsequences are entirely separate in terms of elements.
Just have the increasing subsequence first, then the decreasing subsequence, then all remaining elements in some order. - If there is one common element, say x, do the following:
- First, place all elements of the increasing subsequence.
- Then, before x, place all elements of the decreasing subsequence that are larger than x (in descending order of course).
- Next, after x, place all elements of the decreasing subsequence that are smaller than x.
- Finally, append all unused elements.
This constructs the LIS and LDS of the required lengths while keeping the chosen x in common.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
f = list(map(int, input().split()))
ones, more = 0, 0
for x in f:
if x == 1: ones += 1
if x > 1: more += 1
print(more + (ones + 1) // 2)