#include <bits/stdc++.h>
using namespace std;
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	for(int test_number = 0; test_number < t; test_number++){
		int n; cin >> n;
		vector <string> long_subs;
		for(int i = 0; i < 2 * n - 2; i++){
			string s; 
			cin >> s;
			if((int)s.size() == n - 1){
				long_subs.push_back(s);
			}
		}
		reverse(long_subs[1].begin(), long_subs[1].end());
		if(long_subs[0] == long_subs[1]){
			cout<<"YES\n";
		}else{
			cout<<"NO\n";
		}
	}
	
	return 0;
}

• Amazing problem:
• Good problem:
• Bad problem:
• Didn't solve:

#include <bits/stdc++.h>
using namespace std;
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	for(int test_number = 0; test_number < t; test_number++){
		int n; cin >> n;
		vector <int> a(n);
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		for(int i = 0; i < n; i++){
			if(a[i] == 1){
				a[i]++;
			}
		}
		for(int i = 1; i < n; i++){
			if(a[i] % a[i - 1] == 0){
				a[i]++;
			}
		}
		for(auto i : a){
			cout << i << " ";
		}
		cout << "\n";
	}
	return 0;
}

Actually, the maximum number of operations performed by this algorithm is $$$\frac{3}{2}n$$$. Try to prove it!

• Amazing problem:
• Good problem:
• Bad problem:
• Didn't solve:

#include <bits/stdc++.h>
using namespace std;
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	for(int test_number = 0; test_number < t; test_number++){
		int n; cin >> n;
		vector <int> a(n);
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		vector<int> res;
		for(int i = 0; i < n; i++){
			int l = 1, r = i + 1;
			while(l <= r){
				int m = (l + r) / 2;
				if(a[i - m + 1] >= m){
					l = m + 1;
				}else{
					r = m - 1;
				}
			}
			res.push_back(r);
		}
		for(auto i : res){
			cout << i << " ";
		}
		cout<<"\n";
	}
	return 0;
}

• Amazing problem:
• Good problem:
• Bad problem:
• Didn't solve:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const ll MOD = 998244353;
 
//checks if n is prime
bool is_prime(ll n){
	if(n == 1){
		return false;
	}
	for(ll i = 2; i * i <= n; i++){
		if(n %i == 0){
			return false;
		}
	}
	return true;
}
 
//computes b ** e % MOD
ll fast_pow(ll b, ll e){
	ll res = 1;
	while(e > 0){
		if(e % 2 == 1){
			res = res * b % MOD;
		}
		b = b * b % MOD;
		e /= 2;
	}
	return res;
}
 
vector<pair<ll, ll>> primes;
 
const int MAXN = 5050;
 
ll dp[MAXN][MAXN];
 
ll fact[MAXN], fact_inv[MAXN];
 
ll f(ll x, ll y){
	ll &res = dp[x][y];
	if(res >= 0){
		return res;
	}
	if(x == (int)primes.size()){
		return res = (y == 0);
	}
	res = fact_inv[primes[x].second] * f(x + 1, y) % MOD;
	if(y > 0){
		res = (res + fact_inv[primes[x].second - 1] * f(x + 1, y - 1)) % MOD;	
	}
	return res;
}
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//reading the input
	int n; cin >> n;
	vector<ll> a(2 * n);
	for(int i = 0; i < 2 * n; i++){
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	//compressed version of a, pairs {value, #occurrences}
	vector<pair<ll, ll>> a_comp;
	for(int i = 0; i < 2 * n; i++){
		if(a_comp.size() == 0u || a_comp.back().first != a[i]){
			a_comp.push_back({a[i], 1});
		}else{
			a_comp.back().second++;
		}
	}
	//computing factorials and inverses
	fact[0] = 1;
	for(ll i = 1; i < MAXN; i++){
		fact[i] = fact[i-1] * i % MOD;
	}
	fact_inv[0] = 1;
	for(ll i = 0; i < MAXN; i++){
		fact_inv[i] = fast_pow(fact[i], MOD - 2);
	}
	//adding only primes for the dp
	for(auto i : a_comp){
		if(is_prime(i.first)){
			primes.push_back(i);
		}
	}
	memset(dp, -1, sizeof(dp));
	ll res = f(0, n);
	//we have to consider the contribution of non-primes too!
	for(auto i : a_comp){
		if(!is_prime(i.first)){
			res = res * fact_inv[i.second] % MOD;
		}
	}
	res = res * fact[n] % MOD;
	cout << res << "\n";
	return 0;
}

It is possible to solve the problem with greater constraints, like $$$n \leq 10^5$$$. Try to solve it with this new constraint!

• Amazing problem:
• Good problem:
• Bad problem:
• Didn't solve:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAXN = 200005;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
 
//Hashing stuff
const ll MOD[3] = {999727999, 1070777777, 1000000007};
ll B[3];
 
vector<ll> shift(vector<ll> h, ll val = 0){
	for(int k = 0; k < 3; k++){
		h[k] = (h[k] * B[k] + val) % MOD[k];
	}
	return h;
}
 
vector<ll> add(vector<ll> a, vector<ll> b){
	vector<ll> res(3);
	for(int k = 0; k < 3; k++){
		res[k] = (a[k] + b[k]) % MOD[k];
	}
	return res;
}
 
vector<ll> sub(vector<ll> a, vector<ll> b){
	vector<ll> res(3);
	for(int k = 0; k < 3; k++){
		res[k] = (a[k] - b[k] + MOD[k]) % MOD[k];
	}
	return res;
}
 
//Tree stuff
vector<int> g[MAXN];
 
bool vis[MAXN];
int parent[MAXN];
vector<ll> dp[MAXN], dp2[MAXN];
 
void dfs(int x){
	vis[x] = true;
	for(auto i : g[x]){
		if(!vis[i]){
			parent[i] = x;
			dfs(i);
			dp[x] = add(dp[x], shift(dp[i]));
		}
	}
	dp[x] = add(dp[x], {1, 1, 1});
}
 
void dfs2(int x){
	if(x != 0){
		dp2[x] = sub(dp[parent[x]], shift(dp[x]));
		dp2[x] = add(dp2[x], shift(dp2[parent[x]]));
	}
	for(auto i : g[x]){
		if(i != parent[x]){
			dfs2(i);
		}
	}
}
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(int k = 0; k < 3; k++){
		B[k] = rng() % MOD[k];
	}
	//reading the input
	int n; cin >> n;
	vector<int> occurrences(n);
	for(int i = 0; i < n - 1; i++){
		int a; cin >> a;
		occurrences[a]++;
	}
	for(int i = 0; i < n - 1; i++){
		int u, v; cin >> u >> v;
		u--; v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	//calculating possible list hashes
	vector<vector<ll>> list_hashes;
	vector<ll> h = {0, 0, 0};
	for(int i = n - 1; i >= 0; i--){
		h = shift(h, occurrences[i]);
	}
	vector<ll> extra = {1, 1, 1};
	for(int i = 0; i < n; i++){
		list_hashes.push_back(add(h, extra));
		extra = shift(extra);
	}
	//calculating possible tree hashes
	for(int i = 0; i < n; i++){
		dp[i] = {0, 0, 0};
		dp2[i] = {0, 0, 0};
	}
	parent[0] = -1;
	dfs(0);
	dfs2(0);
	vector<pair<vector<ll>, int>> tree_hashes;
	for(int i = 0; i < n; i++){
		if(i == 0){
			tree_hashes.push_back({dp[i], i});
		}else{
			tree_hashes.push_back({add(dp[i], shift(dp2[i])), i});
		}
	}
	//calculting the answer
	sort(list_hashes.begin(), list_hashes.end());
	sort(tree_hashes.begin(), tree_hashes.end());
	vector<int> res;
	int pos = 0;
	for(auto lh : list_hashes){
		while(pos < n && tree_hashes[pos].first < lh){
			pos++;
		}
		while(pos < n && tree_hashes[pos].first == lh){
			res.push_back(tree_hashes[pos].second);
			pos++;
		}
	}
	sort(res.begin(), res.end());
	cout << res.size() << "\n";
	for(auto i : res){
		cout << i + 1 << " ";
	}
	cout << "\n";
	return 0;
}

• Amazing problem:
• Good problem:
• Bad problem:
• Didn't solve:

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

int main(){
	int t; cin >> t;
	for(int i = 0; i < t; i++){
		long long n, s; 
		cin >> n >> s;
		cout << s / (n * n) << "\n";
	}
	return 0;
}

It can be proven that (try to prove it!) if some $$$k$$$ works, then $$$k=\displaystyle \left \lfloor \frac{n-1}{2} \right \rfloor$$$ has to work. This means that there is always an answer using $$$n$$$ or $$$n-1$$$ elements, depending on parity.

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

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin >> t;
	for(int test_number = 0; test_number < t; test_number++){
		int n; cin >> n;
		vector <long long> a(n);
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		sort(a.begin(), a.end());
		vector <long long> prefix_sums = {0};
		for(int i = 0; i < n; i++){
			prefix_sums.push_back(prefix_sums.back() + a[i]);
		}
		vector <long long> suffix_sums = {0};
		for(int i = n - 1; i >= 0; i--){
			suffix_sums.push_back(suffix_sums.back() + a[i]);
		}
		bool answer = false;
		for(int k = 1; k <= n; k++){
			if(2 * k + 1 <= n){
				long long blue_sum = prefix_sums[k + 1];
				long long red_sum = suffix_sums[k];
				if(blue_sum < red_sum){
					answer = true;
				}
			}
		}
		if(answer) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

Actually, there is no problem in repeating $$$1$$$, $$$2$$$, or any other power of two. This is because it can be proven that (try to prove it!) those sums are not optimal.

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

const long long MAXAI = 1000000000000ll;

int get_first_bit(long long n){
	return 63 - __builtin_clzll(n);
}

int get_bit_count(long long n){
	return __builtin_popcountll(n);
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin >> t;
	for(int test_number = 0; test_number < t; test_number++){
		long long n; cin >> n;
		//Computing factorials <= MAXAI
		vector<long long> fact;
		long long factorial = 6, number = 4;
		while(factorial <= MAXAI){
			fact.push_back(factorial);
			factorial *= number;
			number++;
		}
		//Computing masks of factorials
		vector<pair<long long, long long>> fact_sum(1 << fact.size());
		fact_sum[0] = {0, 0};
		for(int mask = 1; mask < (1 << fact.size()); mask++){
			auto first_bit = get_first_bit(mask);
			fact_sum[mask].first = fact_sum[mask ^ (1 << first_bit)].first + fact[first_bit];
			fact_sum[mask].second = get_bit_count(mask);
		}
		long long res = get_bit_count(n);
		for(auto i : fact_sum){
			if(i.first <= n){
				res = min(res, i.second + get_bit_count(n - i.first));
			}
		}
		cout << res << "\n";
	}
	
	return 0;
}

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

const int MAXN = 400005;

vector<int> g[MAXN];

bool vis[MAXN];
int pa[MAXN];

//DFS to compute the parent of each node
//parent of node i is stored at pa[i]
void dfs(int v){
	vis[v] = 1;
	for(auto i : g[v]){
		if(!vis[i]){
			pa[i] = v;
			dfs(i);
		}
	}
}

pair<int, int> dp[MAXN][2];

//Computes the value of function f, using dp
//the second coordinate of the pair is negated (to take maximums)
pair<int, int> f(int x, int y){
	pair<int, int> & res = dp[x][y];
	if(res.first >= 0) return res;
	res = {y, y ? -((int) g[x].size()) : -1};
	for(auto i : g[x]){
		if(i != pa[x]){
			pair<int, int> maxi = f(i, 0);
			if(y == 0) maxi = max(maxi, f(i, 1));
			res.first += maxi.first;
			res.second += maxi.second;
		}
	}
	return res;
}

vector<int> is_good;

//Recursive construction of the answer
//is_good[i] tells whether vertex i is good or not.
void build(pair<int, int> value, int v){
	if(value == f(v, 0)){
		is_good[v] = 0;
		for(auto i : g[v]){
			if(i != pa[v]){
				build(max(f(i, 0), f(i, 1)), i);
			}
		}
	}else{
		is_good[v] = 1;
		for(auto i : g[v]){
			if(i != pa[v]){
				build(f(i, 0), i);
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin >> n;
	for(int i = 0; i < n - 1; i++){
		int u, v; 
		cin >> u >> v; u--; v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	if(n == 2){
		cout<<"2 2\n1 1\n";
		return 0;
	}
	pa[0] = -1;
	dfs(0);
	for(int i = 0; i < n; i++) dp[i][0] = {-1, -1}, dp[i][1] = {-1, -1};
	pair<int, int> res = max(f(0, 0), f(0, 1));
	cout << res.first << " " << -res.second << "\n";
	is_good.resize(n);
	build(res, 0);
	for(int i = 0; i < n; i++){
		if(is_good[i]) cout << g[i].size() << " ";
		else cout << "1 ";
	}
	cout << "\n";
	return 0;
}

This solution uses the fact that $$$m\le 10^6$$$, other solutions do not use this, and work for much larger values of $$$m$$$ (like $$$m\leq 10^{18}$$$, but taking the answer modulo some big prime number). Try to solve the problem with this new constraint!

#include <bits/stdc++.h>
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;++i)
using namespace std;
typedef long long ll;

const int MAXM = 1000006;

const int MAXLOGN = 20;

bool visited_mul[MAXM * MAXLOGN];

int main(){
	ll n, m; cin >> n >> m;
	vector<ll> mul_quan(MAXLOGN);
	ll current_vis = 0;
	fore(i, 1, MAXLOGN){
		fore(j, 1, m+1){
			if(!visited_mul[i * j]){
				visited_mul[i * j] = 1;
				current_vis++;
			}
		}
		mul_quan[i] = current_vis;
	}
	ll res=1;
	vector<ll> vis(n + 1);
	fore(i, 2, n+1){
		if(vis[i]) continue;
		ll power = i, power_quan = 0;
		while(power <= n){
			vis[power] = 1;
			power_quan++;
			power *= i;
		}
		res += mul_quan[power_quan];
	}
	cout << res << "\n";
	
	return 0;
}

#include <bits/stdc++.h>
#define fore(i, a, b) for(int i = a; i < b; ++i)
using namespace std;
 
const int MAXN = 1010;

//c[i][j] = number of cards player i has, with the number j
int c[MAXN][MAXN];
 
//extras[i] is the stack of repeated cards for player i.
vector<int> extras[MAXN];
 
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin >> n;
	fore(i, 0, n){
		fore(j, 0, n){
			int x; cin >> x; x--;
			c[i][x]++;
			if(c[i][x] > 1) extras[i].push_back(x);
		}
	}
	vector<vector<int>> res;
	//First part
	while(true){
		//oper will describe the next operation to perform
		vector<int> oper(n);
		//s will be the first non-diverse player
		int s = -1;
		fore(i, 0, n){
			if(extras[i].size()){
				s = i;
				break;
			}
		}
		if(s == -1) break;
		//last_card will be the card that the previous player passed
		int last_card = -1;
		fore(i, s, s + n){
			int real_i = i % n;
			if(extras[real_i].size()){
				last_card = extras[real_i].back();
				extras[real_i].pop_back();
			}
			oper[real_i] = last_card;
		}
		res.push_back(oper);
		fore(i, 0, n){
			int i_next = (i + 1) % n;
			c[i][oper[i]]--;
			c[i_next][oper[i]]++;
		}
		fore(i, 0, n){
			int i_next = (i + 1) % n;
			if(c[i_next][oper[i]] > 1) extras[i_next].push_back(oper[i]);
		}
	}
	//Second part
	fore(j, 1, n){
		vector<int> oper;
		fore(i, 0, n) oper.push_back((i - j + n) % n);
		fore(i, 0, j) res.push_back(oper);
	}
	cout << res.size() << "\n";
	for(auto i : res){
		for(auto j : i) cout<< j + 1 << " ";
		cout << "\n";
	}
	return 0;
}