Replace for X SOLUTIONS REPLESX

Replace for X Codechef Solution

You are given an array of NN integers A1,A2,…,ANA1,A2,…,AN and three more integers X,p,X,p, and kk.

An operation on the array is defined to be: replace the kk-th smallest integer in the array with any integer you want.

Output the minimum number of operations you must perform on the array (possibly 00 operations) to make the pp-th smallest element of the array equal to XX. If it is impossible to do so output −1−1.

Note: the kk-th smallest number in an array is the kk-th number from the left when the array is sorted in non-decreasing order.

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains four integers N,X,p,kN,X,p,k respectively.
  • The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

Output

For each test case, print a single line containing one integer ― the minimum number of operations you must perform to make XX the pp-th smallest element or −1−1 if its impossible to do so.

Constraints

  • 1≤T≤1001≤T≤100
  • 1≤p,k≤N1≤p,k≤N
  • 0≤X≤1090≤X≤109
  • The sum of NN over all test cases does not exceed 4∗1054∗105
  • 0≤Ai≤1090≤Ai≤109 for each valid ii

Subtasks

Subtask #1 (10 points): N≤5N≤5

Subtask #2 (40 points): The sum of NN over all test cases does not exceed 3∗1033∗103

Subtask #3 (50 points): Original constraints

Example Input

2
5 4 3 4
4 9 7 0 8
2 25 1 2
100 20

Example Output

1
-1

Explanation

Example case 1:

  • We can perform one operation in the array. Take the kk-th smallest integer of the current array (which is 88 in this case) and replace it with 00. The array then becomes [4,9,7,0,0][4,9,7,0,0] which now makes 44 as the 3rd smallest number of the array.

Example case 2:

  • It is impossible to make 2525 as the smallest number of the array.

Solution

Program C++:

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

int main(){
    int t;
    cin>>t;
    while(t--){
        int i,n,x,p,k;
        cin>>n>>x>>p>>k;
        vector<int> vect;
        for(i=0;i<n;i++){
            int temp;
            cin>>temp;
            vect.push_back(temp);
        }
        sort(vect.begin(),vect.end());
        int minOp=0;
        if(k>p){
            if(x>vect[p-1]) cout<<-1;
            else{
                i=p-1;
                while(vect[i]>x&&i>=0) {
                    minOp++;
                    i--;
                }
                cout<<minOp;
            }
        }
        else if(k<p){
            if(x<vect[p-1]) cout<<-1;
            else{
                i=p-1;
                while(vect[i]<x&&i<n) {
                    minOp++;
                    i++;
                }
                cout<<minOp;
            }
        }
        else{
            if(x<vect[p-1]){
                i=p-1;  
                while(vect[i]>x&&i>=0) {
                    minOp++;
                    i--;
                }
                cout<<minOp;
            }
            else if(x==vect[p-1]) {
                cout<<0; 
            }
            else{
                 i=p-1;
                while(vect[i]<x&&i<n) {
                    minOp++;
                    i++;
                }
                cout<<minOp;
            }
        }
        cout<<endl;
    }

}

Program Python:

def find(x, a):
    for i in range(n):
        if a[i] == x:
            return i
for i in range(int(input())):
    n, x, p, k = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    a.sort()
    s = 0
    if x not in a:
        a[k-1] = x
        a.sort()
        s += 1
    i = find(x, a)
    i += 1
    if a[p-1] == x:
        print(s)
    elif i >= p and k <= p:
        print(i-p + s)
    elif i <= p and k >= p:
        while a[i] == x:
            i += 1
        s += p - i
        print(s)
    else:
        print(-1)

Program Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		try {

			int testCases = Integer.parseInt(bufferedReader.readLine());

			for(int i=0; i<testCases; i++) {

				String[] testCase = bufferedReader.readLine().split(" ");

				int X = Integer.parseInt(testCase[1]);
				int p = Integer.parseInt(testCase[2]) - 1;
				int k = Integer.parseInt(testCase[3]) - 1;

				String[] inputs = bufferedReader.readLine().split(" ");
				List<Integer> list = new ArrayList<Integer>();

				for (String string : inputs) {
					list.add(Integer.parseInt(string));
				}

				Collections.sort(list);

				int numberOfOperations = 0;

				int indexOfElement = list.indexOf(X);

				if(indexOfElement == -1) {
					list.set(k, X);
					numberOfOperations++;
					Collections.sort(list);
					indexOfElement = list.indexOf(X);
				} else {
					int lastIndex = list.lastIndexOf(X);

					if(indexOfElement != lastIndex) {
						if(p >= lastIndex)
							indexOfElement = lastIndex;
					}
				}

				while(true) {

					if(list.get(p) == X) {
						System.out.println(0 + numberOfOperations);
						break;
					}

					if(indexOfElement == p) {
						System.out.println(0 + numberOfOperations);
						break;
					} 

					if(indexOfElement > p) {
						if(k > p) {
							System.out.println(-1);
							break;
						} else {
							System.out.println(indexOfElement - p + numberOfOperations);
							break;
						}
					}

					if(indexOfElement < p) {
						if(k < p) {
							System.out.println(-1);
							break;
						} else {
							System.out.println(p - indexOfElement + numberOfOperations);
							break;
						}
					}
				}					
			}		
		} 
		catch (Exception e) {e.printStackTrace();} 
		finally {
			try {
				bufferedReader.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}

Codechef Long Challenge Solutions

November Long Challenge 2020

Leave a Comment