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. 