SHUFFLE - Editorial

editorial
, , , ,
6

I used a form of modified bubble sort for this question. But it barely passed the test cases in pypy CodeChef: Practical coding for everyone
When i ran the same code in Python3 it gave TLE as was expected.
CodeChef: Practical coding for everyone
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.

8

I do not know where i made mistake but it gives only partially correct answer.

2 Likes
9

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

1 Like
10

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

11

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

12

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

13

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.

14

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;
}
}

15

i used the same approach and got partial correct answer

16

Bro my approach—> #include<bits/stdc++.h>#define fast cin.tie(0);cout.tie(0); ios_base::sync_wit - Pastebin.com
I handle Duplicates all done but given WA for part-2

17

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;
}

19

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
20

Why does the code fail, when there are duplicates

22

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

23

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?

24

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

Hope this solution helps you all. I used binary search to compare the positions of each element in sorted array and unsorted array and checked whether the difference is divisible by k.

2 Likes
25

Sorry but I don’t want others solution but just the explanation that why my code didn’t work

26

I had a similar approach but somewhat easy to understand. Hopefully, it helps :slight_smile:

so, if an element’s original index in the array is i and its index in the sorted array is j
then because of the reason mentioned in the editorial, abs(j-i)%k==0

or I can simply write i%k == j%k
Therefore I stored original indexes(mod k) and those in a sorted array in a map and compared.
To handle duplicacy, all we need to do is to check for a particular element, the number of indexes(mod k) in the original and sorted array is equal.

example:

n=5 k=2
arr:
[3,2,1,2,2]
sorted arr:
[1,2,2,2,3]

element → indexes(original) | indexes(sorted)
1-> 2 | 0
2->1,3,4 | 1,2,3
3->0 | 4

element->[index%k - count] (original) | [index%k - count] (sorted)

1->[0-1] | [0-1]
2->[0-1],[1-2] | [0-1],[1-2]
3->[0-1] | [0-1]

This is my code link : https://www.codechef.com/viewsolution/32273690
P.S. This is my first time writing something here, so all the feedbacks are highly welcomed. :slight_smile:

1 Like
27

Your for loop has i variable and inside the loop you are assigning i=-1 if you have found the condition. So, loop will never terminate and then TLE.

28

This code will fail when there are duplicate numbers.

1 Like