Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Fake Binary Search CodeChef Solution

Problem -Fake Binary Search CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Fake Binary Search CodeChef Solution in C++14

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define bpc __builtin_popcount
#define forn(i,e) for(ll i = 0; i < e; i++)
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define fi                first
#define se                second
#define sz(x)             (int)((x).size())
#define all(x)            (x).begin(),(x).end()
#define alr(s)            s.rbegin(),s.rend()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define vi vector<ll>
#define vpi vector<pair<ll,ll>>
#define vvi vector<vector<ll>>
#define pi pair<ll,ll>
#define vppi vector<pair<pair<ll,ll>,ll>>
#define pq_max priority_queue<ll>
#define pqp_max priority_queue<pi>
#define pq_min priority_queue<ll, vector<ll>, greater<ll>>
#define pqp_min priority_queue<pi, vector<pi>, greater<pi>>
#define m_pi              3.141592653589793238
#define lb lower_bound
#define ub upper_bound
#define uset unordered_set<ll>
#define oset set<ll>
#define umap unordered_map<ll,ll>
#define omap map<ll,ll>
void solve()
{
    ll n,q;
    cin>>n>>q;
    vi a(n);
    
    forn(i,n)
    cin>>a[i];
    
    vi b=a;
    sort(all(b));
    uset st;
    umap mp;
    umap mp1;
    //for(auto x:b)
    //	cout<<x<<" ";
    forn(i,n)
    {
        if(a[i]==b[i])
        {
            st.insert(a[i]);
        }
        mp[a[i]]=i;
        mp1[b[i]]=i;
    }
    vi tmp;
    //cout<<endl;
    forn(i,n)
    { // cout<<i<<" ";
    tmp.pb(i);
    }
    //cout<<endl;
    while(q--)
    {
        ll x;
        cin>>x;
        ll pos=mp[x];
       //cout<<x<<" ";
       //cout<<pos<<" ";
        ll l=0,r=n-1;
        ll c=0;    ll greater=0;
        ll lower=0;
        ll low=mp1[x];
        ll gre=n-1-mp1[x];
        ll lll=0,rrr=0;
        while(l<=r)
        {   c++;
    
            ll mid=l+(r-l)/2;
          //  cout<<mid<<" ";
            if(tmp[mid]==pos)
            {
                break;
            }
            
            if(tmp[mid]<pos)
            {
            l=mid+1;
            if(a[mid]>x)
            {
                greater++;
            }
            else
            	lll++;
            }
            else
           { 
           	if(a[mid]<x)
            {
                lower++;
            }
            else
            	rrr++;
               r=mid-1;
           }
        }
        //cout<<c<<" "<<mx<<" "<<mn<<" ";
        ll mx=max(lower,greater);
        ll mn=min(lower,greater);
      //  cout<<" break "<<c<<" "<<mx<<" "<<mn<<" ";
        //cout<<gre<<" "<<low<<" ";
          if(greater+lll>(low)||lower+rrr>(gre))
          {
              cout<<-1<<endl;
              continue;
          }
          
        ll ans=mn+(mx-mn);
        cout<<ans<<endl;
        //cout<<0<<endl;
    }
    
    
    
}
int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	cin>>t;
	while(t--)
	{
	    solve();
	    
	}
	return 0;
}

Fake Binary Search CodeChef Solution in PYTH 3

# cook your dish here
def bsearch(arr, size, ind):
    mid = 0
    left = 0
    right = size - 1
    reqToGrt = 0
    reqToLess = 0
    changeToGrt = 0
    changeToLess = 0
    while left <= right:
        mid = (left + right) // 2
        if ind == mid:
            break
        if ind < mid:
            if arr[ind] > arr[mid]:
                changeToGrt += 1
            reqToGrt += 1
            right = mid - 1
        else:
            if arr[ind] < arr[mid]:
                changeToLess += 1
            reqToLess += 1
            left = mid + 1
    return reqToGrt, reqToLess, changeToGrt, changeToLess


def main():
    t = int(input())
    for _ in range(t):
        n, q = tuple(map(int, input().split()))
        pos = {}
        rank = {}
        arr = list(map(int, input().split()))
        b = sorted(arr)

        for i in range(n):
            pos[arr[i]] = i
            rank[b[i]] = i
        # queries = [0] * q
        for i in range(q):
            x = int(input())
            cnt_less = rank[x]
            cnt_grt = n - rank[x] - 1
            reqToGrt, reqToLess, changeToGrt, changeToLess = bsearch(arr, n, pos[x])
            if reqToGrt > cnt_grt or reqToLess > cnt_less:
                ans = -1
            else:
                ans = min(changeToLess, changeToGrt) + abs(changeToGrt - changeToLess)
            print(ans)


if __name__ == '__main__':
    main()

Fake Binary Search CodeChef Solution in C

#include<stdio.h>
#include<stdlib.h>
 
typedef struct node{
	int val;
	int id;
}node;
 
node arr[100001];
int vis[100001];
 
 
int maximum(int a,int b){
	 return (a<=b)?b:a;
}
 
 
int findid(node* arr,int low,int high,int x){
 
      
      int mid,i,j,k;
 
      if(low == high)return 1; 
 
      mid = (low+high)/2;
 
      if(arr[mid].val == x)return mid;
      else if(arr[mid].val < x) return mid+findid(arr+mid,1,high-mid,x);
      else return findid(arr,1,mid-1,x);
 
}
 
int findid_linser(int* arr,int low,int high,int x){
 
    
      int i,j,k;
      for(i=low;i<=high;i++){
      	if(arr[i]==x)return i;
      }
 
}
 
 
 
node* mergesort(node* arr, int n){
 
        int i,j,k,p,q,r,v;
        if(n==1)return arr;
 
        i=n/2;
        j=n-i;
 
        node* a = mergesort(arr,i);
        node* b = mergesort(arr+i,n-i);
        node* c = (node*)malloc((n+1)*sizeof(node));
 
        p=1;q=1;k=1;
 
          while((p<=i)  && (q<=j)){
          
                if(a[p].val <= b[q].val){c[k++]=a[p++];}
                else {c[k++]=b[q++];}
          
          }
 
          while(p<=i){c[k++]=a[p++];}
          while(q<=j){c[k++]=b[q++];}
 
          for(i=1;i<=n;i++){arr[i]=c[i];}
 
          free(c);
          
 
         return arr;
 
}
 
 
int main(){
 
    int i,j,k,a,b,c,t,n,q,x,y,z;
    node* myarr;
    int mid,low,high;
    scanf("%d",&t);
 
    while(t--){
 
 
    	 scanf("%d %d",&n,&q);
 
         for(i=1;i<=n;i++){
         	 scanf("%d",&k);
             arr[i].val=k;
             arr[i].id=i;
             vis[i]=k;
         }
 
 
            myarr=mergesort(arr,n);
         	
         	while(q--){
 
         		scanf("%d",&x);
         		y=0;z=0;
         		a=0;b=0;
         		
         		k = findid(myarr,1,n,x);
         		y = k - 1;
         		z = n-1-y;
         		j=myarr[k].id;
 
         		low=1;high=n;
 
         		while(low <= high){
 
         			mid = (high + low)/2;
 
         			if(vis[mid] == x)break;
         			
         			if(vis[mid] < x){
 
         				 if( j < mid){
         				 	  a++; //need arr[mid] > x
         				 	  high=mid-1;
         				 }
         				 else{
         				 	y--;
                            low=mid+1;
         				 }
 
         			}
         			else{
 
         				if(j > mid){
 
         					b++; // need arr[mid] < x
         					low=mid+1;
 
         				}
         				else{
         					z--;
         					high=mid-1;
         				}
 
         			}
 
 
 
         		}
 
              c=0;
              y-=a;
              z-=b;
 
              
              if(a<=b){
 
                      c=a;
                      b-=a;
                      if(y>=b){c+=b;printf("%d\n",c);}
                      else{
                      	 printf("%d\n",-1);
                      	 //printf("%d\n", maximum(a,b));
                      }
              }
              else{
 
              	    c=b;
              	    a-=b;
              	    if(z>=a){c+=a;printf("%d\n",c);}
              	    else{
              	    	 printf("%d\n",-1);
              	    	 //printf("%d\n", maximum(a,b));
              	    }
 
              }
              
         	}
 
    }	
 
 
	return 0;
}

Fake Binary Search CodeChef Solution in JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static void main(String[] args) {
        FastScanner sc=new FastScanner();
        int T=sc.nextInt();
//        int T=1;
        for (int tt=0; tt<T; tt++){
            int n =sc.nextInt();
            int q = sc.nextInt();
            int arr[]= new int [n];
            Pair arr2[]= new Pair[n];
            for (int i=0; i<n; i++){
                arr[i]=sc.nextInt();
                arr2[i]= new Pair(arr[i],i);
            }
            Arrays.sort(arr2);
            for (int i=0; i<q; i++){
                int less=0;
                int greater=0;
                Pair temp= bs(arr2, sc.nextInt());
                int find =temp.x;
                int grr=n-1-temp.y;
                int lrr=temp.y;
                int lo = 0;
                int hi=n-1;

                while (lo<=hi){
                    int mid =(lo+hi)/2;
                    if (mid==find) break;
                    else if (mid<find){
                        if (arr[mid]>arr[find]) {
                            less++;
                        }
                        lrr--;
                        lo=mid+1;
                    }
                    else {
                        if (arr[mid]<arr[find]) {
                            greater++;
                        }
                        grr--;
                        hi=mid-1;
                    }
                }
                if (lrr<0 || grr<0) System.out.println(-1);
                else System.out.println(Math.max(less,greater));
            }
        }
    }
    static Pair bs(Pair arr[], int x){
        int lo=0;
        int hi= arr.length-1;
        int ans =0;
        while (lo<=hi){
            int mid = (lo+hi)/2;
            if (arr[mid].x==x) return new Pair (arr[mid].y,mid);
            else if (arr[mid].x<x) lo=mid+1;
            else hi=mid-1;
        }
        return null;
    }
    static long factorial (int x){
        if (x==0) return 1;
        long ans =x;
        for (int i=x-1; i>=1; i--){
            ans*=i;
            ans%=mod;
        }
        return ans;
    }
    static long mod =1000000007L;
    static long power2 (long a, long b){
        long res=1;
        while (b>0){
            if ((b&1)== 1){
                res= (res * a % mod)%mod;
            }
            a=(a%mod * a%mod)%mod;
            b=b>>1;
        }
        return res;
    }

    boolean[] sieveOfEratosthenes(int n)
    {

        boolean prime[] = new boolean[n+1];
        for(int i=0;i<=n;i++)
            prime[i] = true;

        for(int p = 2; p*p <=n; p++)
        {
            if(prime[p] == true)
            {
                for(int i = p*p; i <= n; i += p)
                    prime[i] = false;
            }
        }
        return prime;
    }
    static void sort(int[] a) {
        ArrayList<Integer> l=new ArrayList<>();
        for (int i:a) l.add(i);
        Collections.sort(l);
        for (int i=0; i<a.length; i++) a[i]=l.get(i);
    }
    static void sortLong(long[] a) {
        ArrayList<Long> l=new ArrayList<>();
        for (long i:a) l.add(i);
        Collections.sort(l);
        for (int i=0; i<a.length; i++) a[i]=l.get(i);
    }
    static long gcd (long n, long m){
        if (m==0) return n;
        else return gcd(m, n%m);
    }

    static class Pair implements Comparable<Pair>{
        int x,y;
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(Pair o){
            return this.x-o.x;
        }
    }
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        int[] readArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

Fake Binary Search CodeChef Solution in PYPY 3

t=int(input())
while(t!=0):
    t-=1
    n,q=[int(x) for x in input().strip().split()]
    a=[int(x) for x in input().strip().split()]
    sorted_a=sorted(a)  #sorted list 
    indexOf={} #retrieving index of elements in O(1) lookup
    index=0
    for ele in a:
        indexOf[ele]=index 
        index+=1
    
    index=0 #reset 
    countlessthan={}    #to predict number of elements less than ele
    countgreaterthan={} #to predict number of elements greater than ele
    for ele in sorted_a:
        countlessthan[ele]=index 
        countgreaterthan[ele]=n-1-index
        index+=1 
    
    while(q!=0):
        q=q-1
        x=int(input())
        low=0
        high=n-1 
        swapGreaterYes=0
        swapGreaterNo=0 
        swapLesserYes=0
        swapLesserNo=0 
        while(low<=high):
            
            mid=(low+high)//2 
            if(a[mid]==x):
                break
            elif(a[mid]<x and indexOf[x]>mid):
                low=mid+1
                swapLesserNo+=1 
            elif(a[mid]<x and indexOf[x]<mid): #FakeBS case 1
                high=mid-1 
                swapGreaterYes+=1 
            elif(a[mid]>x and indexOf[x]<mid):
                swapGreaterNo+=1 
                high=mid-1 
            elif(a[mid]>x and indexOf[x]>mid): #FakeBS case 2
                swapLesserYes+=1
                low=mid+1  
                
            
        neededswaps=max(swapLesserYes,swapGreaterYes) 
        ans=neededswaps

        #not enough elements in pool required for swapping
        if((swapLesserYes>countlessthan[x]- swapLesserNo) or (swapGreaterYes>countgreaterthan[x]- swapGreaterNo)):
            ans=-1 
       
        print(ans)

Fake Binary Search CodeChef Solution in PYTH

for ttt in range(int(raw_input())):
    n,q = map(int,raw_input().strip().split())
    a = map(int,raw_input().strip().split())
    sa = list(a)
    sa.sort()
    d = {}
    d1 = {}
    for i in range(n):
        d[sa[i]] = i
    for i in range(n):
        d1[a[i]] = i

    for qs in range(q):
        x = int(raw_input())
        curr = d1[x]
        nl = d[x]
        nh = n-nl-1

        tl = 0
        sl = 0
        th = 0
        sh = 0
        
        low = 0
        high = n-1
        while low<=high:
            mid = (low+high)/2
            #print low,high,sl,sh,mid,a[mid],x,curr
            
            if a[mid] == x:
                break
            elif a[mid]<x:
                if mid>curr:
                    sl+=1
                    th+=1
                    high = mid - 1
                else:
                    tl+=1
                    low = mid + 1
            else:
                if mid<curr:
                    sh+=1
                    tl+=1
                    low = mid + 1
                else:
                    th+=1
                    high = mid - 1
        if tl<=nl and th<=nh:
            print max(sh,sl)
        else:
            print -1

Fake Binary Search CodeChef Solution in C#

using System;
using System.Collections.Generic;
using System.Linq;

namespace CC_FakeBinarySearch
{
    class Program
    {
        static void Main(string[] args)
        {
            int terms = int.Parse(Console.ReadLine());
            //int terms = 1;
            int[][] swaps = new int[terms][];

            for (int i = 0; i < terms; i++)
            {
                int[] data = Array.ConvertAll(Console.ReadLine().Trim().Split(), Convert.ToInt32);
                long[] array = Array.ConvertAll(Console.ReadLine().Trim().Split(), Convert.ToInt64);

                //int[] data = { 7, 7 };
                //long[] array = { 3, 1, 6, 7, 2, 5, 4 };

                //int[] data = { 5, 5 };
                //long[] array = { 4, 3, 5, 1, 2 };

                //int[] data = { 10, 10 };
                //long[] array = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
                //long[] array = { 5, 6, 1, 4, 8, 9, 7, 2, 3, 10 };
                //long[] array = { 7, 8, 9, 10, 5, 1, 2, 3, 4, 6 };
                //long[] array = { 6, 10, 9, 8, 7, 3, 2, 1, 5, 4 };

                int[][] aux = GetKeys(data[0]);
                int[] keys = aux[0];
                int[] maxSwaps = aux[1];

                var sortedPairs = array.Select((x, j) => new { Value = x, Key = keys[j] })
                        .OrderBy(x => x.Value)
                        .ThenBy(x => x.Key)
                        .ToArray();

                long[] sortedArray = sortedPairs.Select(x => x.Value).ToArray();
                int[] sortedKeys = sortedPairs.Select(x => x.Key).ToArray();

                swaps[i] = new int[data[1]];

                for (int j = 0; j < data[1]; j++)
                {
                    long query = long.Parse(Console.ReadLine());
                    //long query = array[j];
                    int index = GetIndex(query, data[0], sortedArray);

                    int fakeIndex = sortedKeys[index];
                    int[] swapMax = { maxSwaps[index], data[0] - 1 - maxSwaps[index] };

                    //List<long[]> sequence = GetSequence(fakeIndex, data[0], array);
                    //Print(sequence);

                    swaps[i][j] = GetCount(query, fakeIndex, data[0], array, swapMax);
                }
            }

            foreach (int[] term in swaps)
            {
                foreach (int count in term)
                    Console.WriteLine(count);
            }
            Console.ReadLine();
        }

        static int[][] GetKeys(int size)
        {
            int[][] keys = new int[2][];
            keys[0] = new int[size];
            keys[1] = new int[size];

            for (int i = 0; i < size; i++)
            {
                keys[0][i] = i;
                keys[1][i] = size - 1 - i;
            }

            return keys;
        }

        static int GetCount(long x, int fakeIndex, int size, long[] array, int[] swapMax)
        {
            int count = 0;
            int[] pair = { 0, 0 };

            int lo = 0;
            int hi = size - 1;
            int mid = 0;

            while (lo <= hi)
            {
                mid = (lo + hi) / 2;

                if (mid == fakeIndex)
                    break;

                if (mid < fakeIndex)
                {
                    //moving right
                    swapMax[1]--;
                    if (array[mid] > x)
                    {
                        pair[1]++;                        
                    }
                    else
                    {
                        //Check if already swapped
                        if (swapMax[1] < 0)
                        {
                            return -1;
                        }
                    }

                    lo = mid + 1;
                }
                else
                {
                    //moving left
                    swapMax[0]--;
                    if (array[mid] < x)
                    {
                        pair[0]++;
                       
                    }
                    else
                    {
                        //Check if already swapped
                        if (swapMax[0] < 0)
                        {
                            return -1;
                        }
                    }

                    hi = mid - 1;
                }

                if (swapMax[0] < 0 || swapMax[1] < 0)
                    return -1;

                if (pair[0] != 0 && pair[1] != 0)
                {
                    pair[0]--;
                    pair[1]--;

                    count++;
                }
            }

            count += (pair[0] + pair[1]);

            return count;
        }

        static int GetIndex(long num, int size, long[] array)
        {
            int lo = 0;
            int hi = size - 1;
            int index = 0;

            while (lo <= hi)
            {
                index = (lo + hi) / 2;

                if (array[index] == num)
                    break;

                if (array[index] < num)
                    lo = index + 1;
                else
                    hi = index - 1;
            }

            return index;
        }

        static List<long[]> GetSequence(int fakeIndex, int size, long[] array)
        {
            List<long[]> sequence = new List<long[]>();

            int lo = 0;
            int hi = size - 1;
            int mid = 0;

            while (lo <= hi)
            {
                mid = (lo + hi) / 2;

                if (mid == fakeIndex)
                    break;

                if (mid < fakeIndex)
                {
                    sequence.Add(new long[] { array[mid], 0 });
                    lo = mid + 1;
                }
                else
                {
                    sequence.Add(new long[] { array[mid], 1 });
                    hi = mid - 1;
                }
            }

            return sequence;
        }

        static void Print(long[] array)
        {
            for (int i = 0; i < array.Length; i++)
                Console.Write("{0} ", array[i]);
            Console.WriteLine();
        }

        static void Print(int[] array)
        {
            for (int i = 0; i < array.Length; i++)
                Console.Write("{0} ", array[i]);
            Console.WriteLine();
        }

        static void Print(List<long[]> array)
        {
            for (int i = 0; i < array.Count; i++)
            {
                Console.Write("{0}", array[i][0]);
                Console.Write(array[i][1] == 0 ? "R " : "L ");
            }

            Console.WriteLine();
        }
    }
}

Fake Binary Search CodeChef Solution in GO

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

var scanner *bufio.Scanner = bufio.NewScanner(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)

func readInt64() (n int64) {
	scanner.Scan()
	buffer := scanner.Bytes()
	for _, v := range buffer {
		n = n*10 + int64(v-'0')
	}
	return
}
func printf(f string, a ...interface{}) { fmt.Fprintf(writer, f, a...) }

func search(a []int64, i int) (u []bool, c []bool) {
	u, l, h, m := make([]bool, 0), 0, len(a)-1, (len(a)-1)/2
	for m != i {
		if i > m {
			u, c = append(u, true), append(c, a[i] > a[m])
			l, m = m+1, (h+m+1)/2
		} else {
			u, c = append(u, false), append(c, a[i] < a[m])
			h, m = m-1, (m-1+l)/2
		}
	}
	return
}

var A, P []int64

type ByP []int64

func (a ByP) Len() int           { return len(a) }
func (a ByP) Less(i, j int) bool { return A[P[i]] < A[P[j]] }
func (a ByP) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
	defer writer.Flush()
	scanner.Split(bufio.ScanWords)

	T := readInt64()
	for ; T > 0; T-- {
		N, Q := readInt64(), readInt64()
		A, P = make([]int64, N), make([]int64, N)
		for i := range A {
			A[i], P[i] = readInt64(), int64(i)
		}
		sort.Sort(ByP(P))
		S := make(map[int64]int)
		for i := range P {
			u, c := search(A, int(P[i]))
			tui, tdi, tu, td := 0, 0, 0, 0
			for j := range u {
				if u[j] {
					tu++
					if !c[j] {
						tui++
					}
				} else {
					td++
					if !c[j] {
						tdi++
					}
				}
			}
			if tu > i {
				S[A[P[i]]] = -1
			} else if td > len(P)-1-i {
				S[A[P[i]]] = -1
			} else if tui < tdi {
				S[A[P[i]]] = tdi
			} else {
				S[A[P[i]]] = tui
			}
		}
		for ; Q > 0; Q-- {
			q := readInt64()
			printf("%d\n", S[q])
		}
	}
}
Fake Binary Search CodeChef Solution Review:

In our experience, we suggest you solve this Fake Binary Search CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Fake Binary Search CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Fake Binary Search CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *