No.3477 Yet Another LIS Triangle
タグ : / 解いたユーザー数 41
作問者 : 👑
kidodesu
Problem Statement
Let's arrange integers in a triangular shape to form $3$ sequences, and make the lengths of the LIS of those sequences all equal to a fixed value.
Determine whether there exist $3$ integer sequences $A, B, C$ satisfying all of the following conditions, and if they exist, show $1$ example.
- The lengths of $A, B, C$ are all $N$.
- The lengths of the longest increasing subsequences (LIS) of $A, B, C$ are all $K$.
- $A_N = B_1$
- $B_N = C_1$
- $C_N = A_1$
- Define the sequence $P$ of length $3N - 3$ as $P = \{A_1, A_2, \dots, A_{N - 1}, B_1, B_2, \dots, B_{N - 1}, C_1, C_2, \dots, C_{N - 1}\}$. Then, the sequence $P$ contains each integer between $1$ and $3N - 3$, inclusive, exactly $1$ time.
You are given $T$ test cases; answer each of them.
Constraints
- $T \geq 1$
- $2 \leq N \leq 10^5$
- $1 \leq K \leq N$
- The sum of $N$ in $1$ input file is at most $10^5$.
Input
The input is given from Standard Input in the following format. Here, $\mathrm{case}_i(1 \leq i \leq T)$ represents the $i$-th test case.
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each case is given in the following format.
$N$ $K$
Output
For each test case, if no integer sequences $A, B, C$ satisfying the conditions exist, print No, followed by a newline. If they exist, print the integer sequences $A, B, C$ in the following format, followed by a newline. If there are multiple integer sequences $A, B, C$ satisfying the conditions, any of them will be accepted.
Yes $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$ $C_1$ $C_2$ $\dots$ $C_N$
Sample
Sample 1
Input
3 2 1 3 2 5 5
Output
No Yes 3 6 5 5 1 4 4 2 3 No
For test case number $1$, no integer sequences $A, B, C$ satisfying the conditions exist. For example, if $A = \{1, 2\}, B = \{2, 3\}, C = \{3, 1\}$, all conditions other than condition number $2$ are satisfied, but the lengths of the LIS of $A, B, C$ are $2, 2, 1$, respectively, so condition number $2$ is not satisfied.
For test case number $2$, the integer sequences $A = \{3, 6, 5\}, B = \{5, 1, 4\}, C = \{4, 2, 3\}$ satisfy all the conditions. There are other integer sequences $A, B, C$ satisfying the conditions, and any of them will be accepted.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。