Given an array A of size n, and integers X, p, k,
find minimum number of operations to make the p^{th} smallest element equal to k where in each
operation you can change k^{th} smallest element to any value.
EXPLANATION:
Consider an operation where you change k^{th} smallest element to some value y.
If y lands up at position l, then all values between k and l will be changed.
All elements closer to k than l are shifted by one unit closer to k.
Let consider two cases
The X that ends up at position p is already present in the array.
If X is at position p_X then after applying any operation, p_X can only become closer to k.
If p_X is further to k than p then it’s possible in |p_X - p| operations
otherwise it’s not possible.
The X that ends up was added in some operation. In the first operation, insert X, we can acheive any
possible configuration after the insertion of X. Then proceed to above case to check for the possibility as above.
So we consider every position of X already present in the array or present after one operation of adding X and use the above criteria to find minimum operations.
TIME COMPLEXITY:
TIME:\mathcal{O}(n) SPACE:\mathcal{O}(n)
SOLUTIONS:
Setter's Solution
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
int n, x, p, k;
int a[MAXN];
void read() {
cin >> n >> x >> p >> k;
assert(x >= 0 && x <= (int)1e9);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
p--, k--;
}
bool no_x() {
for(int i = 0; i < n; i++) {
if(a[i] == x) return false;
}
return true;
}
void solve() {
sort(a, a + n);
int add = 0;
if(no_x()) {
add++;
a[k] = x;
sort(a, a + n);
}
if(a[p] == x) {
cout << add << endl;
return;
}
// binary search -> loop
int position_x = -1;
for(int dx = 0; dx < n; dx++) {
if(k >= dx && a[k - dx] == x) {
position_x = k - dx;
break;
}
if(k + dx < n && a[k + dx] == x) {
position_x = k + dx;
break;
}
}
if(position_x <= k && position_x <= p && p <= k) {
cout << add + p - position_x << endl;
} else if(position_x >= k && k <= p && p <= position_x) {
cout << add + position_x - p << endl;
} else {
cout << -1 << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) {
read();
solve();
}
return 0;
}
this one was also an interesting problem and gave a boost to my confidence along with DDIMST and Adding Square,
It feels really good after coding it all, https://www.codechef.com/viewsolution/38542357
the answer for this must be 4, I guess your code might print 1.
p==k doesn’t mean answer is 1 because even after we make k to X, sorting need not keep it in the same place.
for _ in range(int(input())):
n,x,p,k = map(int,input().split())
a = list(map(int,input().split()))
gInd = lInd = fInd = Ln = 0 ; f = False; g = False
a.sort()
for i in range(n):
if x==a[i]:
if f:
Ln += 1
else:
fInd = i+1; f = True
elif a[i]<x:
lInd = i+1
elif not g:
gInd = i+1; g = True
if f:
if p>=fInd:
if p<=(fInd+Ln):
print(0)
elif k>=p:
print(abs(fInd-p))
else:
print(-1)
else:
if p>=k:
print(abs(fInd-p))
else:
print(-1)
else:
if k>=p and p>=gInd:
print(p-lInd)
elif lInd>=p and p>=k:
print(gInd-p)
else:
print(-1)
Will you please provide your solution with O(N) time complexity?
Could anyone help me in understanding what’s wrong in my code?
#include <bits/stdc++.h>
using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define input freopen(“input.txt”, “r”, stdin),freopen(“output.txt”, “w”, stdout); #define test ll t; cin>>t; while(t–) #define ll long long #define pb push_back #define fi first #define se second
const ll mod=1000000007;
When k and p are equal, answer is not going to be -1. I did not find any such instance of this equality being handled.
You can start debugging from there.
