(Challenge) Maximizing LIS

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/OCT19/hindi/MAXLIS.pdf), [Bengali](http://www.codechef.com/download/translated/OCT19/bengali/MAXLIS.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/OCT19/mandarin/MAXLIS.pdf), [Russian](http://www.codechef.com/download/translated/OCT19/russian/MAXLIS.pdf), and [Vietnamese](http://www.codechef.com/download/translated/OCT19/vietnamese/MAXLIS.pdf) as well. You are given an integer $K$ and a random permutation ― sequence $A_1, A_2, \ldots, A_N$ of integers $1$ through $N$. You have to perform the following process: 1. Split the permutation $A$ into $K$ nonempty contiguous subsequences $S_1, S_2, \dots, S_K$ such that each element of $A$ appears in exactly one of them. 2. Choose an arbitrary permutation $P$ of the integers $1$ through $K$. 3. Create a new permutation $B_1, B_2, \ldots, B_N$ by concatenating the sequences $S_{P_1}, S_{P_2}, \ldots, S_{P_K}$ in this order. You are allowed to split the permutation $A$ into $K$ subsequences in any valid way and choose any permutation $P$ you want. Your goal is to make the length of the longest increasing subsequence of the permutation $B$ as large as possible. ### Input  The first line of the input contains two spaceseparated integers $N$ and $K$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$. ### Output Print a single line containing $N$ spaceseparated integers $B_1, B_2, \ldots, B_N$. ### Constraints  $5 \le N \le 5 \cdot 10^5$  $3 \le K \le N$  $1 \le A_i \le N$ for each valid $i$  $A_i \neq A_j$ for each valid $i, j$ ($i \neq j$) ### Scoring In each test case (and therefore each test file), let $L_A$ and $L_B$ be the lengths of the longest increasing subsequences of the permutations $A$ and $B$ respectively. If $L_B \le L_A$, your submission will receive the Wrong Answer verdict. Otherwise, your score for this test case is $(L_B  L_A) \cdot W$, where $W$ is a parameter of the grader. The values of $W$ for all tests are specified in the Test Generation section. The score of a submission is equal to the sum of its scores over all test cases. The goal is to maximise the score of your submission. There are 18 test files. During the contest, the displayed score will account for exactly five test files (belonging to groups 1, 3, 5, 7, 9 from the test generation section), i.e. your score reflects your submission's performance on roughly 28% (5 / 18) of the test files. However, if your program gets a nonAC verdict on any test file, your submission's verdict will be nonAC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program's scores over the other $13$ test files. ### Example Input ``` 7 3 5 3 7 1 2 6 4 ``` ### Example Output ``` 1 2 6 4 5 3 7 ``` ### Explanation The permutation $B = (1, 2, 6, 4, 5, 3, 7)$ could be obtained from $A = (5, 3, 7, 1, 2, 6, 4)$ in the following way: 1. Choose subsequences $S_1 = (5, 3)$, $S_2 = (7)$, $S_3 = (1, 2, 6, 4)$. 2. Choose the permutation $P = (3, 1, 2)$. 3. Concatenate $S_{P_1}, S_{P_2}, S_{P_3} = S_3, S_1, S_2 = (1, 2, 6, 4), (5, 3), (7)$. The longest increasing subsequence of $A$ is $(1, 2, 6)$ and its length is $L_A = 3$. The longest increasing subsequence of $B$ is $(1, 2, 4, 5, 7)$ and its length is $L_B = 5$. If $W = 1$, the final score of this solution on this test case is $L_B  L_A = 5  3 = 2$. ### Test generation There are nine test groups. In each test group, there are two test cases; the values of $N$, $K$ and $W$ (the scoring coefficient) are listed in the table below. In each test case, the permutation $A$ is chosen uniformly randomly among all $N!1$ permutations other than $1, 2, \ldots, N1, N$. Group N K W1  5 · 10^{3}  50  8284 
2  5 · 10^{3}  140  4745 
3  5 · 10^{3}  400  2124 
4  5 · 10^{4}  150  2676 
5  5 · 10^{4}  450  1484 
6  5 · 10^{4}  1500  580 
7  5 · 10^{5}  500  828 
8  5 · 10^{5}  1400  474 
9  5 · 10^{5}  5000  175 
Author:  alexey_adm 
Editorial  https://discuss.codechef.com/problems/MAXLIS 
Tags  alexey_adm, challenge, oct19, r_64 
Date Added:  10092019 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 