There are $$$n$$$ valid $$$x=n+k(0\le k \lt n)$$$. So the answer is $$$n$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<pdd> vpdd;
typedef vector<vd> vvd;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
template<class T> bool chmax(T &a, T b) {
	if (a >= b) return false;
	a = b; return true;
}
template<class T> bool chmin(T &a, T b) {
	if (a <= b) return false;
	a = b; return true;
}
#define FOR(i, s, e, t) for ((i) = (s); (i) < (e); (i) += (t)) 
#define REP(i, e) for (int i = 0; i < (e); ++i) 
#define REP1(i, s, e) for (int i = (s); i < (e); ++i)
#define RREP(i, e) for (int i = (e); i >= 0; --i)
#define RREP1(i, e, s) for (int i = (e); i >= (s); --i)
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
#define maxe max_element
#define mine min_element
ll inf = 1e18;
#define DEBUG printf("%d\n", __LINE__); fflush(stdout);
template<class T> void print(vector<T> &v, bool withSize = false) {
	if (withSize) cout << v.size() << endl;
	REP(i, v.size()) cout << v[i] << " "; 
	cout << endl;
}
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

int __FAST_IO__ = []() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	return 0;
}();

#define TESTS int t; cin >> t; while (t--)
#define TEST 
int main() {
    TESTS {
    	ll N;
    	cin >> N;
    	printf("%lld\n", N);
    }
    
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<pdd> vpdd;
typedef vector<vd> vvd;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
template<class T> bool chmax(T &a, T b) {
	if (a >= b) return false;
	a = b; return true;
}
template<class T> bool chmin(T &a, T b) {
	if (a <= b) return false;
	a = b; return true;
}
#define FOR(i, s, e, t) for ((i) = (s); (i) < (e); (i) += (t)) 
#define REP(i, e) for (int i = 0; i < (e); ++i) 
#define REP1(i, s, e) for (int i = (s); i < (e); ++i)
#define RREP(i, e) for (int i = (e); i >= 0; --i)
#define RREP1(i, e, s) for (int i = (e); i >= (s); --i)
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
#define maxe max_element
#define mine min_element
ll inf = 1e18;
#define DEBUG printf("%d\n", __LINE__); fflush(stdout);
template<class T> void print(vector<T> &v, bool withSize = false) {
	if (withSize) cout << v.size() << endl;
	REP(i, v.size()) cout << v[i] << " "; 
	cout << endl;
}
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

int __FAST_IO__ = []() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	return 0;
}();

#define TESTS int t; cin >> t; while (t--)
#define TEST 
int main() {
    TESTS {
    	int N, X;
    	cin >> N >> X;
    	vi C(N), A(N);
    	REP(i, N) cin >> C[i];
    	REP(i, N) cin >> A[i];
    	int ans = 0, left = X;
    	priority_queue<int> q;
    	REP(i, N) {
    		q.push(C[i]);
    		left -= C[i];
    		while (left < 0) {
    			left += q.top();
    			ans++;
    			q.pop();
    		}
    		left += A[i];
    	}
    	printf("%d\n", ans);
    }
    
    return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

According to the Binomial Theorem,

The general $$$(r+1)$$$-th term is:

A key observation for this problem is that if any term in the binomial expansion is constant, the power of $$$x$$$ in that term must be zero (since $$$x^0 = 1$$$).

If the $$$(r+1)$$$-th term is constant, then:

(because $$$\binom{n}{r} \gt 0$$$)

Solving for $$$r$$$:

This means a constant term exists if and only if $$$(1 + m)$$$ divides $$$n$$$ (i.e., $$$n \equiv 0 \pmod{1 + m}$$$).

Equivalently, $$$(1 + m) \mid n$$$ if and only if $$$(m - 1)$$$ is a divisor of $$$n$$$.

Thus, the answer to this problem is:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<pdd> vpdd;
typedef vector<vd> vvd;
#define yn(ans) printf("%s\n", (ans)?"Yes":"No");
#define YN(ans) printf("%s\n", (ans)?"YES":"NO");
template<class T> bool chmax(T &a, T b) {
	if (a >= b) return false;
	a = b; return true;
}
template<class T> bool chmin(T &a, T b) {
	if (a <= b) return false;
	a = b; return true;
}
#define FOR(i, s, e, t) for ((i) = (s); (i) < (e); (i) += (t)) 
#define REP(i, e) for (int i = 0; i < (e); ++i) 
#define REP1(i, s, e) for (int i = (s); i < (e); ++i)
#define RREP(i, e) for (int i = (e); i >= 0; --i)
#define RREP1(i, e, s) for (int i = (e); i >= (s); --i)
#define all(v) v.begin(), v.end()
#define pb push_back
#define qb pop_back
#define pf push_front
#define qf pop_front
#define maxe max_element
#define mine min_element
ll inf = 1e18;
#define DEBUG printf("%d\n", __LINE__); fflush(stdout);
template<class T> void print(vector<T> &v, bool withSize = false) {
	if (withSize) cout << v.size() << endl;
	REP(i, v.size()) cout << v[i] << " "; 
	cout << endl;
}
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());

int __FAST_IO__ = []() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	return 0;
}();

#define TESTS int t; cin >> t; while (t--)
#define TEST 
int main() {
    TESTS {
    	int N;
    	cin >> N;
    	ll ans = 0;
    	for (int i = 1; 1ll * i * i <= N; ++i) {
    		if (N % i == 0) {
    			if (i > 1) ans += i - 1;
    			if (1ll * i * i != N) ans += N / i - 1;
    		}
    	}
    	printf("%lld\n", ans);
    }
    
    return 0;
}

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: