struct minstack {
	stack<pair<int, int>> st;
	int getmin() {return st.top().second;}
	bool empty() {return st.empty();}
	int size() {return st.size();}
	void push(int x) {
		int mn = x;
		if (!empty()) mn = min(mn, getmin());
		st.push({x, mn});
	}
	void pop() {st.pop();}
	int top() {return st.top().first;}
	void swap(minstack &x) {st.swap(x.st);}
};

struct mindeque {
	minstack l, r, t;
	void rebalance() {
		bool f = false;
		if (r.empty()) {f = true; l.swap(r);}
		int sz = r.size() / 2;
		while (sz--) {t.push(r.top()); r.pop();}
		while (!r.empty()) {l.push(r.top()); r.pop();}
		while (!t.empty()) {r.push(t.top()); t.pop();}
		if (f) l.swap(r);
	}
	int getmin() {
		if (l.empty()) return r.getmin();
		if (r.empty()) return l.getmin();
		return min(l.getmin(), r.getmin());
	}
	bool empty() {return l.empty() && r.empty();}
	int size() {return l.size() + r.size();}
	void push_front(int x) {l.push(x);}
	void push_back(int x) {r.push(x);}
	void pop_front() {if (l.empty()) rebalance(); l.pop();}
	void pop_back() {if (r.empty()) rebalance(); r.pop();}
	int front() {if (l.empty()) rebalance(); return l.top();}
	int back() {if (r.empty()) rebalance(); return r.top();}
	void swap(mindeque &x) {l.swap(x.l); r.swap(x.r);}
};

There is no need to take segments, we can go with whole array.

If all elements are equal to $$$0$$$, we don't need to do anything, so the answer is $$$0$$$.

If there is any bit $$$\leq k$$$ which is set to $$$0$$$ for all $$$a_i$$$, then answer will be $$$1$$$.

If $$$k$$$ is $$$1$$$, then answer is $$$−1$$$, in all other cases answer is $$$2$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    int t;
    cin>>t;
    while(t--){
        int n,x;
        cin>>n>>x;
        vector<int> a(n);
        for(int i=0;i<n;i++) cin>>a[i];
        int cnt=count(a.begin(),a.end(),0);
        if(cnt==n) cout<<0<<endl;
        else if(x==1){
            for(int i=0;i<n;i++) a[i]=a[i]&1;
            int cnt=count(a.begin(),a.end(),0);
            if(cnt==n) cout<<1<<endl;
            else cout<<-1<<endl;
        }
        else{
            bool ok=false;
            for(int i=0;i<31;i++){
                int cnt=0;
                for(int j=0;j<n;j++){
                    if((a[j]&(1<<i))==0) cnt++;
                }
                if(cnt==n && x>=(1<<i)){
                    ok=true;
                    break;
                }
            }
            if(ok) cout<<1<<endl;
            else cout<<2<<endl;
        }
    }
}

If $$$n=1$$$, then the answer is YES if and only if $$$x=y$$$.

Otherwise, we consider each binary bit of $$$x$$$ and $$$y$$$.

If there is any bit which is set to $$$0$$$ in $$$x$$$ and to $$$1$$$ in $$$y$$$, then the answer is NO.

Let $$$c$$$ be the number of bits set to $$$1$$$ in $$$x$$$ and to $$$0$$$ in $$$y$$$. There can be at most $$$2^c$$$ different elements in $$$a$$$. So just check if $$$n \leq 2^c$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,x,y;

int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d%d",&n,&x,&y);
		if(n==1) printf("%s\n",(x==y)?"YES":"NO");
		else
		{
			int flg=1,sz=1;
			for(int i=0;i<30;i++)
			{
				int bx=((x&(1<<i))!=0),by=((y&(1<<i))!=0);
				if((!bx)&&by)      flg=0;
				else if(bx&&(!by)) sz<<=1;
			}
			if(n>sz) flg=0;
			printf("%s\n",flg?"YES":"NO");
		}
	}
	
	//fclose(stdin);
	return 0;
}

Let $$$p_0$$$ be the first occurrence of $$$0$$$. It's not hard to find that $$$a_{p_0}$$$ cannot be increased, since in order to make $$$a_{p_0} > 0$$$, $$$a_i = 0$$$ should exist for $$$i < p_0$$$. So, we cannot make any $$$a_i = 0$$$, for $$$i > p_0$$$, because MEX($$$a_0, a1, \ldots, a{i-1}$$$) $$$\ge 1$$$. However, we can apply operations for $$$i = p_0, p_0 - 1, \ldots, 2, 1$$$, obtaining $$$a_i = 0$$$, for each $$$i \in [1, p_0]$$$.

After that, let's find the first occurrence of $$$1$$$ — $$$p_1$$$. (If there are no $$$1$$$s in the sequence, let $$$p_1 = n$$$). Similarly, we can apply operations for each $$$i = p_1, p_1 - 1, \ldots p_0 + 1$$$, where $$$a_i \le 1$$$, obtaining $$$a_i = min(a_i, 1)$$$, for each $$$i \in [p_0, p_1]$$$.

Increasing the value, we repeat the process, while $$$[1, p_0] \cup [p_0, p_1] \cup \ldots \cup [p_{k-1}, p_k] \ne [1, n]$$$.

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(0);
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] == cur) {
                ++cur;
            }
            a[i] = min(a[i], cur);
        }
        for (auto el : a) {
            cout << el << " ";
        }
        cout << endl;
    }
    return 0;
}

Let's find an $$$i$$$ such that $$$a_i \ne b_i$$$. If $$$a_1 \oplus \ldots a_{i - 1} = 1$$$, then we can flip $$$a_i$$$ straightaway. Otherwise, let $$$cnt$$$ be the number of indices $$$j$$$ such that $$$a_j = 1, j < i$$$. If $$$cnt = 0$$$, then we cannot flip $$$a_j$$$ for all $$$1 \le j \le i$$$, so the answer is $$$-1$$$. So now $$$cnt \ge 2$$$. Let $$$j_2$$$ be the second position for which $$$a_{j_2} = 1$$$. Let's flip $$$a_{j_2}$$$, then flip $$$a_i$$$ and once again flip $$$a_{j_2}$$$. Since for every $$$i$$$ such that $$$a_i \ne b_i$$$, we apply at most $$$3$$$ operations, there are at most $$$3 \cdot n$$$ operations in total.

Let $$$i_1, i_2, \ldots, i_k$$$ be the indices that we need to flip in $$$a$$$. Let's iterate over them in increasing order and flip indices that we can ($$$cnt$$$ should be odd). After that, we know that for all remaining indices, corresponding $$$cnt$$$ is even. We can make corresponding $$$cnt$$$s odd by flipping the second occurrence of $$$1$$$ in $$$a$$$ — $$$j_2$$$, then we can flip all remaining $$$i_1, i_2, \ldots, i_k$$$ in reverse order, and finally flip $$$a_{j_2}$$$ back.

#include <bits/stdc++.h>

using namespace std;

int32_t main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(0);
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;
        string a, b;
        cin >> a;
        cin >> b;
        vector<int> ans;
        vector<int> ones;
        int fl = true;
        for (int i = 0; i < n; ++i) {
            if (a[i] != b[i]) {
                if (ones.empty()) {
                    fl = false;
                    break;
                }
                int k = (int)ones.size();
                if (k % 2 == 1) {
                    ans.push_back(i);
                } else {
                    ans.push_back(ones[1]);
                    ans.push_back(i);
                    ans.push_back(ones[1]);
                }
            }
            if (b[i] == '1') {
                ones.push_back(i);
            }
        }
        if (!fl) {
            cout << -1 << endl;
            continue;
        }
        cout << ans.size() << endl;
        for (auto el : ans) {
            cout << el + 1 << " ";
        }
        cout << endl;
    }
    return 0;
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n;
int  a[N],b[N];
char s[N],t[N];

int check()
{
	int ca=0,cb=0;
	for(int i=1;i<=n;i++) ca+=a[i],cb+=b[i];
	if(!ca) return cb!=0;  
	for(int i=1;i<=n;i++) 
	{
	    if(a[i]) return (!b[i]);
	    else if(b[i]) return 1;
	}
}

int main()
{
	//freopen("1.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
	    scanf("%d%s%s",&n,s,t);
	    for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
	    for(int i=1;i<=n;i++) b[i]=t[i-1]-'0';
	    if(check())
	    {
    		printf("-1\n");
    		continue;
    	}
	    int p=INF,x=0;
	    vector<int> ans;
	    for(int i=1;i<=n;i++)
	    {
    		if(a[i])
    		{
		    	p=i+1;
		    	break;
		    }
    	}
	    if(p<=n)
	    {
    		for(int i=1;i<=n;i++)
  	 	    {
    			x^=a[i];
    			if((a[i]!=b[i])&&x==b[i]&&i>p)
    			{
		    		ans.push_back(i);
		    		x^=1;a[i]^=1;
		    	}
    		}
    		a[p]^=1;ans.push_back(p);
    		for(int i=n;i>=p;i--) if(a[i]^b[i]) ans.push_back(i);
    	}
    	printf("%d\n",ans.size());
    	if(!ans.size()) printf("\n");
    	for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');
	}
	
	//fclose(stdin);
	return 0;
}

For $$$i$$$ in range $$$1\le l \le r \le n$$$,

$$$a_i \bmod m = b_i$$$

$$$\Rightarrow (a_i-b_i) \bmod m =0$$$

$$$\Rightarrow m \text{ divides } (a_i-b_i)$$$

Therefore, the biggest possible value of $$$m$$$ is gcd of all $$$(a_i-b_i)$$$ $$$(l \le i \le r)$$$ (except when $$$gcd=0$$$, then $$$m$$$ can be arbitrarily large).

But we need the smallest value of $$$m$$$, so we will find the smallest factor of $$$m$$$ strictly greater than all $$$b_i$$$ $$$(l \le i \le r)$$$.

To efficiently answer the queries, we can use some data structures like segment tree or sparse table to find the range gcd of $$$(a_i-b_i)$$$ in range and also to find the maximum value of $$$b_i$$$ in the range.

We will also need to do some precomputation for finding the factors of the gcd we obtained. Then, we can do binary search over the factors, to find the smallest factor strictly greater than the maximum value of $$$b_i$$$ in the range.

We will print -1 when we are unable to find any such $$$m$$$, like when $$$(a_i-b_i)$$$ is negative for some $$$i$$$ in or no factor of $$$gcd$$$ is strictly greater than the maximum value of $$$b_i$$$ in the range.

#include<bits/stdc++.h>
using namespace std;
 
//#define int long long
#define endl "\n"
 
const int N=1000001;
 
vector<vector<int>>divisors(N);
 
void init_sparse_max(vector<int>&a,vector<vector<int>>&dp){
    int n=a.size();
    for(int i=0;i<n;i++){
        dp[i][0]=a[i];
    }
    for(int j=1;j<30;j++){
        for(int i=0;i+(1LL<<j)-1<n;i++){
            dp[i][j]=max(dp[i][j-1],dp[i+(1LL<<(j-1))][j-1]);
        }
    }
}
 
void init_sparse_gcd(vector<int>&a,vector<vector<int>>&dp){
    int n=a.size();
    for(int i=0;i<n;i++){
        dp[i][0]=a[i];
    }
    for(int j=1;j<30;j++){
        for(int i=0;i+(1LL<<j)-1<n;i++){
            dp[i][j]=__gcd(dp[i][j-1],dp[i+(1LL<<(j-1))][j-1]);
        }
    }
}
 
int query_max(int l,int r,vector<vector<int>>&dp){
    int j=log2(r-l+1);
    int ans=max(dp[l][j],dp[r-(1LL<<j)+1][j]);
 
    return ans;
}
 
int query_gcd(int l,int r,vector<vector<int>>&dp){
    int j=log2(r-l+1);
    int ans=__gcd(dp[l][j],dp[r-(1LL<<j)+1][j]);
 
    return ans;
}
 
void solve(){
    int n,q;
    cin>>n>>q;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<int>b(n);
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    vector<vector<int>>sparse_max(n,vector<int>(30));
    init_sparse_max(b,sparse_max);
    vector<int>c(n);
    set<int>st;
    for(int i=0;i<n;i++){
        c[i]=a[i]-b[i];
        if(c[i]<0){
            st.insert(i);
        }
    }
    vector<vector<int>>sparse_gcd(n,vector<int>(30));
    init_sparse_gcd(c,sparse_gcd);
    while(q--){
        int l,r;
        cin>>l>>r;
        l--;r--;
        auto it=st.lower_bound(l);
        if(it!=st.end() && *it<=r){
            cout<<-1<<endl;
            continue;
        }
        int m=query_gcd(l,r,sparse_gcd);
        int maxi=query_max(l,r,sparse_max);
        int index=upper_bound(divisors[m].begin(),divisors[m].end(),maxi)-divisors[m].begin();
        if(index!=(int)divisors[m].size()){
            cout<<divisors[m][index]<<endl;
        }else{
            cout<<-1<<endl;
        }
    }
}
 
signed main(){
 
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
 
    for(int i=1;i<=1000000;i++){
        for(int j=i;j<=1000000;j+=i){
            divisors[j].push_back(i);
        }
    }
 
    int t;
    cin>>t;
    while(t--){
        solve();
    }
 
    return 0;
}

Soon...

Soon...

Let $$$k=\lfloor\frac{n}{m}\rfloor$$$. The answer is $$$(1+\cdots+k)\cdot m=\frac{k(k+1)}{2}\cdot m$$$.

Consider modifying each character from left to right.

To change character $$$s_i$$$ to $$$'a'$$$, it is not difficult to see that the minimum number of operations needed is $$$min(s_i-'a','z'+1-s_i)$$$.

If the remaining number of operations $$$r$$$ is less than $$$min(s_i-'a','z'+1-s_i)$$$, then shift the current character to the left $$$r$$$ times.

You need to be careful: if all characters become $$$'a'$$$ and the remaining number of operations is odd, you need to change $$$s_n$$$ to $$$'b'$$$.

Consider the following problem:

For a string $$$t$$$ of length $$$m$$$, if $$$t$$$ is palindrome and $$$t+t_m$$$ is also palindrome, what kind of string is $t$？

We can find that $$$t_1=t_2=\cdots=t_m$$$ must hold.

Then the solution is clear. We can do bruteforce until we obtain a string where all characters are equal. Afterwards, you only need to add the same character at the end every time.

There will be only $$$O(\log n)$$$ iterations because after every time we add character to the end we will divide size of string by $$$2$$$.

What's the minimum sum we can get? The answer is $$$2l+2$$$.

Consider starting from the minimum sum and only increasing the sum by $$$1$$$ at a time.

Construction: $$$l+2, l, l+3, l+1, l+4 \dots$$$

Let $$$dp_{i,fa,fb}$$$ be answer if we consider only first $$$i$$$ columns, where $$$fa$$$ and $$$fb$$$ respectively represent whether $$$a_i$$$ and $$$b_i$$$ are covered by dominoes or not. Transitions are obvious.

let's say that $$$l=r=n$$$.

It's obvious that if $$$a$$$ is not a divisor of $$$n$$$, then vertex $$$a$$$ cannot contribute to $$$flow(n)$$$.

Think about the divisors less than $$$\sqrt{n}$$$ or more than $$$\sqrt{n}$$$.

How about the divisors which is just equal to $$$\sqrt{n}$$$?

How can we calculate $$$\Sigma_{i=l} ^r flow(i)$$$ faster? How about count the multiples instead of divisors?

First notice that we only need to make first $$$m$$$ characters contain $$$k$$$ ones, and $$$s_i=s_{i-m}$$$ for all $$$i$$$ such that $$$m+1\leq i\leq n$$$.

Now let's say you fixed your answer string and you want to find the minimum number of operations to get it. Obviously the answer is the number of segments of consecutive ones after xoring the answer string with $$$s$$$.

Number of segments of consecutive ones can be calculated using amount of pairs of distinct adjacent numbers, so our answer is $$$\frac{\sum{x_i\oplus x_{i-1}}}{2}$$$ where $$$x$$$ is xor string. (you need to add zeros on left and right of string).

You can calculate it using dp.

Solution is to print "TheForces rounds!".

#include <bits/stdc++.h>
using namespace std;
 
int32_t main() {
	cout << "TheForces rounds!";
}

The answer is the number of TheForces Rounds with less than 100 participants (7).

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

int32_t main() {
	cout << 7;
}

In this problem, you need to determine if the string is a palindrome when translated into Morse.

#include <bits/stdc++.h>
using namespace std;
 
int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	string s; cin >> s; int n = s.size();
	bool bad = false;
	for (int i = 0; i < n; i++)
		if ((s[i] + s[n - 1 - i] - '0' - '0') % 10 != 0)
			bad = true;
	if (bad) cout << "NO";
	else cout << "YES";
}

In this problem, you need to print concatenation of missing characters in statements B, A, and D. The answer is "mty".

#include <bits/stdc++.h>
using namespace std;
 
int32_t main() {
    cout << "mty";
}

You need to find how cringe is the given string. To do it you should calculate the cost of the string and divide it by the cost of "cringe". The cost of the string is equal to $$$\sum (a_i\mod 10)$$$ where $$$a_i$$$ is the index (0-based) of $$$s_i$$$ in the English alphabet.

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

void test_case() {
	string s; cin >> s;
	int cringe = 30, sum = 0;
	for (char c : s)
		sum += (c - 'a') % 10;
	cout << sum / cringe << '\n';
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

You have to find the degree of the root in directed tree.

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

#define N 1100

int in[N], out[N];

int main() {
	int n; cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		in[v]++; out[u]++;
	}
	for (int i = 1; i < n; i++) if(in[i] == 0)
		cout << out[i];
}

All characters in the statement and the name of the problem are encoded in the next way: letter changes to the letter to the right of it. The name of the problem is actually "Power of two". It is not hard to guess that the answer is the last digit of $$$2^m$$$.

#include <bits/stdc++.h>
using namespace std;
 
int32_t main() {
	int m; cin >> m;
	if (m == 1) cout << 1;
	else cout << "2486"[(m - 2) % 4];
}

The answer to this problem is 1. There is no reason why is it 1.

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

int32_t main() {
	cout << 1;
}

TheForces Rounds is a series of contests which are created by a group of CP lovers in the CF community. You can join our discord server with more than 1000 members for more information about the contests: https://discord.gg/h9N2vGmwep

Save the position of each character in the corresponding vector, and then select the smallest value each time.

That way, all strings can be generated. The complexity is $$$\Theta(n|c|^2)$$$, we can also use the priority queue do it in $$$\Theta(n|c|\log|c|)$$$.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
const int MOD=998244353;
void Delta() {
   string s,answer;cin >> s;
   vector<vector<int>> Q(26,vector<int>{});
   for(int i=0;i<(int)s.size();++i)
      Q[s[i]-'a'].push_back(i);
   for(int i=0;i<26;++i)
      reverse(Q[i].begin(),Q[i].end());
   while(true) {
      bool flag=true;
      for(int i=0;i<26;++i)
         if(!Q[i].empty()) flag=false;
      if(flag) break;
      vector<bool> Flag(26,false);
      string temp;
      for(int j=0;j<26;++j) {
         int mnidx=-1,mnvalue=2147483647;
         for(int i=0;i<26;++i)
            if(!Flag[i]&&!Q[i].empty()&&Q[i].end()[-1]<mnvalue) {
               mnvalue=Q[i].end()[-1];
               mnidx=i;
            }
         if(mnidx==-1) break;
         Q[mnidx].pop_back();
         temp.push_back(s[mnvalue]);
         Flag[mnidx]=true;
      }
      answer=temp;
   }
   cout << answer << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

Using Greed to solve this problem.

If two points are on a straight line, they can be directly reached through the line. This must be the shortest.

Otherwise, we hope to follow as many curves as possible. Because the arc of a unit is $$$\frac{\pi}{2}$$$, it can replace the effect of $$$2$$$ straight lines.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
 
#define int long long
 
const long double pi=3.141592653589793238462643383279L;
void Delta() {
   long double x1,y1,x2,y2,answer;
   cin >> x1 >> y1 >> x2 >> y2;
   if((x1==0&&x2==0)||(y1==0&&y2==0))
      answer=abs(x1+y1-x2-y2);
   else {
      x1=abs(x1);y1=abs(y1);x2=abs(x2);y2=abs(y2);
      answer=pi/2*min(x1+y1,x2+y2)+max(x1+y1,x2+y2)-min(x1+y1,x2+y2);
   }
   if(abs(answer)>100000000) cout << (int)answer << endl;
   else cout << fixed << setprecision(20) << answer << endl;
}
signed main() {
   cin.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

Another problem of greed.

Let's first consider the situation of the last position. Obviously, the last position can only be modified by manipulating the entire string.

Therefore, we first change the last position, and then change the last two positions until all strings are the same.

For each position, there are some strings that are either $$$0$$$ or $$$1$$$. Each time we select fewer strings to change. Because the answer only requires comparing the strings, modifying more or fewer will not affect subsequent operations.

To facilitate the calculation of flipping, flip tags can be used for maintenance. It's $$$\Theta(nm)$$$

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
 
#define int long long
 
const int MOD=998244353;
string a[100001];
bool flip[100001];
void Delta() {
   int n,m,answer=0;
   cin >> n >> m;
   for(int i=1;i<=n;++i) {
      cin >> a[i];
      flip[i]=false;
   }
   for(int i=m-1;i>=0;--i) {
      vector<int> c[2];
      for(int j=1;j<=n;++j)
         c[(a[j][i]-'0')^flip[j]].push_back(j);
      for(int j:(c[0].size()>c[1].size()?c[1]:c[0])) {
         answer++;
         flip[j]^=true;
      }
   }
   cout << answer << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

For this problem we can use binary serach to solve it.

Firstly, if there is a square of size $$$x$$$, then there must also be a square of size $$$x-1$$$, so we can use binary serach.

To verify the existence of a square of size $$$x$$$, we use a sliding window for maintenance. In a sliding window, we place all soldiers in their positions. If there is an adjacent position difference greater than $$$x$$$, then we can place a square of size x at this position.

For calculating sliding windows, we can use multiset for maintenance. Use one multiset to maintain all soldier positions and query adjacent soldiers, while another multiset is used to maintain all adjacent differences and find the maximum value.

That way, we can make single modifications in $$$\Theta(\log n)$$$, The total complexity is $$$\Theta(n\log^2n)$$$.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
long long isqrt(int x){long long a=x,b=(x+1)/2;while(a>b){a=b;b=(b+x/b)/2;}return a;}
const int MOD=998244353;
int n,a[50001];
void ins(multiset<int> &P,multiset<int> &Q,int x) {
   auto itr=Q.insert(x),nxt=next(itr,1),pre=prev(itr,1);
   P.erase(P.lower_bound(*nxt-*pre-1));
   P.insert(*itr-*pre-1);
   P.insert(*nxt-*itr-1);
}
void del(multiset<int> &P,multiset<int> &Q,int x) {
   auto itr=Q.lower_bound(x),nxt=next(itr,1),pre=prev(itr,1);
   P.insert(*nxt-*pre-1);
   P.erase(P.lower_bound(*itr-*pre-1));
   P.erase(P.lower_bound(*nxt-*itr-1));
   Q.erase(itr);
}
bool check(int x) {
   int answer=0;
   multiset<int> Q={0,n+1},P={n};
   for(int i=1;i<=x;++i) ins(P,Q,a[i]);
   answer=max(answer,*P.rbegin());
   for(int i=x+1;i<=n;++i) {
      ins(P,Q,a[i]);
      del(P,Q,a[i-x]);
      answer=max(answer,*P.rbegin());
   }
   return answer>=x;
}
void Delta() {
   cin >> n;
   for(int i=1;i<=n;++i) cin >> a[i];
   int l=1,r=n,m,s=0;
   while(l<=r) {
      m=(l+r)/2;
      if(check(m)) {
         l=m+1;s=m;
      } else r=m-1;
   }
   cout << s << endl;
   if(s==isqrt(n-1)) cout << "NO" << endl;
   else cout << "YES" << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   Delta();
}

Interesting problem.

First, this $$$69$$$ is not special, so we first subtract all of $$$a_i$$$ from $$$69$$$ and then turn the problem into at most $$$0$$$.

Consider, if we already know a sequence, how do we decide whether it can become $$$0$$$? For some prefix and suffix operations, we can translate this into the sum of an ascending sequence and a descending sequence.

Here is a greedy observation. Because a falling sequence cannot rise again once it has fallen, and can fall at any time, we want the value of the falling sequence to be as large as possible. The same goes for an ascending sequence, the smaller the better.

So we would set the first value of the ascending sequence to $$$0$$$ and the first value of the descending sequence to $$$a_1$$$. (assuming $$$a_1$$$ is the first number to become $$$0$$$)

It is easy to find that the sum of the ascending and descending sequences must equal the last number taken, and that each number taken must degrade the sequence value. So there is monotonicity here.

Since $$$n$$$ is small and $$$a_i$$$ is large, you can set the dp state to "$$$x$$$ numbers are taken from $$$1$$$ to $$$i$$$ and last is $$$a_i$$$, and the minimum value of the ascending sequence at that point is $$$dp_{i,x}$$$".

For the initial value we have $$$dp_{i,1}=0$$$, and the transfer has $$$dp_{i,x}=\text{min}_{j<i\text{ and }dp_{j,x-1}\le a_i}(\max(0,a_i-a_j)+dp_{j,x-1})$$$. It's $$$\Theta(n^3)$$$, not fast enough, so it needs optimization.

First, $$$a_i$$$ is discretized, and then stored $$$\min dp_j$$$ and $$$\min dp_j-a_j$$$ with segment tree. The values of max in dp transitions are classified and then calculated separately. Then the total complexity is $$$\Theta(n^2\log n)$$$.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
struct node {int mndp,mndpa;};
node merge(node a,node b) {return {min(a.mndp,b.mndp),min(a.mndpa,b.mndpa)};}
template <class T> class segment {
   private:
      int id(int l,int r){return (l+r)|(l!=r);}
      void change(int l,int r,int x,T &y){if(l==r){seg[id(l,r)]=y;return;}int mid=(l+r)/2;if(x<=mid)change(l,mid,x,y);else change(mid+1,r,x,y);seg[id(l,r)]=merge(seg[id(l,mid)],seg[id(mid+1,r)]);}
      T query(int L,int R,int l,int r){if(l<=L&&R<=r)return seg[id(L,R)];int mid=(L+R)/2;if(l<=mid&&r>mid)return merge(query(L,mid,l,r),query(mid+1,R,l,r));if(l<=mid)return query(L,mid,l,r);return query(mid+1,R,l,r);}
   public:
      vector<T> seg;int siz;
      segment(int n){siz=n;seg.resize(2*n+4);}
      void change(int x,T y){change(1,siz,x,y);}
      T query(int l,int r){return query(1,siz,l,r);}
};
const int MOD=998244353;
int n,a[2001],b[2001],dp[2001][2001],answer;
void Delta() {
   cin >> n;vector<int> Q;
   for(int i=1;i<=n;++i) {
      cin >> a[i];a[i]-=69;
      Q.push_back(a[i]);
   }
   Q.push_back(-2147483647);sort(Q.begin(),Q.end());
   Q.resize(unique(Q.begin(),Q.end())-Q.begin());
   for(int i=1;i<=n;++i) {
      dp[i][1]=0;
      b[i]=lower_bound(Q.begin(),Q.end(),a[i])-Q.begin();
   }
   for(int x=2;x<=n;++x)  {
      segment<node> P(n);
      for(int i=1;i<=n;++i) dp[i][x]=2147483647;
      for(auto &i:P.seg) i={2147483647,2147483647};
      for(int i=1;i<=n;++i) {
         dp[i][x]=min(dp[i][x],P.query(b[i],n).mndp);
         dp[i][x]=min((long long)dp[i][x],(long long)P.query(1,b[i]).mndpa+a[i]);
         P.change(b[i],{dp[i][x-1],dp[i][x-1]-a[i]});
      }
   }
   for(int i=1;i<=n;++i)
      for(int j=1;j<=n;++j)
         if(dp[i][j]<=a[i])
            answer=max(answer,j);
   cout << answer << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   Delta();
}

Answer is $$$floor(sqrt(r)) — floor(sqrt(l — 1))$$$.

Alternatively you can use binary search to calculate square root.

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

#define int long long

int get(int r) {
	int tt = 0;
	for (int uu = r; uu >= 1; uu /= 2)
		while ((tt + uu) * (tt + uu) <= r)
			tt += uu;
	return tt;
}

int32_t main() {
	iostream::sync_with_stdio(0); cin.tie(0);
	int q; cin >> q;
	while (q--) {
		int l, r; cin >> l >> r;
		cout << get(r) - get(l - 1) << '\n';
	}
}

You always can make all bits less or equal to the most significant bit set to $$$1$$$. Also you cant make most significant bit greater.

Just go through numbers and find the minimal most significant bit.

Answer is number with all bits less or equal to minimal most significant bit set to $$$1$$$.

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

#define int long long

int32_t main() {
	iostream::sync_with_stdio(0); cin.tie(0);
	int q; cin >> q;
	while (q--) {
		int n; cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; i++)
			cin >> a[i];
		int bb = a[0];
		for (int i = 0; i < n; i++) {
			int tt = 0;
			while (a[i] / (1ll << (tt + 1)) > 0)
				tt++;
			bb = min(bb, tt);
		}
		cout << (1ll << (bb + 1)) - 1 << '\n';
	}
}

Best way to choose the integer is the $$$gcd$$$ of all elements in the array except for element you want to change.

So you just need to calculate the $$$gcd$$$ of all elements in the array except for one in some fast way.

You can use pre-calculated prefix/suffix $$$gcd$$$ to do it.

Also take care about the case $$$n = 1$$$, The answer for this case will be always $$$10^9$$$.

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
int32_t main() {
	iostream::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	if (n == 1) {
		int a; cin >> a;
		cout << 1000000000;
		return 0;
	}
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	vector<int> pp(n), ss(n);
	pp[0] = a[0];
	ss[n - 1] = a[n - 1];
	for (int i = 1; i < n; i++)
		pp[i] = __gcd(pp[i - 1], a[i]);
	for (int i = n - 2; i >= 0; i--)
		ss[i] = __gcd(ss[i + 1], a[i]);
	int bb = max(ss[1], pp[n - 2]);
	for (int i = 1; i < n - 1; i++)
		bb = max(bb, __gcd(pp[i - 1], ss[i + 1]));
	cout << bb;
}

We can imagine that Alice and Bob are on different sides of the river. It's obvious that in this case best path is just straight line between Alice and Bob.

So you can just negate $$$y$$$ coordinate for Bob and calculate the Euclidean distance of the obtained point with the other point, It can be proven that the obtained distance is the shortest possible.

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
int32_t main() {
	iostream::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) {
		long double x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		y2 = -y2;
		cout << fixed << sqrtl((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) << '\n';
	}
}

It's obvious that you can change bases in original formula to their last digits.

After you can just check some cases.

$$$1^{10x+1}$$$ mod $$$10$$$ is always $$$1$$$
$$$2^{10x+2}$$$ mod $$$10$$$ is switching between $$$4$$$ and $$$6$$$
$$$3^{10x+3}$$$ mod $$$10$$$ is switching between $$$7$$$ and $$$3$$$
$$$4^{10x+4}$$$ mod $$$10$$$ is always $$$6$$$
$$$5^{10x+5}$$$ mod $$$10$$$ is always $$$5$$$
$$$6^{10x+6}$$$ mod $$$10$$$ is always $$$6$$$
$$$7^{10x+7}$$$ mod $$$10$$$ is switching between $$$3$$$ and $$$7$$$
$$$8^{10x+8}$$$ mod $$$10$$$ is switching between $$$6$$$ and $$$4$$$
$$$9^{10x+9}$$$ mod $$$10$$$ is always $$$9$$$
$$$0^{10x+0}$$$ mod $$$10$$$ is always $$$0$$$

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

#define int long long

int32_t main() {
	iostream::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		int ss = 0;
		for (int x = 1; x <= 10; x++) {
			int aa = n / 10 + ((n % 10) >= x);
			if (x == 4)
				ss = (ss + 6 * aa) % 10;
			else if (x == 2)
				ss = (ss + (4 * ((aa + 1) / 2) + 6 * (aa / 2))) % 10;
			else if (x == 3)
				ss = (ss + (7 * ((aa + 1) / 2) + 3 * (aa / 2))) % 10;
			else if (x == 7)
				ss = (ss + (3 * ((aa + 1) / 2) + 7 * (aa / 2))) % 10;
			else if (x == 8)
				ss = (ss + (6 * ((aa + 1) / 2) + 4 * (aa / 2))) % 10;
			else
				ss = (ss + x * aa) % 10;
		}
		cout << ss << '\n';
	}
}

First, we need to write sieve for finding primes to $$$sqrt(a_i)$$$ it means $$$10^4$$$ to solve problem faster, then find prime divisors of number $$$k$$$ and their count.

If $$$N=p^a*q^b*r^c$$$ .

Number of divisors = $$$(a+1)*(b+1)*(c+1)$$$,

Sum of divisors = $$$(p^0+p^1+p^2......p^a)(q^0+q^1+q^2......q^b)(r^0+r^1+r^2......r^c)$$$ .

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

#define int long long

#define N 10001
#define M 1000000007

vector<int> pp;
bool prime[N];

void init() {
	for (int i = 0; i < N; i++)
		prime[i] = true;
	for (int i = 2; i < N; i++) {
		if (!prime[i])
			continue;
		pp.push_back(i);
		for (int j = i * i; j < N; j += i)
			prime[j] = false;
	}
}

int32_t main() {
	iostream::sync_with_stdio(0); cin.tie(0);
	init();
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; i++)
			cin >> a[i];
		map<int, int> mp;
		for (int i = 0; i < n; i++) {
			for (int x : pp)
				while (a[i] % x == 0) {
					a[i] /= x;
					mp[x]++;
				}
			if (a[i] > 1)
				mp[a[i]]++;
		}
		int aa = 1;
		int bb = 1;
		for (auto [x, y] : mp) {
			aa = (aa * (y + 1)) % M;
			int vv = bb;
			bb = 0;
			for (int i = 0; i <= y; i++) {
				bb = (bb + vv) % M;
				vv = (vv * x) % M;
			}
		}
		cout << aa << ' ' << bb << '\n';
	}
}

If you already calculated answer for $$$n$$$ — $$$1$$$, you can find answer for $$$n$$$ in next way:

You already have calculated answer for all subsets without $$$n$$$.

Now you want to find answer for all new subsets.

It's obvious that all new subsets are old subsets but with $$$n$$$ in them.

So for all subsets you want to change answer from $$$\frac{f}{s}$$$ to $$$\frac{f + n}{s * n}$$$.

$$$\frac{f + n}{s * n} = \frac{f}{s}/n + \frac{n}{s}/n = \frac{ans_{old}}{n} + \frac{1}{s}$$$.

So you want to keep sum of $$$\frac{1}{s}$$$ and sum of $$$\frac{f}{s}$$$ over all subsets

Let sum of $$$\frac{1}{s}$$$ be $$$Y$$$ and sum of $$$\frac{f}{s}$$$ be $$$X$$$

When you add $$$n$$$, $$$Y$$$ changes to $$$Y + Y/n$$$, and $$$X$$$ changes to $$$X + X/n + Y$$$

Final answer is $$$X$$$

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

#define int long long

int32_t main() {
	iostream::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	long double x = 0, y = 1;
	for (int i = 1; i <= n; i++) {
		x += x / i + y;
		y += y / i;
	}
	cout << fixed << x << '\n';
}