alwaysGREEEN's blog

By alwaysGREEEN, history, 4 years ago, In English

I recently gave Atcoder Round 163 and could not solve this problem Can anyone explain the math behind this problem ?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By alwaysGREEEN, history, 5 years ago, In English

Hey Guys ! I am solving this problem

(https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/distinct-integers-in-range-66eca44b/description/)

on Hackerearth which ultimately boils down to finding distinct integers in a range from L to R. I am having a hard time understanding how the bitset class is used with segment trees to find the solution. I am posting one of the accepted solutions. Can anyone please explain the logic.

#include<bits/stdc++.h>
using namespace std;
bitset<5001> seg_a[400001],seg_b[400001],rst;
int a[100005],b[100005];
void built_a(int node,int start,int end){
	if(start==end){
		seg_a[node].set(a[start]);
		return;
	}
	int mid=(start+end)/2;
	built_a(2*node,start,mid);
	built_a(2*node+1,mid+1,end);
	seg_a[node]=(seg_a[2*node]|seg_a[2*node+1]);
}
void built_b(int node,int start,int end){
	if(start==end){
		seg_b[node].set(b[start]);
		return;
	}
	int mid=(start+end)/2;
	built_b(2*node,start,mid);
	built_b(2*node+1,mid+1,end);
	seg_b[node]=(seg_b[2*node]|seg_b[2*node+1]);
}
bitset<5001> query_a(int node,int start,int end,int L,int R){
	if(R<start||end<L)return rst;
	if(start>=L && end<=R)return seg_a[node];
	int mid=(start+end)/2;
	return query_a(2*node,start,mid,L,R)|query_a(2*node+1,mid+1,end,L,R);
}
bitset<5001> query_b(int node,int start,int end,int L,int R){
	if(R<start||end<L)return rst;
	if(start>=L && end<=R)return seg_b[node];
	int mid=(start+end)/2;
	return (query_b(2*node,start,mid,L,R)|query_b(2*node+1,mid+1,end,L,R));
}
int main(){
	int n;cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++)cin>>b[i];
	
	built_a(1,0,n-1);
	built_b(1,0,n-1);
	
	cout<<seg_a[1].
	int q;cin>>q;
	int L1,R1,L2,R2;
	while(q--){
		cin>>L1>>R1>>L2>>R2;
		int ans=(query_a(1,0,n-1,L1-1,R1-1)|query_b(1,0,n-1,L2-1,R2-1)).count();
		cout<<ans<<"\n";
	}
	return 0;
}

Full text and comments »

  • Vote: I like it
  • -14
  • Vote: I do not like it

By alwaysGREEEN, history, 5 years ago, In English

Hello Friends, I recently faced a problem in my coding interview that i was unable to solve. The problem statement is -

A binary matrix of nxm was given, you have to toggle any column k number of times so that you can get the maximum number of rows having all 1’s.

for eg, n=3, m=3,

1 0 0

        1 0 1

        1 0 0

if k=2, then we will toggle column 2 and 3 once and we will get rows 1 and 3 with 1 1 1 and 1 1 1 i.e. all 1’s so answer is 2 as there are 2 rows with all 1’s.

if k=3, then we will toggle column 2 thrice and we will get row 2 with 1 1 1 i.e. all 1’s so answer is 1 as there is 1 row with all 1’s.

Please help me solve this question !

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it

By alwaysGREEEN, history, 6 years ago, In English

MILITARY PROBLEM

I am trying to solve this problem by running dfs from every node. I am getting TLE verdict. Please help me speed up my solution

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

By alwaysGREEEN, history, 6 years ago, In English

Hello everyone ! please help in this question 682C - Alyona and the Tree Alyona and the tree. I know how to find distance between two vertices but i have no clue what to do afer that.

Full text and comments »

  • Vote: I like it
  • -8
  • Vote: I do not like it

By alwaysGREEEN, history, 7 years ago, In English

Hey, guys, I have been working on this dfs problem for 2 days but I am not able to crack the logic. please suggest some hints or solution to this problem. Your text to link here...

Full text and comments »

  • Vote: I like it
  • -11
  • Vote: I do not like it