Codeforces #276 (Div. 1) Problem C: Strange Sorting

Problem Statement:
484C - Strange Sorting

Solution:
This is an awesome problem. Good stuff.
The first thing to notice is that that the length of string n and the number of queries is bounded by \(nm \leq 10^6\). What happens if \(n = 10^6\)? In this case for \(K\) large enough, the running time of pure simulation of the operations will take too much time.

The great idea that is suggested by the problem setter (Codeforces handle: Bugman. You are awesome) is to think of each sorting operations as permutations on the string, which it indeed is. The good thing about permutation is that we can represent it in an NxN elementary matrix (which only has one "1" in each rows and each columns, and "0" everywhere else). Let's call this permutation matrix as P. Then each shuffling operations can be seen as matrix multiplications of S and \(P^n\). So if we can find a matrix P to represent the d-sorting on S at different substring of S, we can proceed with doing a fast matrix multiplication of \(P^n\) which takes \(O(N\lg{n})\), which also marks the bound for the running time of each query (Btw, the matrix multiplication itself in general is \(O(N^3)\), but since the matrices multiplied are elementary, we only need \(O(N)\) time, and it is quite fun to figure out how to do it :D).



We can quite easily represent d-sorting of S[0..k-1] as a permutation matrix, but what about the fact that each time we have to perform the d-sorting on the consecutive substring S[1..k], S[2..k+1], and so on? We will end up with \(O(N)\) permutation matrices which are very memory consuming, and in the end defeat the purpose for the fast matrix multiplication to work. Here is another creative idea: instead of having to perform d-sorting at different substring, we can do a left rotation of the whole string by one character instead before performing a d-sorting on the next substring. This rotation can also be represented in the form of permutation matrix. Hence multiplying these two permutation matrices will give us the desired P.

Then the rest is a matter of implementation to get the idea working :D

/*
UPSOLVING:
Codeforces #276 Div. 1 Problem C
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

string str;
int P[1000003];
int R[1000003];
int T[1000003];
int onP[1000003];
int onT[1000003];
int onR[1000003];
int ans[1000003];
int res[1000003];
int D, K, N;

void rec_mult(int n){
    if(n==0) return;
    if(n%2==0){
        for(int i=0;i<N;++i){
            onP[P[i]] = i;
        }
        for(int i=0;i<N;++i){
            P[onP[onP[i]]] = i;
        }
        return rec_mult(n/2);
    }else{
        for(int i=0;i<N;++i){
            onR[R[i]] = i;
            onP[P[i]] = i;
        }
        for(int i=0;i<N;++i){
            R[onP[onR[i]]] = i;
        }
        return rec_mult(n-1);
    }
}

void solve(){
    for(int i=0;i<N;++i){
        R[i] = i;
        P[i] = i;
        T[i] = i+1;
    }
    T[N-1] = 0;
    int pos = 0;
    for(int i=0;i<D;++i){
        for(int j=i;j<K;j+=D){
            P[pos++] = j;
        }
    }
    for(int i=0;i<N;++i){
        onP[P[i]] = i;
        onT[T[i]] = i;
    }
    for(int i=0;i<N;++i){
        P[onT[onP[i]]] = i;
    }

    rec_mult(N-K+1);
    int start = N - (N-K+1); 
    pos = 0;
    for(int i=start;;i=(i+1)%N,++pos){
        if(pos!=0 && i==start) break;
        res[pos] = R[i];
    }
    for(int i=0;i<N;++i){
        onR[res[i]] = i;
        onT[ans[i]] = i;
    }
    for(int i=0;i<N;++i){
        ans[onR[onT[i]]] = i;
    }
    for(int i=0;i<N;++i){
        printf("%c", str[ans[i]]);
    }
    printf("\n");
}

int main(){
    int qq;
    cin >> str;
    cin >> qq;
    N = str.size();
    for(int i=0;i<N;++i){
        ans[i] = i;
    }
    while(qq--){
        scanf("%d %d", &K, &D);
        solve();
    }
    return 0;
}