SHUFFLE - Editorial

editorial
, , , ,
4

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;
}
1 Like
5

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. [CodeChef: Practical coding for everyone]

2 Likes
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