Longest Increasing Subsequences
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef recently learned about the classic Longest Increasing Subsequence problem. However, Chef found out that while the length of the longest increasing subsequence is unique, the longest increasing subsequence itself is not necessarily unique; for example, in the array [1, 3, 2, 4], there are two longest increasing subsequences: [1, 3, 4] and [1, 2, 4].
Chef decided to investigate on this more, and now he has sufficient mastery in it that he was able to come up with a problem:
Given an integer K, output an integer N and a permutation of the array [1, 2, ..., N] such that there are exactly K longest increasing subsequences. Chef also requires that 1 ≤ N ≤ 100, otherwise he found the problem is too easy.
In case there are multiple possible answers, any one will be accepted.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case consists of a single line containing a single integer K.
For each test case, output two lines. The first line contains a single integer, N. The second line contains N space separated integers denoting the permutation of [1,2,...,N].
- 1 ≤ T ≤ 2×104
- 1 ≤ K ≤ 105
Input: 2 1 2 Output: 5 1 2 3 4 5 4 1 3 2 4
Example case 1. Here, K = 1. The array [1, 2, 3, 4, 5] indeed contains exactly one longest increasing subsequence: the whole sequence itself.
Example case 2. Here, K = 2. As explained in the problem statement, the array [1, 3, 2, 4] contains exactly two longest increasing subsequences: [1, 3, 4] and [1, 2, 4].
|Tags||dynamic-programming, kevinsogo, lis, medium, snckpa16, subsequence|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.