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 $$$\operatorname{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)$$$.

// 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;
    vi a(n);
    vi cnt(n + 1);
    for (int i = 0; i < n; i++) {
    	cin >> a[i];
    	cnt[a[i]]++;
    }
    if (cnt[0] == 0) {
    	cout << "NO" << endl;
    	return;
    }
    if (cnt[1] == 0) {
    	cout << "NO" << endl;
    	return;
    }
    if (cnt[2] > 0) {
    	cout << "NO" << endl;
    	return;
    }
    if (cnt[0] > n / 2 || cnt[1] > n / 2) {
    	cout << "NO" << endl;
    } else {
    	cout << "YES" << 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 $$$pre_i=\max_{1 \le j \le i}(a_j+a_{j+1}+\ldots+a_i)$$$, and $$$suf_i=\max_{i \le j \le n}(a_i+a_{i+1}+\ldots+a_j)$$$.

The answer is $$$\max_{1 \le j \le i \le}(pre_i+suf_j)$$$.

#include<bits/stdc++.h> 

using namespace std;  

typedef long double ld;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define int long long
#define C(x) ((x) * ((x) - 1) / 2)

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

  ll ans = 0, suf = 0, sm = 0;
  ll pref[n + 1] = {};
  pref[0] = 0;
  for(int i = 0; i < n; i ++)
    {
      sm += a[i];
      sm = max(0ll, sm);
      ans = max(ans, sm);
      pref[i + 1] = ans;
    }
  ans = pref[n - 1];
  sm = 0;
  for(int i = n - 1; i > 0; i--)
    {
      sm += a[i];
      sm = max(0ll, sm);
      suf = max(suf, sm);
      ans = max(pref[i - 1] + suf, ans);
    }   

  cout << ans << endl;
  
}
// if i % 2 == 1, i + 2, else i - 2
signed main()
{  
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  
  int t = 1;
  cin >> t;
  while(t--)
    solve();
  return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Observe that $$$x \oplus (x + 1) = 1$$$ when $$$x$$$ is even. This expression can be used to reduce $$$f(x)$$$.

Now, consider an array $$$b$$$ of length $$$m$$$. Let the number of odd values in the array be $$$p$$$. Let's check for the conditions which make the array good.

Case I: $$$p$$$ is even

Now, the total sum is even. So, $$$f(b_1 + b_2 + \cdots + b_m) = b_1 + b_2 + \cdots + b_m - 2$$$.

For array $$$b$$$ to be good, $$$(#\text{even}) - (#\text{odd}) = 1$$$.

Case II: $$$p$$$ is odd

Now, the total sum is odd. So, $$$f(b_1 + b_2 + \cdots + b_m) = b_1 + b_2 + \cdots + b_m + 2$$$.

For array $$$b$$$ to be good, $$$(#\text{even}) - (#\text{odd}) = -1$$$.

We can count subarrays of these two types using map and prefix sums.

Time Complexity: $$$O(n\text{log}n)$$$.

// 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;
    vi a(n);
    for (int i = 0; i < n; i++) {
    	cin >> a[i];
    }
    vvi cnt(4, vi(2 * n + 1));
    cnt[3][n] = 1;
    int cur = n;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
    	cur += ((a[i] % 2) ? 1 : -1);
    	cnt[i % 4][cur]++;
    	if (cur) ans += cnt[(i + 3) % 4][cur-1];
    	if (cur < 2 * n) ans += cnt[(i + 3) % 4][cur+1];
    }
    cout << ans << 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:

Several important observations: - If a node $$$x$$$ is the last node traversed by a node $$$i$$$, ($$$a_i = x$$$), then $$$a_x = x$$$.

• No other node, apart from the root node, can have the root node as the last traversed node, i.e., if $$$a_i = r$$$, then $$$i = r$$$.

• $$$a_i$$$ appears later than $$$i$$$ in the inorder traversal of the full binary tree.

• $$$a_r$$$ (where $$$r$$$ is the root) should be the last node in the inorder traversal of the full binary tree.

This gives us a simple solution -

• First check whether $$$a_{a_i} = a_i$$$ $$$\forall$$$ $$$i, 1 \leq i \leq n$$$.

• Then check if $$$a_i = r$$$ for $$$i \neq r$$$.

• After doing these checks, a traversal can be constructed as follows-

  • For a node $$$x$$$, map all those nodes $$$y$$$ such that $$$a_y = x$$$.
  • Mark a special node $$$last$$$ such that $$$a_r = last$$$.
  • Run a greedy solution over all nodes except the special node and first add those nodes to the traversal which are in the map and then that node itself.
  • Then finally add the root and the nodes in map of special node and then the special node itself.

Also look at the code for more clarification.

BONUS: can you implement the checker?

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