Try to find the upper bound of $$$\gcd(x,y)+y$$$.

$$$\gcd(x,y)+y=\gcd(x-y,y)+y$$$.

$$$\gcd(x,y)+y\le x$$$. Try to find such $$$y$$$, that $$$\gcd(x,y)+y=x$$$?

#include<iostream>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int x;
		cin>>x;
		cout<<x-1<<"\n";
	}
}

• Didn't solve
• Good task
• Average task
• Bad task

Try to check for every $$$k$$$ if the prefix of $$$a$$$ of length $$$k$$$ is a subsequence of $$$b$$$.

#include<iostream>
#include<vector>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		vector<char>a(n+1),b(m+1);
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=1;i<=m;i++){
			cin>>b[i];
		}
		vector<int>dp(m+1);
		dp[1]=(a[1]==b[1]?1:0);
		for(int i=2;i<=m;i++){
			if(dp[i-1]!=n && b[i]==a[dp[i-1]+1]){
				dp[i]=dp[i-1]+1;
			}else{
				dp[i]=dp[i-1];
			}
		}
		cout<<dp[m]<<"\n";
	}
}

• Didn't solve
• Good task
• Average task
• Bad task

Why constraints are small?

Try to think about increacing $$$a_1,\dots,a_n$$$.

$$$((a + b)\bmod a) = b$$$ for $$$0\le b < a$$$.

#include<iostream>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int S=1000;
		cout<<S<<" ";
		for(int i=2;i<=n;i++){
			int x;
			cin>>x;
			S+=x;
			cout<<S<<" ";
		}
		cout<<"\n";
	}
}

• Didn't solve
• Good task
• Average task
• Bad task

Consider a cycle of the permutation.

When it is optimal to stay on the same place till the end of the game?

#include<bits/stdc++.h>
using namespace std;
long long score(vector<int>&p,vector<int>&a,int s,int k){
	int n=p.size();
	long long mx=0,cur=0;
	vector<bool>vis(n);
	while(!vis[s]&&k>0){
		vis[s]=1;
		mx=max(mx,cur+1ll*k*a[s]);
		cur+=a[s];
		k--;
		s=p[s];
	}
	return mx;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,k,s1,s2;
		cin>>n>>k>>s1>>s2;
		vector<int>p(n),a(n);
		for(auto&e:p){
			cin>>e;
			e--;
		}
		for(auto&e:a){
			cin>>e;
		}
		long long A=score(p,a,s1-1,k),B=score(p,a,s2-1,k);
		cout<<(A>B?"Bodya\n":A<B?"Sasha\n":"Draw\n");
	}
}

• Didn't solve
• Good task
• Average task
• Bad task

What is the maximal possible size of $$$\mathcal{H}$$$?

Can you always get that size for $$$n\geq 4$$$?

Consider odd and even distances independently.

Let us find an interesting pattern for $$$n\geq 4$$$.

Can you generalize the pattern? We put $$$n-2$$$ cells on the main diagonal. Then put two cells at $$$(n-1,n)$$$ and $$$(n,n)$$$.

But why does it work? Interesting fact, that in such way we generate all possible Manhattan distances. Odd distances are generated between cells from the main diagonal and $$$(n-1,n)$$$. Even distances are generated between cells from the main diagonal and $$$(n,n)$$$.

#include<iostream>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=1;i<=n-2;i++){
			cout<<i<<' '<<i<<"\n";
		}
		cout<<n-1<<' '<<n<<"\n"<<n<<' '<<n<<"\n";
	}
}

• Didn't solve
• Good task
• Average task
• Bad task

Is it useful to divide the segment into more than three segments?

Use the fact, that $$$x\oplus x=0$$$ and $$$x\oplus x\oplus x=x$$$.

When you can divide the segment into $$$2$$$ parts?

When can you divide the segment into $$$3$$$ parts?

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int a[N];
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,q;
		cin>>n>>q;
		map<int,vector<int>>id;
		id[0].push_back(0);
		for(int i=1;i<=n;i++){
			cin>>a[i];
			a[i]^=a[i-1];
			id[a[i]].push_back(i);
		}
		while(q--){
			int l,r;
			cin>>l>>r;
			if(a[r]==a[l-1]){
				cout<<"YES\n";
				continue;
			}
			int pL=*--lower_bound(id[a[l-1]].begin(),id[a[l-1]].end(),r);
			int pR=*lower_bound(id[a[r]].begin(),id[a[r]].end(),l);
			cout<<(pL>pR?"YES\n":"NO\n");
		}
		if(t)cout << "\n";
	}
}

• Didn't solve
• Good task
• Average task
• Bad task

Binary search.

How to check if two strings are equal?

#include<bits/stdc++.h>
using namespace std;
vector<int>Zfunc(string& str){
	int n=str.size();
	vector<int>z(n);
	int l=0,r=0;
	for(int i=1;i<n;i++){
		if(i<=r){
			z[i]=min(r-i+1,z[i-l]);
		}
		while(i+z[i]<n&&str[z[i]]==str[i+z[i]]){
			z[i]++;
		}
		if(i+z[i]-1>r){
			l=i;
			r=i+z[i]-1;
		}
	}
	return z;
}
int f(vector<int>&z,int len){
	int n=z.size();
	int cnt=1;
	for(int i=len;i<n;){
		if(z[i]>=len){
			cnt++;
			i+=len;
		}else{
			i++;
		}
	}
	return cnt;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,k;
		string s;
		cin>>n>>k>>k>>s;
		vector<int>z=Zfunc(s);
		int l=0,r=n+1;
		while(r-l>1){
			int mid=(l+r)/2;
			if(f(z,mid)>=k){
				l=mid;
			}else{
				r=mid;
			}
		}
		cout<<l<<"\n";
	}
}

• Didn't solve
• Good task
• Average task
• Bad task

Consider the general case: $$$L=1$$$ and $$$R=n$$$.

You must find the answer for each $$$k$$$ in the range $$$[1,n]$$$. Consider the cases $$$k\le \sqrt{n}$$$ and $$$k\geq \sqrt{n}$$$.

#include<bits/stdc++.h>
using namespace std;
vector<int>Zfunc(string& str){
	int n=str.size();
	vector<int>z(n);
	int l=0,r=0;
	for(int i=1;i<n;i++){
		if(i<=r){
			z[i]=min(r-i+1,z[i-l]);
		}
		while(i+z[i]<n&&str[z[i]]==str[i+z[i]]){
			z[i]++;
		}
		if(i+z[i]-1>r){
			l=i;
			r=i+z[i]-1;
		}
	}
	return z;
}
int f(vector<int>&z,int len){
	int n=z.size();
	int cnt=1;
	for(int i=len;i<n;){
		if(z[i]>=len){
			cnt++;
			i+=len;
		}else{
			i++;
		}
	}
	return cnt;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,L,R;
		string s;
		cin>>n>>L>>R>>s;
		vector<int>z=Zfunc(s);
		const int E=ceil(sqrt(n));
		vector<int>ans(n+1);
		for(int k=1;k<=E;k++){
			int l=0,r=n+1;
			while(r-l>1){
				int mid=(l+r)/2;
				if(f(z,mid)>=k){
					l=mid;
				}else{
					r=mid;
				}
			}
			ans[k]=l;
		}
		for(int len=1;len<=E;len++){
			int k=1;
			for(int i=len;i<n;){
				if(z[i]>=len){
					k++;
					i+=len;
				}else{
					i++;
				}
			}
			ans[k]=max(ans[k],len);
		}
		for(int i=n-1;i>=1;i--){
			ans[i]=max(ans[i],ans[i+1]);
		}
		for(int i=L;i<=R;i++){
			cout<<ans[i]<<' ';
		}
		cout<<"\n";
	}
}

• Didn't solve
• Good task
• Average task
• Bad task

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            int x;cin>>x;
            if(x%2!=0)cnt++;
        }
        if(cnt%2==0)cout<<"YES\n";
        else cout<<"NO\n";
    }
}

for i in range(int(input())):
    n=int(input())
    a=[*map(int,input().split())]
    cnt=0
    for i in range(n):
        if a[i]%2!=0:cnt+=1
    if cnt%2==0:print('YES')
    else:print('NO')

• Good task
• Average task
• Bad task
• Didn't solve

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;cin>>t;
    while(t--)
    {
        string s;cin>>s;
        s='0'+s;
        int p=s.size();
        for(int i=s.size()-1;i>=0;i--)
        {
            if(s[i]>='5')s[i-1]++,p=i;
        }
        for(int i=(s[0]=='0');i<s.size();i++)
        {
            cout<<(i>=p?'0':s[i]);
        }
        cout<<"\n";
    }
}

for i in range(int(input())):
    s=[0]+[*map(int,list(input()))]
    k=len(s)
    for i in range(len(s)-1,0,-1):
        if s[i]>4:s[i-1]+=1;k=i
    if s[0]!=0:print(s[0],end='')
    s=[*map(str,s)]
    print(''.join(s[1:k]+['0']*(len(s)-k)))

• Good task
• Average task
• Bad task
• Didn't solve

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        int m=n*(n-1)/2,b[m];
        for(int i=0;i<m;i++)cin>>b[i];
        sort(b,b+m);
        for(int i=0;i<m;i+=--n)cout<<b[i]<<' ';
        cout<<"1000000000\n";
    }
}

for _ in range(int(input())):
    n=int(input())
    l=sorted(map(int,input().split()))
    j=0
    for i in range(n-1,0,-1):
        print(l[j],end=' ')
        j+=i
    print(l[-1])

• Good task
• Average task
• Bad task
• Didn't solve

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int a[N],b[N];
int main()
{
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        int mx=INT_MIN;
        for(int i=1;i<=n;i++)mx=max(mx,a[i]-b[i]);
        int c=0;
        for(int i=1;i<=n;i++)c+=(a[i]-b[i]==mx);
        cout<<c<<"\n";
        for(int i=1;i<=n;i++)if(a[i]-b[i]==mx)cout<<i<<' ';
        cout<<"\n";
    }
}

for _ in range(int(input())):
    n=int(input())
    a=[*map(int,input().split())]
    b=[*map(int,input().split())]
    c=[a[i]-b[i] for i in range(n)]
    mx=max(c)
    ans=[]
    for i in range(n):
        if c[i]==mx:ans.append(i+1)
    print(len(ans))
    print(*ans)

• Good task
• Average task
• Bad task
• Didn't solve

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
pair<int,int>x[N];
long long a[N];
int main()
{
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        long long s1=0,s2=0;
        for(int i=1;i<=n;i++)
        {
            cin>>x[i].first;
            x[i].second=i;
            s2+=x[i].first;
        }
        sort(x+1,x+n+1);
        for(int i=1;i<=n;i++)
        {
            s2-=x[i].first;
            s1+=x[i].first;
            a[x[i].second]=n+1ll*x[i].first*(2*i-n)-s1+s2;
        }
        for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
    }
}

for i in range(int(input())):
    n=int(input())
    a=sorted([(b,i)for i,b in enumerate(map(int,input().split()))])
    ans=[0]*n
    s1=0
    s2=sum(a[i][0] for i in range(n))
    for i in range(n):
        ans[a[i][1]]=s2-a[i][0]*(n-i)+n-i+a[i][0]*i-s1+i
        s1+=a[i][0]
        s2-=a[i][0]
    print(*ans)

• Good task
• Average task
• Bad task
• Didn't solve

#include<bits/stdc++.h>
using namespace std;
map<long long,int>cnt;
long long my_sqrt(long long a)
{
    long long l=0,r=5000000001;
    while(r-l>1)
    {
        long long mid=(l+r)/2;
        if(1ll*mid*mid<=a)l=mid;
        else r=mid;
    }
    return l;
}
long long get(int b,long long c)
{
    long long D=1ll*b*b-4ll*c;
    if(D<0)return 0;
    long long x1=(b-my_sqrt(D))/2;
    long long x2=(b+my_sqrt(D))/2;
    if(x1+x2!=b||x1*x2!=c)return 0;
    if(x1==x2)return 1ll*cnt[x1]*(cnt[x1]-1)/2ll;
    else return 1ll*cnt[x1]*cnt[x2];
}
int main()
{
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        cnt.clear();
        for(int i=1;i<=n;i++)
        {
            int x;cin>>x;
            cnt[x]++;
        }
        int q;cin>>q;
        for(int i=0;i<q;i++)
        {
            int b;long long c;
            cin>>b>>c;
            cout<<get(b,c)<<" \n"[i==q-1];
        }
    }
}

from collections import Counter
from math import sqrt
 
for _ in range(int(input())):
    n=int(input())
    a=[*map(int,input().split())]
    d=Counter(map(str,a))
    for i in range(int(input())):
        x,y=map(int,input().split())
        if x*x-4*y<0:print(0);continue
        D=int(sqrt(x*x-4*y))
        x1=(x+D)//2
        x2=(x-D)//2
        if x1+x2!=x or x1*x2!=y:print(0);continue
        if x1!=x2:print(d[str(x1)]*d[str(x2)])
        else:print(d[str(x1)]*(d[str(x1)]-1)//2)

• Good task
• Average task
• Bad task
• Didn't solve

#include<bits/stdc++.h>
using namespace std;
const int N=200000,mod=998244353;
int p[N+1],sz[N+1];
struct edge
{
    int u,v,w;
    void read(){cin>>u>>v>>w;}
    bool operator<(edge x){return w<x.w;}
}a[N+1];
int leader(int v)
{
    if(p[v]==v)return v;
    else return p[v]=leader(p[v]);
}
void unite(int u,int v)
{
    u=leader(u);
    v=leader(v);
    p[u]=v;
    sz[v]+=sz[u];
}
long long binpow(long long a,long long n)
{
    if(n==0)return 1;
    if(n%2==0)return binpow(a*a%mod,n/2);
    else return a*binpow(a,n-1)%mod;
}
int main()
{
    int t;cin>>t;
    while(t--)
    {
        int n,S;cin>>n>>S;
        for(int i=1;i<=n;i++)p[i]=i,sz[i]=1;
        for(int i=0;i<n-1;i++)a[i].read();
        sort(a,a+n-1);
        long long ans=1;
        for(int i=0;i<n-1;i++)
        {
            int sub_u=sz[leader(a[i].u)];
            int sub_v=sz[leader(a[i].v)];
            ans=ans*binpow(S-a[i].w+1,1ll*sub_u*sub_v-1)%mod;
            unite(a[i].u,a[i].v);
        }
        cout<<ans<<"\n";
    }
}

mod=998244353
def find_(v):
    stack=[v]
    while dsu[v]!=v:
        stack.append(dsu[v])
        v=stack[-1]
    while stack:
        dsu[stack[-1]]=dsu[v]
        v=stack.pop()
    return dsu[v]
 
for i in range(int(input())):
    n,S=map(int,input().split())
    l=[tuple(map(int,input().split()))for i in range(n-1)]
    l.sort(key=lambda x:x[2])
    ans=1
    dsu=[i for i in range(n)]
    coun=[1]*n
    for a,b,c in l:
        a-=1;b-=1
        if find_(a)!=find_(b):
            ans=ans*pow(S-c+1,coun[dsu[a]]*coun[dsu[b]]-1,mod)
            ans%=mod
            coun[dsu[a]]+=coun[dsu[b]]
            coun[dsu[b]]=0
            dsu[b]=dsu[a]
    print(ans)

• Good task
• Average task
• Bad task
• Didn't solve

Greedy

Consider the string $$$s=s_1,\dots,s_n$$$. Suppose $$$s_i$$$ is the first occurence of a letter $$$c$$$ (the string looks $$$s_1,\dots,s_i,\dots,s_n$$$). If we output $$$c$$$, the problem reduces to $$$s=s_{i+1},\dots,s_n$$$. The number of such outputs must be minimalized.

Observation: the largest $$$i$$$ we choose, the smallest string we obtain.

Greedy solution is always to take the largest $$$i$$$ such that $$$s_i$$$ is the first occurence. But after this traversal, the string we output is still a subsequence of $$$s$$$, so we need to output one more letter.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;cin>>s;
    map<char,bool>used;
    for(auto&c:s)
    {
        used[c]=1;
        if(used.size()==4)
        {
            cout<<c;
            used.clear();
        }
    }
    if(!used['A'])cout<<'A';
    else if(!used['C'])cout<<'C';
    else if(!used['G'])cout<<'G';
    else cout<<'T';
}

BFS

The number of permutations of the grid is $$$9!=362880$$$. We can precalculate the answer for each case.

Let's make a graph, where each vertex is a grid. And there will be an edge between vertices $$$A$$$ and $$$B$$$, if we can make one operation on $$$A$$$ and get $$$B$$$.

The answer for

is obviously $$$0$$$.

We can run BFS starting from this grid and get all the answers.

In practice, we can maintain each grid as an integer. For example the starting grid is $$$123456789$$$. Notice that we can still maintain the required operations using the integer.

#include<bits/stdc++.h>
using namespace std;
int pw[10];
int get(int x,int i)
{
    return x/pw[i]%10;
}
int f(int x,int i,int j)
{
    i=9-i,j=9-j;
    int di=get(x,i),dj=get(x,j);
    return x+pw[j]*(di-dj)+pw[i]*(dj-di);
}
int main()
{
    pw[0]=1;
    for(int i=1;i<10;i++)pw[i]=pw[i-1]*10;
    unordered_map<int,int>d;
    queue<int>q;
    q.push(123456789);
    d[123456789]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=1;i<=8;i++)
        {
            if(i%3==0)continue;
            int y=f(x,i,i+1);
            if(d.find(y)==d.end())
            {
                d[y]=d[x]+1;
                q.push(y);
            }
        }
        for(int i=1;i<=6;i++)
        {
            int y=f(x,i,i+3);
            if(d.find(y)==d.end())
            {
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }
    int x=0;
    for(int i=8;i>=0;i--)
    {
        int a;cin>>a;
        x+=pw[i]*a;
    }
    cout<<d[x]<<"\n";
}

Tree theory

Let's define the Prüfer Code as $$$P=p_1,\dots,p_{n-2}$$$.

Feature of the Prüfer Code: if the given tree is $$$G$$$, and its Prüfer Code is $$$p_1,\dots,p_{n-2}$$$, after removing the leaf from $$$G$$$ with the smallest label, the code will be $$$p_2,\dots,p_{n-2}$$$.

That means, that after removing the leaf, we get the same problem with smaller Prüfer Code.

The integers that are missing in $$$P$$$ are leaves. Thats because the Prüfer Code is constructed is such a way, that it never contains the leaves of the tree.

Suppose we are proccessing $$$p_i$$$. There exist two cases:

1. We take the leaf with the smallest label that is connected with $$$p_i$$$ and delete the it.
2. We take the leaf with the smallest label that is connected with $$$p_i$$$ and delete the it. After what $$$p_i$$$ becomes a leaf.

In the second case $$$p_i$$$ becomes a leaf if $$$p_{i+1},\dots,p_{n-2}$$$ does not contain $$$p_i$$$. It follows from the feature.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;cin>>n;
    vector<int>p(n-2),cnt(n+1);
    for(auto&x:p)
    {
        cin>>x;
        cnt[x]++;
    }
    set<int>leaves;
    for(int v=1;v<=n;v++)
    {
        if(cnt[v]==0)leaves.insert(v);
    }
    for(auto&x:p)
    {
        auto it=leaves.begin();
        cout<<*it<<' '<<x<<"\n";
        leaves.erase(it);
        if(--cnt[x]==0)leaves.insert(x);
    }
    cout<<*leaves.begin()<<' '<<*leaves.rbegin()<<"\n";
}

Graph theory

I assume, that if all the edges are directed from smaller vertex to largest one, the graph is acyclic.

Proof:

Suppose, such graph consists a cycle.

$$$a_1,\dots,a_n$$$ is a subset of vertices which forms a cycle.

$$$a_1 < a_2 < a_3< \dots <a_n < a_1$$$, because we construct the graph in such way. As you can notice, this expression is impossible.

#include<iostream>
using namespace std;
int main()
{
    int n,m;cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v;cin>>u>>v;
        if(u>v)swap(u,v);
        cout<<u<<' '<<v<<"\n";
    }
}

Binary search

Let $$$F(k)$$$ is the amount of integers in the table with values $$$\le k$$$.

To calculate this function we can proccess each row seperately. $$$x$$$-th row contains integers $$$x,2x,\dots,nx$$$. There are $$$\min(n,\lfloor\frac{k}{x}\rfloor)$$$ integers from this list which are not greater than $$$k$$$.

To get the answer we need to find such maximal $$$k$$$, that $$$F(k)\le \lceil{\frac{n^2}{2}}\rceil$$$. Notice, the function is non-decreasing, hence we can use binary search.

#include<iostream>
typedef long long ll;
using namespace std;
ll n;
bool F(ll k)
{
    ll s=0;
    for(int x=1;x<=n;x++)s+=min(n,k/x);
    return s<n*n/2+1;
}
int main()
{
    cin>>n;
    ll l=1,r=n*n;
    while(r-l>1)
    {
        ll mid=(l+r)/2;
        if(F(mid))l=mid;
        else r=mid;
    }
    cout<<r<<"\n";
}

Monotonic stack

Let's fix the height of the rectangular. The high can be any of the boards, so let's consider $$$k_i (1\le i\le n)$$$.

The idea is that we can extend this rectangular to the left and right, while the heights are not less than $$$k_i$$$. Formally, the problem is to find:

1. The minimal $$$l$$$, that $$$1\le l\le i$$$ and $$$\min(k_l,\dots,k_i)\ge k_i$$$.
2. The maximal $$$r$$$, that $$$i\le r \le n$$$ and $$$\min(k_i,\dots,k_r)\ge k_i$$$.

If we found such $$$l,r$$$ for fixed $$$i$$$, the area of the rectangular is $$$k_i \cdot (r-l+1)$$$.

Let's maintain a stack which contains the positions $$$p_1,\dots,p_m$$$ such that $$$k_{p_1} \le \dots, \le k_{p_m}$$$. When we want to push $$$i$$$ to the stack, the condition of monotonic elements must be still met. So we need to pop the elements from the stack while $$$k_i \le k_{p_m}$$$. The advantage of such stack is that after erasing the positions, $$$k_{p_m}$$$ will always be the first element less than $$$k_i$$$. So the $$$l$$$ we need in the problem is $$$p_m+1$$$.

The idea of finding $$$r$$$ is symmetric.

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int k[N],l[N],r[N];
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>k[i];
    stack<int>s;
    for(int i=1;i<=n;i++)
    {
        while(!s.empty()&&k[s.top()]>=k[i])s.pop();
        if(s.empty())l[i]=1;
        else l[i]=s.top()+1;
        s.push(i);
    }
    while(!s.empty())s.pop();
    for(int i=n;i>=1;i--)
    {
        while(!s.empty()&&k[s.top()]>=k[i])s.pop();
        if(s.empty())r[i]=n;
        else r[i]=s.top()-1;
        s.push(i);
    }
    long long mx=0;
    for(int i=1;i<=n;i++)mx=max(mx,1ll*k[i]*(r[i]-l[i]+1));
    cout<<mx<<"\n";
}

Prefix sums

Suppose, the string contains the characters $$$c_1,c_2,\dots,c_k$$$. The first idea is to make $$$k$$$ prefix sums, where each of them responds for each character.

Now the substring $$$[l,r]$$$ is special iff $$$P_{r,ch}-P_{l-1,ch}$$$ is equal to $$$x$$$ where $$$ch$$$ is one of $$$c_1,\dots,c_k$$$.

Notice that if the string is special, than all the elements from $$$P_r$$$ are not less than $$$x$$$. So let's substract $$$x$$$ from $$$P_r$$$. The problem is, that we have no $$$x$$$, but we can substract the minimal value from $$$P_r$$$, bacause it is the largest $$$x$$$ we can choose.

The task is reduced to finding the number of such $$$1\le l\le r\le n$$$, that $$$P_r=P_{l-1}$$$, what can be done in $$$O(n\cdot k)$$$ time.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;cin>>s;
    map<char,int>h;
    int k=0;
    for(auto&c:s)
    {
        if(!h.count(c))h[c]=k++;
    }
    map<vector<int>,int>cnt;
    vector<int>P(k);
    cnt[P]=1;
    long long ans=0;
    for(auto&c:s)
    {
        P[h[c]]++;
        int mx=*max_element(P.begin(),P.end());
        for(auto&a:P)a-=mx;
        ans+=cnt[P]++;
    }
    cout<<ans<<"\n";
}

Trie, Bitmasks

At first, let's construct new array $$$a$$$ where $$$a_i=a_{i-1}\oplus x_i$$$. Now $$$x_l \oplus \dots \oplus x_r$$$ is equal to $$$a_r \oplus a_{l-1}$$$.

We can add the integers to a list and for each $$$a_r$$$ find optimal $$$a_{l-1}$$$. It can be done using Trie. It will contain integers in binary representation from the most significant bit.

Suppose we process $$$k$$$-th bit of $$$a_r$$$. If the trie contain the oposite bit from $$$k$$$-th, we can go to that subtree and improve the answer (because their xor gives $$$1$$$). Such improvement leads to correct answer because number comparison depends on the most significant bit.

#include<iostream>
using namespace std;
const int N=200005;
int T[N*30][2],t;
void upd(int x)
{
    for(int k=29,v=0;k>=0;k--)
    {
        bool c=(x>>k)&1;
        if(!T[v][c])T[v][c]=++t;
        v=T[v][c];
    }
}
int get(int x)
{
    int ans=0;
    for(int k=29,v=0;k>=0;k--)
    {
        bool c=(x>>k)&1;
        if(T[v][c^1])ans|=1<<k,v=T[v][c^1];
        else v=T[v][c];
    }
    return ans;
}
int main()
{
    int n;cin>>n;
    int x=0,mx=0;
    upd(x);
    for(int i=1,a;i<=n;i++)
    {
        cin>>a;
        x^=a;
        mx=max(mx,get(x));
        upd(x);
    }
    cout<<mx<<"\n";
}

Binary jumping

The greedy solution is to jump to the nearest end of the movie everytime while it possible. So let's generalize this idea.

Consider a function $$$up(k,i)$$$ returns the position $$$j$$$, when we do $$$2^k$$$ greedy jumps from position $$$i$$$.

The transitions are:

because the jump of length $$$2^k$$$ can be represented as two smaller jumps of length $$$2^{k-1}$$$.

To find the answer for a query $$$[l,r]$$$ we can start from the largest $$$k$$$ trying to make the longest jump and still be in the range. And if it is possible we perform this jump and add to the answer $$$2^k$$$.

In practice, it is better to do it backwards, jumping from $$$r$$$ to $$$l$$$. The problems are equal but the implementation is a bit easier.

#include<bits/stdc++.h>
using namespace std;
const int maxB=1000002;
int up[18][maxB];
int main()
{
    int n,q;cin>>n>>q;
    for(int i=0;i<n;i++)
    {
        int l,r;cin>>l>>r;
        up[0][r]=max(up[0][r],l);
    }
    for(int i=2;i<maxB;i++)
    {
        up[0][i]=max(up[0][i],up[0][i-1]);
    }
    for(int k=1;k<18;k++)
    {
        for(int i=1;i<maxB;i++)
        {
            up[k][i]=up[k-1][up[k-1][i]];
        }
    }
    while(q--)
    {
        int l,r;cin>>l>>r;
        int ans=0;
        for(int k=17;k>=0;k--)
        {
            if(up[k][r]>=l)
            {
                ans|=(1<<k);
                r=up[k][r];
            }
        }
        cout<<ans<<"\n";
    }
}

Bright mind

We trace the work of Euclid's algorithm for two coprime integers $$$a,b$$$

by writing '1' to a string if the second case and '0' in the third case. For example, for $$$a, b = 7, 5$$$, the string is $$$1001$$$. We denote this string by $$$trace(a,b)$$$.

Let us examine the construction of $$$trace(a,b)$$$ in terms of a number of distinct subsequences. By symmetry, we can only consider $$$cnt_1(trace(a,b)) = $$$ the number of distinct subsequences starting with $$$1$$$ (including empty string $$$\varnothing$$$) in $$$trace(a,b)$$$. We have

Taking $$$cnt_1(\varnothing)=cnt_0(\varnothing)=1$$$, we inductively obtain $$$cnt_1(trace(a,b))=a$$$ and $$$cnt_0(trace(a,b))=b$$$. So, the number of distinct subsequences in $$$trace(a,b)$$$ is $$$a+b-1$$$.

On the other hand, we can easily see that any binary string can be written via $$$trace(a,b)$$$ for some $$$a,b$$$ (just perform the algorithm backwards). Therefore, we have a bijection the set of binary strings with exactly $$$n$$$ subsequences (including the empty one) and the set of binary strings generated by $$$trace(a,b)$$$ for $$$a+b-1=n$$$.

The solution to the problem is easy now if one notices that we can iterate over the strings with exactly $$$n$$$ distinct subsequences. Go over $$$a$$$ and take $$$b=n-a+1$$$, then request $$$(a,b)=1$$$ and obtain $$$(a,n+1)=1$$$. In other words, the algorithm is the following.

1. Increment $$$n$$$ by 1 (to eliminate empty substring).
2. Iterate over $$$a$$$ coprime with $$$n+1$$$.
3. Take $$$b=n-a+1$$$ and relax $$$trace(a,b)$$$.

#include<bits/stdc++.h>
using namespace std;
string trace(int a,int b)
{
    if(a==b)return "";
    else if(a>b)return '1'+trace(a-b,b);
    else return '0'+trace(a,b-a);
}
int trace_len(int a,int b)
{
    if(a==b)return 0;
    else if(a>b)return 1+trace_len(a-b,b);
    else return 1+trace_len(a,b-a);
}
int main()
{
    int n;cin>>n;
    int b,mn=++n;
    for(int a=1;a<=n+1;a++)
    {
        if(__gcd(a,n+1)!=1)continue;
        int len=trace_len(a,n-a+1);
        if(len<mn)mn=len,b=n-a+1;
    }
    cout<<trace(n-b+1,b)<<"\n";
}

Greedy

See example 2 in.

FFT

First of all, we evaluate $$$p_n = $$$ the number of ones among $$$s_1, \dots, s_{n - 1}$$$ and $$$p_0 = 0$$$. Then, the naїve algorithm is the following:

1. iterate $$$i, j$$$ over $$$0, 1, 2, \dots, n$$$ and increment $$$cnt[p_i - p_j]$$$,
2. output $$$(cnt[0] - (n+1))/2$$$ (because we counted $$$i=j$$$ and $$$i\neq j$$$ twice) and $$$cnt[1], \dots, cnt[n]$$$.

The complexity of this algorithm is $$$O(n^2)$$$, which is not fast enough to solve the problem. Instead, we shall do the trick.

Consider the following expression

and it can be easily seen that the coefficient at $$$x^{k}$$$ is the number of pairs $$$(i, j)$$$ such that $$$p_i-p_j=k$$$, that is $$$cnt[k]$$$. As $$$p_n$$$ is the largest among $$$p_1,\dots,p_n$$$, we can make the second factor a polynomial multiplying the whole expression $$$P_{aux}$$$ by $$$x^{p_n}$$$

Then we multiply these two polynomials using FFT, and output the desired coefficients with respect to our shift by $$$x^{p_n}$$$.

#include<bits/stdc++.h>
using namespace std;
namespace FFT
{
    typedef complex<double>base;
    double PI=acos(-1);
    void fft(vector<base>&a,bool invert)
    {
        int n=a.size();
        for(int i=1,j=0;i<n;i++)
        {
            int bit=n>>1;
            for(;j>=bit;bit>>=1)j-=bit;
            j+=bit;
            if(i<j)swap(a[i],a[j]);
        }
        for(int len=2;len<=n;len<<=1)
        {
            double ang=2*PI/len*(invert?-1:1);
            base wlen(cos(ang),sin(ang));
            for(int i=0;i<n;i+=len)
            {
                base w(1);
                for(int j=0;j<len/2;j++)
                {
                    base u=a[i+j],v=a[i+j+len/2]*w;
                    a[i+j]=u+v;
                    a[i+j+len/2]=u-v;
                    w*=wlen;
                }
            }
        }
        if(invert)
        {
            for(int i=0;i<n;i++)a[i]/=n;
        }
    }
    vector<long long>multiply(vector<int>&a,vector<int>&b)
    {
        vector<base>fa(a.begin(),a.end()),fb(b.begin(),b.end());
        int n=1;
        while(n<max(a.size(),b.size()))n<<=1;
        n<<=1;
        fa.resize(n),fb.resize(n);
        fft(fa,0),fft(fb,0);
        for(int i=0;i<n;i++)fa[i]*=fb[i];
        fft(fa,1);
        vector<long long>res;
        res.resize(n);
        for(int i=0;i<n;i++)res[i]=(long long)(fa[i].real()+0.5);
        return res;
    }
};
int main()
{
    string s;cin>>s;
    int n=s.size();
    vector<int>p(n+1),a(n+1),b(n+1);
    for(int i=1;i<=n;i++)p[i]=p[i-1]+s[i-1]-'0';
    for(int i=0;i<=n;i++)a[p[i]]++;
    for(int i=0;i<=n;i++)b[p[n]-p[i]]++;
    auto Paux=FFT::multiply(a,b);
    cout<<(Paux[p[n]]-(n+1))/2<<' ';
    for(int i=p[n]+1;i<=p[n]+n;i++)cout<<Paux[i]<<' ';
}