Stack-Queue Sort Challenge SQSORT SOLUTION Code Chef

Stack-Queue Sort Challenge SQSORT SOLUTION Code Chef

There are BB blocks (numbered 11 through BB) distributed in NN containers (numbered 11 through NN). For each valid ii, the weight of the ii-th block is WiWi kilograms.

For each container ii, 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 jj-th block (indexed from 11) in the ii-th container by Ai,jAi,j.

stack is a data structure that stores a sequence of integers (X1,X2,…,XM)(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)(X1,…,XM−1); it must be non-empty before this instruction. The return value of this instruction is XMXM.
  • push a: Add an element aa at the end of the sequence. After this instruction, the sequence becomes (X1,…,XM,a)(X1,…,XM,a).

Similarly, a queue is a data structure that stores a sequence of integers (X1,X2,…,XM)(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)(X2,…,XM); it must be non-empty before this instruction. The return value of this instruction is X1X1.
  • push a: Add an element aa at the end of the sequence. After this instruction, the sequence becomes (X1,…,XM,a)(X1,…,XM,a).

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

Using the given data structures, you may perform the following operation at most B2/2B2/2 times: choose two containers c1c1 and c2c2 (c1≠c2c1≠c2), pop a block from the c1c1-th container and then push this block to the c2c2-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)(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 NN and BB.
  • The second line contains NN space-separated integers C1,C2,…,CNC1,C2,…,CN.
  • The third line contains NN space-separated integers D1,D2,…,DND1,D2,…,DN.
  • The fourth line contains BB space-separated integers W1,W2,…,WBW1,W2,…,WB.
  • The next NN lines describe the initial distribution of blocks in containers. For each valid ii, the ii-th of these lines contains an integer MM denoting the number of blocks which are initially in the ii-th container, followed by a space and MM space-separated integers Ai,1,Ai,2,…,Ai,MAi,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 NN. For each valid ii, the ii-th character of this string should be either ‘S’ if the ii-th sequence is used as a stack or ‘Q’ if it is used as a queue.
  • Then, print a line containing a single integer QQ ― the number of operations to perform.
  • Finally, print QQ lines. Each of these lines should contain two space-separated integers c1c1 and c2c2 describing an operation that pops an element from the c1c1-th container and pushes it into the c2c2-th container.

Constraints

  • 2≤N≤1282≤N≤128
  • B=1,024B=1,024
  • 1≤Ci,Di≤501≤Ci,Di≤50 for each valid ii
  • 1≤Wi≤501≤Wi≤50 for each valid ii
  • 0≤M≤B0≤M≤B
  • 1≤Ai,j≤B1≤Ai,j≤B for each valid i,ji,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)(3,2),(1),(4).
  • After the first operation: (2),(1),(4,3)(2),(1),(4,3).
  • After the second operation: (),(1,2),(4,3)(),(1,2),(4,3).
  • After the third operation: (),(1,2,3),(4)(),(1,2,3),(4).
  • After the fourth operation: (),(1,2,3,4),()(),(1,2,3,4),().

Test Generation

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

  • NN can be 1616, 3232, 6464 or 128128.
  • All values of CiCi, DiDi and WiWi are chosen uniformly randomly and independently between 11 and 5050 inclusive.
  • A permutation of the integers 11 through BB is chosen uniformly randomly. The blocks are pushed to the containers one by one in this order.
  • One of the following two initial distribution schemes is chosen:
    • All BB blocks are pushed into the 11-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 NN 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/2B2/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.

Solution

Program Python:

#!/usr/bin/env python3

import sys

def compute(N, B, C, D, W, A):
    def perform_op(c1, c2): # pop and push, and return nanoseconds
        assert(c1 != c2)
        x, A[c1] = A[c1][0], A[c1][1:]
        A[c2].append(x)
        ops.append((c1, c2))
        return 0

    # N is 16, 32, 64 or 128 !
    # either all blocks are in the 1st container, or they're spread uniformly among them.
    t, ops = 0, []

    if  A[2]:
        for i in range(2, N + 1):
            while A[i]:
                t += perform_op(i, 1)
    # now all elements are in the first container

    # 1st: all elements,        2nd: buffer for 1st container
    # 3rd: all elements <= 128, 4th: buffer for 3rd container

    for j in range(8):
        while A[1+j%2]:
            if  128*j+1 <= A[1+j%2][0] <= 128*j+128: t += perform_op(1+j%2, 3)
            else:                                    t += perform_op(1+j%2, 2-j%2)
        for k in range(16*j, 16*j + 16):
            while A[3+k%2]:
                if  8*k+1 <= A[3+k%2][0] <= 8*k+8:   t += perform_op(3+k%2, 4-8*k + A[3+k%2][0])
                else:                                t += perform_op(3+k%2, 4-k%2)
            for i in range(1, 8 + 1):
                t += perform_op(4 + i, N)

    assert(A[N] == list(range(1, 1024 + 1)))
    assert(len(ops) <= B**2 // 2)

    print('score = %s' % t, file=sys.stderr)
    return ops

def main():
    N, B = [int(x) for x in input().strip().split()[:2]]
    C    = [int(x) for x in input().strip().split()[:N]]
    D    = [int(x) for x in input().strip().split()[:N]]
    W    = [int(x) for x in input().strip().split()[:B]]
    A    = [None]
    for _ in range(N):
        X = [int(x) for x in input().strip().split()]
        M, Ai = X[0], X[1:]
        A.append(Ai)
    ANS = compute(N, B, C, D, W, A)
    print('Q' * N)
    print(len(ANS))
    for c1, c2 in ANS: print(c1, c2)

if  __name__ == '__main__':
    main()

Program C++:

#include<bits/stdc++.h>

#define pb push_back
#define ff first

#define ss second

#define mpr make_pair

using namespace std;


const int N=1e4;

int n,b;

int c[N],d[N],w[N],inp[N];

int main()

{

    cin>>n>>b;

    for(int i=0;i<n;i++)cin>>c[i];

    for(int i=0;i<n;i++)cin>>d[i];

    for(int i=0;i<b;i++)cin>>w[i];

    unordered_map<int,deque<int>>mp;

    unordered_map<int,int>h;

    for(int i=0;i<n;i++){

        cin>>inp[i];

        for(int j=0;j<inp[i];j++){

            int y;cin>>y;

            mp[i+1].pb(y);

            h[y]=i+1;

        }

    }

    vector<pair<int,int>>op;

    string s;for(int i=0;i<n;i++)s+='S';

    int one=h[1];

    s[one-1]='Q';

    cout<<s<<endl;

    int buf1=1,buf2=2;

    if(one==1){

        buf1=3;

    }

    if(one==2){

        buf2=3;

    }

    while(mp[one].front()!=1){

        int tmp=mp[one].front();

        mp[one].pop_front();

        h[tmp]=buf1;

        mp[buf1].pb(tmp);

        op.pb(mpr(one,buf1));

    }

    int tmp=1;

    mp[one].pop_front();

    h[tmp]=buf2;

    mp[buf2].pb(tmp);

    op.pb(mpr(one,buf2));

    while(mp[one].size()!=0){

        tmp=mp[one].front();

        mp[one].pop_front();

        h[tmp]=buf1;

        mp[buf1].pb(tmp);

        op.pb(mpr(one,buf1));

    }

    tmp=1;

    mp[h[1]].pop_back();

    mp[one].pb(1);

    op.pb(mpr(buf2,one));

    for(int i=2;i<=b;i++){

        sort(inp,inp+N);

        while(mp[h[i]].back()!=i){

            tmp=mp[h[i]].back();

            mp[h[i]].pop_back();

            int buf=-1,val=INT_MAX;

            for(int j=1;j<=n;j++){

                if(j==one||j==h[i])

                    continue;

                if(mp[j].size()==0){

                    buf=j;

                    break;

                }

                int bk=mp[j].back();

                if(bk>tmp&&val>bk){

                    val=bk;

                    buf=j;

                }

            }

            if(buf==-1){

                for(int j=1;j<=n;j++){

                    if(j==one||j==h[i])

                        continue;

                    if(val>mp[j].size()){

                        val=mp[j].size();

                        buf=j;

                    }

                }

            }

            op.pb(mpr(h[i],buf));

            mp[buf].pb(tmp);

            h[tmp]=buf;

        }

        op.pb(mpr(h[i],one));

        tmp=mp[h[i]].back();

        mp[h[i]].pop_back();

        mp[one].pb(tmp);

        h[tmp]=one;

    }

    cout<<op.size()<<endl;

    for(int i=0;i<op.size();i++){

        cout<<op[i].ff<<" "<<op[i].ss<<endl;

    }


}

January Long Challenge 2021

Leave a Comment