PROBLEM LINK:
Author: Alexey Zayakin
Tester: Hanlin Ren
Editorialist: Hanlin Ren
DIFFICULTY:
CHALLENGE
PREREQUISITES:
Perhaps you need to know how to compute the length of the longest increasing sequence fast enough 
You can also refer to this page for computing the LIS in O(N\log N) time.
PROBLEM:
Given a random permutation A of 1,2,\dots,N, you need to split A into K parts, rearrange them in any order you like, then concatenate them. You need to maximize the longest increasing sequence of the final permutation.
EXPLANATION:
A very simple approach is: we move the smallest \lfloor \frac{K-1}{2}\rfloor numbers to the start of the permutation. It’s easy to see that the solution is valid, as it always cut the input permutation into no more than K parts. This algorithm gets 29.3pts. Many contestants use this approach, and one of the solutions can be found here.
Of course, we can also try to move the largest \lfloor \frac{K-1}{2}\rfloor numbers to the end of the permutation. Unfortunately, the score is 29.2pts which is a little bit lower. There are also many contestants that use this approach, and one of the solutions can be found here.
Actually, we can simply output the better of the two permutations generated above: we calculate the LIS of two permutations respectively, and output the one with the larger LIS. This strategy also gets 29.3pts, but its score is (of course) a little bit higher than the previous two. A sample solution can be found here.
Another strategy, as in Setter’s solution, is as follows. We split the permutation by making a cut before each of the numbers 1\sim (K-1). (e.g. if A=(5,2,6,3,1,4,7) and K=4, then we split A into (5), (2,6), (3) and (1,4,7).) Then we sort these sequences by their first number. (e.g. in the aforementioned instance, we concatenate (1,4,7), (2,6), (3) and (5) together, so our final permutation is (1,4,7,2,6,3,5).)
When K is large, this method performs better than methods discussed above. However, when K is small, this method does not guarantee that the LIS of the new permutation is better than the LIS of the input one. Therefore we need to combine it with other solutions. Tester’s implementation gets a score of about 0.352pts, compared to the best solutions in contest.
Of course, we can use more methods to generate more solutions, and output the optimal one. What’s your algorithm? Feel free to share with us!
ALTERNATE EXPLANATION:
As this is a challenge problem, there must be a lot of different approaches. Please feel free to share your approach!
(It seems that some discussion is already happening here.)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int MX = 500000;
int a[MX];
int main() {
int n, k;
ignore = scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) ignore = scanf("%d", a + i);
int x = (k - 1) / 2;
if (x + 2 * sqrt(n - x) > k) {
for (int i = 1; i <= x; i++) printf("%d ", i);
for (int i = 0; i < n; i++) {
if (a[i] <= x) continue;
printf("%d ", a[i]);
}
printf("\n");
}
else {
vector<bool> split(n + 1, false);
split[0] = true;
split[n] = true;
vector<pair<int, int>> vec;
for (int i = 0, f = 0; i < n; i++) {
if (a[i] > k) continue;
vec.emplace_back(a[i], i);
if (f > 0) split[i] = true;
f++;
}
sort(vec.begin(), vec.end());
for (auto& x : vec) {
int i = x.second;
while (split[i] == false) i--;
do {
printf("%d ", a[i]);
i++;
} while (split[i] == false);
}
printf("\n");
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
void gi(int &x) {char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();}
#define sz 1020202
void pi(int x) {if (x > 9) pi(x / 10); putchar(x % 10 + 48);}
int n, k;
int z[sz];
int add(int x, int y) {for (; x <= n; x += x & -x) z[x] = max(y, z[x]);}
int MAX(int x) {int a = 0; for (; x; x -= x & -x) a = max(a, z[x]); return a;}
int lis(int *a) {
int mx = 0, f = 0;
for (int i = 0; i <= n; i++) z[i] = 0;
for (int i = 1; i <= n; i++) {
f = MAX(a[i]) + 1;
add(a[i], f); mx = max(mx, f);
}
return mx;
}
void output(int *a) {
for (int i = 1; i <= n; i++) pi(a[i]), putchar(' ');
}
int a[sz], b[sz], bl, c[sz], cl, d[sz];
void do3(int *b) {
static int z[sz]; int l = 0;
for (int i = 1; i <= n; i++) z[a[i]] = i;
for (int i = 0; i < k; i++) {
int s = 1; if (i) s = z[i];
while (s <= n) {
b[++l] = a[s++]; if (a[s] < k) break;
}
}
}
int main() {
gi(n); gi(k);
for (int i = 1; i <= n; i++) gi(a[i]);
int tmp = (k - 1) / 2;
for (int i = 1; i <= tmp; i++) b[++bl] = i;
for (int i = 1; i <= n; i++) if (a[i] > tmp) b[++bl] = a[i];
for (int i = 1; i <= n; i++) if (a[i] <= n - tmp) c[++cl] = a[i];
for (int i = n - tmp + 1; i <= n; i++) c[++cl] = i;
do3(d);
int lisb = lis(b), lisc = lis(c), lisd = lis(d);
int lm = max(lisb, max(lisc, lisd));
if (lisb == lm) output(b);
else if (lisc == lm) output(c);
else output(d);
return 0;
}
