SHUFFLE - Editorial

editorial
, , , ,
45

declared “int” and not long long

Because int datatype can hold upto 2*10^9 value (i.e. 2^31 = 2147483648).

1 Like
46

your solution outputs no for
4 2
1 4 4 2
shouldn’t it be yes??

47

Is my approach is correct. CodeChef: Practical coding for everyone

48

Can anyone please find what’s wrong in my approach.
I used the logic following logic

49

Your approach is correct only if there are distinct numbers. So, second subtask gives WA

50

No. I got a TLE for the modified bubble sort approach in C++.

51

Thanks for creating such a detailed editorial.

52

I adopted a slightly different approach, but nevertheless, it was still of O(n log(n)) time complexity. I also made a duplicate array b and sorted it. Then, for every i in a[i], I binary searched the array b for a[i] and got its index in b(say x). Then, if (x%k == i%k) for all i, print “yes”. Else, print “no”. Here’s a link to my code. Please HELP!!
https://www.codechef.com/viewsolution/32331012

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

#define ll             long long
#define pb              push_back
#define mp              make_pair
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)

void shammi() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int main() {
	shammi();
	w(t) {
		ll n, k; cin >> n >> k;
		ll A[n];
		for (ll i = 0; i < n; i++) cin >> A[i];
		for (ll i = 0; i < n - k; i++) {
			if (A[i] > A[i + k]) {
				swap(A[i], A[i + k]);
			}
		}
		bool sorted = true;
		for (ll i = n - k; i < n - 1; i++) {
			if (A[i] > A[i + 1]) {
				sorted = false;
				break;
			} else sorted = true;
		}
		// cout << (sorted) ? "yes\n" : "no\n";
		if (sorted) cout << "yes\n";
		else cout << "no\n";
	}
	return 0;
}Preformatted text

This is my code. The weird thing is I never thought this would work because it doesn’t even give correct answers on the sample test cases. But I submitted it without checking and it turns out the code got AC !
I think the test cases for this problem are very weak.

54

#include<bits/stdc++.h>
#define long long int int
using namespace std;
struct point{
int x,y;
};
bool compareInterval(point i1, point i2)
{
return (i1.x < i2.x);
}

int main()
{
point arr[100000];
int t,f,n,m,a;
cin >> t;
while(t–)
{
cin >> n >> m;
f=0;
for(int i=0;i<n;i++)
{
cin >> a;
arr[i].x=a;
arr[i].y=i;
}
if(m==1)
{
cout <<“yes”<<"\n";
}
else
{
sort(arr,arr+n,compareInterval);
for(int i=0;i<n-1;i++)
{

			if(abs((arr[i].y)-i)%m==0)
			{
				f++;
			}
		    }
		    
			
		}
		if(f==n)
		cout << "yes"<<"\n";
		else
		cout <<"no"<<"\n";
	}
}

}

55

i have this code its not working …

56

what if i set v2.at(x)=0; in the loop to counter the duplicates after finding any element in this vector??

for(i=0;i<n;++i)
{
vector::iterator j=find(v2.begin(),v2.end(),v1.at(i));
x=distance(v2.begin(),j);
v2.at(x)=0;
if(abs((x-i))%k!=0)
{
y=1;
break;
}
}

57

why using break after the else part with flag++ is giving partial correct answer.
plz explain what is the idea behind not using break @anon94108972

58

@taran_1407 @s_h_shahin

59

What’s wrong with this code??

#include<bits/stdc++.h>
using namespace std;
void swap(int ,int );
int main(){
int T;
cin>>T;
for(int i=0;i<T;i++){
int N,K;
cin>>N>>K;
int a[N];
int j;
for(j=0;j<N;j++){
cin>>a[j];
}
int x,y,t1,t2;
for(j=0;j<K;j++){
t1 = a[j];
for(y=1;y<ceil((N/K));y++){
t2 = a[j+(yK)];
if(t2 < t1){
swap(&t1,&t2);
a[j] = t1;
a[j+(yK)] = t2;
}
t1 = t2;
}
}

int c=0,f1=0,f2=0;
for(j=0;j<N-1;j++){
    if(a[j]  < a[j+1]){
        f1 =1;
        break;
    }
}

if(f1==1){


    for(j=0;j<N-1;j++){
        if(a[j] > a[j+1]){
            f2 =1;
            break;
        }
    }

}


if(f1==1 && f2==1){
    cout<<"no"<<endl;
}
else{
    cout<<"yes"<<endl;
}

}

return 0;

}

void swap(int *a,int *b){
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;

}

60

Well, I always prefer not using break, unless necessary, hence I decided just to record if the condition isn’t met and use flag to do that, and print the answer accordingly.

61

Instead of saying |p - q| % k is x, it makes sense to say we can only swap every Kth element from an index, and we build K arrays out of every index this way. To me this is more intuitive.

62

for duplicate cases your approach " sum of absolute values must be divisible by k" is not correct
as you see 4 and 5 both are not divisible by 3 but there sum 9 is divisible.
i also got stuck but finally here is my sol
https://www.codechef.com/viewsolution/32944658

63

Didn’t get it. Are these 4 & 5 are values from array or difference between previous and current index in sorted array?

My logic for duplication is, summation of difference between previous and current index in sorted array for a value should be divisible by K.

64

You need to handle duplicates.
Here is my simple solution:
https://www.codechef.com/viewsolution/33015577