[Solution] Reversort Engineering Solution Code Jam 2021

Reversort engineering solution codejam 2021

Table of Contents

Problem

Note: The main parts of the statements of the problems “Reversort” and “Reversort Engineering” are identical, except for the last paragraph. The problems can otherwise be solved independently.

Reversort is an algorithm to sort a list of distinct integers in increasing order. The algorithm is based on the “Reverse” operation. Each application of this operation reverses the order of some contiguous part of the list.

The pseudocode of the algorithm is the following:

Reversort(L):
  for i := 1 to length(L) - 1
    j := position with the minimum value in L between i and length(L), inclusive
    Reverse(L[i..j])

After i−1i−1 iterations, the positions 1,2,…,i−11,2,…,i−1 of the list contain the i−1i−1 smallest elements of L, in increasing order. During the ii-th iteration, the process reverses the sublist going from the ii-th position to the current position of the ii-th minimum element. That makes the ii-th minimum element end up in the ii-th position.

For example, for a list with 44 elements, the algorithm would perform 33 iterations. Here is how it would process L=[4,2,1,3]L=[4,2,1,3]:

i=1, j=3⟶L=[1,2,4,3]i=1, j=3⟶L=[1,2,4,3]
i=2, j=2⟶L=[1,2,4,3]i=2, j=2⟶L=[1,2,4,3]
i=3, j=4⟶L=[1,2,3,4]i=3, j=4⟶L=[1,2,3,4]

The most expensive part of executing the algorithm on our architecture is the Reverse operation. Therefore, our measure for the cost of each iteration is simply the length of the sublist passed to Reverse, that is, the value j−i+1j−i+1. The cost of the whole algorithm is the sum of the costs of each iteration.

In the example above, the iterations cost 33, 11, and 22, in that order, for a total of 66.

You are given a size NN and a cost CC. Find a list of NN distinct integers between 1 and NN such that the cost of applying Reversort to it is exactly CC, or say that there is no such list.

Input

The first line of the input gives the number of test cases, TT. TT lines follow. Each line describes a test case with two integers NN and CC, the size of the wanted list and the desired cost, respectively.

Output

For each test case, if there is no list of size NN such that applying Reversort to it costs exactly CC, output one line containing Case #xx: IMPOSSIBLE, where xx is the test case number (starting from 1). Otherwise, output one line containing Case #xx: y1y1 y2y2 ... yNyN, where xx is the test case number (starting from 1) and each yiyi is a distinct integer between 11 and NN, representing the ii-th element of one such possible list.

If there are multiple solutions, you may output any one of them. (See “What if a test case has multiple correct solutions?” in the Competing section of the FAQ.) This information about multiple solutions will not be explicitly stated in the remainder of the 2021 contest.

Limits

Time limit: 10 seconds.
Memory limit: 1 GB.
1≤T≤1001≤T≤100.
1≤C≤10001≤C≤1000.

Test Set 1 (Visible Verdict)

2≤N≤72≤N≤7.

Test Set 2 (Visible Verdict)

2≤N≤1002≤N≤100.

Sample

Sample Input

Sample Output

Case #1: 4 2 1 3
Case #2: 1 2
Case #3: 7 6 5 4 3 2 1
Case #4: IMPOSSIBLE
Case #5: IMPOSSIBLE

Sample Case #1 is described in the statement above.

In Sample Case #2, the algorithm runs for only one iteration on the proposed output. In that iteration, reverse is applied to a sublist of size 1, therefore, its cost is 1.

In Sample Case #3, the first iteration reverses the full list, for a cost of 7. After that, the list is already sorted, but there are 5 more iterations, each of which contributes a cost of 1. Another valid output would be 7 5 4 3 2 1 6. For that output, the first iteration has a cost of 6, the last one has a cost of 2, and all others have a cost of 1.

In Sample Case #4, Reversort will necessarily perform 6 iterations, each of which will have a cost of at least 1, so there is no way the total cost can be as low as required.

Solution:

def create(n):
h=[]
for i in range(1,n+1):
h.append(i)
return h

def op2(n,c):
if c<n-1:
return[]
h=[]
a=0
b=1
for i in range(n-1,0,-1):
b+=1

if(a+b+i-1>=c):
e=c-a-i+1
h.append(e)
for k in range(i-1):
h.append(1)
a=c
break

a+=b
h.append(b)
if(a<c):
return []
return h

def op1(h,h1):
n=len(h1)
for i in range(n):
t=len(h)-(i+2)
s=t+h1[i]
h=h[:t]+list(reversed(h[t:s]))+h[s:]
return h

def op():
inp=input().split()
n=int(inp[0])
c=int(inp[1])
h=create(n)
h1=op2(n,c)
h=op1(h,h1)
ans=” “
if h1:
for item in h:
ans+=str(item)+” “
else:
ans=” IMPOSSIBLE”
print(“Case #”+str(i+1)+”: “+str(ans))

for i in range(int(input())):
op()