DECSUBK - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY

PREREQUISITES:

Greedy, Brute force, Longest Increasing Subsequence

PROBLEM:

Given an array A of length N. You’re also given an integer K.
Determine the lexicographically smallest array B such that:

  • B is a rearrangement of the elements of A, and
  • the length of the longest non-decreasing subsequence of B is K.

EXPLANATION:

Notation: LLNDS of a sequence S refers to the length of the longest non-decreasing subsequence of S.


Let’s handle the trivial case first. When a particular value occurs more than K times in A, then no valid sequence B exists.

I claim that it is always possible to construct the sequence B otherwise.

How?

Sort A in non-decreasing order. Let x=N-K+1.
Then, it’s not too hard to show that

B = [A_{x}, A_{x+1},\dots,A_{N}, A_{x-1},A_{x-2},\dots,A_1]

is a valid sequence (but it might not be the lexicographically smallest).

Lemma: If it is possible to rearrange A to create sequences with LLNDS equal to p and q respectively, then it is also possible to rearrange A to get a sequence with LLNDS equal to r\ (p\le r\le q).

Proof

Let P and Q represent the rearranged sequences with LLNDS equal to p and q respectively.

Consider a sequence of swaps of consecutive elements in P that transforms it into sequence Q. It’s clear that each swap changes the LLNDS of P by at most 1.

Therefore, since the LLNDS of P equals q at the end of all the swaps, and the LLNDS changes by at most 1 in each swap, it follows that a sequence with LLNDS equal to r\ (p\le r\le q) must also exist.

We employ a bruteforce strategy to solve the problem.

Create array S to hold the final answer. Initially, S is empty.
Then, while A is not empty, do the following:

  • determine the smallest element x in A such that, if you appended x to S, and then appended all other elements in A to S in some optimal fashion, the LLNDS of S would be equal to K.
  • erase x from A and append it to S.

The validity of the solution constructed using this greedy strategy is trivial to verify (and left to the reader as an exercise).

We are now left to find the smallest x in each step. The constraints immediately hint the viability of a bruteforce. That is, we can try every value in A (from least to greatest) as x, and determine if it’s possible to append the remaining values to get a sequence whose LLNDS is equal to K.

So, how do we efficiently determine if it’s possible to append the remaining values to get a sequence whose LLNDS is equal to K?

Here’s when the above lemma comes into the picture!
Let p and q respectively represent the smallest and largest possible LLNDS attainable (after appending the remaining values to S). The answer to the above query is YES only if p\le K\le q.

All we are left to do is find the value of p and q.
The value of p is equal to the LLNDS of the sequence formed after appending the remaining values of A to S, in non-increasing order. Similarly, the value of q is equal to the LLNDS after appending the values in non-decreasing order.
(Validity of both statements is easy to observe; rigorious proof is left to the reader as an exercise).

Computing the LLNDS of a sequence can be done efficiently in O(N\log N) using the following method.


Here’s a quick implementation draft:

  • Check if a value occurs more than K times in A; output -1 and continue to the next test case, if any such value exists.
  • Sort A in non-decreasing order. Also create an empty array S.
  • Then, while A is not empty:
    • Iterate over A from left to right. Let the current value be x.
    • Let S_1 = S_2 = S. Append x to S_1 and S_2. Then append all other elements of A to S_1 and S_2 in non-increasing and non-decreasing order respectively.
    • If \text{LLNDS}(S_1)\le K\le \text{LLNDS}(S_2) append x to S, erase x from A, and restart the loop from the beginning.
  • Print array S at the end.

TIME COMPLEXITY:

The above steps are run N times. In each step, we iteratively try one of the N elements in A as x. For each x, we append the remaining values in linear time. Calculating the LLNDS in each case takes O(N\log N).
Therefore, the total time complexity is

O(N\times N\times 2\cdot N\log N) \approx O(N^3\log N)

per test case.

SOLUTIONS:

BONUS: It suffices to only check if \text{LLNDS}(S_1)\le K. That is, if a solution exists, then K\le \text{LLNDS}(S_2) holds true in each iteration.

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

2 Likes

Crystal Clear Explanation. Kudos !!
JAVA implementation of the above approach : Soln

1 Like