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 -1Fake 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.
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!
