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:

Notice that, we can always swap two odd value and two even values, becuase their sum will always will be a even number greater than 2. Now, In the sorted permutation, all the odd values will be at odd and same for the even values. So, if the all the odd values are at odd indices and even values are at even indices, then we can always sort the permuation (by the first observation).

Now, only case left is when there are odd values which are at even indices and even values are at odd indices. for this case we only need to find a pair such that we can swap the odd value with even value,one such smallest pair is (4, 5). let say we want to swap $$$od$$$ with $$$ev$$$, so just swap the $$$od$$$ with 5 and $$$ev$$$ with 4. then we can swap (5, 4) and again we will swap 5 with $$$od$$$ and $$$ev$$$ with 4.

So, whenever the size of permutation >= 5, it is always possible, and for size <= 4, we can check it with brute force.

For more clear understanding please check this example:

so the final answer is just print "Yes" when the size of permutation >= 5. and for the lower values we can just do brute force.

#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$$$.

First, let's identify the positions of $$$0$$$ and $$$1$$$. Then we will find that this method is applicable to any $$$x$$$ and $$$x+1$$$.

Let $$$S_0$$$ and $$$S_1$$$ be the sets of possible positions for $$$0$$$ and $$$1$$$, respectively. Initially, $$$S_0 = S_1 = {0, 1, ..., n-1 } $$$.

Case $$$1$$$: $$$S_0 = S_1$$$.

Let $$$lhalf$$$ be a half of $$$S_0$$$, and $$$rhalf = S_0 - lhalf$$$. Consider querying $$$lhalf$$$:

• If the answer is $$$1$$$, we immediately know that $$$0$$$ is in $$$lhalf$$$ and $$$1$$$ is in $$$rhalf$$$.

• If the answer is $$$ \gt 1$$$, we immediately know that both $$$0$$$ and $$$1$$$ are in $$$lhalf$$$.

• If the answer is $$$0$$$, we need to query rhalf once more to determine the distribution of $$$0$$$ and $$$1$$$.

Through this operation, we reduce the size of both $$$S_0$$$ and $$$S_1$$$ by half. If randomization is used, the expected number of queries needed is $$$\frac{3}{2}$$$.

Case 2: $$$S_0$$$ and $$$S_1$$$ are disjoint.

Similarly, we randomly select half of $$$S_0$$$, $$$lhalf_0$$$, and half of $$$S_1$$$, $$$lhalf_1$$$. Consider querying $$$lhalf_0 ∪ lhalf_1$$$:

• If the answer is $$$1$$$ or $$$ \gt 1$$$, we can reduce the size of both $$$S_0$$$ and $$$S_1$$$ by half with just one query.

• Otherwise, we need to spend an additional query on $$$rhalf_0 ∪ lhalf_1$$$.

The total (expected) number of queries is $$$\frac{3}{4}$$$ of the easy version (i.e. $$$\frac{3}{4}\ \cdot 9n=6.75n$$$ ).

What is the probability that the number of queries exceeds $$$7n$$$? After transformation, this problem is equivalent to tossing a uniform coin $$$5000$$$ times, with a probability of facing up more than $$$3000$$$ times. This is a binomial distribution. We approximate it using a normal distribution, calculate the Z-value, and query the table. We can know that the probability is less than $$$10^{-9}$$$, which is small enough.

#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]$$$".

Conclusion: Assuming a player chooses the interval $$$[L, R]$$$ and reduces $$$x$$$ numbers by $$$1$$$. Observe the corresponding changes in the $$$b$$$ array, which corresponds to reducing $$$b[a[L]]$$$ by $$$x$$$ and reordering the array $$$b$$$.

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

So we only need to calculate the xor sum of array $$$b$$$. If the xor sum is $$$0$$$, then the answer is "NO". Otherwise, the answer is "YES".

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