guacamolesyrup's blog

By guacamolesyrup, history, 9 months ago, In English,

Recently I have encountered a problem regarding searching.Any help would be appreciated.It says let, A be a sorted array(1-based index) of size n where n is even.A new array B is generated by swapping some elements in odd-numbered positions in the first half of A with some elements in odd-numbered positions in the second half of A.Note that elements in the even numbered positions are the same in both A and B, whereas each element in an odd-numbered position in A takes part in at most one swap.Write an algorithm that takes A and an integer x as inputs and finds whether x is present in B or not.

Read more »

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

By guacamolesyrup, history, 14 months ago, In English,

Can anyone suggest me good resource for learning bitmask dp? Thanks in advance..

Read more »

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

By guacamolesyrup, history, 2 years ago, In English,

Sabbir and GCDs I was trying this problem but somehow i am getting WA after 10th testcase. Can anyone give me some hints how to solve it?Thanks in advance.I have updated my solution now it is showing WA again.

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

#define ll long long
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define MAX 100009
#define MOD 1000000007
#define fast ios::sync_with_stdio(false);
#define INF 1000000000000000LL
#define INM -INF
#define pi 3.14159265358979323846264338327950

vector<int>prime;
bool isprime[1000011];

void sieve(){
	for(int i=2;i<=sqrt(1000010);i++){
		if(!isprime[i]){
			for(int j=i+i;j<=1000010;j+=i)
			isprime[j]=1;
		}
	}
	prime.pb(2);
	for(int i=3;i<=1000010;i+=2){
		if(!isprime[i])
		prime.pb(i);
	}
}
int main(){
	fast
	int t;
	sieve();
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		int a[n];
		for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	    }
	    set<int>S;
		for(int i=0;i<n;i++){
			for(int j=0;j<prime.size()&& prime[j]*prime[j]<=a[i];j++){
				while(a[i]%prime[j]==0){
					S.insert(prime[j]);
					a[i]/=prime[j];
				}
			}
			if(a[i]>1){
				S.insert(a[i]);
			}
		}
		for(int i=0;i<prime.size();i++){
			if(S.find(prime[i])==S.end()){
				printf("%d\n",prime[i]);
				break;
			}
		}
	}
}

Read more »

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