SHUFFLE - Editorial

editorial
, , , ,
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
30

can you provide a test case for the same.

31

Your time comp is O(n^2). So,it got TLE.
For TC-
1
100000 1
array in decreasing order (100000 9999 9998…)

32

I think this problem is unclear. Because sorting can also be possible in descending order.
But its not handling that case.
e.g. n=4 k=2
sequence is 4 3 2 1
then it will give output as “no” . But it is sorted though.
i think you should clarify this thing in problem :slightly_smiling_face:

33

So what else i have to do to make this code work?

34

Just Sharing my approach which doesn’t require to sort each sub list separately:

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <bitset>
#include <iomanip>
using namespace std;
#define endl '\n'
#define bp(x) __builtin_popcount(x)
#define zf(x) __builtin_clz(x)
#define zl(x) __builtin_ctz(x)
#define par(x) __bultin_parity(x)
#define FAST_IO ios::sync_with_stdio(0); std::cin.tie(0);
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
typedef long long ll;

void test_case()
{
FAST_IO
int n, k;
cin >> n >> k;
vector <ll> a(n);
for(ll &x: a) cin >> x;
if(k == 1 || is_sorted(a.begin(), a.end()))
{
    cout << "yes" <<endl;
    return;
}
vector <ll> b = a;
sort(b.begin(), b.end());
map <ll,int> m, freq;
for(int i = 0; i < n ; i ++)
{
    m[b[i]] = i;
    freq[b[i]] ++;
}
for(int i = 0 ; i < n; i ++)
{
    if(freq[a[i]] >= 2)
    {
        bool ok = false;
        for(int j = m[a[i]]; j >= 0; j --)
        {
            if(a[i] == b[j] && abs(i - j) % k == 0)
            {
                ok =true;
                b[j] = -1;
                break;
            }
        }
        if(!ok)
        {
            cout << "no" <<endl;
            return ;
        }
    }
    else 
    {
        if(abs(m[a[i]] - i) % k !=0 )
        {
            cout << "no" <<endl;
            return ;
        }
        else 
        {
            b[m[a[i]]] = -1;
        }
    }
}
cout << "yes" <<endl;
return ;
}
int main()
{
FAST_IO
int t;
cin >> t;
while(t--)
test_case();
return 0;
}
35

Can somebody tell why this is partially correct? https://pastebin.com/70AaUtxb

36

https://www.codechef.com/viewsolution/32261341
It’s my solution from the contest. It will be easy to understand for you.

1 Like
37

can anyone suggest how to optimize this code.
time limit is being exceeded

#include<stdio.h>
#include<math.h>
void main()
{
int f=1;
int i;
scanf("%d",&i);

while(f<=i)
{
    int f1=0;
    int t;
    scanf("%d",&t);
    int k;
    scanf("%d",&k);
    int a[t];
    for(int j=0;j<t;j++)
    {
        scanf("%d",&a[j]);
    }

    for(int j=0;j<t;j++)
    {
        int n=0;
        int min=a[j];
        int temp=j;
        for(int b=j+1;b<t;b++)
        {
            if(a[b]<min)
            {
                min=a[b];
                temp=b;
            }
        }
        int temp1=a[j];
        a[j]=min;
        a[temp]=temp1;
        int j1=j;
        while(j1<t)
        {
            if(j1==temp)
            {
                n=1;
                break;
            }
            j1=j1+k;
        }
        if(n==0)
        {
            f1=1;
            printf("no\n");
            break;
        }
    }
    if(f1==0)
    {
        printf("yes\n");
    }
    f++;
}

}

1 Like
38

you might want to try using merge sort

39

was your submission accepted?