DPERM - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

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 :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

5 Likes

I used Merge Sort but it got me SIGSEGV everytime.

1 Like

Someone can tell me why I pointed out in my commit to the contest that there was a problem with the Chinese translation of this problem, and the commit was deleted by the administrator, and the error has not been corrected yet.
The Chinese problem statement said that the absolute value was not more than D, so I was thinking about Example 2. After a while I went to see the English problem and found this error.
image

3 Likes

I tried this problem by evaluating all the cycles and in each cycle absolute difference of two nodes should be D. if this condition is satisfied ans will be sum of (each cycle length-1).
I don’t know where this approach fails,can someone please help?
https://www.codechef.com/viewsolution/25003115

1 Like

5 1
5 4 3 2 1
This is solvable.
The answer will be 10. but your is -1

4 Likes

Thanks. :slight_smile:

1 Like

Can someone explain me this part please!
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";
	}
1 Like

Idk why but your editorials seems better than before and excellent :slight_smile:

4 Likes

Nice Editorial mate. Thanks! :slight_smile:

2 Likes

How does the transforming the problem statement gurantees that the number of swaps required (final answer) will remain the same ?

4 Likes

it can also be done using simple a vector and a special set type data structure which can handle order query like number of elements strictly less than x in the set or find kth order element in O(logn) hence getting over time complexity same as in editorial.
here is my solution:-https://www.codechef.com/viewsolution/24991404 (please ignore that blank if statement i forgot to delete it)
link for that data structure used-https://codeforces.com/blog/entry/11080
I think this is the shortest solution you will find :stuck_out_tongue_winking_eye:

2 Likes

How to sort
5 1
5 4 3 2 1
Can you pls write all steps?

For the test case
1
3 1
8 11 9
the answer to this should be -1 right?
But the tester’s solution shows the answer to be 1. Why?
[https://www.codechef.com/viewsolution/24987185](http://this link) show the answer to be 3.

Your test case is invalid. It should be a permutation of 1 to N. It can’t be 8 11 9

5 4 3 2 1 ( 0th step)
4 5 3 2 1 (1)
3 5 4 2 1 (2)
…
1 5 4 3 2 (4)
1 4 5 3 2 (5)
…
1 2 5 4 3 (7)
…
1 2 3 5 4 (9)
1 2 3 4 5 (10)

1 Like

any idea what can I do in order to fix the TLE in my solution for 2 subtasks (1,3) ?
(i have used sets to calculate the inversion count)
https://www.codechef.com/viewsolution/25019402

Can you please tell me where is it written in the question that P1 to Pn numbers should be from 1 to N only?

It is mentioned P_i lies between 1 and N (both inclusive), and P_1,P_2,…,P_N are pairwise distinct…that leads to P being a permutation from 1 to N.

5 Likes

Obviously in problem statement.
1 \leq P_i \leq N for each valid i
P_1,P_2,…,P_N are pairwise distinct

3 Likes

How did we both reply at the same time?
xd

1 Like