SHUFFLE - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Shahadat Hossain Shahin
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

Sorting, and basic implementation.

PROBLEM:

Given an array, A consisting of N integers and an integer K, determine whether you can sort the array using the following operation any number of times.
Swap A_i and A_{i+K} for any valid i.

QUICK EXPLANATION

  • We can move some element from position p to position q if and only if |p-q| is divisible by K
  • Hence, we can divide the given array into K list, i-th list having all elements at positions p such that p \bmod K is i. It’s easy to see that we can swap any pair of elements within the list.
  • After sorting each list, we just merge the lists back in the same way we had divided. p-th position shall have an element from list i if and only if p \bmod K is i.
  • If the resulting array is sorted, we can sort, otherwise, there’s nothing more we can do to sort.

EXPLANATION

Lemma: We can move element at position p to position q if and only if |p-q| is divisible by K
Proof: Consider initial position p such that p \bmod K is x. By doing a swap, we move this element to position p+K. But (p+K) \bmod K is x. We are unable to move this element to any position q such that q \bmod K \neq x which implies that We can move element at position p to position q if and only if |p-q| is divisible by K

Giving a visualization, consider an example

5 2
3 4 5 2 1

In the above case, we can swap any pair of elements among positions 0, 2 and 4, and among any pair of positions withing 1 and 3 through some sequence of swaps.

So, we can divide these elements into K lists, such that within each list, we can swap any pair of elements. This happens when we put all positions p in list numbered x such that p \bmod K is x, as we did in the above example.

Now, it’s optimal to sort each list, as the first position in i-th list corresponds to i-th position in the original array, second position in i-th list corresponds to K+i-th position in the original array and so on.

Let’s merge back the lists.
Back to our example, we had lists

3 5 1
4 2

After sorting, we get

1 3 5
2 4

We need to merge the lists in a way that if the element at p-th position is added from i-th list, we must add the smallest element from i-th list and remove this element from the list.

Merging back gives us

1 2 3 4 5

which is sorted, hence we can sort. If we had got an unsorted array, we can be sure that we cannot sort the array at all, since we have already considered all optimal possible swaps.

TIME COMPLEXITY

The time complexity is O(N+K*log(N/K) or O(N*log(N)) per test case depending upon the implementation.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>

using namespace std;

const int MAX = 100005;

int a[MAX], b[MAX];

int main() {
	// freopen("1.in", "r", stdin); 
	// freopen("1.out", "w", stdout);

	int T;
	cin >> T;
	for(int t=1;t<=T;t++) {
	    int n, k;
	    cin >> n >> k;
	    for(int i=1;i<=n;i++) {
	        cin >> a[i]; b[i] = a[i];
	    }
	    sort(b + 1, b + n + 1);
	    string ans = "yes";
	    for(int i=1;i<=k;i++) {
	        vector <int> p, q;
	        for(int j=i;j<=n;j+=k) {
	            p.push_back(a[j]);
	            q.push_back(b[j]);
	        }
	        sort(p.begin(), p.end());
	        if(p != q) ans = "no";
	    }
	    cout << ans << '\n';
	}
	return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std; 
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
 
 
vector<vi> vec(123456); 
int a[123456];
signed main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		int i,j;
		rep(i,k){
			vec[i].clear();
		}
		rep(i,n){
			cin>>a[i];
			vec[i%k].pb(a[i]);
		}
		rep(i,k){
			sort(all(vec[i]));
			rep(j,vec[i].size()){
				a[j*k+i]=vec[i][j];
			}
		}
		int flag=1;
		rep(i,n-1){
			if(a[i]>a[i+1]){
				flag=0;
				break;
			}
		}
		if(flag){
			cout<<"yes"<<endl;
		}
		else{
			cout<<"no"<<endl;
		}
	}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class SHUFFLE{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni(), k = ni();
	    int[][] list = new int[k][];
	    for(int i = 0; i< k; i++)list[i] = new int[1+(n-i-1)/k];
	    for(int i = 0; i< n; i++){
	        list[i%k][i/k] = ni();
	    }
	    for(int i = 0; i< k; i++)Arrays.sort(list[i]);
	    boolean sorted = true;
	    for(int i = 0; i< n-1; i++)sorted &= list[i%k][i/k] <= list[(i+1)%k][(i+1)/k];
	    pn(sorted?"yes":"no");
	}
	//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 SHUFFLE().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. Suggestions are welcomed as always. :slight_smile:

11 Likes

Link I think test cases were weak. My wrong solution is getting accepted.

6 Likes

that was easy but such a nice a problem

2 Likes

To move from p to q, |p-q| must divisible by k. So if we sort the array and finds the q for all element and check whether |p-q| is divisible by k , if all the element satisfies this condition output yes else no.
Is my logic is wrong?

#include <bits/stdc++.h>
using namespace std;

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

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--)
    {
        int k, n;
        cin >> n >> k;
        int flag = 1;
        vector<pair<int, int>> seq(n);
        for (int i = 0; i < n; ++i)
        {
            cin >> seq[i].first;
            seq[i].second = i;// storing the initial position :- q
        }

        sort(seq.begin(), seq.end());

        for (int i = 0; i < n; ++i)
        {
            if ( (abs(i - seq[i].second)) % k != 0) // checking the condition
            {
                flag = 0;
                break;
            }
        }
        if (flag) cout << "yes"<< "\n";
        else cout << "no"<< "\n";
    }
    return 0;
}

Its is observable that we can directly swap 2 elements Ai and Aj (i<j) if j is at some integral multiple of k position from i. So, starting at index i then traversing through all the possible positions of j keeping a record of the minimum value obtained from j’s ( and if this min value is less than a[i] ) swapping a[i] and the minimum value. After doing this for possible values of i.
If we get a sorted array then yes else no .
I thought i ll get a TLE over this but didn’t . Can somebody point out why it didnt get a TLE. [https://www.codechef.com/viewsolution/32255561]

2 Likes

I used a form of modified bubble sort for this question. But it barely passed the test cases in pypy https://www.codechef.com/viewsolution/32243642
When i ran the same code in Python3 it gave TLE as was expected.
https://www.codechef.com/viewsolution/32277303
I suppose it would have done slightly better in C++ in terms of time. But this anomaly should not have happened between different languages. I think the tester should have looked into it.

I do not know where i made mistake but it gives only partially correct answer.
https://pastebin.com/7CGyDzfc

1 Like

Your code doesn’t seem to handle duplicates. I did the same approach and got only 50 points.

1 Like

why are you initializing your loop from n-k+1 while checking for flag ?

your solution is giving a WA on sample test case. how did it get accepted ?

What is the O(nlong(n)) implementation ?

Yes, that’s why i wrote in comment wrong solution. Actually my approach is whole wrong. It shouldn’t have been accepted. One of the participant has done the same during contest, so I was just checking it by submitting it myself.

why my solution is giving partial correct answer

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
int t{};
cin>>t;
while(t–)
{
ll n{},k{},i{},x{},y{},z{};
cin>>n>>k;
vector v1(n,0);
for(i=0;i<n;++i)
scanf("%lld",&v1.at(i));
vector v2(n,0);
v2=v1;
sort(v1.begin(),v1.end());
for(i=0;i<n;++i)
{
vector::iterator j=find(v2.begin(),v2.end(),v1.at(i));
x=distance(v2.begin(),j);
if(abs((x-i))%k!=0)
{
y=1;
break;
}
}
if(y==0)
cout<<“yes”<<endl;
else
cout<<“no”<<endl;
}
}

i used the same approach and got partial correct answer

Bro my approach—> https://pastebin.com/LWzMs7Gp
I handle Duplicates all done but given WA for part-2

can some one explain me why this solution is wrong…i have taken a 2d ‘f’ vector of k rows then sorted each row and merged them back to another vector ‘g’…and then checked if g is sorted or not…
and my solution is getting wrong answer for both all cases.

#include
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
int n,k;
cin>>n>>k;
vector<vector > f(k);
for(int i=0;i<n;i++)
{
int x;
cin>>x;
f[i%k].push_back(x);
}
for(int i=0;i<k;i++)
{
sort(f[i].begin(),f[i].end());
}
vector g;
int count=0;
for(int i=0;i<ceil(n/k);i++)
{
for(int j=0;j<k && count<n;j++,count++)
{
int x=f[j][i];
g.push_back(x);
}
}
count=0;
for(int i=0;i<n-1;i++)
{
if(g[i]>g[i+1])
{
cout<<“no”<<endl;
count++;
break;
}
}
if(count==0)
{
cout<<“yes”<<endl;
}
}
return 0;
}

Yeah, even I feel the test cases are weak. I have seen some of the solutions with time complexity O(n^2). This time complexity indicates that we cannot solve the question with given constraints ( t<=100 and n<=10^5) with in 1 second. Problem setters and testers should have looked into it.
I agree with you @rajankur.

3 Likes

Why does the code fail, when there are duplicates

this is my solution but it gives tle for both test cases can someone please point out the mistake

https://www.codechef.com/viewsolution/32290926

https://www.codechef.com/viewsolution/32291616

while this is my other solution and working fine but having the same approach
can someone explain why does it happen?