What is the O(nlong(n)) implementation ?
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.
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;
}
}
i used the same approach and got partial correct answer
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
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;
}
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
Why does the code fail, when there are duplicates
this is my solution but it gives tle for both test cases can someone please point out the mistake
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?
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 
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 | 4element->[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.
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 
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;
}