The key observation is that the parity of the distance between Alice and Bob always changes after one move. Therefore, if $$$|x - y|$$$ is even, Alice can always move closer to Bob and corner him to win. Otherwise, Bob will win.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define mod  1000000007
#define mod2 998244353
#define ll long long
#define bl __int128_t
#define pb push_back
#define all(v) v.begin(),v.end()
#define bs binary_search
#define rall(v) v.rbegin(),v.rend()
#define lb lower_bound
#define ub upper_bound
#define pl pair<ll,ll>
#define f(i,n) for(ll i=0;i<n;i++)
#define inp(a,n) vector<ll> a(n); f(i,n) cin>>a[i]
#define pyes cout<<"YES\n"
#define pno cout<<"NO\n"
using Mat = array<array<ll,2>,2>;

#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt")

ll power(ll x,ll y,ll z=LLONG_MAX){
    ll res=1;
    while(y>0){
        if(y%2) res=(res*x)%z;
        y/=2;
        if(y) x=(x*x)%z;
    }return res%z;
}

ll gcd(ll a,ll b,ll& x,ll& y){
    x=1,y=0;
    ll x1=0,y1=1,a1=a,b1=b;
    while(b1){
        ll q=a1/b1;
        tie(x,x1)=make_tuple(x1,x-q*x1);
        tie(y,y1)=make_tuple(y1,y-q*y1);
        tie(a1,b1)=make_tuple(b1,a1-q*b1);
    }return a1;
}



int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll t=1,i,j,n,m,z=1e9+7,z2=998244353,k,x,y,q;
    // sieve(); // for SPF
    cin>>t;
    ll tt=t;
    string s,s2;
    while(tt--){
        ll n, x, y;
        cin >> n >> x >> y;
        if((x + y) % 2) pno;
        else pyes;
    }
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Add as many segments with $$$1$$$ as one endpoint as possible. The answer is $$$n - 3$$$, which reaches the upper limit of the triangulation number.

#include <bits/stdc++.h>
using namespace std;
int n,m;
int solve(string s){
    map<int,int> mp;
    int x=0;
    for(int i=0;i<m;i++) 
    {
        if(s[i]=='L') x++;
        else x--;
        mp[x]=1;
    }

    mp.erase(0);
    return mp.size()>=n;

}

int main() {

    int t;
    cin>>t;

    while(t--)
    {
        cin>>n>>m;
        string s;
        cin>>s;

        string T=s;
        for(int i=0;i<m;i++) if(s[i]=='?') T[i]='L';

        if(solve(T)) cout<<"YES\n"<<T<<"\n";
        else 
        {
            for(int i=0;i<m;i++) if(s[i]=='?') T[i]='R';
            if(solve(T)) cout<<"YES\n"<<T<<"\n";
            else cout<<"NO\n";
        }

    }

    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Assume $$$x$$$ is the optimal solution, and $$$gcd(n, x) = y$$$. Then, $$$x$$$ must be equal to $$$y$$$; otherwise, $$$y$$$ would be a smaller solution. Therefore, we only need to factorize $$$n$$$ and find the smallest factor of $$$n$$$ in the range $$$[l, r]$$$.

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

int main() {
    long long t;
    cin>>t;

    while(t--)
    {
        long long n,l,r;
        cin>>n>>l>>r;

        if(n<l) cout<<"-1\n";
        else
        {
            long long ans=1e9+1;
            for(long long i=1;i*i<=n;i++)
            {
                if(n%i==0)
                {
                    long long A=i;
                    long long B=n/i;
                    if(A>=l && A<=r)
                    {
                        ans=min(ans,A);
                    }
                    if(B>=l && B<=r)
                    {
                        ans=min(ans,B);
                    }
                }
            }
            if(ans>n) cout<<"-1\n";
            else cout<<ans<<"\n";
        }
    }
    
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Greedily replace all '?' with 'L' or replace all '?' with 'R'. Then, check if the robot will explode.

#include <bits/stdc++.h>
using namespace std;
int n,m;
int solve(string s){
    map<int,int> mp;
    int x=0;
    for(int i=0;i<m;i++) 
    {
        if(s[i]=='L') x++;
        else x--;
        mp[x]=1;
    }

    mp.erase(0);
    return mp.size()>=n;

}

int main() {

    int t;
    cin>>t;

    while(t--)
    {
        cin>>n>>m;
        string s;
        cin>>s;

        string T=s;
        for(int i=0;i<m;i++) if(s[i]=='?') T[i]='L';

        if(solve(T)) cout<<"YES\n"<<T<<"\n";
        else 
        {
            for(int i=0;i<m;i++) if(s[i]=='?') T[i]='R';
            if(solve(T)) cout<<"YES\n"<<T<<"\n";
            else cout<<"NO\n";
        }

    }

    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

If $$$k$$$ is chosen for the first time, we can recalculate the answer using brute force. Otherwise, the answer can be updated in $$$O(1)$$$. Since all values on the diagonal are already the same, the update operation will only increase the answer by (new_value — old_value).

Time complexity: $$$O(n^3)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1010;
const int LOGN=28;
const ll  TMD=1000000007;
const ll  INF=2147483647;
int T,n,q;
ll  ans;
ll  a[N][N],dp[N][N];

ll DP()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
    return dp[n][n];
}

void init()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    ans=DP();
}

void modify(int k,int v)
{
    ll delta;
    for(int i=min(k-1,n),j=k-i;i>=1&&j<=n;i--,j++)
    {
        delta=v-a[i][j];
        a[i][j]=v;
    }
    ans+=delta;
}

void solve()
{
    vector<int> tag(2*n);
    for(int i=1;i<=q;i++)
    {
        int k,v;
        cin>>k>>v;
        modify(k,v);
        if(!tag[k])
        {
            tag[k]=1;
            ans=DP();
        }
        cout<<ans<<'\n';
    }
}

//-------------------------------------------------------

void gen_data()
{
    srand(time(NULL));
}

int bruteforce()
{
    return 0;
}

//-------------------------------------------------------

int main()
{
    fastio;

	cin>>T;
	while(T--)
	{
		init();
		solve();

		/*

		//Stress Test

		gen_data();
		auto ans1=solve(),ans2=bruteforce();
		if(ans1==ans2) printf("OK!\n");
		else
		{
			//Output Data
 		}

		*/
	}

	return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Note: $$$'('$$$ is $$$1$$$ and $$$')'$$$ is $$$-1$$$, with $$$S$$$ as the current sum.

If $$$a \geq 2b$$$, Alice always wins.

The strategy is: $$$S = b \xrightarrow{\text{Bob}} 0 \leq S \leq 2b \xrightarrow{\text{Alice}} S = b \xrightarrow{\text{Bob}} 0 \leq S \leq 2b \xrightarrow{\text{Alice}} \dots \xrightarrow{\text{Bob}} 0 \leq S \leq 2b \xrightarrow{\text{Alice}} S = 0$$$.

Otherwise, Bob always wins.

The strategy is: $$$S \geq b \xrightarrow{\text{Bob}} S \geq 2b \xrightarrow{\text{Alice}} S \geq b \xrightarrow{\text{Bob}} S \geq 2b \xrightarrow{\text{Alice}} \dots \xrightarrow{\text{Bob}} S \geq 2b \xrightarrow{\text{Alice}} S \gt 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>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
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;
int n,a,b;

/*
 * stuff you should look for
 * [Before Submission]
 * array bounds, initialization, int overflow, special cases (like n=1), typo
 * [Still WA]
 * check typo carefully
 * casework mistake
 * special bug
 * stress test
 */

void init()
{
    cin>>n>>a>>b;
}

int cal(string s)
{
    int sum=0;
    for(int i=0;i<s.length();i++)
        sum+=(s[i]=='('?1:-1);
    return sum;
}

void solve()
{
    string s;
    if(a>=2*b)
    {
        cout<<1<<'\n'<<flush;
        for(int i=1;i<=n;i+=2)
        {
            int cur=cal(s)-a;
            string t,tt;
            if(i==n)
            {
                for(int j=1;j<=a;j++)
                {
                    if(cur<0) cur+=2,t+='(';
                    else t+=')';
                }
                cout<<t<<'\n'<<flush;
                s+=t;
            }
            else
            {
                for(int j=1;j<=a;j++)
                {
                    if(cur<b) cur+=2,t+='(';
                    else t+=')';
                }
                cout<<t<<'\n'<<flush;
                s+=t;
                cin>>tt;
                s+=tt;
            }
        }
    }
    else
    {
        cout<<0<<'\n'<<flush;
        for(int i=1;i<=n;i+=2)
        {
            string t,tt;
            cin>>t;
            s+=t;
            if(i==n) break;
            if(cal(s)<b)
            {
                for(int j=1;j<=b;j++) tt+=')';
                cout<<tt<<'\n'<<flush;
            }
            else
            {
               for(int j=1;j<=b;j++) tt+='(';
                cout<<tt<<'\n'<<flush;
            }
            s+=tt;
        }
    }
}

//-------------------------------------------------------

void gen_data()
{
    srand(time(NULL));
}

int bruteforce()
{
    return 0;
}

//-------------------------------------------------------

int main()
{
    fastio;

    cin>>T;
	while(T--)
	{
		init();
		solve();

		/*

		//Stress Test

		gen_data();
		auto ans1=solve(),ans2=bruteforce();
		if(ans1==ans2) printf("OK!\n");
		else
		{
			//Output Data
 		}

		*/
	}

	return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

For fixed $$$m$$$, we can construct intervals for $$$n \in [mL, mR]$$$. Let $$$m = \left\lfloor \frac{n}{L} \right\rfloor$$$. If $$$n \gt mR$$$, output $$$-1$$$; otherwise, we can always construct a valid solution.

Now, let's consider constructing a solution with the minimum $$$\gcd$$$. Let $$$minlen$$$ be the minimum length of all intervals. We can observe that all scores $$$(l[i] \cdot (l[i] + 1) \cdots \cdot r[i])$$$ in the intervals are multiples of $$$(minlen!)$$$.

Let's prove it in one line:
$$$\frac{r \cdot (r-1) \cdots (r-minlen+1)}{minlen!} = \frac{r!}{(r-minlen)! minlen!} = C(r, minlen)$$$.

Thus, we can simply choose $$$[1, minlen]$$$ to minimize the gcd. For construction, we choose the scheme that minimizes the value of $$$minlen$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
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=998244353;
const ll  INF=2147483647;
ll T,n,L,R;
ll fac[N];

/*
 * stuff you should look for
 * [Before Submission]
 * array bounds, initialization, int overflow, special cases (like n=1), typo
 * [Still WA]
 * check typo carefully
 * casework mistake
 * special bug
 * stress test
 */

void init_fac()
{
	fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=(fac[i-1]*i)%TMD;
}

void init()
{
    cin>>n>>L>>R;
}

void solve()
{
    ll mn=INF,m=0;
    for(int i=1;i<=n;i++)
    {
        if(i*L<=n&&n<=i*R)
        {
            ll res=max(0LL,n-(L+R*(i-1)));
            if(L+res<mn) mn=L+res,m=i;
        }
    }
    if(!m)
    {
        cout<<"-1\n";
        return ;
    }
    vector<ll> len(m+4);
    for(int i=1;i<=m;i++) len[i]=L;
    n-=m*L;
    for(int i=m;i;i--)
        len[i]+=min(R-L,n),n-=min(R-L,n);
    cout<<m<<' '<<fac[mn]<<'\n';
    for(int i=1,cur=1;i<=m;i++)
    {
        cout<<cur<<' '<<cur+len[i]-1<<'\n';
        cur+=len[i];
    }
}

//-------------------------------------------------------

void gen_data()
{
    srand(time(NULL));
}

int bruteforce()
{
    return 0;
}

//-------------------------------------------------------

int main()
{
    fastio;

    init_fac();
	cin>>T;
	while(T--)
	{
		init();
		solve();

		/*

		//Stress Test

		gen_data();
		auto ans1=solve(),ans2=bruteforce();
		if(ans1==ans2) printf("OK!\n");
		else
		{
			//Output Data
 		}

		*/
	}

	return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

One key observation is that only the last operation of type $$$2$$$ matters.

The answer is $$$x + \max(b[j] + a[j+1:r[i]])$$$. There are two other cases: $$$x$$$ and $$$x + \sum(a[l[i]:r[i]])$$$. To simplify, let’s define $$$c[i] = b[i] + a[i+1:]$$$, and then build a sparse table on $$$c$$$ to maintain the answer.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
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,q;
int a[N],b[N];
ll  presum[N];

//-------------------------------------------------
int lg2[N];
ll  mx[N][LOGN];

void init()
{
	for(int i=1;i<=n;i++) lg2[i]=(int)log2(i);
	for(int i=1;i<=n;i++) mx[i][0]=b[i]-presum[i];
	for(int i=1;i<LOGN;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int p=j+(1<<(i-1));
			if(p>n) 
			{
				mx[j][i]=mx[j][i-1];
			}
			else    
			{
				mx[j][i]=max(mx[j][i-1],mx[p][i-1]);
			}
		}
	}
}

ll getmax(int L,int R)
{
	int t=lg2[R-L+1];
	return max(mx[L][t],mx[R-(1<<t)+1][t]);
}

//-------------------------------------------------

int main()
{
	scanf("%d",&T);
	while(T--)
	{
	    scanf("%d%d",&n,&q);
	    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	    for(int i=1;i<=n;i++) a[i]=max(0,a[i]);
	    for(int i=1;i<=n;i++) presum[i]=presum[i-1]+a[i];
	    init();
	    for(int i=1;i<=q;i++)
	    {
    		int k,l,r;
    		//ll  ans;
    		scanf("%d%d%d",&k,&l,&r);
    		printf("%I64d\n",max(k+presum[r]-presum[l-1],presum[r]+getmax(l,r)));
    		//ans=presum[r]-presum[l-1];
    	}
	}
	
	//fclose(stdin);
	return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve: