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