Beauty of a Permutation
Contest: Codeforces Round 580 (Div. 1)
Difficulty rating: 3400
Tags: constructive algorithms, math

Define the beauty of a permutation of numbers from $$$1$$$ to $$$n$$$ $$$(p_1, p_2, \dots, p_n)$$$ as number of pairs $$$(L, R)$$$ such that $$$1 \le L \le R \le n$$$ and numbers $$$p_L, p_{L+1}, \dots, p_R$$$ are consecutive $$$R-L+1$$$ numbers in some order. For example, the beauty of the permutation $$$(1, 2, 5, 3, 4)$$$ equals $$$9$$$, and segments, corresponding to pairs, are $$$[1]$$$, $$$[2]$$$, $$$[5]$$$, $$$[4]$$$, $$$[3]$$$, $$$[1, 2]$$$, $$$[3, 4]$$$, $$$[5, 3, 4]$$$, $$$[1, 2, 5, 3, 4]$$$.

Answer $$$q$$$ independent queries. In each query, you will be given integers $$$n$$$ and $$$k$$$. Determine if there exists a permutation of numbers from $$$1$$$ to $$$n$$$ with beauty equal to $$$k$$$, and if there exists, output one of them.

Input format:
The first line contains a single integer $$$q$$$ ($$$1\le q \le 10\,000$$$) — the number of queries.

Follow $$$q$$$ lines. Each line contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 100$$$, $$$1 \le k \le \frac{n(n+1)}{2}$$$) — the length of permutation and needed beauty respectively.

Output format:
For a query output "NO", if such a permutation doesn't exist. Otherwise, output "YES", and in the next line output $$$n$$$ numbers — elements of permutation in the right order.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let's look at the first example.

The first query: in $$$(1)$$$ there is only one segment consisting of consecutive numbers — the entire permutation.

The second query: in $$$(2, 4, 1, 5, 3)$$$ there are $$$6$$$ such segments: $$$[2]$$$, $$$[4]$$$, $$$[1]$$$, $$$[5]$$$, $$$[3]$$$, $$$[2, 4, 1, 5, 3]$$$.

There is no such permutation for the second query.

The fourth query: in $$$(2, 3, 1, 4, 5)$$$ there are $$$10$$$ such segments: $$$[2]$$$, $$$[3]$$$, $$$[1]$$$, $$$[4]$$$, $$$[5]$$$, $$$[2, 3]$$$, $$$[2, 3, 1]$$$, $$$[2, 3, 1, 4]$$$, $$$[4, 5]$$$, $$$[2, 3, 1, 4, 5]$$$.

Example input:
4
1 1
5 6
5 8
5 10

Example output:
YES
1 
YES
2 4 1 5 3 
NO
YES
2 3 1 4 5

Example input:
2
4 10
100 1

Example output:
YES
1 2 3 4 
NO

Editorial:
We will denote $$$ (a, b) $$$ if there exists a permutation of length $$$ a $$$ with beauty equal to $$$ b $$$. To begin with, it is obvious that the beauty of a permutation of length $$$ a $$$ is at least $$$ a + 1 $$$ for $$$ a> 1 $$$: indeed, you can take each element individually and the entire permutation completely.
** Statement 1 **: if $$$ (a_1, b_1) $$$ and $$$ (a_2, b_2) $$$, then $$$ (a_1 + a_2 - 1, b_1 + b_2 - 1) $$$.
Let $$$ p_1, p_2, \dots, p_ {a_1} $$$ be a permutation of length $$$ a_1 $$$, whose beauty is $$$ b_1 $$$, and $$$ q_1, q_2, \dots, q_ {a_2} $$$ be a permutation of length $$$ a_2 $$$, whose beauty is equal to $$$ b_2 $$$. Let us build from them a permutation of length $$$ a_1 + a_2 - 1 $$$, whose beauty is $$$ b_1 + b_2 - 1 $$$. We "expand" $$$ p_1 $$$ in the permutation $$$ p $$$ to $$$ p_1 + q_1 - 1, p_1 + q_2 - 1, \dots, p_1 + q_ {a_2} - 1 $$$, and to the rest of the elements $$$ p $$$, greater than $$$ p_1 $$$ , add $$$ a_2-1 $$$. We got a permutation of length $$$ a_1 + a_2 - 1 $$$. Denote it by $$$ t $$$. If $$$ t_1 $$$ is not between $$$ t_ {a_2}, t_ {a_2 + 1} $$$, then we reverse the first $$$ a_2 $$$ elements, and this will be done in a new permutation. Now let $$$ t_1 $$$ be between $$$ t_ {a_2} $$$, $$$ t_ {a_2 + 1} $$$. Then what good pairs do we have in $$$ t $$$? There are $$$ b_2 $$$ good pairs among the first $$$ a_2 $$$ elements, there are $$$ b_1 $$$ good pairs if you count the first $$$ a_2 $$$ elements in one, and we counted the interval from the first $$$ a_2 $$$ elements twice, so we counted $$$ b_1 + b_2 - 1 $$$ pairs At the same time, this is all pairs, because if some good segment contains $$$ t_ {a_2} $$$ and $$$ t_ {a_2 + 1} $$$, then it must contain $$$ t_1 $$$ as well. Thus, this statement is proved.
** Statement 2 **: if $$$ (a, b) $$$, then either $$$ b = a + 1 $$$, or $$$ b = \frac{a (a + 1)}{2} $$$, or exist $$$ (a_1 , b_1) $$$, $$$ (a_2, b_2) $$$ such that $$$ 1 <a_1, a_2 $$$, $$$ a_1 + a_2 - 1 = a $$$ and $$$ b_1 + b_2 - 1 = b $$$.
Show it. We will call subsegments consisting of several consecutive numbers in some order good. Consider some kind of permutation of length $$$ a $$$ of beauty $$$ b $$$. Suppose that $$$ b \neq a + 1 $$$.
We want to show that in the permutation there is some good $$$ [L, R] $$$ subsegment of length not equal to $$$ 1 $$$ or $$$ a $$$, with the following property: for any other good $$$ [L1, R1] $$$ subsegment if $$$ [L , R] $$$ and $$$ [L1, R1] $$$ intersect, then one of them contains the second. In this case, by analogy with the proof of Proposition 1, we can "squeeze" the segment $$$ [L, R] $$$ into one element, obtaining some kind of permutation $$$ q $$$. Then the number of good segments in the entire permutation will be equal to the number of good sub-segments on the segment $$$ [L, R] + $$$ the number of good segments in $$$ q $$$ $$$ -1 $$$ (since we counted the segment $$$ [L, R] $$$ twice). We will call such a segment very good. Thus, if in each permutation there is a very good segment, then the statement $$$ 2 $$$ is true.
Suppose that $$$ b \neq a + 1 $$$, then in the permutation there is a good segment $$$ [L, R] $$$ of length not equal to $$$ 1 $$$ or $$$ a $$$. Let's say he's not very good. Then there is another. We denote $$$ (a, b) $$$ if there exists a permutation of length $$$ a $$$ with beauty equal to $$$ b $$$. To begin with, it is obvious that the beauty of a permutation of length $$$ a $$$ is at least $$$ a + 1 $$$ for $$$ a> 1 $$$: indeed, you can take each element individually and the entire permutation completely.
** Statement 1 **: if $$$ (a_1, b_1) $$$ and $$$ (a_2, b_2) $$$, then $$$ (a_1 + a_2 - 1, b_1 + b_2 - 1) $$$.
Let $$$ p_1, p_2, \ dots, p_ {a_1} $$$ & mdash; a permutation of length $$$ a_1 $$$, whose beauty is $$$ b_1 $$$, and $$$ q_1, q_2, \ dots, q_ {a_2} $$$ & mdash; a permutation of length $$$ a_2 $$$, whose beauty is equal to $$$ b_2 $$$. Let us build from them a permutation of length $$$ a_1 + a_2 - 1 $$$, whose beauty is $$$ b_1 + b_2 - 1 $$$. We "expand" $$$ p_1 $$$ in the permutation $$$ p $$$ to $$$ p_1 + q_1 - 1, p_1 + q_2 - 1, \ dots, p_1 + q_ {a_2} - 1 $$$, and to the rest of the elements $$$ p $$$, greater than $$$ p_1 $$$ , add $$$ a_2-1 $$$. We got a permutation of length $$$ a_1 + a_2 - 1 $$$. Denote it by $$$ t $$$. If $$$ t_1 $$$ is not between $$$ t_ {a_2}, t_ {a_2 + 1} $$$, then we reverse the first $$$ a_2 $$$ elements, and this will be done in a new permutation. Now let $$$ t_1 $$$ be between $$$ t_ {a_2} $$$, $$$ t_ {a_2 + 1} $$$. Then what good pairs do we have in $$$ t $$$? There are $$$ b_2 $$$ good pairs among the first $$$ a_2 $$$ elements, there are $$$ b_1 $$$ good pairs if you count the first $$$ a_2 $$$ elements in one, and we counted the interval from the first $$$ a_2 $$$ elements twice, so we counted $$$ b_1 + b_2 - 1 $$$ pairs At the same time, this is all pairs, because if some good segment contains $$$ t_ {a_2} $$$ and $$$ t_ {a_2 + 1} $$$, then it must contain $$$ t_1 $$$ as well. Thus, this statement is proved.
** Statement 2 **: if $$$ (a, b) $$$, then either $$$ b = a + 1 $$$, or $$$ b = \frac {a (a + 1)} {2} $$$, or $$$ (a_1 exists , b_1) $$$, $$$ (a_2, b_2) $$$ such that $$$ 1 <a_1, a_2 $$$, $$$ a_1 + a_2 - 1 = a $$$ and $$$ b_1 + b_2 - 1 = b $$$.
Show it. We will call subsegments consisting of several consecutive numbers in some order good. Consider some kind of permutation of length $$$ a $$$ of beauty $$$ b $$$. Suppose that $$$ b \neq a + 1 $$$.
We want to show that in the permutation there is some good $$$ [L, R] $$$ subsegment of length not equal to $$$ 1 $$$ or $$$ a $$$, with the following property: for any other good $$$ [L1, R1] $$$ subsegment if $$$ [L , R] $$$ and $$$ [L1, R1] $$$ intersect, then one of them contains the second. In this case, by analogy with the proof of Proposition 1, we can "squeeze" the segment $$$ [L, R] $$$ into one element, obtaining some kind of permutation $$$ q $$$. Then the number of good segments in the entire permutation will be equal to the number of good sub-segments on the segment $$$ [L, R] + $$$ the number of good segments in $$$ q $$$ $$$ -1 $$$ (since we counted the segment $$$ [L, R] $$$ twice). We will call such a segment very good. Thus, if in each permutation there is a very good segment, then the statement $$$ 2 $$$ is true.
Let $$$ [L, R] $$$ be a good segment that is not very good. Then there is a good segment $$$ [L_1, R_1] $$$, which intersects with $$$ [L, R] $$$, but does not contain and is not contained in it. The segments $$$ [L, R] $$$ and $$$ [L_1, R_1] $$$ form together $$$ 3 $$$ segmentы. It is easy to show that each of them is good, and the numbers in the segments go monotonously. Let us demonstrate this with an example: $$$ p = (2, 1, 3, 5, 4) $$$, the first segment is $$$ [2, 1, 3] $$$, the second is $$$ [3, 5, 4] $$$. Then together they will give the union of three segments: $$$ [2, 1], [3], [5, 4] $$$. As we can see, each of these segments is good, and also all numbers in the second segment are larger than all numbers in the first, all numbers in the third segment are larger than all numbers in the second.
Let at the moment we have lined up a chain of good segments (going consecutively) $$$ s_1, s_2, \dots, s_m $$$, where the union of any several consecutive ones is a good segment, as well as all the numbers in $$$ s_ {i + 1} $$$ more than all the numbers in $$$ s_i $$$ (or vice versa). As long as $$$ S = s_1 + s_2 + \dots + s_m $$$ is not equal to the whole segment, we will do this: since $$$ S $$$ is very good, there is a segment $$$ [L, R] $$$ that intersects with it but is not contained in it does not contain. It is easy to see that, thanks to the segment $$$ [L, R] $$$, our chain of good segments is extended.
Now suppose that $$$ s_1 + s_2 + \dots + s_m $$$ is the whole segment. While there is a segment of length greater than $$$ 1 $$$ among the segments, we will do the same: if $$$ len (s_i)> 1 $$$, then we will find the necessary $$$ [L, R] $$$ for it, then $$$ s_i $$$ will be split into two smaller good segments .
At the end of the process, we get $$$ a $$$ good segments of length $$$ 1 $$$ each, and the numbers are sorted monotonously. Hence, the numbers in the permutation were initially sorted monotonously, whence the number of good segments is $$$ \frac {a (a + 1)} {2} $$$. The statement $$$ 2 $$$ is proved.
Now the left is easy: for each $$$ i $$$ from $$$ 1 $$$ to $$$ 100 $$$, we calculate what beauty values ​​can be in a permutation of length $$$ i $$$ using statement $$$ 2 $$$, storing the corresponding values ​​$$$ (a_1, b_1), (a_2, b_2 ) $$$. After that, it is easy to answer the request by building a permutation of the desired beauty according to the algorithm with the approval of $$$ 1 $$$.
Asymptotics of $$$ O (n ^ 6) $$$ (With an incredibly small constant, up to $$$ n = 100 $$$ on $$$ Codeforces $$$ this works for 300 ms).
Challenge: improve the asymptotics to $$$ O (n ^ 5) $$$ (works in less than 30 ms).