- vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); for ( int i = 4; i <= N; i += 2 ) sieve[i] = 1; int sqrtn = sqrt ( N ); for ( int i = 3; i <= sqrtn; i += 2 ) { if ( sieve[i] == 0 ) { for ( int j = i * i; j <= N; j += 2 * i ) sieve[j] = 1; } } for ( int i = 3; i <= N; i += 2 ) if ( sieve[i] == 0 ) prime.push_back(i); }
- vector <int> factors; void factorize( ll n ) { ll sqrtn = sqrt ( n ); for ( ll i = 0; i < prime.size() && prime[i] <= sqrtn; i++ ) { if ( n % prime[i] == 0 ) { while ( n % prime[i] == 0 ) { n /= prime[i]; factors.push_back(prime[i]); } sqrtn = sqrt ( n ); } } if ( n != 1 ) { factors.push_back(n); } }
Subhashis_Mollick's Blog
আমার ব্লগে আপনাকে স্বাগতম...... আমি সুভাশিষ মল্লিক... পড়াশোনা করছি কুষ্টিয়ার ইসলামী বিশ্ববিদ্যালয়ের কম্পিউটার সায়েন্স এন্ড ইঞ্জিনিয়ারিং বিভাগে... প্রোগ্রামিং করতে অনেক ভালো লাগে আর তার চেয়েও বেশি ভালো লাগে প্রোগ্রামিং এর যেকোনো কাজে কাওকে সাহায্য করতে,আর সেই জন্যই আমার এই ব্লগ... আপনার জন্যই আমার এই ব্লগ... নিজে প্রোগ্রামিং করুন ও অন্যকে প্রোগ্রামিং করতে উৎসাহ প্রদান করুন.... Happy Coding
বৃহস্পতিবার, ১২ অক্টোবর, ২০২৩
Factorization with prime Sieve
বৃহস্পতিবার, ৩ মার্চ, ২০২২
Longest Increasing Subsequence & Path Print (LIS)
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> sub, subIndex;
vector<int> path(n, -1);
for (int i = 0; i < n; ++i) {
if (sub.empty() || sub[sub.size() - 1] < nums[i]) {
path[i] = sub.empty() ? -1 : subIndex[sub.size() - 1];
sub.push_back(nums[i]);
subIndex.push_back(i);
} else {
int idx = lower_bound(sub.begin(), sub.end(), nums[i]) - sub.begin();
path[i] = idx == 0 ? -1 : subIndex[idx - 1];
sub[idx] = nums[i];
subIndex[idx] = i;
}
}
vector<int> ans;
int t = subIndex[subIndex.size() - 1];
while (t != -1) {
ans.push_back(nums[t]);
t = path[t];
}
reverse(ans.begin(), ans.end());
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
cout<<endl;
return ans.size();
}
};
শনিবার, ২৯ জানুয়ারী, ২০২২
Longest non-decreasing subsequence - TC: O(nlogn)
int longestNonDecresingSubsequenceLength(vector<int> a) {
vector<int> s;
s.push_back(a[0]);
int n = a.size();
int len = 1;
for (int i = 1; i < n; i++) {
int idx = upper_bound(s.begin(), s.end(), a[i]) - s.begin();
int m = s.size();
if (m > idx) {
s[idx] = a[i];
} else {
s.push_back(a[i]);
}
}
return s.size();
}
সোমবার, ৩০ আগস্ট, ২০২১
Mobius Inversion (Mobius Precalculate)
const ll N=1e6+5;
ll lp[N];
ll mob[N];
void mobiusPreCalc(){
mob[1] = 1;
for (ll i = 2; i < N; ++i) {
if (!lp[i]) for (ll j = i; j < N; j += i)
if (!lp[j]) lp[j] = i;
mob[i] = [](ll x) {
ll cnt = 0;
while (x > 1) {
ll k = 0, d = lp[x];
while (x % d == 0) {
x /= d;
++k;
if (k > 1) return 0;
}
++cnt;
}
if (cnt & 1) return -1;
return 1;
}(i);
}
}
সোমবার, ২৩ আগস্ট, ২০২১
Detect Cycle and Print Cycle in an directed Graph
Problem :
https://leetcode.com/problems/course-schedule-ii/
class Solution {
public:
vector<int>vis;
vector<int>vec[5005];
vector<int> ans;
bool dfsAndReturnCycle(int src)
{
if(vis[src] == 1)
return true;
if(vis[src] == 2)
return false;
vis[src] = 1;
for (const auto& nextNode: vec[src])
{
if(dfsAndReturnCycle(nextNode))
return true;
}
vis[src] = 2;
ans.push_back(src);
return false;
}
vector<int> findOrder(int numCourses, vector<vector<int>>& ar) {
int n=ar.size();
for(int i=0;i<n;i++){
int v=ar[i][0];
int u=ar[i][1];
vec[u].push_back(v);
}
int flag=0;
vis = vector<int>(numCourses+2,0);
for(int i=0;i<numCourses;i++)
{
if(vis[i]==0){
if(dfsAndReturnCycle(i))
{
return {};
}
}
}
reverse(ans.begin(),ans.end());
return ans;
}
};
শুক্রবার, ৩০ এপ্রিল, ২০২১
FREQ2 - Most Frequent Value- Using Mo's Algorithm
You are given a sequence of n integers a0, a1, ..., an-1. You are also given several queries consisting of indices i and j (0 ≤ i ≤ j ≤ n-1). For each query, determine the number of occurrences of the most frequent value among the integers ai, ..., aj.
Mo's Algorithm Related Problem:
1) DQUERY - D-query , 2) FREQ2 - Most Frequent Value , 3) D. Cut and Stick , 4) D. Powerful array , 5) Chef and Graph Queries 6) D. Tree and Queries 7) Sherlock and Inversions
///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sf(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define timesave ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define tz 100005
#define clr0(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
#define space " "
#define yesp cout<<"YES"<<endl;
#define nop cout<<"NO"<<endl;
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
#define flagone(f) cout<<(f?"YES":"NO")<<endl;
#define flagzero(f) cout<<(f?"NO":"YES")<<endl;
int ar[tz],cnt[tz],ans[tz],freq[tz];
struct node
{
int lft,right,index;
};
int mx=0;
node query[tz];
int blockSize=317;
bool cmp(node fst,node scnd)
{
if(fst.lft/blockSize == scnd.lft/blockSize)
{
return fst.right/blockSize < scnd.right/blockSize;
}
return fst.lft<scnd.lft;
}
void addValue(int pos)
{
cnt[ar[pos]]++;
freq[cnt[ar[pos]]]++;
mx=max(mx,cnt[ar[pos]]);
}
void removeValue(int pos)
{
freq[cnt[ar[pos]]]--;
if(freq[cnt[ar[pos]]]==0)
mx--;
cnt[ar[pos]]--;
}
main()
{
timesave;
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
int n,q,a,b;
sf2(n,q);
for(int i=0; i<n; i++)
{
sf(ar[i]);
}
for(int i=0; i<q; i++)
{
sf2(a,b);
query[i].lft=a;
query[i].right=b;
query[i].index=i;
}
sort(query,query+q,cmp);
int leftPointer = 0,rightPointer=0;
for(int i=0; i<q; i++)
{
int leftValue = query[i].lft;
int rightValue = query[i].right;
int queryIndex = query[i].index;
while(leftPointer<leftValue)
{
removeValue(leftPointer);
leftPointer++;
}
while(leftPointer>leftValue)
{
addValue(leftPointer-1);
leftPointer--;
}
while(rightPointer<=rightValue)
{
addValue(rightPointer);
rightPointer++;
}
while(rightPointer>rightValue+1)
{
removeValue(rightPointer-1);
rightPointer--;
}
ans[query[i].index]=mx;
//cout<<leftValue<<" "<<rightValue<<" "<<mx<<endl;
}
for(int i=0; i<q; i++)
{
printf("%d\n",ans[i]);
}
}
সোমবার, ৯ নভেম্বর, ২০২০
Dhaka Regional ACM ICPC 2016 Preleminary Contest Solution
F. Counter RMQ
#include<bits/stdc++.h>
using namespace std;
int main()
{
int ts,cs=1;
cin>>ts;
while(ts--)
{
int n,q,ar[20005]={0},i,j,a,b,x;
cin>>n>>q;
for(i=1;i<=q;i++)
{
cin>>a>>b>>x;
for(j=a;j<=b;j++)
{
ar[j]=max(ar[j],x);
}
}
printf("Case %d:",cs++);
for(i=1;i<=n;i++)
{
if(ar[i]==0)
{
ar[i]=20000;
}
cout<<" "<<ar[i];
}
cout<<endl;
}
return 0;
}
I. Gadgets of Tomishu
#include <bits/stdc++.h>
#define sf1(a) scanf("%ld",&a)
#define sf2(a,b) scanf("%ld%ld",&a,&b);
#define sf3(a,b,c) scanf("%ld%ld%ld",&a,&b,&c);
using namespace std;
main()
{
long ts,cs=1;
sf1(ts);
while(ts--)
{
long long i,ans,ar[100010]={0};
long long n,k,mod;
cin>>n>>k>>mod;
//ar[0]=k%mod;
ar[1]=((k%mod)*(k%mod))%mod ;
ar[2]= ((ar[1]%mod) * (k%mod));
for(i=3;i<=n;i++)
{
ar[i]=((ar[i-1]%mod) * (ar[i-2]%mod))%mod;
//cout<<ar[i]<<" "<<ar[i-1]<<" "<<ar[i-2]<<endl;
}
ans=ar[n];
printf("Case %ld: %lld\n",cs++,ans);
}
}
Factorization with prime Sieve
vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); ...
-
#include<bits/stdc++.h> using namespace std; main() { long long n,m; while(cin>>n>>m) { if(m==...
-
Input : n = 5, m = 100 Output : 8 The numbers with odd factors are 9, 16, 25, 36, 49, 64, 81 and 100 Input : n = 8, m = 65 Output : 6 ...
-
#include<bits/stdc++.h> using namespace std; vector<long long>vec; void calc() { long i,i1,i2,i3; for(i=0;i<31...