SHUFFLE - Editorial

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

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

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

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.

This code will fail when there are duplicate numbers.

1 Like

can you provide a test case for the same.

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

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:

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

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

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

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

1 Like

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

you might want to try using merge sort

was your submission accepted?

http://p.ip.fi/yYHL

can someone optimize this problem
http://p.ip.fi/xA9q

How is this merging done? Itā€™s not clear for meā€¦ please give an exampleā€¦

My approach during contest,
Store current index for each element in form of pair (i.e. vector<pair<int, int>> a // {element, index}); then sort array, and after that take absolute value of index stored with element and current position of element in sorted array; this approach leads to correct answer for first testcase, see submission, 32237336.

Now, to handle duplicate cases, sum of absolute values must be divisible by k to get answer as yes, otherwise no. Here, submission during the contest, 32255840. But still Iā€™m getting wrong answer in second testcase, couldnā€™t think of any test case where my logic fails; even after generating some random testcases and comparing output with correct solution (32287959 which is based on editorial).

pseudo code:

vector<pair<int, int>> a(n)
for_each element in []:
    a[i].first = num;
    a[i].second = i;    // index of element in input array
sort(a)
for_each element in a:
    a[i].second = abs(a[i].second-i)
shift = a[0].second
for i in range (1,n):
    if(a[i-1] == a[i]) shift += a[i].second
    else{
        if(shift%k){
            print("no")
            exit
         }
    }

if(shift%k){
    print("no")
}else{
    print("yes")
}

Any help would be greatly appreciated.

Can you explain why in the question the constraints are upto 10^9 but in solutions i see here everyone has declared ā€œintā€ and not long long?