REPLESX - Editorial

PROBLEM LINK:

Division 1
Division 2
Video Editorial

Author:
Tester:
Editorialist:

DIFFICULTY:

Easy

PREREQUISITES:

arrays, sorting

PROBLEM:

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


9 Likes

Replace For X: Full Explanation - Link

2 Likes

Replace X editorial beginner friendly

3 Likes

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, :slight_smile:
https://www.codechef.com/viewsolution/38542357

6 Likes

Did by using upper and lower bounds here

replace for x
video solution

@jafar00
1
5 4 4 4
5 5 5 5 5

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.

2 Likes

As there is a need to sort the array, time complexity should be O(n* log n) , or am I missing something ?

1 Like

Hello,

Can someone guide me on why this solution is failing ? https://www.codechef.com/viewsolution/38817320

Intresting problem able to solve in one go.
Seen very lengthy code here,but I think my code is very less and very simple
https://www.codechef.com/viewsolution/38467835

Hi Author,

Why can’t the below logic work

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?

I was getting WA during contest but still not able to figure out why it’s failing. Please help me to fix this.

Thank You

Code snippet :

 #include <bits/stdc++.h>
using namespace std;

long long n, x, p, k;
long long arr[500009];

void solve() {
	sort(arr, arr+n);
	if (arr[p] == x) {
		cout << "0" << endl;
		return;
	}
	if ((arr[k] > arr[p]) && (x > arr[p])) {
		cout << "-1" << endl;
		return;
	}
	if ((arr[k] < arr[p]) && (x < arr[p])) {
		cout << "-1" << endl;
		return;
	}
	long long cnt = 0;
	if (arr[k] > arr[p]) {
		while ((arr[p] > x) && (p >= 0)) {
			p--;
			cnt++;
		}
	} else {
		while ((arr[p] < x) && (p <= n)) {
			p++;
			cnt++;
		}
	}
	cout << cnt << endl;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> x >> p >> k;
		for (long long i = 1; i <= n; i++) cin >> arr[i];
		solve();
	}
	return 0;
}
2 Likes

38812517-sol code
can somebody help me with the problem in code please??

debugging or dry running someone’s else code is really difficult ,
after an hour , i found a that

for input
5 1 2 2
2 3 4 5 6
your code printing 0 which is wrong

i have found some wrong
you can see that once

5 11 2 2
10 12 14 16 18
getting 0
but 1 is right

5 1 2 2
10 11 12 13 14
getting 0
but 2 is right

for k=p your code is not correct

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;

int main(){
test{
ll n,x,p,k; cin>>n>>x>>p>>k;
ll f=0;
vectorv;
for(ll i=0;i<n;i++){
ll z; cin>>z;
if(z==x) f=1;
v.pb(z);
}
sort(v.begin(),v.end());
vector::iterator lower;
lower = lower_bound (v.begin(), v.end(), x);
ll ans=0;
k–;p–;
ll val = lower - v.begin();
//cout<<val<<" “;
if(v[p]==x) ans=0;
else if(k>=p && v[p]>=x){
if(f) ans = abs(val-p);
else ans = abs(val-p)+1;
}
else if(p>=k && v[p]<=x) {;
ans = abs(val-p);
}
else ans = -1;
cout<<ans<<”\n";
}
}

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.

What is wrong with my solution…someone please find it…

#include

using namespace std;

int compare(const void* a,const void* b)

{

return(*(int*)a-*(int*)b);

}

int search(long int *ar,long int n,long int x)

{

long int mid,l,r,pos;

    l=0;r=n-1;

    while(l<=r)

    {

        mid=(l+r)/2;

        if(ar[mid]==x)

        {

            pos=mid;

            break;

        }

        if(x>ar[mid])

            l=mid+1;

        else

        {

                r=mid-1;

        }

            

    }

    if(l>r)

        return -1;

    else

    {

        return pos;

    }

}

int main()

{

int t;

long int x,k,p,n,sv,i,pos;

cin>>t;

while(t--)

{   int cnt=0;

    cin>>n>>x>>p>>k;

    k=k-1;p=p-1;

    long int arr[n];

    for(i=0;i<n;i++)

        cin>>arr[i];

    qsort(arr,n,sizeof (long int),compare);

    pos=search(arr,n,x);

    if(pos==-1)

    {   cnt++;

        arr[k]=x;

        qsort(arr,n,sizeof (long int),compare);

        pos=search(arr,n,x);

    }

    if(k==pos)

    {

        if(p==pos)

            cout<<cnt;

        else

        {

            cout<<"-1";

        }

        

    }

    else

    {

        if(k>pos)

        {

            if(pos<=p)

            {

                if(p>k)

                    cout<<"-1";

                else

                {

                    cout<<p-pos+cnt;

                }

            

            }

            else

            {

                cout<<"-1";

            }

        }

        else

        {

            if(p>pos)

                cout<<"-1";

            else

            {

                if(p<k)

                    cout<<"-1";

                else

                    cout<<pos-p+cnt;

            }

            

        }

    }

    cout<<"\n";

                

}

return 0;

}

plsss someone point out where I am WRONG

https://www.codechef.com/submit/REPLESX

Thanks a lot Sir @satyam_patidar for pointing out the corner case.

1 Like