For any non-decreasing sequence $$$(b_1, b_2, \ldots, b_m)$$$, $$$b_1$$$ $$$|$$$ $$$b_2$$$ $$$|$$$ $$$b_3$$$ $$$|$$$ $$$\cdots$$$ $$$|$$$ $$$b_m$$$ $$$\ge$$$ $$$b_1$$$.

So, it is always better to consider subsequences of length $$$1$$$. Out of these, we can simply choose the smallest element and this is always optimal.

Time Complexity: $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int t;
    cin >> t;
 
    while(t--){
        
        int n;
        cin >> n;

        vector<int> a(n);
        for(int i = 0; i < n; i++) cin >> a[i];

        cout << *min_element(a.begin(), a.end()) << '\n';

    }
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

We can observe that $$$f(i,1)=0$$$ for $$$i \ge 1$$$ and $$$f(1,i)$$$ for $$$i \ge 2$$$.

Thus, "1 n-1" is always a valid answer.

// By Auchenai01
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
const ll MOD = 998244353;
const ll MAXX = 1e16;
const int INF = 1e9 + 7;
void solve() {
    int n;
    cin >> n;
    cout << 1 << " " << n - 1 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

If $$$m=1$$$, the answer is "YES".

Otherwise, to make $$$f(x,i)=1$$$ for all $$$2 \le i \le n$$$, the valuse of $$$x$$$ must be at least $$$\lcm(2,3,\ldots,n)+1$$$. We can see it will exceed $$$10^{18}$$$ when $$$n$$$ is larger than $$$30$$$.

Thus, the solution is: When $$$m=1$$$, output "YES". Otherwise, run bruteforce when $$$n \le 30$$$ and output "NO" when $$$n \gt 30$$$,

// By Auchenai01
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
const ll MOD = 998244353;
const ll MAXX = 1e16;
const int INF = 1e9 + 7;
void solve() {
    int n, m;
    cin >> n >> m;
    if (n <= 30) {
    	for (int i = 2; i <= n; i++) {
    		if (m % i != 1) {
    			cout << "NO" << endl;
    			return;
    		}
    	}
    	cout << "YES" << endl;
    	return;
    }
    cout << (m == 1 ? "Yes" : "no") << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Let's assume $$$\operatorname{mex}(a_1, a3, \ldots, a{n-1}) = p$$$ and $$$\operatorname{mex}(a_2, a4, \ldots, a{n}) = q$$$. Now the condition becomes $$$\operatorname{mex}(p, q) = \operatorname{mex}(a_1, a_2, a_3, \ldots, a_n)$$$.

We can see that the inequality $$$\operatorname{mex}(p, q) \le 2$$$ holds for any value of $$$p$$$ and $$$q$$$. So, we can simply check the three possible cases:

Case I: $$$\operatorname{mex}(p, q) = 0$$$

Here, we should have $$$p \gt 0$$$ and $$$q \gt 0$$$, and this implies that there are at least two 0's in the array $$$a$$$. Then, we have $$$\operatorname{mex}(a_1, a_2, a_3, \ldots, a_n) \gt 0 = \operatorname{mex}(p, q)$$$.

So, the array is not good in this case.

Case II: $$$\operatorname{mex}(p, q) = 1$$$

Here, we should have $$$p = 0$$$ and $$$q \ne 1$$$, or $$$p \ne 1$$$ and $$$q = 0$$$. In any case, $$$\operatorname{mex}(a_1, a_2, a_3, \ldots, a_n) \ne 1 = \operatorname{mex}(p, q)$$$.

So, the array is not good in this case.

Case III: $$$\operatorname{mex}(p, q) = 2$$$

Here, we should have $$$p = 0$$$ and $$$q = 1$$$, or $$$p = 1$$$ and $$$q = 0$$$. For the array to be good, we should also have $$$\operatorname{mex}(a_1, a_2, a_3, \ldots, a_n) = 2$$$.

Thus, an array is good if it's $$$\operatorname{mex} = 2$$$ and $$$\operatorname{mex}$$$ of even and odd indexed values are $$$0$$$ and $$$1$$$.

So, any array of length $$$n$$$ can be rearranged into a good array if all the following conditions are satisfied: $$$\operatorname{mex}$$$ of array is $$$2$$$. number of 0's in the array $$$\le \frac{n}{2}$$$. number of 1's in the array $$$\le \frac{n}{2}$$$.

Time Complexity: $$$O(n)$$$.

#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: