Let $$$x = n \times k + r$$$, where $$$r$$$ is the remainder when $$$x$$$ is divided by $$$n$$$ ($$$r \lt n$$$).

$$$x + $$$ $$$(x$$$ $$$mod$$$ $$$n)$$$ $$$= n \times k + r + r = n \times k + 2 \times r = n$$$

First case: $$$k = 0$$$

$$$2 \times r = n$$$, $$$r$$$ must be an integer, so we have $$$+1$$$ solution if $$$n$$$ is even.

Second case: $$$k = 1$$$

$$$n + 2 \times r = n$$$, $$$\Rightarrow r = 0$$$, here we have $$$+1$$$ solution for every $$$n$$$.

In general:

If $$$n$$$ is even, we have $$$2$$$ solutions.

If $$$n$$$ is odd, we have only $$$1$$$ solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        if(n%2) cout<<"1\n";
        else cout<<"2\n";
    }   
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Let $$$n$$$ in canonical form be $$${a_1} ^ {b_1} \times {a_2} ^ {b_2} \times {a_3} ^ {b_3} ...$$$, where $$$a_{i}$$$ is the $$$i-$$$th prime number and $$$b_{i}$$$ is its power. For example: $$$2025 = 2 ^ 0 \times 3 ^ 4 \times 5 ^ 2 \times 7 ^ 0 \times 11 ^ 0 ...$$$.

Let $$$E$$$ be an even square number. That means $$$E = e ^ 2$$$. $$$E$$$ is even, when $$$e$$$ is even too $$$\Rightarrow$$$ $$$E = e ^ 2 = (2 \times k) ^ 2 = 4 \times k^2$$$. We can see that $$$E$$$ is divisible by $$$2^2$$$. $$$E$$$ is square number $$$\Rightarrow$$$ every power is even. So we can represent $$$E = {c_1} ^ {d_1} \times {c_2} ^ {d_2} \times {c_3} ^ {d_3} ...$$$ where $$$c_{i}$$$ is the $$$i-$$$th prime number, $$$d_{i}$$$ is its power, $$$d_{i}$$$ is always even, and we know that $$$2^2$$$ divides $$$O$$$, so $$$d_{1} \ge 2$$$. $$$(*)$$$

Let $$$O$$$ be an odd square number. In analogical way: $$$O = {x_1} ^ {y_1} \times {x_2} ^ {y_2} \times {x_3} ^ {y_3} ...$$$ where $$$x_{i}$$$ is the $$$i-$$$th prime number and $$$y_{i}$$$ is its power. $$$O$$$ is not even, so we know for sure that $$$y_{1} = 0$$$. And $$$O$$$ is square number $$$\Rightarrow$$$ all $$$y$$$ are even numbers. $$$(**)$$$

Now we can calculate $$$f(n)$$$ and $$$g(n)$$$. We know that $$$n = {a_1} ^ {b_1} \times {a_2} ^ {b_2} \times {a_3} ^ {b_3} ...$$$.

From $$$(*)$$$: $$$f(n) = (\lfloor \frac{b_{1}}{2} \rfloor) \times (\lfloor \frac{b_{2}}{2} \rfloor + 1) \times (\lfloor \frac{b_{3}}{2} \rfloor + 1) ...$$$

From $$$(**):$$$ $$$g(n) = (\lfloor \frac{b_{2}}{2} \rfloor + 1) \times (\lfloor \frac{b_{3}}{2} \rfloor + 1) \times (\lfloor \frac{b_{4}}{2} \rfloor + 1) ...$$$

$$$\frac{f(n)}{g(n)} = \lfloor \frac{b_{1}}{2} \rfloor$$$. We know $$$a_{1} = 2$$$, so we must find the largest power of $$$2$$$, which divides $$$n$$$, and the final answer is this power divided by $$$2$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        if(n%2) cout<<"0\n";
        else{
            ll cnt=0;
            while(n%2==0){
                n/=2;
                cnt++;
            }
            cout<<(cnt/2)<<"\n";
        }
    }   
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<ll> a(n);
        for(ll i=0;i<n;i++) cin>>a[i];
        if(n>=5) cout<<"YES\n";
        else{
            bool ok=true;
            for(ll i=0;i<n;i++){
                if(a[i]%2!=(i+1)%2) ok=false;
            }
            if(ok) cout<<"YES\n";
            else cout<<"NO\n";
        }
    }   
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

An important observation is that for an $$$i$$$, its contribution for inversions is only related to the type of operation, and not to the arrangement of the numbers before $$$i$$$.

Note:

• $$$left[i]$$$: number of inversions made by $$$a[i]$$$ if we insert it to front.

• $$$right[i]$$$: number of inversions made by $$$a[i]$$$ if we insert it to back.

We can calculate $$$left[i]$$$ and $$$right[i]$$$ for each $$$i$$$ independently using Fenwick tree.

To find the answer for each $$$j$$$, we can sort $$$(left[i],right[i])$$$ by the value of $$$(left[i]-right[i])$$$. Then run the greedy algorithm.

#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;
int a[N],BIT[N],op1[N],op2[N],d[N];

void add(int p,int x)
{
	for(int i=p;i<=n;i+=(i&-i)) BIT[i]+=x;
}

int getsum(int p)
{
	int sum=0;
	for(int i=p;i;i-=(i&-i)) sum+=BIT[i];
	return sum;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) BIT[i]=0;
        for(int i=1;i<=n;i++)
        {
        	op1[i]=getsum(a[i]-1);
        	op2[i]=getsum(n)-getsum(a[i]);
        	d[i]=op1[i]-op2[i];
        	add(a[i],1);
        }
        ll cur=0;
        for(int i=1;i<=n;i++) cur+=op2[i];
        printf("%I64d ",cur);
        sort(d+1,d+n+1);
        for(int i=1;i<=n;i++)
        {
        	cur+=d[i]; 
        	printf("%I64d%c",cur,i==n?'\n':' ');
        }
	}
	
	return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Let's say we have already found the positions of the numbers $$$0$$$, $$$1$$$, $$$\ldots$$$, $$$k-1$$$ and want to find the position where the number $$$k$$$ is hidden. We will add positions of the numbers $$$0$$$, $$$1$$$, $$$\ldots$$$, $$$k-1$$$ to each query and binary search on the remaining positions that are not yet occupied.

Number of queries made is $$$\Sigma_{i=0}^{n-1} \log(n-i) \le 9n+1$$$.

#include <bits/stdc++.h>
#define endl '\n'

using ll = long long;
using namespace std;

const ll MOD = 1e9 + 7;

int perm[1026];
int id[1026];

void solve()
{
    int n;

    cin >> n;

    set <int> st;

    for (int i = 0; i < n; i++)
    {
        perm[i] = id[i] = 0;
        st.insert(i);
    }

    for (int i = 0; i < n; i++)
    {
        int l = 0, r = st.size() - 1;
        int mid, pos = *(st.rbegin());

        while (l < r)
        {
            mid = l + r >> 1;

            vector <int> query;

            for (int q = 0; q < i; q++)
            {
                query.push_back(id[q]);
            }

            int curr = -1;
            int last = 0;

            for (auto it : st)
            {
                curr++;
                query.push_back(it);

                if (curr == mid)
                {
                    last = it;

                    break;
                }
            }

            cout << "? " << query.size();

            for (auto it : query)
            {
                cout << " " << it;
            }

            cout << endl;
            cout.flush();

            int mex;

            cin >> mex;

            if (mex > i)
            {
                r = mid;
                pos = last;
            }
            else
            {
                l = mid + 1;
            }
        }

        perm[pos] = i;
        st.erase(pos);
        id[i] = pos;

        cout << "! " << pos << " " << i << endl;
        cout.flush();
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;

    cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}

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

#define all(x) x.begin(),x.end()

const int N = 2000;
int n, ans[N];

vector<int> f; // position of already found nums

int ask(vector<int> &v) { // asking funciton for case 1
    cout << "? " << (int)v.size() + (int)f.size(); 
    for(int &x : f) cout << ' ' << x-1;
    for(int &x : v) cout << ' ' << x-1;
    cout << endl;

    int mex;
    cin >> mex;
    return mex;
}

int ask(vector<int> &v, vector<int> &u) { // asking function for case 2
    cout << "? " << (int)v.size() + (int)u.size() + (int)f.size();
    for(int &x : f) cout << ' ' << x-1;
    for(int &x : v) cout << ' ' << x-1;
    for(int &x : u) cout << ' ' << x-1;
    cout << endl;

    int mex;
    cin >> mex;
    return mex;
}

void answer(int i,int v)
{
    cout<<"! "<<i<<' '<<v<<endl;
    cout<<flush;
}

void rand_shuffle(vector<int> &v, vector<int> &q1, vector<int> &q2) {
    int sz = v.size();
    for(int i = 0; i < sz; ++i) { // random shuffle
        int j = rand() % (i + 1);
        swap(v[i], v[j]);
    }
    for(int i = 0; i < sz; ++i) {
        if(i + i < sz) {
            q1.push_back(v[i]);
        } else {
            q2.push_back(v[i]);
        }
    }
}

void solve() {
    cin >> n;

    set<int> pos;
    for(int i = 1; i <= n; ++i) pos.insert(i);

    for(int cur = 1; cur < n; cur += 2) {
        vector<int> A(all(pos)), B(all(pos));

        while(A.size() > 1 || B.size() > 1) {

            bool ok = (A[0] == B[0]); // To check for case 1 or 2
            vector<int> q1, q2, q3, q4;

            rand_shuffle(A, q1, q2); // shuffle and split the set S0
            
            if(ok) { // Case 1 : S0 == S1

                int mex = ask(q1);
                if(mex > cur) {  
                    A = q1;
                    B = q1;
                } else if(mex == cur) {
                    A = q1;
                    B = q2;
                } else {
                    mex = ask(q2);
                    if(mex > cur) {
                        A = q2;
                        B = q2;
                    } else {
                        A = q2;
                        B = q1;
                    }
                }

            } else { // Case 2 : S0 != S1

                rand_shuffle(B, q3, q4); // shuffle and split the set S1

                int mex = ask(q1, q3);
                if(mex > cur) {
                    A = q1;
                    B = q3;
                } else if(mex == cur) {
                    A = q1;
                    B = q4;
                } else {
                    mex = ask(q2, q3);
                    if(mex > cur) {
                        A = q2;
                        B = q3;
                    } else {
                        A = q2;
                        B = q4;
                    }
                }
            }
        }

        //
        answer(A[0]-1,cur-1);
        answer(B[0]-1,cur);
        //

        ans[A[0]] = cur - 1; // fill the answer
        ans[B[0]] = cur;

        pos.erase(A[0]); // erase the already used positions 
        pos.erase(B[0]);

        f.push_back(A[0]); // add used positions for all future queries
        f.push_back(B[0]);
    }

    if(n & 1) {
        answer(*pos.begin()-1,n-1);
        
        ans[*pos.begin()] = n - 1;
    }

    /*
    cout << "!";
    for(int i = 1; i <= n; ++i) cout << ' ' << ans[i];
    cout << endl; 
    */

    f.clear();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    srand(chrono::steady_clock::now().time_since_epoch().count());
    
    int tt = 1; 
    cin >> tt;
    while(tt--) {
        solve();
    }
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Note $$$b[i]$$$: Number of $$$j$$$'s with $$$a[j] \gt = i$$$.

Let's see what happens when a move happens.

$$$oldb[i]=(number\ of\ olda[j]=i)+(number\ of\ olda[j] \gt i)$$$.

For all $$$L \lt =i \lt R$$$, all $$$a[j]=i$$$ has been decreased by $$$1$$$ so $$$newb[i]=(number\ of\ olda[j] \gt i)=oldb[i+1]$$$. This is left shift $$$b[L...R]$$$.

What about $$$b[R]$$$? Since we can choose any $$$a[j]=R$$$, the value range of $$$newb[R]$$$ is $$$[oldb[R+1],oldb[R]]$$$.

Generally, doing an operation in $$$[L,R]$$$ is to set $$$b[L]:=\ a\ value\ in\ [b[R+1],b[R]]$$$, then left shift $$$b[L...R]$$$.

Consider different $$$R$$$ (including $$$+\infty$$$), the value range of $$$b[L]$$$ is $$$[0,b[L]-1]$$$, this corresponds to "taking any number ($$$ \gt 0$$$) of stones from the pile of stones in $$$b[L]$$$".

Overall, the game is classical nim game on array $$$b$$$.

#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;
int a[N],b[N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		int NIM_SUM=0,cur=0;
		vector<int>  v;
		map<int,int> cnt;
		v.push_back(0);
		for(int i=1;i<=n;i++)
		{
			if(!cnt[a[i]]) v.push_back(a[i]);
			cnt[a[i]]++;
		}
		sort(v.begin(),v.end());
		for(int i=v.size()-1;i;i--)
		{
			cur+=cnt[v[i]];
			if((v[i]-v[i-1])&1) NIM_SUM^=cur;
		}
		printf("%s\n",NIM_SUM?"YES":"NO");
	}
	
	return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve: