My code Tle's for this problem but I am sure about the complexity. Here's my code --

#include "bits/stdc++.h"
using namespace std;
#define lli long long
#define gc getchar_unlocked
#define MAX 10000001
bool vv[MAX];
int len, sp[MAX];
int dp[MAX];
map<int, map<lli,lli> >  dpsum;
vector<pair<lli, lli> > v[4*MAX];

void scanint(int &x)
{
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
void Sieve(){
    for (int i = 2; i < MAX; i += 2) sp[i] = 2;//even numbers have smallest prime factor 2
    for (lli i = 3; i < MAX; i += 2){
    if (!vv[i]){
    sp[i] = i;
    for (lli j = i; (j*i) < MAX; j += 2){
    if (!vv[j*i]) vv[j*i] = true, sp[j*i] = i;
    }
    }
    }
}

void build(int node, int l, int r)
{
    if(l > r)return;
    for(int i = l; i <= r; i++)
    {
        v[node].push_back(make_pair((lli)dp[i], (lli)i));
    }
    sort(v[node].begin(), v[node].end());
    dpsum[node][0] = v[node][0].second*v[node][0].first;
    for(int i = 1; i < v[node].size(); i++)
    {
        dpsum[node][i] = dpsum[node][i-1] + v[node][i].first*v[node][i].second;
    }
    if(l==r)return;
    build(node*2, l, (l+r)/2);
    build(node*2+1, (l+r)/2+1, r);
}

lli query(int node, int L, int R, int l, int r, int k)
{
    if(l > R || r < L || L > R)return 0;
    if(L >= l && R <= r)
    {
        int idx = lower_bound(v[node].begin(), v[node].end(), make_pair((lli)k+1,(lli)0)) - v[node].begin();
        lli sum = 0;
        int tt = v[node].size()-1;
        sum = dpsum[node][tt] - dpsum[node][idx-1];
        return sum;
    }
    lli aa = query(node*2, L, (L+R)/2, l, r, k);
    lli bb = query(node*2+1, (L+R)/2+1, R, l, r, k);
    return (aa+bb);
}

int main()
{
    Sieve();
    
    int n, q;
    
    scanint(n);
    scanint(q);
    
    int a[n+1];
    for(int i = 1; i <= n; i++)
        scanint(a[i]);
        
    map<int, int> ss;
    
    for(int i = 1; i <= n; i++)
    {
        int temp = a[i];
        while(temp > 1)
        {
            if(ss[sp[temp]] == 0){
            dp[i] += sp[temp];ss[sp[temp]]=1;}
            temp = temp/sp[temp];
        }
        ss.clear();
    }
    
    build(1, 1, n);
    while(q--)
    {
        int l, r, k;
        scanint(l);scanint(r);scanint(k);
        printf("%lld\n",query(1, 1, n, l, r, k));
    }
    return 0;
}

I am doing this question but i am only able to pass 36/60 test cases i can't find my mistake in code . here's my code -

int dp[104+1][104+1][605];
class Solution {
public:
int dd=0;
int freq[602][2];

    int findMaxForm(vector<string>& strs, int m, int n)
    {
        
        for(int i = 0; i <= m; i++)
        {
            for(int j = 0; j <= n; j++)
            { 
                for(int k = 0; k <= 604; k++)
                    dp[i][j][k] = -1;
            }
        }
        memset(freq, 0, sizeof freq);
        
        for(int i = 0; i < strs.size(); i++)
        {
            for(int j = 0; j < strs[i].length(); j++)
            {
               freq[i][strs[i][j] - '0']++; 
            }
        }
       return letsee(m, n, strs.size(),0);
    }
    
    int letsee(int m, int n, int len, int state)
    {
        // cout << m << " " << n << " "<<state<<"*"
        if(m == 0 && n == 0)return 0;
        if(m < 0 && n < 0)
            return -1;
        if(dp[m][n][state] != -1)
            return dp[m][n][state];
        for(int i = 0; i < len; i++)
        {
            if(m >= freq[i][0] && n >= freq[i][1])
            {
                int temp = freq[i][0];
                int temp2 = freq[i][1];
                freq[i][0] = freq[i][1] = 1000000000;
                dp[m][n][state] = max(letsee(m-temp, n-temp2, len, i+1)+1, dp[m][n][state]);
                freq[i][0] = temp; 
                freq[i][1] = temp2;
            }
        }
        if(dp[m][n][state] == -1)dp[m][n][state] = 0;
        // if(dp[m][n][state] == 5)return 4;
        return dp[m][n][state];
    }
};

I am doing this question I implemented it using rolling hash like for each position calculating the hash considering the string begins at that position and ends at one position back. But the problem coming is when i take mod with 1000000007 the hash value changes so i can't compare now between hashes as the value itself is changed so does anyone has a different idea?

here's my code —

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define MOD 1000000007
ll pw[10010];

ll pwr(ll base, ll p, ll mod){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}
ll modularInverse(ll a,ll m) { return pwr(a,m-2,m); }
int main()
{
    ios_base::sync_with_stdio(false);
    int t;
    cin >> t;
    
    pw[0] = 1;
    for(int i=1; i<=10010; i++)
        pw[i] = (pw[i-1]*31)%MOD;
    
    while(t--)
    {
        string s;
        cin >> s;
        ll cumu[10010];
        memset(cumu, 0, sizeof cumu);
        for(int j = 0; j < s.length(); j++)
        {
            if(j != 0)
                cumu[j] = (cumu[j-1] + (s[j]-'a'+1)*pw[j])%MOD;
            else
                cumu[j] = s[j]-'a'+1;
        }
        
        pair<int, int> a[s.length() + 1];
        
        for(int j = 0; j < s.length(); j++)
        {
          ll sum = cumu[s.length()-1] - ((j-1)>0?cumu[j-1]:0);
        //   cout << sum <<" ";
          if(j-1 < 0){a[j] = make_pair(sum, j);continue;}
             sum = (sum*modularInverse(pw[j],MOD))%MOD; 
            //  cout << sum <<" ";
          sum = (sum + cumu[j-1]*pw[s.length()-j])%MOD;
          a[j] = make_pair(sum, j);
        }
        sort(a, a + s.length());
        // for(int i = 0; i < s.length(); i++)
            cout << a[0].second + 1 << "\n";
    }
    return 0;
}

In this question isn't it enough to check the gcd(A,B) divisibility with each number? i am getting wrong answer!

code--

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//utility function to find the GCD of two numbers
ll gcd(ll a, ll b)
{
    return (a%b == 0)? abs(b) : gcd(b,a%b);
}
 
int main() {
	// your code goes here
	int t;
	cin >> t;
	while(t--)
	{
	    ll n, x, y;
	    cin >> n >> x >> y;
	    ll gdc = gcd(x,y);
	    ll a[n+1];
            ll c  =0;
	    for(int i = 0; i < n; i++)
	    {
	        cin >> a[i];
	        if((a[i]%gdc == 0))
	        c++;
	        
	        
	    }
	    cout << c << " " << n-c << "\n";
	    
	}
	return 0;
}

I was reading about algorithms to find LCS in O(nlogn) and i came through this research paper — link

It claims to find LCS in O((n+r)logn) where r are the number of matching pairs.

But I can't understand how the final algorithm is O(n+rlogn) , I guess the algorithm is O(n*r*logn) ,please clear my doubt I can't understand?

here's my code —

#include "bits/stdc++.h"
using namespace std;
char a[50001];
char b[50001];
int thresh[50001];
int freq[27];
int freq1[27][50001];

int main()
{
	scanf("%s",a+1);
	scanf("%s",b+1);
	
	int c = 0 ;
	for(int i = strlen(b+1); i >= 1; i--)
	{
		freq1[b[i]-'a'][freq[b[i]-'a']] = i;
		freq[b[i]-'a']++;
	}
	
	fill(thresh,thresh+max(strlen(a+1)+1,strlen(b+1)+1),10000000);
	thresh[0] = 0;
	
	int N = max(strlen(a+1)+1,strlen(b+1)+1);
	
	for(int i = 1; i <= strlen(a+1); i++)
	{
		for(int j = 0; j < freq[a[i] - 'a']; j++)
		{
			int k = lower_bound(thresh,thresh + N, freq1[a[i] - 'a'][j]) - thresh;
			if(freq1[a[i] - 'a'][j] < thresh[k])
			{
				thresh[k] = freq1[a[i] - 'a'][j];
			}
		}}
	
	int max1 = -1;
	for(int i = 0; i < N; i++){
		if(thresh[i] != 10000000)
			max1 = max(max1, thresh[i]);
	}
	printf("LCS is \n");
	printf("%d",max1);
	return 0;
}

If i have an update condition like if i want to assign all elements in range (l,r) with a value x(x!=0) and i have many updates like this , for example —

l r x

1 4 2

3 4 3

7 8 9

now if i want to query for an index y , then can i do this using BIT? I have come up with this solution but it isn't working —

update(l, x)

update(r+1, 0) #0 means index still unassigned.

now if i query for like index 4(read(4) — read(4-1)) i am not getting the correct answer. Is my approach correct ?

Hi! Codeforces community

Recently I was searching for a scraper for Codeforces code's but I didn't found one so I made my own.

It scrapes out all your Accepted codes from your profile and stores them in your working directory.The file name for your code will be of format ContestId-ProblemId , for example a code of contest 531 and id 15397405 will be stored as 531-15397405 .

The dependency are mentioned on github.

https://github.com/SuryanshTiwari/Beautiful-Scrape.

Any issues related to the code will be appreciated.

Edit: to enhance readability now the format of file name will be ContestId-ProblemCategory , for example problem B of contest 631 will be stored as 631-B .

Hi codeforces community!

I have made a blog which will be about computer vision stuff.

I have currently written about edge detection and will keep on posting new things I come through in Computer Vision.

If you find any discrepancy in my article then please inform me and I will try correcting it.

blog link

Thank you!

I am new to Topcoder and when i click on practice rooms a dropdown menu appears which is only displaying 3 single round matches , how to access all srms?

Yesterday I was doing c ladder on ahmed-aly and I decided to try a new thing. I clicked on my account and I changed my handle from t3rminated to I_love_Tanya_Romanova(no bad intentions bohdan :) ) and what I saw that I unlocked the first 76 problems.

I think that its a bug.

P.s. I Changed back my handle to -NE0- :)

I was solving this its problem on perfect matching in a graph.I have to tell whether a graph can be perfect matched.I used tutte matrix and Gaussian elimination method to find whether a perfect matching exists but i don't know why my code doesn't works , please help!

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

#define ll long long
#define mod 10000+7
#define MAX 101
ll r,i,j,k;

ll lcm(ll x,ll y)
{
    ll t;
    while (y != 0)
    {
      t=y;
      y=x%y;
      x=t;
    }
    return x;
}
ll random_number_generator()
{
	// Declare variable to hold seconds on clock.

time_t seconds;

// Get value from system clock and
// place in seconds variable.

time(&seconds);

// Convert seconds to a unsigned
// integer.

srand((unsigned ll) seconds);

// Output random values.

return (rand()+mod) % mod;
}

ll det(ll a[101][101]) /*this code converts mtrix to upper triangle so dterminant can be found by taking product of just diagonal elements*/
{ll l,d1,d2;
 for(i=0;i<r-1;i++)
       {
           for(j=i+1;j<r;j++)
           {
             l=lcm(a[i][i],a[j][i]);
             if(l!=0&&(a[i][i]!=0&&a[j][i]!=0))
             {
               l=(a[i][i]*a[j][i])/l;
               d1=l/a[i][i];
               d2=l/a[j][i];
               a[j][i]=0;
               for(k=i+1;k<r;k++)
               {
                 a[j][k]=(d2*a[j][k])-(d1*a[i][k]);
               }
             }
           }
        }
        ll p =1;
        for(int i = 0 ;i < r; i++)
        {
        	
        	p = (p * a[i][i]+mod)%mod;
        	p = (p * a[i][r-1-i] + mod)%mod;
        }
        return p;
} 

int main(int argc, char const *argv[])
{
	ll t;
	cin >> t;

	while(t--)
	{
		ll n , m;
		cin >> n >> m;

		r=n;
ll a[101][101];

		for(ll i = 0; i <= n; i++)
		{
			for(ll j = 0; j <= n; j++)
				a[i][j] = 0;
		}

		ll rnd = random_number_generator();

		while(m--)
		{
			ll x , y;
			cin >> x >> y;
			x--;y--;
			ll rnd = random_number_generator();

			if(x < y)
				a[x][y] = (rnd);
			else if(x > y)
				a[x][y] = (-rnd);

			a[y][x] = -a[x][y];
		}

		ll dete = det(a);

		if(dete == 0)
			cout << "NO" << endl;
		else
			cout << "YES" << endl;
	}
	return 0;
}