The goal is to count the same objects with both left and write parts of the expression. The thing is that the formula is symmetric with respect to $$$(n,m)$$$ so the objects should be symmetric as well. I propose to count the following objects: grids of size $$$n\times m$$$ which cells are colored into black and white while each row and column contains at least one black cell. It is clear that such objects are symmetric, since we can rotate each grid by $$$90$$$ degrees and get a grid of size $$$m\times n$$$.

First, let's consider grids that may have zero black cells in the columns but have at least one black cell in the rows. We can color a certain row in $$$2^{m}-1$$$ ways, since each number in the range $$$[1, 2^m)$$$ responds for the distinct coloring in its binary representation with at least one black cell. As we are not interested about the columns, we may count each row independently and get $$$(2^m-1)^n$$$ such grids.

However, it isn't that easy to get rid of those completely white columns. One of the ways to do that is to use inclusion-exclusion principle. In the $$$k^\text{th}$$$ term we count the number of grids that have at least $$$k$$$ completely white columns, what means that some of the columns must be fixed and contain zero black cells. We can fix them in $$$\binom{m}{k}$$$ ways. Now we have the same problem but with the grid of size $$$n\times(m-k)$$$ and we can apply our previous formula.

At last we get the formula $$$\displaystyle \sum_{k=0}^{m}(-1)^k\binom{m}{k}(2^{m-k}-1)^n$$$ for counting the desired grids.

We may count the same objects with by fixing completely white rows and get the left part of the formula.

From my proof we see what objects does that formula counts. Moreover, I found two more types of objects counted by that expression:

If you have other objects counted by this formula, feel free to share about them in the comments.

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]<<' ';
}