Help Required (Easy Queries Hackerearth)

general
, ,
1

Question Link : Easy Queries

Please help my solution giving wrong answer i tried many time , but my nearest left and right functions are wrong , please tell me where i m wrong.
PS : Just make nearest left function in same way as i made . @waqar_ahmad224 @ssjgz

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


#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX 100050
#define INF INT_MAX

/* ------------------------------------------------- Segment tree----------------------------------------------------------- */

int arr[MAX] , st[4*MAX];
/*
si = segemnt index   ss = segment start
se = segment end     qs = query start
qe = query end
1 based indexing
build_tree(1,1,n);
*/

void build_tree(int si , int ss , int se){

    if(ss == se)
    {
        st[si] = arr[ss];
        return;
    }
    int mid = ss + (se-ss)/2;
    build_tree(2*si,ss,mid);
    build_tree(2*si+1,mid+1,se);
    st[si] = st[2*si]+st[2*si+1];
}

int nearest_left(int si, int ss , int se , int qi){
    if(st[si]==0 or qi<ss)
        return -INF;
    if(ss==se){
        return ss;
    }
    int mid = ss + (se-ss)/2;
    if(qi<=mid)
        return(max(-INF,nearest_left(2*si,ss,mid,qi)));
    else
        return(max(-INF, nearest_left(2*si+1,mid+1,se,qi)));
}
int nearest_right(int si, int ss , int se , int qi){
    if(st[si]==0 or qi>se)
        return INF;
    if(ss==se){
        return ss;
    }
    int mid = ss + (se-ss)/2;
    int left = nearest_right(2*si,ss,mid,qi);
    int right = nearest_right(2*si+1,mid+1,se,qi);
    return min(left,right);
}
void update(int si, int ss, int se, int qi ){

    if(ss == se)
    {
        st[si] = arr[ss];
        return;
    }
    int mid = ss + (se-ss)/2;
    if(qi<=mid) // means we have to update in left sub tree
        update(2*si,ss,mid,qi);
    else
        update(2*si+1,mid+1,se,qi);
    st[si] = st[2*si]+st[2*si+1];

}
/* ------------------------------------------------- Segment tree----------------------------------------------------------- */


int main(){
fastio
int n,l,r,q;
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>arr[i];
build_tree(1,1,n);
while(q--){
    int type;
    cin>>type;
    if(type==0)//print nearest left , right
    {
        int ind;
        cin>>ind;
        ind++;
        int nearleft = nearest_left(1,1,n,ind);
        int nearright = nearest_right(1,1,n,ind);
		if(nearleft == -INF)
			cout<<"-1 ";
		else
			cout<<nearleft-1<<" ";
		if(nearright == INF)
			cout<<"-1\n";
		else
			cout<<nearright-1<<"\n";
    }
    else
    {
       int ind;
       cin>>ind;
       ind+=1;
       if(arr[ind]==0){
           arr[ind]=1;
           update(1,1,n,ind);
       }
    }
}

return 0;
}
2

the nodes of your segment tree store the number of elements with value 1 but in your queries you need the positions of the elements, not the number of them.

One way to do it is make your Segment Tree to store in each node the answers to you query, that is, nearest left and nearest right element with value 1.

You use the ST to apply range updates, that is, when you update element i, the nearest left of elements i+1 to n may be modified and the nearest right of the elements 1 to i-1 may be modified.

The queries are point queries, that is, the answer to your query is in one of the leaf nodes of your ST.

1 Like
3

Thanks for reply @carre help me littile bit more , My solution is inspired from this -

    #include<stdio.h>
    #define MAXSIZE 131072
     
    int N, Q;
    int input[MAXSIZE];
     
    typedef struct sNode {
    	int value;
    } sNode;
     
    sNode node[MAXSIZE*2 -1];
    int iteration = 0;
    //int maxTreeNode;
     
    void buildTree(int, int, int);
    void takeInput();
    int findNearestLeft(int, int, int, int);
    int findNearestRight(int, int, int, int);
    void updateTree(int, int, int, int);
    void answerQueries();
     
    int main() {
    	takeInput();
    	buildTree(0, N-1, 0);
    	answerQueries();
    	return 0;
    }
     
    void buildTree(int lb, int ub, int nodeNumber) { //bulding 0 based index tree
    	//printf("%d Building tree for %d %d index %d\n", iteration++, lb, ub, nodeNumber);
    /*	if(!(nodeNumber < maxTreeNode)) {
    		printf("Returning\n");
    		return;
    	}*/
    	if(lb == ub) {
    		node[nodeNumber].value = input[lb];
    		return;
    		//return node[nodeNumber].value;
    	}
    	int mid = (lb+ub)/2;
    	buildTree(lb,	mid,	2*nodeNumber+1);
    	buildTree(mid+1,ub,	2*nodeNumber+2);
    	node[nodeNumber].value = node[2*nodeNumber+1].value + node[2*nodeNumber+2].value;
    }
     
    void takeInput() {
    	int i;
    	scanf("%d%d", &N, &Q);
    	for(i=0 ; i<N ; i++) {
    		scanf("%d", &input[i]);
    	}
    	//maxTreeNode = 2*N -1;
    }
     
    int findNearestLeft(int query, int lb, int ub, int nodeNumber) {
    	if(node[nodeNumber].value == 0 || query <= lb) {
    		return -1;
    	}
    	if(lb == ub) {
    		return lb;
    	}
    	int mid = (lb+ub)/2;
    	int answer;
    	answer = findNearestLeft(query, mid+1, ub, 2*nodeNumber+2);
    	if(answer != -1) {
    		return answer;
    	}
    	answer = findNearestLeft(query, lb, mid, 2*nodeNumber+1);
    	if(answer != -1) {
    		return answer;
    	}
    	return -1;
    }
     
    int findNearestRight(int query, int lb, int ub, int nodeNumber) {
    	if(node[nodeNumber].value == 0 || query >= ub) {
    		return -1;
    	}
    	if(lb == ub) {
    		return lb;
    	}
    	int mid = (lb+ub)/2;
    	int answer;
    	answer = findNearestRight(query, lb, mid, 2*nodeNumber+1);
    	if(answer != -1) {
    		return answer;
    	}
    	answer = findNearestRight(query, mid+1, ub, 2*nodeNumber+2);
    	if(answer != -1) {
    		return answer;
    	}
    	return -1;
    }
     
    void updateTree(int idx, int lb, int ub, int nodeNumber) {
    	if(ub < idx || lb > idx) {// || nodeNumber >= maxTreeNode) {
    		return;
    	}
    	if(lb == ub) {
    		input[idx] = 1;
    		node[nodeNumber].value = 1;
    		return;
    	}
    	int mid = (lb+ub)/2;
    	updateTree(idx,	lb,	mid,	2*nodeNumber+1);
    	updateTree(idx,	mid+1,	ub,	2*nodeNumber+2);
    	node[nodeNumber].value = node[2*nodeNumber+1].value + node[2*nodeNumber+2].value;
    }
     
    void answerQueries() {
    	int queryType, query;
    	while(Q--) {
    		scanf("%d%d", &queryType, &query);
    		switch(queryType) {
    		case 0:
    			printf("%d ",findNearestLeft(query, 0, N-1, 0));
    			printf("%d\n",findNearestRight(query, 0, N-1, 0));
    			break;
    		case 1:
    			updateTree(query, 0, N-1, 0);
    			break;
    		}
    	}
    }

But in above solution i don’t understand why this guy expand first right subtree first in case of nearest left 1 and left subtree in case of nearest right 1 .
What this user wanna do means what is the intution for this solution…I tried since from morning but i can’t.

4

yeah, I see. That’s a nice approach.

When you want to find the nearest left of i element with value 1 then you have to check the larger index lower than i with value 1, so you expand first the right half of the range (1,i-1). If you don’t find go to the left. Moving recursively to the right half of each range will scan the larger positions first (neighboard to the left).

The same to find the nearest right, you scan the left half of the range (i+1,n), if don’t find scan the right half. Moving recursively to the left half of each range will scan the lower positions first.

1 Like
5

any other approach …instead of range update as i m practicing only those question which require point update.

6

can u explan this with small example :pray:

7

the last one uses point update. Do you mean another approach employing ST? You don’t even need ST but that doesn’t matter if you’re practicing ST.

Example:
[1,0,0,1,0,1,1,0]

You want to find the nearest left 1 of position 6 (1-indexed). The answer is 4, right?

The findNearestLeft function will scan:

  • range (4,8); as the sum is not equal -1 then go to right half:
  • (6,8); as query<=lb (6==6) returns -1 and we scan left half of (4,8):
  • (4,5); as sum is not equal -1 go to right half:
  • (5); as sum==0 go to left half:
  • (4) and here is your answer.
1 Like
8

I think first you should do it with easier method of segment tree ,after doing that you will find how to improve your solution.

  1. Segment tree is simple which stores no. of ones of a range. point updates are required.

  2. You can easily put conditions when answer will be -1 or id from above segment tree.

  3. Lets denote number of ones from 1 to id-1 as ‘m’.
    nearest_left(id) = index of mth 1 in the array
    nearest_right(id) = index of (m+1)th 1 in the array

You can study it here : Segment Tree - Algorithms for Competitive Programming

Name of the topic is : Counting the number of zeros, searching for the kk-th zero

1 Like
9

Thanks… Bro it will be really helpful i will go through above link and try to understand :slight_smile: