PROBLEM LINK:
Setter: Mladen Puzic
Tester: Michael Nematollahi
Editorialist: Taranpreet Singh
DIFFICULTY:
PREREQUISITES:
Observations, Merge Sort or BIT/Segment Tree.
PROBLEM:
Given a permutation of first N natural numbers and an integer D, can you sort the permutation, if you are allowed to swap any pair of elements at position i and j if |P_i - P_j| = D holds. If you can sort the permutation, also find the minimum number of swaps required to do so.
EXPLANATION
For simplicity, let us transform our problem.
Let us generate another permutation Q such that Q_{P_i} = i. This way, Allowed swaps |P_i - P_j| = D translates to swaps allowed in permutation Q such that |i-j| = D where i and j are the positions of swap in Q. Since after applying all operations, we aim to get P_i = i, which means Q_i = i.
This solution has two parts, determining whether it is possible to sort the permutation, and counting the minimum number of swaps needed.
Whether it is possible to sort the array:
Since we are allowed to swap any pair of elements at positions i and j such that |i-j| = D, we can see that we can decompose the permutation D lists, such that in each list, we are allowed to swap adjacent elements.
For example, if Q = [4,3,1,5,2] and D = 3, we have three lists [4, 5], [3,2] and [1]. We can see, that we are allowed to swap adjacent elements in these lists.
Let us sort these lists. (That’s the best we can do, isn’t it?) and let us generate the permutation from these sorted lists. In our example, the sorted lists become [4, 5], [2,3] and [1]. These lists generate permutation [4,2,1,5,3]. Since this is not sorted, we cannot sort the permutation using specified swaps. Hence, we now have a way to check if a permutation can be sorted.
Another example is Q = [4,5,3,1,2], the lists generated are [4,1], [5,2] and [3] which when sorted, leads to lists [1,4], [2,5] and [3] which correspond to sorted permutation [1,2,3,4,5], hence permutation [4,5,3,1,2] can be sorted.
Counting number of swaps needed:
If the permutation can be sorted using above, all we need to know is the summation of number of swaps to sort each list, if we are allowed only to swap adjacent elements from the lists. This is same as the number of inversions in an array, since
- each swap between adjacent element changes number of inversions in array by exactly one.
- Sorted array is the array with no inversions.
There are a couple of ways to count inversions, this article explains using Merge Sort, using BIT/Segment Tree
We can just compute number of inversions for each list and print their sum.
An interesting problem to try on inversions is here.
TIME COMPLEXITY
Time complexity is O(N*log(N/D)) per test case.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 200010
int bit[MAXN];
int query(int idx) {
int rez = 0;
while(idx) {
rez += bit[idx];
idx -= idx&-idx;
}
return rez;
}
void update(int idx, int val) {
while(idx < MAXN) {
bit[idx] += val;
idx += idx&-idx;
}
}
vector<int> els;
int d[MAXN], p[MAXN];
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
int T; cin >> T;
while(T--) {
int N, D; cin >> N >> D;
PRINT(N);
PRINT(D);
bool possible = 1;
for(int i = 1; i <= N; i++) cin >> d[i];
for(int i = 1; i <= N; i++) p[d[i]] = i; ///calculate inverse permutation
D = min(D, N);
long long rez = 0;
for(int i = 1; i <= D; i++) {
els.clear();
for(int j = i; j <= N; j += D) {
els.push_back(p[j]);
}
sort(els.begin(), els.end());
for(int j = i; j <= N; j += D) { ///we check whether all needed positions are available
if(j != els[(j-i)/D]) {
possible = 0;
rez = -1;
break;
}
}
if(!possible) break;
for(int j = i; j <= N; j += D) { ///here we use Fenwick tree to calculate number of inversions for each modulo D
update(p[j], +1);
rez += query(MAXN-1) - query(p[j]);
}
for(int j = i; j <= N; j += D) {
update(p[j], -1); ///restoring the Fenwick tree to original state
}
}
cout << rez << endl;
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
const int MAXN = 2e5 + 10;
int n, d, p[MAXN], fen[MAXN];
void add(int v, int val){for (v++; v<MAXN; v+=v&-v) fen[v] += val;}
int get(int v){
int ret = 0;
for (; v; v-=v&-v)
ret += fen[v];
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int te; cin >> te;
while (te--){
cin >> n >> d;
bool failed = false;
for (int i = 0; i < n; i++) {
cin >> p[i], p[i]--;
if (p[i]%d != i%d)
failed = true;
}
if (failed)
cout << "-1\n";
else{
ll ans = 0;
for (int beg = 0; beg < d; beg++) {
for (int i = beg; i < n; i += d) {
ans += (i/d) - get(p[i]);
add(p[i], 1);
}
for (int i = beg; i < n; i += d)
add(p[i], -1);
}
cout << ans << "\n";
}
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class DPERM{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), d = ni();
int[] p = new int[n];
for(int i = 0; i< n; i++)p[i] = ni()-1;
int[][] g = new int[d][];
for(int i = 0; i< d; i++)g[i] = new int[(n+d-i-1)/d];
for(int i = 0; i< n; i++)g[p[i]%d][p[i]/d] = i;
for(int i = 0; i< d; i++)Arrays.sort(g[i]);
boolean yes = true;
for(int i = 0; i< n; i++)yes &= g[i%d][i/d] == i;
if(yes){
for(int i = 0; i< n; i++)g[p[i]%d][p[i]/d] = i;
long ans = 0;
for(int i = 0; i< d; i++)ans += sort(g[i]);
pn(ans/2);
}else pn(-1);
}
//Sorts the array, and returns the number of inversions using merge sort
long sort(int[] a){
if(a.length==1)return 0;
int n = a.length;
int[] left = Arrays.copyOfRange(a, 0, n/2), right = Arrays.copyOfRange(a, n/2, n);
long ans = 0;
ans += sort(left);
ans += sort(right);
int j = 0, k = 0;
for(int i = 0; i< n; i++){
if(j == left.length)a[i] = right[k++];
else if(k == right.length){
ans += k;
a[i] = left[j++];
}else{
if(left[j] < right[k]){
ans += k;
a[i] = left[j++];
}else{
ans += left.length-j;
a[i] = right[k++];
}
}
}
return ans;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new DPERM().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, if you want to. (even if its same 
) . Suggestions are welcomed as always had been. 
