Page Contents

## Stack-Queue Sort Challenge SQSORT SOLUTION Code Chef

There are B blocks (numbered 1 through B) distributed in N containers (numbered 1 through N). For each valid i, the weight of the i-th block is Wi kilograms.

*Stack-Queue Sort Challenge SQSORT SOLUTION*For each container i, you should decide if it will be used like a stack or a queue. At any time, a container may contain any sequence of blocks (possibly the empty sequence); let’s denote the number of the j-th block (indexed from 1) in the i-th container by Ai,j.

A stack is a data structure that stores a sequence of integers (X1,X2,…,XM) and supports two types of instructions:

pop: Remove the last element of the sequence. After this instruction, the sequence becomes (X1,…,XM−1); it must be non-empty before this instruction. The return value of this instruction is XM.

*Stack-Queue Sort Challenge SQSORT SOLUTION*push a: Add an element a at the end of the sequence. After this instruction, the sequence becomes (X1,…,XM,a).

Similarly, a queue is a data structure that stores a sequence of integers (X1,X2,…,XM) and supports two types of instructions:

pop: Remove the first element of the sequence. After this instruction, the sequence becomes (X2,…,XM); it must be non-empty before this instruction. The return value of this instruction is X1.

push a: Add an element a at the end of the sequence. After this instruction, the sequence becomes (X1,…,XM,a).

For each valid i, it takes Ci⋅w nanoseconds to pop a block with weight w from the container i and Di⋅w nanoseconds to push a block with weight w to the container i.

*Stack-Queue Sort Challenge SQSORT SOLUTION*Using the given data structures, you may perform the following operation at most B2/2 times: choose two containers c1 and c2 (c1≠c2), pop a block from the c1-th container and then push this block to the c2-th container.

Your task is to sort all the blocks in a single container, i.e. after performing all operations, the sequence of blocks in some container must be (1,2,…,B). The time spent performing operations should be as small as possible.

Input

- The first line of the input contains two space-separated integers N and B.
- The second line contains N space-separated integers C1,C2,…,CN.
- The third line contains N space-separated integers D1,D2,…,DN.
- The fourth line contains B space-separated integers W1,W2,…,WB.
- The next N lines describe the initial distribution of blocks in containers. For each valid i, the i-th of these lines contains an integer M denoting the number of blocks which are initially in the i-th container, followed by a space and M space-separated integers Ai,1,Ai,2,…,Ai,M denoting the sequence of blocks which are initially in this container.

Output

- First, print a line containing a string with length N. For each valid i, the i-th character of this string should be either ‘S’ if the i-th sequence is used as a stack or ‘Q’ if it is used as a queue.
*Stack-Queue Sort Challenge SQSORT SOLUTION* - Then, print a line containing a single integer Q ― the number of operations to perform.
- Finally, print Q lines. Each of these lines should contain two space-separated integers c1 and c2 describing an operation that pops an element from the c1-th container and pushes it into the c2-th container.

Constraints

- 2≤N≤128
- B=1,024
- 1≤Ci,Di≤50 for each valid i
- 1≤Wi≤50 for each valid i
- 0≤M≤B
- 1≤Ai,j≤B for each valid i,j

Example Input

3 4

1 2 3

1 2 3

2 1 4 3

2 3 2

1 1

1 4

Example Output

QQS

4

1 3

1 2

4 2

4 2

Explanation

The first two containers are used as queues and the third container as a stack. The sequences change as follows:

Initially: (3,2),(1),(4).

After the first operation: (2),(1),(4,3).

After the second operation: (),(1,2),(4,3).

After the third operation: (),(1,2,3),(4).

After the fourth operation: (),(1,2,3,4),().

Test Generation

The source code used to generate test data can be downloaded here.

N can be 16, 32, 64 or 128.

All values of Ci, Di and Wi are chosen uniformly randomly and independently between 1 and 50 inclusive.

A permutation of the integers 1 through B is chosen uniformly randomly. The blocks are pushed to the containers one by one in this order.

*Stack-Queue Sort Challenge SQSORT SOLUTION*One of the following two initial distribution schemes is chosen:

All B blocks are pushed into the 1-st container.

For each block, a container into which it is pushed is chosen uniformly randomly and independently.

There are eight test files ― one for each possible value of N and distribution scheme.

Scoring

If your output is invalid (in particular if you attempt to pop an empty container), you do not sort the blocks in a single container or you use more than B2/2 operations, you will receive the Wrong Answer verdict.

Otherwise, the score of a test file is the number of nanoseconds spent performing your operations. The score of a submission is the sum of scores of all test files. Your goal is to minimise the score of your submission.

There are eight test files. During the contest, the displayed score will account for exactly four test files, i.e. your score reflects your submission’s performance on 50% (4/8) of the test files; However, if your program gets a non-AC verdict on any test file, your submission’s verdict will be non-AC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program’s scores over the other 4 test files.Stack-Queue Sort Challenge SQSORT SOLUTION

### January Long Challenge 2021

**Chef and Division 3 DIVTHREE SOLUTION Code Chef****Encoded String DECODEIT SOLUTION Code Chef****Point Of Impact BILLRD SOLUTION Code Chef****Fair Elections FAIRELCT SOLUTION Code Chef****Watching CPL WIPL SOLUTION Code Chef****Chef and Ants ANTSCHEF SOLUTION Code Chef****Blackjack BLKJK SOLUTION Code Chef****And-Or Game ORAND SOLUTION Code Chef****Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef****Expected Number of SCCs RCTEXSCC SOLUTION Code Chef****Curious Matrix CURMAT SOLUTION Code Chef****Cool Subsets COOLSBST SOLUTION Code Chef****Sequence Creation ARCRT SOLUTION Code Chef****Greedy Students GRDSTD SOLUTION Code Chef**

## 4 thoughts on “Stack-Queue Sort Challenge SQSORT SOLUTION Code Chef”