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.
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.
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.
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.
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;
}
https://www.codechef.com/viewsolution/32261341
Itās my solution from the contest. It will be easy to understand for you.
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++;
}
}
you might want to try using merge sort
was your submission accepted?
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?