SQSORT - Editorial

PROBLEM LINK:

Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest

Author & Editorialist: Alei Reyes
Tester: Radoslav Dimitrov

DIFFICULTY:

Tie-break

PREREQUISITES:

Stacks, Queues

PROBLEM:

There are B blocks distributed in N containers, the weight of the i-th block is W_i. For each container you can decide if it will behave like a stack or a queue. In one operation you can pop a block from one container and push it to another container. The cost to pop a block of weight w from container i is C_i \cdot w, and the cost to push it to container j is D_j \cdot w. Find the minimum cost to sort all the blocks in one of the containers.

EXPLANATION:

There are many heuristics to decide for each container if it should be stack or queue e.g compare the longest increasing subsequence and the longest decreasing subsequence or check if the smallest element is nearest to the top or bottom. To sort the sequences we can empty one container, and divide the remaining containers in two groups S and T, where S contains the smallest k elements, then keep moving elements from S to T, until the k elements are at the top. Finally move the k elements to the empty container. Rinse and repeat until the initially empty container is filled with all the elements. For an small number of containers is possible to brute force all the possible initial assignments.

60 hours before the end of the contest rajathatr19’s solution was the best in div2 and used only queues. He sorted the containers in increasing order of C_i+D_i and emptied the first container by pushing all its elements to the second container. Then he pushed the blocks from 1 through N in order to the first container, to locate the i-th block he iterated over the blocks of each container, if the current block is y and y\neq i he moved it to container z=\lfloor y/x \rfloor \% m + 1, where x and m are parameters that were tunned, the idea is to uniformly assign it to one of the first m containers. x increases with the number of iterations to give priority to the containers with lowest C_i+D_i.

Meanwhile davi_bart’s solution was ranked sixth in div 1. He randomly assigned either stack or queue to each of the containers. To decide which container should contain the final sorted sequence, he estimated that for container x is necessary (at least) to first pop all its elements and then push all sorted elements back. So he chosed the container x that minimizes (w_1+w_2+...+w_B) \cdot D_x + Z \cdot C_x , where Z is the total weight of the blocks that are initially in container x. The strategy is to empty container x and then for each block b in order 1 through B search its container and move away all the elements that are at its top, to finally move b to container x. The problem is where should we move the blocks that are at the top of b? two priorities were used to choose the target container, one is the cost estimated by C_i+D_i and the other is that if we can keep the elements sorted then it is better to push small elements to stacks and bigger elements to queues. The algorithm runs very fast, so we can do some kind of random search by keeping assigning queues and stacks and take the best one we can find in the given time limit.

About SQSORT

This is one of the first problems I invented and couldn’t solve, I even remember that ~4+ years ago I sent an easier version of this problem to Errichto challenging him to solve it!

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
string itos(int v){
  if(v==0)return "0";   
  string ans="";
  for(;v!=0;v/=10)ans=string(1,'0'+(v%10))+ans;
  return ans;
}
char lastReadChar='?';
int rint(char nxt){
  char ch=getchar();
  int v=0;
  int sgn=1;
  if(ch=='-')sgn=-1;  
  else{
    assert('0'<=ch&&ch<='9');
    v=ch-'0';
  }
  while(true){
    ch=getchar();
    if('0'<=ch && ch<='9')v=v*10+ch-'0';
    else{
      lastReadChar=ch;
      if(nxt!='?')assert(ch==nxt);
      break;
    }
  }
  return v*sgn;
}
const int mx=1024;
int pos[mx+10];
deque<int>q[mx];
string s;
vector<pair<int,int> >ops;
uli C[mx],D[mx],W[mx];
uli score=0;
void move(int i,int j){
  ops.push_back({i,j});
  assert(!q[i].empty());
  int x=-1;
  if(s[i]=='S'){
    x=q[i].back();
    q[i].pop_back();
  }
  else{
    x=q[i].front();
    q[i].pop_front();
  }
  pos[x]=j;
  q[j].push_back(x);
  score+=W[x]*(C[i]+D[j]);
}
void solve(){
  int n=rint(' ');
  int b=rint('\n');
  assert(n==16 || n==32 || n==64 || n==128);
  assert(b==1024);
  for(int i=0;i<n;i++){
    C[i]=rint(i==n-1?'\n':' ');
    assert(1<=C[i] && C[i]<=50);
  }
  for(int i=0;i<n;i++){
    D[i]=rint(i==n-1?'\n':' ');
    assert(1<=D[i] && D[i]<=50);
  }
  for(int i=0;i<b;i++){
    W[i]=rint(i==b-1?'\n':' ');
    assert(1<=W[i] && W[i]<=50);
  }

  for(int i=0;i<b;i++)pos[i]=-1;
  for(int i=0;i<n;i++)q[i].clear();

  for(int i=0;i<n;i++){
    int m=rint('?');
    if(m==0)assert(lastReadChar=='\n');
    else assert(lastReadChar==' ');
    assert(0<=m && m<=b);
    for(int j=0;j<m;j++){
      int x=rint(j==m-1?'\n':' ');
      assert(1<=x&&x<=mx);
      --x;
      assert(pos[x]==-1);
      pos[x]=i;
      q[i].push_back(x);
    }
  }
  for(int i=0;i<mx;i++)assert(pos[i]!=-1);
  s.resize(n);
  for(int i=0;i<n;i++){
    if(rand()%2)s[i]='Q';
    else s[i]='S';
  }
  int trg=0;
  for(int i=0;i<n;i++)if(q[i].size()<q[trg].size())trg=i;
  s[trg]='S';

  ops.clear();

  for(int at=0,it=0;!q[trg].empty() && it<2000;at=(at+1)%n,it++){
    if(at==trg)at=(at+1)%n;
    move(trg,at);
  }  
  for(int v=0;v<mx;v++){
    int i=pos[v];
    for(int it=0;it<2000;it++){
      if(s[i]=='Q' && q[i].front()==v)break;
      if(s[i]=='S' && q[i].back()==v)break;
      int j=i;
      while(j==i || j==trg) j=rand()%n; 
      move(i,j);
    }
    move(i,trg);
  }  
  printf("%s\n",s.c_str());
  assert(ops.size()*2<1024*1024);
  printf("%d\n",(int)ops.size());
  for(auto p:ops)printf("%d %d\n",p.first+1,p.second+1);
  assert(getchar()==EOF);
}
int main(){
  srand(time(NULL));
  for(int tt=0;tt<8;tt++){
    string rd="secret/"+itos(tt)+".in";
    string wt="secret/"+itos(tt)+".out";
    auto flr=freopen(rd.c_str(),"r",stdin);
    auto flw=freopen(wt.c_str(),"w",stdout);
    score=0;
    solve();
    uli top =50*1024*1024;
    assert(score<=top);
    uli dif=top-score;
    cerr<<tt<<"=>"<<score<<" diff="<<dif<<endl;

    fclose(flr);
    fclose(flw);
  }

}
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back

using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int K = 1 << 10;

int n, b;
int C[MAXN], D[MAXN], W[MAXN];
list<int> li[MAXN];
int pos[MAXN];

void read() {
  cin >> n >> b;
  for(int i = 0; i < n; i++) cin >> C[i];
  for(int j = 0; j < n; j++) cin >> D[j];
  for(int i = 0; i < b; i++) cin >> W[i];

  for(int i = 0; i < n; i++) {
    int cnt;
    cin >> cnt;
    while(cnt--) {
      int v;
      cin >> v;
      pos[v - 1] = i;
      li[i].pb(v - 1);
    }
  }
}

int64_t best_score = (int64_t)1e18, current_score;
vector<pair<int, int>> best, current;
string best_tp, tp;

void compare_best() {
  if(chkmin(best_score, current_score)) {
    best = current;
    best_tp = tp;
  }
}

void op(int i,int j) {
  current.pb({i, j});
  if(tp[i] == 'S') {
    int x = li[i].back();
    pos[x] = j;
    li[j].pb(x);
    li[i].pop_back();
    current_score += W[x] * 1ll * (C[i] + D[j]);
  } else {
    int x = li[i].front();
    pos[x] = j;
    li[j].pb(x);
    li[i].pop_front();
    current_score += W[x] * 1ll * (C[i] + D[j]);
  }
}

mt19937 mt(42);

int get_other(const vector<int> &banned) {
  int p = mt() % n;
  while(true) {
    bool ok = true;
    for(int x: banned) {
      if(x == p) {
        ok = false;
        break;
      }
    }
    
    if(ok) return p;
    p = mt() % n;
  }
}

void solve_random() {
  tp.resize(n);
  for(int i = 0; i < n; i++) {
    tp[i] = (mt() % 2) ? 'S' : 'Q';
  }

  int en = mt() % n;
  tp[en] = 'S';
  current_score = 0;
  current.clear();

  while(!li[en].empty()) {
    int oth = get_other({en});
    op(en, oth);
  }

  for(int v = 0; v < K; v++) {
    int i = pos[v];
    assert(i != en);

    while(!(tp[i] =='Q' && li[i].front() == v) && !(tp[i] =='S' && li[i].back() == v)) op(i, get_other({i, en}));
    op(i, en);
  }

  compare_best();
}

void solve() {
  for(int iters = 0; iters < 1; iters++) {
    solve_random();
  }

  cout << best_tp << endl;
  cout << SZ(best) << endl;
  for(auto it: best) {
    cout << it.first + 1 << " " << it.second + 1 << endl;
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  read();
  solve();
  return 0;
}

davi_bart’s solution
rajathatr19’s solution

VIDEO EDITORIAL:

1 Like

@alei I followed a similar strategy as @rajathatr19

Sorted the containers on basis of C[i] + D[i]

I divided the containers into 3 parts:

  1. 2 containers as a working set. Transferring blocks from one to another. Choose the best 2 containers for this.

  2. P containers as the buffer for large values that are not relevant in the current iterations. Chose the next best P containers for this.

  3. K = N - P - 2 as the modulus.

If (i % K) = X, block i goes to the container X, after for all j < i and (j % K) == X goes into that container.

Suppose P = 3.

Then we divide 1024 into P + 1 equal parts. In this case this is 256.

So all elements > 256 go into the buffer container and are not wasted in the iterations for elements < 256.

Then I iterated over all values of P to find the optimal value. Surprisingly, it turned out that P < 8 for all the inputs in this case.

Here’s my solution: CodeChef: Practical coding for everyone

@alei do you create problems and think about it can be solved or not, want to know more about your process XD such an inspiring thing to do

There are many ways of inventing problems. I guess first you have to solve a reasonable amount of problems, then the problems usually arise naturally.

I’ll write a post about problem invention in the future.

1 Like

There are many variants of this problem previously discussed in a lot of research papers starting from Knuth.

Although my approach was nowhere close to the best (3rd in Div3) I wrote a blog post on how I approached the problem: https://github.com/MadaraUchiha-314/blog/blob/master/SQSORT.md