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?

// 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;
class DSU {
public:
    vector<int> parent, size;
    DSU(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i; 
        }
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); 
        }
        return parent[x];
    }
     void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a != b) {
            if (size[a] < size[b]) swap(a, b);
            parent[b] = a;
            size[a] += size[b];
        }
    }
};
void solve() {
    int n, r;
    cin >> n >> r;
    r--;
    DSU D(n);
    vi a(n);
    for (int i = 0; i < n; i++) {
    	int x;
    	cin >> x;
    	x--;
    	D.unite(x, i);
    	a[i] = x;
    }
    for (int i = 0; i < n; i++) {
    	if (a[i] == r && i != r) {
    		cout << -1 << endl;
    		return;
    	}
    }
    vi P(n, -1);
    vvi V(n);
    int mark = -1;
    for (int i = 0; i < n; i++) {
    	int y = D.find(i);
    	if (P[y] == -1) {
    		P[y] = a[i];
    	} else if (P[y] != a[i]) {
    		cout << -1 << endl;
    		return;
    	}
    	V[a[i]].push_back(i);
    	if (i == r) {
    		mark = a[i];
    	}
    }
    vi ans;
    for (int i = 0; i < n; i++) {
    	if (i != mark) {
    		for (int v : V[i]) {
    			if (v != i) ans.push_back(v);
    		}
    		if (V[i].size()) ans.push_back(i);
    	}
    }
    ans.push_back(r);
    for (int v : V[mark]) {
    	if (v != mark && v != r) ans.push_back(v);
    }
    if (mark != r && V[mark].size()) ans.push_back(mark);
    assert(ans.size() == n);
    for (int i = 0; i < n; i++) {
    	cout << ans[i] + 1 << " ";
    }
    cout << 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 find the minimum value first.

We can see there exists a sequence of operations where the last operation is the G-operation and obtains the minimum value. Since $$$\operatorname{lcm}(x,y) \ge \operatorname{gcd}(x,y)$$$, all sequences where the last operation is an L-operation have a value greater than or equal to the value of sequences where the last operation is a G-operation.

When we fix using $$$s_n='G'$$$, we only care about the gcd value of the current value and $$$a_n$$$. Thus, we have $$$dp_{i,j,k= 0/1}$$$ ~--- the number if schemes in the first $$$i$$$ operations, where the gcd value of the current value and $$$a_n$$$ is $$$j$$$ and the last operation is $$$k$$$.

In this way, we can obtain the number of valid operation sequences when $$$s_n='G'$$$. Now lets consier a operation sequences like $$$s=" \ldots GLL \ldots L"$$$. We can see $$$s_j=s_{j+1}=\ldots=s_{n}='L'$$$ is valid only if $$$\operatorname{gcd}(a_j,a_{j+1},\ldots,a_n)=a_n$$$. For such $$$j$$$, we can update the answer with the original dp value.

Then we sill need to find the maximum index $$$mx$$$ such that $$$\operatorname{gcd}(a_j,a_{j+1},\ldots,a_n) \neq a_n$$$. We can see the $$$mx$$$-th operation must be a $$$G$$$-operation. We need to do the above dp again, but this time, we only care about the gcd value of the current value and $$$a_{mx}$$$.

Time Complexity: $$$O(n \cdot \operatorname{divisors}(A) \cdot \log(A))$$$.

#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;
int T;
ll n,x;
ll a[N];
map<ll,ll> dp[N][2];

/*
 * 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
 */

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

vector<ll> divs[N];

void init_divs()
{
	for(int i=1;i<N;i++)
		for(int j=1;j*i<N;j++)
            divs[j*i].push_back(i);
}

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

ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}

ll lcm(ll a,ll b)
{
    return a*b/gcd(a,b);
}

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

void DP(ll k)
{
    //
    //printf("DP\n");
    //
    for(int i=1;i<=n;i++)
        for(int j=0;j<=1;j++)
            dp[i][j].clear();
    queue<tuple<ll,ll,ll> > Q;
    dp[1][0][gcd(k,gcd(x,a[1]))]=1;
    dp[1][1][gcd(k,lcm(x,a[1]))]=1;
    Q.push({1,0,gcd(k,gcd(x,a[1]))});
    Q.push({1,1,gcd(k,lcm(x,a[1]))});
    while(!Q.empty())
    {
        tuple<ll,ll,ll> t=Q.front();
        ll i=get<0>(t),ty=get<1>(t),val=get<2>(t);
        Q.pop();
        //
       // printf("i=%lld ty=%lld val=%lld dp=%lld\n",i,ty,val,dp[i][ty][val]);
        //
        if(i==n) continue;
        if(ty)
        {
            ll vg=gcd(k,gcd(val,a[i+1])),vl=gcd(k,lcm(val,a[i+1]));
            if(!dp[i+1][0][vg]) Q.push({i+1,0,vg});
            dp[i+1][0][vg]+=dp[i][1][val],dp[i+1][0][vg]%=TMD;
            if(!dp[i+1][1][vl]) Q.push({i+1,1,vl});
            dp[i+1][1][vl]+=dp[i][1][val],dp[i+1][1][vl]%=TMD;
        }
        else
        {
            ll vl=gcd(k,lcm(val,a[i+1]));
            if(!dp[i+1][1][vl]) Q.push({i+1,1,vl});
            dp[i+1][1][vl]+=dp[i][0][val],dp[i+1][1][vl]%=TMD;
        }
    }
}

void solve()
{
    //
    //printf("solve\n");
    //
    ll mn=x,ans=0;
    for(int i=1;i<=n;i++)
    {
        if((i&1)==(n&1)) mn=gcd(mn,a[i]);
        else mn=lcm(mn,a[i]);
    }
    DP(a[n]);
    if(mn!=a[n])
    {
        cout<<mn<<" "<<dp[n][0][mn]<<"\n";
        return ;
    }
    //
     //
    //printf("solve2 mn=%lld\n",mn);
    //
    ans=dp[n][0][mn];
    for(int i=n-1;i;i--)
    {
        if(a[n]%a[i])
        {
            //
            //printf("before i=%d ans=%lld\n",i,ans);
            //
            DP(a[i]);
            for(auto &j:dp[i][0])
                if(!(a[n]%j.first)) ans+=j.second,ans%=TMD;
            //
            //printf("after i=%d ans=%lld\n",i,ans);
            //
            break;
        }
        else
        {
            for(auto &j:dp[i][0])
                ans+=j.second,ans%=TMD;
        }
    }
    ans++;      //LLL...L
    ans%=TMD;
    a[0]=x;
    for(int i=0;i<=n;i++)
    {
        if(a[n]%a[i])
        {
            ans+=TMD-1;
            ans%=TMD;
            break;
        }
    }
    //
    cout<<mn<<" "<<ans<<"\n";
}

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

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

int bruteforce()
{
    return 0;
}

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

int main()
{
    fastio;

    init_divs();
    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: