• Great:
• Good:
• Average:
• Bad:
• Trash:

• A:
• B:
• C1:
• C2:
• D:
• E:
• F1:
• F2:
• G:
• H1:
• H2:

• A:
• B:
• C1:
• C2:
• D:
• E:
• F1:
• F2:
• G:
• H1:
• H2:

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

const int N = 3e5 + 9;
using ll = long long;

void solve() {
  int n; cin >> n;
  for (int i = 1; i <= n; i++) {
    cout << 2 * i - 1 << ' ';
  }
  cout << '\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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

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

const int N = 3e5 + 9;
using ll = long long;

void solve() {
  string s; cin >> s;
  int n = s.size();
  for (int i = 0; i + 1 < n; i++) {
    if (s[i] == s[i + 1]) {
      cout << s.substr(i, 2) << '\n';
      return;
    }
  }
  for (int i = 0; i + 2 < n; i++) {
    if (s[i] != s[i + 1] and s[i] != s[i + 2] and s[i + 1] != s[i + 2]) {
      cout << s.substr(i, 3) << '\n';
      return;
    }
  }
  cout << -1 << '\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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

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

using ll = long long;

void solve() {
  int x; ll m; cin >> x >> m;

  int ans = 0;
  for (int y = 1; y <= min(2LL * x, m); y++) {
    if (x != y and ((x % (x ^ y)) == 0 or (y % (x ^ y) == 0))) {
      ++ans;
    }
  }
  cout << ans << '\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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

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

using ll = long long;

void solve() {
  int x; ll m; cin >> x >> m;

  // divisible by x
  ll p = m - m % x;
  ll ans = p / x - (x < p);
  if ((x ^ p) >= 1 and (x ^ p) <= m) ++ans;
  p += x;
  if ((x ^ p) >= 1 and (x ^ p) <= m) ++ans;

  // divisibly by y
  for (int y = 1; y <= min(1LL * x, m); y++) {
    ll cur = x ^ y;
    if (cur % y == 0) {
      ++ans;
    }
  }

  // divisible by both
  if (x <= m) {
    --ans;
  }

  cout << ans << '\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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

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

const int N = 1e5 + 9;
int p[N];
void solve() {
  int n, m; cin >> n >> m;
  vector<int> s(m + 1);
  for (int i = 1; i <= m; i++) {
    cin >> s[i];
  }
  if (m < __lg(n) + 1) {
    cout << -1 << '\n';
    return;
  }
  for (int i = 1; i <= n; i++) {
    cout << s[m - p[i]] << ' ';
  }
  cout << '\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 2; i < N; i++) {
    if (p[i]) continue;
    for (int j = i; j < N; j += i) {
      int x = j;
      while (x % i == 0) x /= i, ++p[j];
    }
  }
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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

const int N = 1e5 + 9;
using ll = long long;

vector<int> d[N];
void solve() {
  int n, m; cin >> n >> m;
  vector<int> s(m + 1);
  for (int i = 1; i <= m; i++) {
    cin >> s[i];
  }
  vector<int> a(n + 1, -1);
  for (int i = 1; i <= n; i++) {
    set<int> banned;
    for (int j: d[i]) {
      banned.insert(a[j]);
    }
    for (int k = m; k >= 1; k--) {
        if (banned.find(s[k]) == banned.end()) {
            a[i] = s[k];
            break;
        }
    }
    if (a[i] == -1) {
        cout << -1 << '\n';
        return;
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << a[i] << ' ';
  }
  cout << '\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 1; i < N; i++) {
    for (int j = i + i; j < N; j += i) {
        d[j].push_back(i);
    }
  }
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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

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

const int N = 1e6 + 9, mod = 998244353;
using ll = long long;

int dp[N]; // count of arrays that we can get if the current number of inversions is > max element of the array
void solve() {
  int n; cin >> n;
  int sum = 0;
  for (int i = n; i >= 1; i--) {
    dp[i] = (1LL * i * sum % mod + 1) % mod;
    sum = (sum + dp[i]) % mod;
  }
  int ans = n - 1; // arrays having 0 and 1 inversions
  for (int k = 3; k <= n; k++) {
    int ways = (1LL * (k - 1) * (k - 2) / 2 - 1 + mod) % mod; // count of arrays achievable such that > 1 inversion count was inserted for the first time
    ans += 1LL * ways * dp[k] % mod;
    ans %= mod;
  }
  cout << ans << '\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

#include <bits/stdc++.h>

#include <chrono>
std::mt19937 eng(std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) { return std::uniform_int_distribution<int>(l, r)(eng); }

namespace FastIO {
//	char buf[1 << 21], *p1 = buf, *p2 = buf;
//	#define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
	template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
	template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
//	inline char rChar() { char ch = getchar(); while (!isalpha(ch)) ch = getchar(); return ch; }
}; using namespace FastIO;

using i32 = int32_t;
using u32 = uint32_t;
using u64 = uint64_t;
template <uint32_t MOD> struct mint {
	static constexpr u32 get_r() {
		u32 ret = MOD;
		for (i32 i = 0; i < 4; ++i) ret *= 2 - MOD * ret;
		return ret;
	}
	static constexpr u32 r = get_r();
	static constexpr u32 n2 = -u64(MOD) % MOD;
	static_assert(r * MOD == 1, "invalid, r * MOD != 1");
	static_assert(MOD < (1 << 30), "invalid, MOD >= 2 ^ 30");
	static_assert((MOD & 1) == 1, "invalid, MOD % 2 == 0");
	u32 a;
	constexpr mint() : a(0) {}
	constexpr mint(const int64_t &b) : a(reduce(u64(b % MOD + MOD) * n2)){};
	static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * MOD) >> 32; }
	 constexpr mint &operator += (const mint &b) { if (i32(a += b.a - 2 * MOD) < 0) a += 2 * MOD; return *this; }
	constexpr mint &operator -= (const mint &b) { if (i32(a -= b.a) < 0) a += 2 * MOD; return *this; }
	constexpr mint &operator *= (const mint &b) { a = reduce(u64(a) * b.a); return *this; }
	constexpr mint &operator /= (const mint &b) { *this *= b.inverse(); return *this; }
	constexpr mint operator + (const mint &b) const { return mint(*this) += b; }
	constexpr mint operator - (const mint &b) const { return mint(*this) -= b; }
	constexpr mint operator * (const mint &b) const { return mint(*this) *= b; }
	constexpr mint operator / (const mint &b) const { return mint(*this) /= b; }
	constexpr bool operator == (const mint &b) const { return (a >= MOD ? a - MOD : a) == (b.a >= MOD ? b.a - MOD : b.a); }
	constexpr bool operator != (const mint &b) const { return (a >= MOD ? a - MOD : a) != (b.a >= MOD ? b.a - MOD : b.a); }
	constexpr mint operator-() const { return mint() - mint(*this); }
	constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul, n >>= 1; } return ret; }
	constexpr mint inverse() const { return pow(MOD - 2); }
	friend std::ostream &operator<< (std::ostream &os, const mint &b) { return os << b.get(); }
	friend std::istream &operator>> (std::istream &is, mint &b) { int64_t t; is >> t; b = mint<MOD>(t); return (is); }
	constexpr u32 get() const { u32 ret = reduce(a); return ret >= MOD ? ret - MOD : ret; }
	static constexpr u32 get_MOD() { return MOD; }
    explicit operator u32() const { return get(); }
}; using modint = mint<998244353>;

// Let's write some brute first
// dp[i][j] := current length is i, current number of inversions is j (not inserted)
// dp[i][j] -> dp[>= i + 1][[j + 1, j + i]]
// this is true for j >= 1, so let's do something when j = 0
// we can generate [0, (0 ... ), 1, 0] -> dp[>= 3][1]
// this is still kinda annoying because 1 > 1 does not hold, we process it till j >= 2
// [0, 0, ..., 0, 1, 0] -> [0, 0, ..., 0, 1, 0, 1, ..., 1]
// after that we insert an 1 before some numbers of 0 and we get dp[i][1] -> dp[>= i + 1][[j + 1, j + i - 1]]
// the answer is sum dp[i][j] for all 1 <= i <= n, j >= 1, plus 1 ([0, 0, 0 ... 1])
// actually we care nothing 'bout, j so let's say f[i] = sum dp[i][j]
// (f[i] * i - 1) -> f[i + 1], f[i + 2], ..., f[n]

#define MAXN 1000001
modint f[MAXN];
void solve() {
	int n = read<int>(); modint ans = 1, pre = 2;
	f[3] = 1;
	for (int i = 4; i <= n; ++i) 
		f[i] = pre + modint(1), pre += f[i] * modint(i) - modint(1);
	for (int i = 3; i <= n; ++i) ans += f[i];
	// f[3] : [0, 1, 0]
	// f[4] : [0, 0, 1, 0] (+1), [0, 1, 1, 0], [1, 0, 1, 0] (dp[3][1] * 2)
	print<int>(ans.get(), '\n');
}

int main() { int T = read<int>(); while (T--) solve(); return 0; }

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

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

const int N = 2e5 + 9, mod = 998244353;
using ll = long long;

int add(int a, int b){
	a += b;
	if(a > mod) a -= mod;
	if(a < 0) a += mod;
	return a;
}

// dp[i][j] = number of arrays where starting element is i and gcd of the array is j
int dp[N], cur[N], uni[N];
int sum[N];
vector<int> d[N];
void solve() {
  int m; cin >> m;
  for (int i = 1; i <= m; i++) {
    dp[i] = cur[i] = 0;
	uni[i] = 0;
	sum[i] = 0;
  }
  int ans = 0;
  ans = 0;
  for (int i = m; i >= 1; i--) {
    for (int j: d[i]) {
      cur[j] = 0;
    }
	int sz = d[i].size();
	for(int idj = sz-1; idj >= 0; idj--){
		int j = d[i][idj];
		uni[j] = add(sum[j],sum[j]);
		for(int idk = idj+1; idk < sz; idk++){
			int k = d[i][idk];
			if(k%j) continue;
			uni[j] = add(uni[j],-uni[k]);
		}
		cur[j] = add(uni[j], - add(dp[j],dp[j]));
	}

    cur[i] += 1;

    for (int j : d[i]) {
	  dp[j] = add(dp[j],cur[j]);
	  for(auto k : d[j]){
	  	sum[k] = add(sum[k],cur[j]);
	  }
	  ans = add(ans,cur[j]);
    }
	
  }
  cout << ans << '\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 1; i < N; i++) {
    for (int j = i; j < N; j += i) {
      d[j].push_back(i);
    }
  }
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e6 + 9, mod = 998244353;
 
inline void add(int &x, int y) {
  x = x + y >= mod ? x + y - mod : x + y;
}
int mob[N];
void mobius() {
  mob[1] = 1;
  for (int i = 2; i < N; i++){
    mob[i]--;
    for (int j = i + i; j < N; j += i) {
      mob[j] -= mob[i];
    }
  }
  for (int i = 1; i < N; i++) {
    mob[i] = (mob[i] % mod + mod) % mod;
  }
}
vector<int> divs[N];
int dp[N];
int f[N];
int tmp[N], ans[N];
void solve() {
  for (int i = 1; i < N; i++) {
    for (int d: divs[i]) {
      tmp[d] = (mod - f[d]) % mod;
      for (int c: divs[d]) {
        add(tmp[d], dp[c]);
      }
      tmp[d] = (2 * tmp[d] + 1) % mod;
    }

    // apply mobius inversion formula
    for (int d: divs[i]) {
      for (int c: divs[d]) {
        add(dp[d], 1LL * mob[c] * tmp[d / c] % mod);
      }
      add(f[d], tmp[d]);
    }

    ans[i] = ans[i - 1];
    add(ans[i], f[i]);
  }
}
 
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 1; i < N; i++) {
    for (int j = i; j < N; j += i) {
      divs[j].push_back(i);
    }
  }
  mobius();
  solve();
  int t = 1;
  cin >> t;
  while (t--) {
    int m; cin >> m;
    cout << ans[m] << '\n';
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e6 + 9, mod = 998244353;
 
inline void add(int &x, int y) {
  x = x + y >= mod ? x + y - mod : x + y;
}
int spf[N];
void sieve() {
  vector<int> p;
  for(int i = 2; i < N; i++) {
    if (spf[i] == 0) spf[i] = i, p.push_back(i);
    int sz = p.size();
    for (int j = 0; j < sz && i * p[j] < N && p[j] <= spf[i]; j++) {
      spf[i * p[j]] = p[j];
    }
  }
}
int mob[N];
void mobius() {
  mob[1] = 1;
  for (int i = 2; i < N; i++){
    mob[i]--;
    for (int j = i + i; j < N; j += i) {
      mob[j] -= mob[i];
    }
  }
  for (int i = 1; i < N; i++) {
    mob[i] = (mob[i] % mod + mod) % mod;
  }
}
int c[N];
vector<int> divs[N];
void gen_divs(int n) { // not sorted
  int id = 1, x = n;
  divs[n][0] = 1;
  while (n > 1) {
    int k = spf[n];
    int cur = 1, sz = id;
    while (n % k == 0) {
      cur *= k;
      n /= k;
      for (int i = 0; i < sz; i++) {
        divs[x][id++] = divs[x][i] * cur;
      }
    }
  }
}

void prec() {
  sieve();
  // generate divisors without using push_back as its really slow on Codeforces
  for (int i = 1; i < N; i++) {
    for (int j = i; j < N; j += i) {
      c[j]++;
    }
    divs[i].resize(c[i]);
    gen_divs(i);
  }
  mobius();
}
int dp[N];
int f[N];
int tmp[N], ans[N];
void solve() {
  for (int i = 1; i < N; i++) {
    for (int d: divs[i]) {
      tmp[d] = (mod - f[d]) % mod;
      for (int c: divs[d]) {
        add(tmp[d], dp[c]);
      }
      tmp[d] = (2 * tmp[d] + 1) % mod;
    }

    // apply mobius inversion formula
    for (int d: divs[i]) {
      for (int c: divs[d]) {
        add(dp[d], 1LL * mob[c] * tmp[d / c] % mod);
      }
      add(f[d], tmp[d]);
    }

    ans[i] = ans[i - 1];
    add(ans[i], f[i]);
  }
}
 
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  prec();
  solve();
  int t = 1;
  cin >> t;
  while (t--) {
    int m; cin >> m;
    cout << ans[m] << '\n';
  }
  return 0;
}

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

#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};

const int N = 1e6 + 9, T = 1e7 + 9, RT = 33333, mod = 998244353; 
using ll = long long;

int power(int n, long long k) {
  int ans = 1 % mod;
  while (k) {
    if (k & 1) ans = (long long) ans * n % mod;
    n = (long long) n * n % mod;
    k >>= 1;
  }
  return ans;
}

int SQRT(int n) {
  int x = sqrt(n);
  while (x * x < n) ++x;
  while (x * x > n) --x;
  return x;
}

int spf[T], id[T], DIAMETER, mu[T];
vector<int> primes; // 1 indexed
int prefix_prime_count[T], prefix_sum_mu[T];
void init() {
  mu[1] = 1;
  for(int i = 2; i < T; i++) {
    if (spf[i] == 0) spf[i] = i, mu[i] = i <= DIAMETER ? 0 : -1, primes.push_back(i);
    int sz = primes.size();
    for (int j = 0; j < sz && i * primes[j] < T && primes[j] <= spf[i]; j++) {
      spf[i * primes[j]] = primes[j];
      if (i % primes[j] == 0) mu[i * primes[j]] = 0;
      else mu[i * primes[j]] = mu[i] * (primes[j] <= DIAMETER ? 0 : -1);
    }
  }
  primes.insert(primes.begin(), 0);
  for (int i = 1; i < primes.size(); i++) {
    id[primes[i]] = i;
  }
  for (int i = 2; i < T; i++) {
    prefix_prime_count[i] = prefix_prime_count[i - 1] + (spf[i] == i);
  }
  for (int i = 1; i < T; i++) prefix_sum_mu[i] = prefix_sum_mu[i - 1] + mu[i];
}
int cnt[N]; // count of nodes having each diameter
int m;
namespace GoodNumbers { // numbers which aren't divisible by the first k primes
  gp_hash_table<int, int, custom_hash> mp[RT << 1];
  int count_num(int n, int k) { // n is a floor value, returns good numbers <= n
    if (k == 0 or n == 0) return n;
    if (primes[k] >= n) return 1;
    if (n < T and 1LL * primes[k] * primes[k] > n) {
      return 1 + prefix_prime_count[n] - k;
    }
    if (mp[k].find(n) != mp[k].end()) return mp[k][n];
    int ans;
    if (1LL * primes[k] * primes[k] > n) {
      int x = upper_bound(primes.begin(), primes.begin() + k, (int)SQRT(n)) - primes.begin() - 1;
      ans = count_num(n, x) - (k - x);
    }
    else ans = count_num(n, k - 1) - count_num(n / primes[k], k - 1);
    mp[k][n] = ans;
    return ans;
  }
};

vector<pair<int, int>> v;
namespace Dirichlet {
  // good number = numbers that aren't divisible by any prime <= DIAMETER
  // we will run dirichlet imagining there exists no prime <= DIAMETER
  gp_hash_table<int, int, custom_hash> mp;
  int p_c(int n) {
    return n < 1 ? 0 : 1;
  }
  int p_g(int n) {
    return GoodNumbers::count_num(n, v.back().first);
  }
  int solve (int x) { // sum of mob[i] over 1 <= i <= x and i is a good number
    if (x < T) return prefix_sum_mu[x];
    if (mp.find(x) != mp.end()) return mp[x];
    int ans = 0;
    for (int i = 2, last; i <= x; i = last + 1) {
      last = x / (x / i);
      ans += solve(x / i) * (p_g(last) - p_g(i - 1));
    }
    ans = p_c(x) - ans;
    return mp[x] = ans;
  }
};

int count_primes(int n) {
  if (n < T) return prefix_prime_count[n];
  int x = SQRT(n);
  int k = upper_bound(primes.begin(), primes.end(), x) - primes.begin() - 1;
  return GoodNumbers::count_num(n, k) + k - 1;
}


// diameter > 2 * sqrt(m)
void solve_large() {
  // only primes are good, so count total ways
  // and subtract where gcd is prime (means all nodes have a fixed prime)
  int total_ways = 1;
  int primes_under_m = count_primes(m);
  for (auto [k, c]: v) {
    if (m <= primes[k]) break;
    total_ways = 1LL * total_ways * power((primes_under_m - k + 1) % mod, c) % mod; // 1 or a prime > k
  }
  int bad_ways = (max(0, primes_under_m - v.back().first)) % mod;
  int ans = (total_ways - bad_ways + mod) % mod;
  cout << ans << '\n';
}

// diameter <= 2 * sqrt(m)
void solve_small() {
  int ans = 0;
  for (int l = 1, r; l <= m; l = r + 1) {
    int x = m / l;
    r = m / x;
    int cur = ((Dirichlet::solve(r) - Dirichlet::solve(l - 1)) % mod + mod) % mod;
    if (cur) {
      int mul = 1;
      for (auto [k, c]: v) {
        if (x <= primes[k]) break;
        mul = 1LL * mul * power(GoodNumbers::count_num(x, k) % mod, c) % mod;
      }
      ans += 1LL * cur * mul % mod;
      ans %= mod;
    }
  }
  cout << ans << '\n';
}

vector<int> g[N];
int dp[N], up[N];
void dfs(int u, int p = 0) {
  dp[u] = 0;
  if (p) g[u].erase(find(g[u].begin(), g[u].end(), p));
  for (auto v: g[u]) {
    if (v ^ p) {
      dfs(v, u);
      dp[u] = max(dp[u], dp[v] + 1);
    }
  }
}
int pref[N], suf[N];
void dfs2(int u) {
  int sz = g[u].size();
  for (int i = 0; i < sz; i++) {
    int v = g[u][i];
    pref[i] = dp[v] + 1;
    if (i) pref[i] = max(pref[i], pref[i - 1]);
  }
  for (int i = sz - 1; i >= 0; i--) {
    int v = g[u][i];
    suf[i] = dp[v] + 1;
    if (i + 1 < sz) suf[i] = max(suf[i], suf[i + 1]);
  }
  for (int i = 0; i < sz; i++) {
    int v = g[u][i];
    int cur = up[u];
    if (i) cur = max(cur, pref[i - 1]);
    if (i + 1 < sz) cur = max(cur, suf[i + 1]);
    up[v] = cur + 1;
  }
  for (auto v: g[u]) {
    dfs2(v);
  }
}
int mx_d[N];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n; cin >> n >> m;
  for (int i = 1; i < n; i++) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1);
  dfs2(1);
  for (int u = 1; u <= n; u++) {
    vector<int> vec;
    if (u != 1) vec.push_back(up[u]);
    for (auto v: g[u]) {
      vec.push_back(dp[v] + 1);
    }
    sort(vec.rbegin(), vec.rend());
    mx_d[u] = vec[0];
    if (vec.size() > 1) {
      mx_d[u] += vec[1];
    }
    mx_d[u] += 1;
  }
  for (int i = 1; i <= n; i++) {
    cnt[mx_d[i]]++;
    DIAMETER = max(DIAMETER, mx_d[i]);
  }

  init();

  int last_prime = 0;
  for (int i = 2; i <= DIAMETER; i++) {
    if (spf[i] == i) last_prime = i;
    if (cnt[i]) {
      int k = id[last_prime];
      if (!v.empty() and v.back().first == k) {
        v.back().second += cnt[i];
      } else {
        v.push_back({k, cnt[i]});
      }
    }
  }

  if (DIAMETER > 2 * SQRT(m)) solve_large();
  else solve_small();
  return 0;
}

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

We can observe that this kind of path is imporatnt — when we are in $$$(x, x)$$$, we only perform one of the following two kind of moves:

Move 1

This move transforms $$$[\ldots,a_x, a_{x+1},\ldots]$$$ into $$$[\ldots,a_{x+1}, a_{x},\ldots]$$$.

Move 2

This move transforms $$$[\ldots,a_x, a_{x+1},a_{x+2},\ldots]$$$ into $$$[\ldots,a_{x+2}, a_{x+1},a_{x},\ldots]$$$.

Summary of the path:

Note the arrays before and after the path as $$$a$$$ and $$$a'$$$, respectively. We can see $$$a'_n=a_1$$$, and $$$[a'_1,\ldots,a'_{n-1}]$$$ can be obtained from $$$[a_2,\ldots,a_{n}]$$$ through the following transformation:

• Swap any two adjacent numbers of $$$[a_2,\ldots,a_{n}]$$$, but each number can be swapped at most once.

This inspires us to use Odd-Even Sort algorithm.

Steps to Achieve the Sorted Array:

Step $$$1$$$: Initialize $$$a_1 = mn$$$: If $$$a_1 \neq mn$$$, where $$$mn$$$ is the minimum of the array, use the following path:

This sequence ensures that $$$a_1 = mn$$$.

Then, repeat steps $$$2$$$ and $$$3$$$ until the array is sorted.

Step $$$2$$$: Perform Odd-Even Sorting: Perform an Odd-Even Sort (a round of comparison) using the key path above on the subarray $$$a_2, \dots, a_n$$$.

Step $$$3$$$: Maintain the orderliness of $$$[a_{2}, \dots ,a_{n}]$$$ while repeatedly making $$$a_1 = mn$$$: After step $$$2$$$, we want $$$mn$$$ back to the head of the array. To achieve this, perform the following operations:

This sequence transforms the array as follows:

When this is performed after an odd-even sort, it ensures that:

• $$$mn$$$ is back to the head of the array.
• The subarray $$$a_1, \dots, a_{n-1}$$$ has been cyclically shifted.

Handling Continuous Cyclic Shifts in Odd-Even Sort:

• Even Length ($$$n-1$$$ is even): Cyclic shifting does not affect the odd-even sort. You can continue applying the sort as usual.
• Odd Length ($$$n-1$$$ is odd): A small modification is needed. Specifically, First compare $$$(a_3,a_4),(a_5,a_6),\ldots$$$ instead of $$$(a_2,a_3),(a_4,a_5),\ldots$$$ This adjustment ensures that the odd-even sort operates correctly despite the continuous cyclic shifts.

Overall, we obtained a sorted array using $$$2n$$$ walks.

#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=2010;
int T,n,mn,tot;
int a[N];
vector<int> X[N],Y[N];

void path1(int num) //(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->...
{
	for(int i=1;i<=n;i++)
	{
		X[num].push_back(i),Y[num].push_back(i);
		if(i!=n)
		{
			X[num].push_back(i),Y[num].push_back(i+1);
			swap(a[i],a[i+1]);
		}
	}
}

void path2(int num) //(1,1)->(1,n)->(n,n)
{
	for(int i=1;i<=n;i++)
	{
		X[num].push_back(1),Y[num].push_back(i);
		swap(a[1],a[i]);
	}
	for(int i=2;i<=n;i++)
	{
		X[num].push_back(i),Y[num].push_back(n);
		swap(a[i],a[n]);
	}
}

void walk1(int j)
{
	X[tot].push_back(j-1),Y[tot].push_back(j);
	X[tot].push_back(j-1),Y[tot].push_back(j+1);
    X[tot].push_back(j),Y[tot].push_back(j+1);
	X[tot].push_back(j+1),Y[tot].push_back(j+1);
    swap(a[j-1],a[j+1]);
}

void walk2(int j)
{
	X[tot].push_back(j-1),Y[tot].push_back(j);
	X[tot].push_back(j),Y[tot].push_back(j);
	X[tot].push_back(j),Y[tot].push_back(j+1);
	X[tot].push_back(j+1),Y[tot].push_back(j+1);
	swap(a[j-1],a[j]);
	swap(a[j],a[j+1]);
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		mn=n;tot=0;
		for(int i=1;i<=n;i++)   mn=min(mn,a[i]);
		for(int i=1;i<=3*n;i++) X[i].clear(),Y[i].clear();
		int p1;
		for(int i=1;i<=n;i++) if(a[i]==mn) p1=i;
		if(p1!=1)
		{
		    tot++;
		    for(int i=1;i<=p1;i++) X[tot].push_back(1),Y[tot].push_back(i),swap(a[1],a[i]);
		    for(int i=2;i<=p1;i++) X[tot].push_back(i),Y[tot].push_back(p1),swap(a[i],a[p1]);
		    for(int i=p1+1;i<=n;i++) X[tot].push_back(p1),Y[tot].push_back(i),swap(a[p1],a[i]);
		    for(int i=p1+1;i<=n;i++) X[tot].push_back(i),Y[tot].push_back(n),swap(a[i],a[n]);
		}
		for(int i=2;i<=n;i++)
		{
			tot++;
			X[tot].push_back(1),Y[tot].push_back(1);
			if(n&1)
			{
				if(i&1)
				{
					for(int j=2;j<=n;j+=2)
					{
						if(j+1==i) walk2(j);
						else if(a[j]>a[j+1]) walk1(j);
						else walk2(j);
					}
				}
				else
				{
					for(int j=2;j<=n;j+=2)
					{
						if(a[j]>a[j+1]) walk1(j);
						else walk2(j);
					}
				}
			}
			else
			{
				if(i&1)
				{
					for(int j=2;j<=n;j+=2)
					{
						if(j==i-1)
						{
							X[tot].push_back(j-1),Y[tot].push_back(j);
							X[tot].push_back(j),Y[tot].push_back(j);
							swap(a[j-1],a[j]);
							j--;
						}
						else if(a[j]>a[j+1]) walk1(j);
						else walk2(j);
					}
				}
				else
				{
					for(int j=2;j<=n;j+=2)
					{
						if(j==i)
						{
							X[tot].push_back(j-1),Y[tot].push_back(j);
							X[tot].push_back(j),Y[tot].push_back(j);
							swap(a[j-1],a[j]);
							j--;
						}
						else if(a[j]>a[j+1]) walk1(j);
						else walk2(j);
					}
				}
			}
			path2(++tot);
		}
		printf("%d\n",tot);
		for(int i=1;i<=tot;i++)
		{
			for(int j=1;j<2*n-1;j++)
			{
			    if(X[i][j]==X[i][j-1]) printf("R");
			    else printf("D");
			}
			printf("\n");
		}

	}

	return 0;
}

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

First, read the editorial of the easy version. We can see that the bottleneck lies in the fact that after every round of odd-even sorting, we need to perform a walk operation to ensure that $$$a_1 = mn$$$.

The following method can break through this bottleneck: for simplicity, let's assume $$$n$$$ is even. Define the numbers smaller than or equal to $$$\frac{n}{2}$$$ as $$$S$$$, and the numbers bigger than $$$\frac{n}{2}$$$ as $$$B$$$. If we have $$$a = [S, \ldots, S, B, \ldots, B]$$$, we can repeatedly perform key path operations to get the following sequence:

1. $$$[S, \ldots, S, B, \ldots, B] \to [S, \ldots, S, B, \ldots, B, S] \to [S, \ldots, S, B, \ldots, B, S, S] \to \ldots \to [B, \ldots, B, S, \ldots, S]$$$ In this process, we only perform odd-even sorting for the subarray $$$[B, \ldots, B]$$$.
2. $$$[B, \ldots, B, S, \ldots, S] \to [B, \ldots, B, S, \ldots, S, B] \to [B, \ldots, B, S, \ldots, B, B] \to \ldots \to [S, \ldots, S, B, \ldots, B]$$$ In this process, we only perform odd-even sorting for the subarray $$$[S, \ldots, S]$$$.

After that, the array is sorted.

Finally, the only remaining problem is how to arrange $$$a = [S, \ldots, S, B, \ldots, B]$$$.

Assume we have $$$k$$$ positions $$$p_1, p_2, \ldots, p_k$$$ such that $$$1 < p_1 < p_2 < \ldots < p_k \leq n$$$. Consider what the following operations are doing:

$$$(1, 1) \to (1, p_1)\to (2, p_1) \to (2, p_2)\to (3, p_2) \to \ldots \to (k, p_k)$$$

If we ignore the other numbers，these operations correspond to:

$$$\text{swap}(a_1, a_{p_1}), \text{swap}(a_2, a_{p_2}), \ldots$$$

Then, we can take any path from $$$(k, p_k)$$$ to $$$(n, n)$$$.

At first, we perform one operation to set $$$a_1 = n$$$, then choose $$$\frac{n}{2}$$$ positions $$$p_1, p_2, \ldots, p_{\frac{n}{2}}$$$ to obtain $$$a = [S, \ldots, S, B, \ldots, B]$$$.

For $$$n$$$ being odd, we need two additional operations for some little adjustments.

Overall, we obtained a sorted array using $$$n + 4$$$ walks.

#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=2010;
int T,n,tot;
int a[N];
vector<int> X[N],Y[N];

void path1(int num)  //(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->...
{
	for(int i=1;i<=n;i++)
	{
		X[num].push_back(i),Y[num].push_back(i);
		if(i!=n)
		{
			X[num].push_back(i),Y[num].push_back(i+1);
			swap(a[i],a[i+1]);
		}
	}
}

void path2(int num) //(1,1)->(1,n)->(n,n)
{
	for(int i=1;i<=n;i++)
	{
		X[num].push_back(1),Y[num].push_back(i);
		swap(a[1],a[i]);
	}
	for(int i=2;i<=n;i++)
	{
		X[num].push_back(i),Y[num].push_back(n);
		swap(a[i],a[n]);
	}
}

void path3(int num,vector<int> p) //swap(1,p[0]),(2,p[1]),... note p[0]!=1
{
	for(int i=1;i<=p[0];i++)
	{
		X[num].push_back(1),Y[num].push_back(i);
		swap(a[1],a[i]);
	}
	for(int i=1;i<p.size();i++)
	{
		for(int j=p[i-1];j<=p[i];j++)
		{
			X[num].push_back(i+1),Y[num].push_back(j);
		    swap(a[i+1],a[j]);
		}
	}
	int x=p.size(),y=p.back();
	while(x!=n)
	{
	    x++;
	    X[num].push_back(x),Y[num].push_back(y);
		swap(a[x],a[y]);
	}
	while(y!=n)
	{
	    y++;
	    X[num].push_back(x),Y[num].push_back(y);
		swap(a[x],a[y]);
	}
}

void walk1(int j)
{
	X[tot].push_back(j-1),Y[tot].push_back(j);
	X[tot].push_back(j-1),Y[tot].push_back(j+1);
    X[tot].push_back(j),Y[tot].push_back(j+1);
	X[tot].push_back(j+1),Y[tot].push_back(j+1);
    swap(a[j-1],a[j+1]);
}

void walk2(int j)
{
	X[tot].push_back(j-1),Y[tot].push_back(j);
	X[tot].push_back(j),Y[tot].push_back(j);
	X[tot].push_back(j),Y[tot].push_back(j+1);
	X[tot].push_back(j+1),Y[tot].push_back(j+1);
	swap(a[j-1],a[j]);
	swap(a[j],a[j+1]);
}

void walk3(int j)
{
	X[tot].push_back(j-1),Y[tot].push_back(j);
	X[tot].push_back(j),Y[tot].push_back(j);
	swap(a[j-1],a[j]);
}

void init()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	tot=0;
	for(int i=1;i<=3*n;i++) X[i].clear(),Y[i].clear();
	vector<pair<int,int> > pr;
	for(int i=1;i<=n;i++) pr.push_back(make_pair(a[i],i));
	sort(pr.begin(),pr.end());
	for(int i=1;i<=n;i++) a[pr[i-1].second]=i;
}

void step1()
{
	int p1,pn;
	vector<int> p;
	for(int i=1;i<=n;i++) if(a[i]==1) p1=i;
	if(p1!=1)
	{
        p.push_back(p1);
        path3(++tot,p);
	}
	if(n==2) return ;
	tot++;
	X[tot].push_back(1),Y[tot].push_back(1);
	for(int j=2;j<=n;j+=2)
	{
	    if(j+1>n) walk3(j);
	    else if(a[j]==n) walk1(j);
		else walk2(j);
	}
	p1=n;
	for(int i=1;i<=n;i++) if(a[i]==n) pn=i;
    p.clear();
    p.push_back(pn);p.push_back(p1);
    path3(++tot,p);
    p.clear();
    for(int i=1;i<=n;i++) if(a[i]<=(n+1)/2) p.push_back(i);
    path3(++tot,p);
}

void step2()
{
	int head;
	if(n&1)
	{
	    for(int t=1;t<=2;t++)
		{
            head=n/2+2;
            for(int i=1;i<=n/2+(t==1);i++)
            {
                tot++;
                X[tot].push_back(1),Y[tot].push_back(1);
                for(int j=2;j<=n;j++)
                {
                    if(!(head<=j&&j<=head+n/2-1)) walk3(j);
                    else if(j==head&&(head&1)) walk3(j);
                    else
                    {
                        if(!(head<=j+1&&j+1<=head+n/2-1)) walk3(j);
                        else if(a[j]>a[j+1]) walk1(j),j++;
                        else walk2(j),j++;
                    }
                }
                head--;
            }
		}
	}
	else
	{
		for(int t=1;t<=2;t++)
		{
            head=n/2+1;
            for(int i=1;i<=n/2;i++)
            {
                tot++;
                X[tot].push_back(1),Y[tot].push_back(1);
                for(int j=2;j<=n;j++)
                {
                    if(!(head<=j&&j<=head+n/2-1)) walk3(j);
                    else if(j==head&&(head&1)) walk3(j);
                    else
                    {
                        if(!(head<=j+1&&j+1<=head+n/2-1)) walk3(j);
                        else if(a[j]>a[j+1]) walk1(j),j++;
                        else walk2(j),j++;
                    }
                }
                head--;
            }
		}
	}
}

void output()
{
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++)
	{
		for(int j=1;j<2*n-1;j++)
		{
		    if(X[i][j]==X[i][j-1]) printf("R");
		    else printf("D");
		}
		printf("\n");
	}
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		init();
		step1();
		step2();
		output();
	}

	return 0;
}

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

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

int main() {
  int a = 1000'000'000,b = 1000'000'000;
  long long product = a * b;
  cout << product << '\n';
  return 0;
}

Overflow!

Even if you declared the product variable as long long, what's happening, in reality, is, first the compiler is multiplying a with b and then it is assigning the output to the product variable and as a and b both are int, that's why the output is also int, but $$$10^{18}$$$ is too much to contain for an int variable.

So how to solve this?

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

int main() {
  int a = 1000'000'000,b = 1000'000'000;
  long long product = (long long) a * b;
  cout << product << '\n';
  return 0;
}

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

int get_size(vector<int> a) {
  return (int)a.size();
}
int main() {
  int n = 1000000;
  vector<int> a(n, 0);
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += get_size(a);
  }
  cout << sum << '\n';
  return 0;
}

Nope! The complexity is actually $$$O(n^2)$$$.

This is because you are passing the vector by value — meaning every time you are calling the function the whole vector of $$$10^6$$$ elements is getting passed in the function. So how to solve this?

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

int get_size(vector<int> &a) {
  return (int)a.size();
}
int main() {
  int n = 1000000;
  vector<int> a(n, 0);
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += get_size(a);
  }
  cout << sum << '\n';
  return 0;
}

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

const int N = 100000;
int main() {
  int test_cases = 100000;
  while (test_cases--) {
    int n; cin >> n;
    vector<int> a(N, 0);
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += a[i];
    }
    cout << sum << '\n';
  }
  // it is guaranteed that total sum of n is <= 100000
  return 0;
}

It's not $$$100000$$$. It's actually around $$$10^{10}$$$ as every time you are declaring a vector of size $$$10^5$$$. I used to do this mistake a lot in the beginning. How to solve this?

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

const int N = 100000;
int main() {
  int test_cases = 100000;
  while (test_cases--) {
    int n; cin >> n;
    vector<int> a(n, 0);
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum += a[i];
    }
    cout << sum << '\n';
  }
  // it is guaranteed that total sum of n is <= 100000
  return 0;
}

Also, check this out.

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

int main() {
  int n = 5;
  int a[n];
  memset(a, 1, sizeof a);
  for (int i = 0; i < n; i++) {
    cout << a[i] << ' ';
  }
  cout << '\n';
  return 0;
}

memset function is actually for char or 1 byte data types! Check out this to learn more.

Then you might ask I have seen people doing memset(a, -1, sizeof a) or memset(a, 0, sizeof a). Well, that's because it works for $$$0$$$ and $$$-1$$$ accidentally! Check out this comment to learn why memset works for $$$0$$$ and $$$-1$$$ correctly.

Using memset to set all elements in an array to $$$-1$$$ or $$$0$$$ is cool as it works really faster than just looping through all the indices and setting them to $$$-1$$$ or $$$0$$$. But be careful while using it for other numbers.

smash me

Don't use pow() unless you are bound to use this because sometimes the answer won't be exactly what you are expecting, and there will be slight precision errors. For example, it's clear that log2(1 << 30) is $$$30$$$. But sometimes it may consider it as $$$29.9999999999999$$$ and when converting it to int, it will return 29.

Similar to this, as pow() takes double as arguments, pow(5, 2) should return $$$5^2=25.00$$$, but sometimes it may consider it as $$$24.9999999999999$$$ and when converting it to int, it will return $$$24$$$. You may use round(pow(5, 2)) in this particular case to avoid the precision issue or just brute force.

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

int main() {
  vector<int> v;
  cout << v.size() - 1 << '\n';;
  return 0;
}

Check this out. Or in short, v.size() acts more like unsigned data types.

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

int main() {
  vector<int> v;
  cout << (int)v.size() - 1 << '\n';;
  return 0;
}

That's why the following code will run indefinitely.

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

int main() {
  vector<int> v;
  for (int i = 0; i < v.size() - 1; i++) { // use i < (int)v.size() - 1 here
    // do something
  }
  return 0;
}

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

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 1; i <= 3; i++) {
    cout << i << '\n';
    printf("%d\n", i + 10);
  }
  return 0;
}

1
11
2
12
3
13

1
2
3
11
12
13

That's because the synchronization has been turned off using the line ios_base::sync_with_stdio(0). Check this out to know more.

So do not mix C-style and C++-style printers after using ios_base::sync_with_stdio(0).

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

int main() {
  int a = 1, b = 3;
  // we want to take b & 3 and add it to a
  int result = a + b & 3;
  cout << result << '\n';
  return 0;
}

The precedence of the + operator is higher than the & operator, so the operator + operates first, meaning a+b = 4 executes and then the & operator comes into play, so 4&3 executes and the output is clearly 0 for this.

Check out this to learn more about C++ operator precedence.

So how to solve this issue?

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

int main() {
  int a = 1, b = 3;
  // we want to take b & 3 and add it to a
  int result = a + (b & 3);
  cout << result << '\n';
  return 0;
}

Another similar classic error is 1 << n - 1 is not $$$2^{n}-1$$$, it's actually $$$2^{n-1}$$$ as - has more precedence than the << operator.

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

const int INF = 1e6;
int main() {
  int minimum = INF;
  for (int i = 1; i <= 10; i++) {
    int x; cin >> x; // the value of x can be up to 10000
    minimum = min(minimum, x * x);
  }
  cout << minimum << '\n';
  return 0;
}

Beginners sometimes don't care about the INF value. For example, here the value of x can be up to $$$10000$$$, meaning the value of x*x, will be up to $$$10^8$$$. But here the value of the minimum variable has been set to $$$10^6$$$, which is not large enough.

So always make sure that the initialized value of a variable is large enough (or small enough).

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

unordered_map<int, int> mp;
int main() {
  int n = 300000;
  for (int i = 1; i <= n; i++) {
    int x; cin >> x;
    mp[x]++;
  }
  int max_occurrence = 0;
  for (auto [val, cnt]: mp) {
    max_occurrence = max(max_occurrence, cnt);
  }
  cout << max_occurrence << '\n';
  return 0;
}

Because of unordered map! The worst-case time complexity of our code is $$$O(n^2)$$$, that's because unordered map is a hash map and it might take more than $$$O(1)$$$ operations to insert or access in case of the input is not random.

Check this post: Blowing up unordered_map, and how to stop getting hacked on it

So always use a custom hash if you don't want to get blown up.

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

int main() {
  multiset<int> se({1, 1, 2, 2, 2, 3, 4, 5, 5});
  // now erase one occurrence of 2
  se.erase(2);
  // now print the elements
  for (auto val: se) {
    cout << val << ' ';
  }
  cout << '\n';
  return 0;
}

That's because if you use a value in the erase() function in a multiset, then all elements will be erased, but if you erase an iterator, then only the element in that iterator will get erased. Check this out for more.

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

int main() {
  multiset<int> se({1, 1, 2, 2, 2, 3, 4, 5, 5});
  // now erase one occurrence of 2
  se.erase(se.find(2));
  // now print the elements
  for (auto val: se) {
    cout << val << ' ';
  }
  cout << '\n';
  // 1 1 2 2 3 4 5 5 
  return 0;
}

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

int main() {
  map<int, int> mp;
  // add 1 to 5 to the map
  for (int i = 1; i <= 5; i++) {
    mp[i]++;
  }
  int cnt = 0;
  // check how many numbers from 1 to 10 exist in the map
  for (int i = 1; i <= 10; i++) {
    if (mp[i]) {
      ++cnt;
    }
  }
  // now print the size of the map
  cout << (int)mp.size() << '\n';
  return 0;
}

No! It's actually $$$10$$$.

That's because of the statement if (mp[i]), mp[i] also inserts the element i into the map even if it doesn't exist. This type of error might get you some unexpected MLEs.

But how to solve this?

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

int main() {
  map<int, int> mp;
  // add 1 to 5 to the map
  for (int i = 1; i <= 5; i++) {
    mp[i]++;
  }
  int cnt = 0;
  // check how many numbers from 1 to 10 exist in the map
  for (int i = 1; i <= 10; i++) {
    if (mp.find(i) != mp.end()) {
      ++cnt;
    }
  }
  // now print the size of the map
  cout << (int)mp.size() << '\n';
  return 0;
}

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

int main() {
  int n = 100000;
  set<int> se;
  for (int i = 1; i <= n; i++) {
    se.insert(i);
  }
  // compute the sum of 1 to n
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    // get the iterator containing the smallest element >= i 
    // it will point to i here
    auto it = lower_bound(se.begin(), se.end(), i);
    sum += *it; // *it = i
  }
  cout << sum << '\n';
  return 0;
}

Wrong!

It's actually $$$O(n^2)$$$. Wait, but doesn't lower_bound work in $$$O(\log{n})$$$?

Actually lower_bound(set.begin(), set.end(), value) is not $$$O(\log{n})$$$! Check out this to learn more.

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

int main() {
  int n = 100000;
  set<int> se;
  for (int i = 1; i <= n; i++) {
    se.insert(i);
  }
  // compute the sum of 1 to n
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    // get the iterator containing the smallest element >= i 
    // it will point to i here
    auto it = se.lower_bound(i);
    sum += *it; // *it = i
  }
  cout << sum << '\n';
  return 0;
}

Same for upper_bound.

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

int main() {
  int n = 1000000;
  string s = "";
  for (int i = 0; i < n; i++) {
    s = s + 'a'; // append a to the string
  }
  cout << s << '\n';
  return 0;
}

It's not $$$O(n)$$$! It's $$$O(n^2)$$$ actually.

Because every time you are using s = s + 'a', on the right side it is accessing the whole string s (which can be $$$O(n)$$$ in size). How to fix this?

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

int main() {
  int n = 1000000;
  string s = "";
  for (int i = 0; i < n; i++) {
    s += 'a'; // append a to the string
  }
  cout << s << '\n';
  return 0;
}

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

int main() {
  int test_cases; cin >> test_cases;
  // take an array of length n as input
  // print YES if the length is 1 or NO otherwise!
  while (test_cases--) {
    int n; cin >> n; // length of the array
    if (n == 1) {
      cout << "YES\n";
      continue;
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) { // taking the array elements as input
      cin >> a[i];
    }
    cout << "NO\n";
  }
  return 0;
}

When n == 1, you are continuing even before taking the array as input. So the code will give WA in some cases.

2
1
1
2
1 3

It happened to me multiple times before! So please take the whole input first if you want to continue by checking some base cases.

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

int main() {
  int test_cases; cin >> test_cases;
  // take an array of length n as input
  // print YES if the length is 1 or NO otherwise!
  while (test_cases--) {
    int n; cin >> n; // length of the array
    vector<int> a(n);
    for (int i = 0; i < n; i++) { // taking the array elements as input
      cin >> a[i];
    }
    if (n == 1) {
      cout << "YES\n";
      continue;
    }
    cout << "NO\n";
  }
  return 0;
}

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

const int MAX_ELEMENT = 1e5;
int cnt[MAX_ELEMENT + 1];
int main() {
  int test_cases; cin >> test_cases;
  while (test_cases--) {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
      int x; cin >> x;
      cnt[x]++;
    }
    int unique_elements = 0;
    for (int i = 0; i <= MAX_ELEMENT; i++) {
      if (cnt[i] > 0) {
        unique_elements++;
      }
    }
    cout << unique_elements << '\n';
  }
  return 0;
}

Notice that the problem has multiple test cases. But you are not resetting the cnt array in each test! So the counts of previous test cases will still be in the cnt array and will produce WA.

2
1
1
1
2

So always clear everything from the previous tests.

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

const int MAX_ELEMENT = 1e5;
int cnt[MAX_ELEMENT + 1];
int main() {
  int test_cases; cin >> test_cases;
  while (test_cases--) {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
      int x; cin >> x;
      cnt[x]++;
    }
    int unique_elements = 0;
    for (int i = 0; i <= MAX_ELEMENT; i++) {
      if (cnt[i] > 0) {
        unique_elements++;
      }
    }
    cout << unique_elements << '\n';

    // resetting everything
    for (int i = 0; i <= MAX_ELEMENT; i++) {
      cnt[i] = 0;
    }
  }
  return 0;
}

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

const int mod = 1e9 + 7;
int main() {
  int a = 1e9, b = 1e9, c = 1e9;
  int sum = (a + b + c) % mod;
  cout << sum << '\n';
  int product = a * b % mod;
  cout << product << '\n';
  int random = 1LL * a * (b * c % mod) % mod;
  cout << random << '\n';
  a = 1e8;
  int sub = (a - b) % mod; 
  cout << sub << '\n';
  return 0;
}

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

const int mod = 1e9 + 7;
int main() {
  // 0 <= a, b, c < mod
  int a = 1e9, b = 1e9, c = 1e9;

  int sum = (a + b + c) % mod; 
  // overflow as (a + b + c) > INT_MAX(=2147483647)
  // better way: ((a + b) % mod + c) % mod
  cout << sum << '\n';

  int product = a * b % mod;
  // overflow as a * b > INT_MAX
  // better way: 1LL * a * b % mod
  cout << product << '\n';

  int random = 1LL * a * (b * c % mod) % mod; 
  // overflow in the (b * c % mod) part
  // correct way: 1LL * a * (1LL * b * c % mod) % mod
  // better way: 1LL * a * b % mod * c % mod
  cout << random << '\n';

  a = 1e8;
  int sub = (a - b) % mod; 
  // not overflow, but when a < b, it will produce a negative number
  // better way: (a - b + mod) % mod
  cout << sub << '\n';

  // Also always make sure that after each arithmetic operation
  // All of your variables are in the range [0, mod-1]
  return 0;
}

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

int main() {
  long long val= 1e12;
  vector<long long> v({val, val, val});
  // now take sum of all elements
  long long sum = accumulate(v.begin(), v.end(), 0);
  cout << sum << '\n';
  return 0;
}

That's because the initialized variable (0) is an int, so the sum also returns as int. Check this out for more.

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

int main() {
  long long val= 1e12;
  vector<long long> v({val, val, val});
  // now take sum of all elements
  long long sum = accumulate(v.begin(), v.end(), 0LL); // typecast
  cout << sum << '\n';
  return 0;
}

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

int main() {
  vector<double> v({1.23, 2.05, 3.003});
  // now take sum of all elements
  double sum = accumulate(v.begin(), v.end(), 0); // correct way: 0.0
  cout << sum << '\n'; // it outputs 6 which is not intended
  return 0;
}

long long x = (long long)1e18 - 1;
long long k = sqrtl(x);
while (k * k < x) ++k;
while (k * k > x) --k;
cout << k << '\n';

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

int main() {
  int n = 100000;
  multiset<int> se;
  // insert n instances of 1
  for (int i = 1; i <= n; i++) {
    se.insert(1);
  }
  long long tot = 0;
  // let's count how many 1s are there in the multiset, n times
  for (int i = 1; i <= n; i++) {
    tot += se.count(1);
  }
  cout << tot << '\n';
  return 0;
}

It's not $$$O(n \, \log{n})$$$, it's actually $$$O(n^2)$$$!

Why? Because the time complexity is logarithmic in the size of the container + linear in the number of occurrences of the element and here, the occurrence of $$$1$$$ is $$$n$$$. So use the count() function for multisets carefully!

Also, if you want to check if a number exists in a multiset use the find() function instead of counting the occurrences.

#include<bits/stdc++.h>
using namespace std;
 
int main() {
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
      int k; cin >> k;
      ans = max(ans, k - i);
    }
    cout << ans << '\n';
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    vector<int> a(n + 1);
    bool inc = true;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      inc &= a[i] > a[i - 1];
    }
    if (n % 2 == 0 or !inc) {
      cout << "YES\n";
    }
    else {
      cout << "NO\n";
    }
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    bool ok = true;
    for (int i = 1; i <= n; i++) {
      int x; cin >> x;
      bool found = false;
      for (int j = i + 1; j >= 2; j--) { // this loop will run not more than 22 times, in practice its much lower than that
        if (x % j) {
          found = true;
          break;
        }
      }
      ok &= found;
    }
    if (ok) {
      cout << "YES\n";
    }
    else {
      cout << "NO\n";
    }
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int x, y; cin >> x >> y;
    if (x <= y) {
      cout << y - y % x / 2 << '\n';
    }
    else {
      cout << x + y << '\n';
    }
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 9, mod = 998244353;
vector<int> v[2];
int dp[2][N];
int a[N];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    long long ans = 0;
    for (int i = n; i >= 1; i--) {
      int k = i & 1;
      v[k].push_back(a[i]);
      dp[k][a[i]] = 1;
      int last = a[i];
      for (auto x: v[k ^ 1]) {
        int y = dp[k ^ 1][x];
        int split = (a[i] + x - 1) / x;
        int st = a[i] / split;
        ans += 1LL * (split - 1) * y * i;
        dp[k][st] += y;
        if (last != st) {
          v[k].push_back(st), last = st;
        }
      }
      for (auto x: v[k ^ 1]) dp[k ^ 1][x] = 0;
      v[k ^ 1].clear();
      ans %= mod;
    }
    cout << ans << '\n';
    for (auto x: v[0]) dp[0][x] = 0;
    for (auto x: v[1]) dp[1][x] = 0;
    v[0].clear(); v[1].clear();
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 9;
const long long inf = 1e12;
using ll = long long;
int phi[N];
void totient() {
  for (int i = 1; i < N; i++) phi[i] = i;
  for (int i = 2; i < N; i++) {
    if (phi[i] == i) {
      for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
    }
  }
}
ll a[N], s1[N][320], s2[N][320];
int root[N];
ll c(int l, int r) {
  if (l > r) return inf;
  ll ans = 0;
  if (r / l <= root[r]) {
    return s1[r][r / l] - a[r / l] * (l - 1 - r / ((r / l) + 1));
  }
  else {
    return s2[r][l];
  }
  return ans;
}
ll dp[N][17];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  totient();
  for (int i = 1; i < N; i++) {
    a[i] = a[i - 1] + phi[i];
  }
  for (int i = 1; i < N; i++) {
    root[i] = 0;
    for (int j = 1; j * j <= i; j++) {
      s1[i][j] = s1[i][j - 1] + a[j] * (i / j - i / (j + 1));
      root[i] = j;
    }
    s2[i][i / (root[i] + 1) + 1] = s1[i][root[i]];
    for (int j = i / (root[i] + 1); j >= 1; j--) {
      s2[i][j] = s2[i][j + 1] + a[i / j];
    }
  }
  int n = 100000;
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    dp[i][0] = inf;
  }
  for (int k = 1; (1 << k) <= n; k++) {
    dp[0][k] = 0;
    vector<pair<int, int> > v; // (start pos, best j)
    v.push_back(make_pair(0, 0));
    for (int x = 1; x <= n; x++) {
      int j = (--lower_bound(v.begin(), v.end(), make_pair(x + 1, 0)))->second;
      dp[x][k] = dp[j][k - 1] + c(j + 1, x);
      for (int i = (int)v.size() - 1; i >= 0; i--) {
        int y = v[i].first, oldj = v[i].second;
        if (y > x && dp[x][k - 1] + c(x + 1, y) < dp[oldj][k - 1] + c(oldj + 1, y)) v.pop_back();
        else {
          int l = y + 1, r = n + 1;
          while (l < r) {
            int mid = (l + r) / 2;
            if (dp[x][k - 1] + c(x + 1, mid) < dp[oldj][k - 1] + c(oldj + 1, mid)) r = mid;
            else l = mid + 1;
          }
          if (r != n + 1) v.push_back(make_pair(r, x));
          break;
        }
      }
      if (v.size() == 0) v.push_back(make_pair(0, x));
    }
  }
  int q; cin >> q;
  while (q--) {
    int n, k; cin >> n >> k;
    if (k >= 20 or (1 << k) > n) {
      cout << n << '\n';
    }
    else {
      cout << dp[n][k] << '\n';
    }
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 9;
const long long inf = 1e12;
using ll = long long;
int phi[N];
void totient() {
  for (int i = 1; i < N; i++) phi[i] = i;
  for (int i = 2; i < N; i++) {
    if (phi[i] == i) {
      for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
    }
  }
}
ll a[N];
ll c(int l, int r) {
  if (l > r) return inf;
  ll ans = 0;
  for (int i = l, last; i <= r; i = last + 1) {
    last = r / (r / i);
    int x = 0;
    if (i >= l) x = last - i + 1;
    else if (last >= l) x = last - l + 1;
    ans += a[r / i] * x;
  }
  return ans;
}
ll dp[N][17];
void yo(int i, int l, int r, int optl, int optr) {
  if(l > r) return;
  int mid = (l + r) / 2;
  dp[mid][i] = inf;
  int opt = optl;
  ll cost = c(min(mid, optr) + 1, mid);
  for(int k = min(mid, optr); k >= optl ; k--) {
    ll cc = dp[k][i - 1] + cost;
    if (cc <= dp[mid][i]) {
      dp[mid][i] = cc;
      opt = k;
    }
    if (k <= mid) {
      if (cost == inf) cost = a[mid / k];
      else cost += a[mid / k];
    }
  }
  yo(i, l, mid - 1, optl, opt);
  yo(i, mid + 1, r, opt, optr);
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  totient();
  for (int i = 1; i < N; i++) {
    a[i] = a[i - 1] + phi[i];
  }
  int n = 100000;
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    dp[i][0] = inf;
  }
  for(int i = 1; i <= n; i++) dp[i][1] = 1LL * i * (i + 1) / 2;
  for(int i = 2; i <= 16; i++) yo(i, 1, n, 1, n);
  int q; cin >> q;
  while (q--) {
    int n, k; cin >> n >> k;
    if (k >= 20 or (1 << k) > n) {
      cout << n << '\n';
    }
    else {
      cout << dp[n][k] << '\n';
    }
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
const int N = 205;
int mod;
 
int power(long long n, long long k) {
  int ans = 1 % mod; n %= mod; if (n < 0) n += mod;
  while (k) {
    if (k & 1) ans = (long long) ans * n % mod;
    n = (long long) n * n % mod;
    k >>= 1;
  }
  return ans;
}
int dp[N][N][40], fac[N], ifac[N];
int vis[N][N][40];
int n, a1;
/*
number of solutions to the equation b1 + b2 + ... bn <= a1
s.t. 0<=bi<=n+1-a1 
and there is at least 1 number >= n + 1 - a1, 
at least 2 numbers >= (n - a1), ..., at least (n - a1) numbers >= 2
*/
int yo(int i, int sum, int k) { // k <= 2 * sqrt(n)
  if (i == n) return fac[n];
  if (k == 0) return 1LL * fac[n] * ifac[n - i] % mod;
  if (vis[i][sum][k] == a1) return dp[i][sum][k];
  vis[i][sum][k] = a1;
  int &ans = dp[i][sum][k];
  ans = 0;
  int r = (a1 - sum) / k;
  for (int cnt = r; cnt >= 0; cnt--) {
    if (k > 1 and i + cnt < n - a1 + 1 - k + 1) continue;
    ans += 1LL * yo(i + cnt, sum + cnt * k, k - 1) * ifac[cnt] % mod;
    ans %= mod;
  }
  return ans;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> mod;
  fac[0] = 1;
  ifac[0] = 1;
  for (int i = 1; i < N; i++) {
    fac[i] = 1LL * fac[i - 1] * i % mod;
    ifac[i] = power(fac[i], mod - 2);
  }
  int ans = 0;
  int lim = 2 * sqrt(n) + 1;
  for (a1 = max(1, n - lim); a1 <= n; a1++) {
    ans += yo(0, 0, n + 1 - a1);
    ans %= mod;
  }
  ans %= mod;
  cout << ans << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e7 + 9, mod = 998244353;
template <const int32_t MOD>
struct modint {
  int32_t value;
  modint() = default;
  modint(int32_t value_) : value(value_) {}
  inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
  inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c <    0 ? c + MOD : c); }
  inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
  inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
  inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
  inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
  inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); }
  modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; }
  modint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
  inline modint<MOD> operator /  (modint<MOD> other) const { return *this *  other.inv(); }
  inline modint<MOD> operator /= (modint<MOD> other)       { return *this *= other.inv(); }
  inline bool operator == (modint<MOD> other) const { return value == other.value; }
  inline bool operator != (modint<MOD> other) const { return value != other.value; }
  inline bool operator < (modint<MOD> other) const { return value < other.value; }
  inline bool operator > (modint<MOD> other) const { return value > other.value; }
};
template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; }
template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; }
 
using mint = modint<mod>;
 
mint pw[N];
mint genius(int n, int k) {
  if (k == 0) return 1;
  vector<mint> c(k, 0), d(k + 1, 0);
  d[k] = 1;
  for (int i = k - 1; i >= 0; i--) {
    c[i] = pw[i] * d[i + 1];
    d[i] = (pw[i] - 1) * d[i + 1];
  }
  mint ans = 0, pwn = mint(2).pow(n), cur = 1;
  for (int i = 0; i < k; i++) {
    ans += ((k - 1 - i) & 1 ? mod - 1 : 1) * c[i] * cur;
    cur *= pwn;
  }
  return ans;
}
mint f(int n, int k) {
  if (k == 0 or n > k) return 0;
  mint ans = 1;
  for (int i = 0; i < n; i++) {
    ans *= pw[k] - pw[i];
  }
  return ans;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  pw[0] = 1;
  for (int i = 1; i < N; i++) {
    pw[i] = pw[i - 1] * 2;
  }
  int t; cin >> t;
  while (t--) {
    int n, k, x; cin >> n >> k >> x;
    if (x) {
      cout << genius(n, k) << '\n';
    }
    else {
      cout << f(n, k) << '\n';
    }
  }
  return 0;
}

Details: here

Div2A - 0.005 USD
Div2B - 0.006 USD
Div2C/Div1A - 0.008 USD
Div2D/Div1B - 0.01 USD
Div2E/Div1C - 0.04 USD
Div2F/Div1D - 0.2 USD
Div1E - 2 USD
Div1F - 2 USD

Div2A - 0.005 * 9529 = 47.645 USD
Div2B - 0.006 * 6274 = 37.644 USD
Div2C/Div1A - 0.008 * (4012+967) = 39.832 USD
Div2D/Div1B - 0.01 * (2273+911) = 31.84 USD
Div2E/Div1C - 0.04 * (27+396) = 16.92 USD
Div2F/Div1D - 0.2 * (1+24) = 5 USD
Div1E - 2 * 8 = 16 USD
Div1F - 2 * 3 = 6 USD

Total - 200.881 USD

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

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    vector<int> a(n);
    for (auto &x: a) {
      cin >> x;
    }
    long long ans = 0;
    for (int i = 1; i < n; i++) {
      ans = max(ans, 1LL * a[i] * a[i - 1]);
    }
    cout << ans << '\n';
  }
  return 0;
}

import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
  n = int(input())
  a = list(map(int, input().split()))
  ans = 0
  for i in range(n - 1):
    ans = max(ans, a[i] * a[i + 1])
  print(ans)

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

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n, k; cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    long long ans = -1e12;
    int l = max(1, n - 2 * k);
    for (int i = l; i <= n; i++) {
      for (int j = i + 1; j <= n; j++) {
        ans = max(ans, 1LL * i * j - 1LL * k * (a[i] | a[j]));
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
  n, k = map(int, input().split())
  a = list(map(int, input().split()))
  l = max(0, n - 2 * k - 1)
  ans = -1e12
  for i in range(l, n):
    for j in range(i + 1, n):
      ans = max(ans, (i + 1) * (j + 1) - k * (a[i] | a[j]))
  print(ans)

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

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n, m; cin >> n >> m;
    ++m;
    int ans = 0;
    for (int k = 30; k >= 0 and n < m; k--) {
      if ((n >> k & 1) == (m >> k & 1)) continue;
      if (m >> k & 1) ans |= 1 << k, n |= 1 << k;
    }
    cout << ans << '\n';
  }
  return 0;
}

import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
  n, m = map(int, input().split())
  m += 1
  ans = 0
  for k in range(30, -1, -1):
    if (n >= m): break
    if ((n >> k & 1) == (m >> k & 1)): continue
    if (m >> k & 1):
      ans |= 1 << k
      n |= 1 << k
  print(ans)

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

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    if (n == 1) {
      cout << "a\n";
    }
    else {
      cout << string(n / 2, 'a') + (n & 1 ? "bc" : "b") + string(n / 2 - 1, 'a') << '\n';
    }
  }
  return 0;
}

t = int(input())
for _ in range(t):
  n = int(input())
  if (n == 1):
    print('a')
  else:
    s = 'a' * (n // 2)
    if (n & 1):
      s += 'bc'
    else:
      s += 'b'
    s += 'a' * (n // 2 - 1)
    print(s)

Write a suffix automata and check if every node occurs an odd number of times.

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

// len -> largest string length of the corresponding endpos-equivalent class
// link -> longest suffix that is another endpos-equivalent class.
// firstpos -> 1 indexed end position of the first occurrence of the largest string of that node
// minlen(v) -> smallest string of node v = len(link(v)) + 1
// terminal nodes -> store the suffixes
struct SuffixAutomaton {
  struct node {
    int len, link, firstpos;
    map<char, int> nxt;
  };
  int sz, last;
  vector<node> t;
  vector<int> terminal;
  vector<int> dp;
  vector<vector<int>> g;
  SuffixAutomaton() {}
  SuffixAutomaton(int n) {
    t.resize(2 * n); terminal.resize(2 * n, 0);
    dp.resize(2 * n, -1); sz = 1; last = 0;
    g.resize(2 * n);
    t[0].len = 0; t[0].link = -1; t[0].firstpos = 0;
  }
  void extend(char c) {
    int p = last;
    int cur = sz++;
    t[cur].len = t[last].len + 1;
    t[cur].firstpos = t[cur].len;
    p = last;
    while (p != -1 && !t[p].nxt.count(c)) {
      t[p].nxt[c] = cur;
      p = t[p].link;
    }
    if (p == -1) t[cur].link = 0;
    else {
      int q = t[p].nxt[c];
      if (t[p].len + 1 == t[q].len) t[cur].link = q;
      else {
        int clone = sz++;
        t[clone] = t[q];
        t[clone].len = t[p].len + 1;
        while (p != -1 && t[p].nxt[c] == q) {
          t[p].nxt[c] = clone;
          p = t[p].link;
        }
        t[q].link = t[cur].link = clone;
      }
    }
    last = cur;
  }
  void build_tree() {
    for (int i = 1; i < sz; i++) g[t[i].link].push_back(i);
  }
  void build(string &s) {
    for (auto x: s) {
      extend(x);
      terminal[last] = 1;
    }
    build_tree();
  }
  int cnt(int i) { // number of times i-th node occurs in the string
    if (dp[i] != -1) return dp[i];
    int ret = terminal[i];
    for (auto &x: g[i]) ret += cnt(x);
    return dp[i] = ret;
  }
};
pair<int, int> ok(string s) {
  int n = s.size();
  SuffixAutomaton sa(n);
  sa.build(s);
  for (int i = 1; i < sa.sz; i++) {
    if (sa.cnt(i) % 2 == 0) {
      return {sa.t[i].firstpos - sa.t[i].len, sa.t[i].firstpos - 1};
    }
  }
  return {-1, -1};
}
int main(int argc, char* argv[]) {
  registerTestlibCmd(argc, argv);
  int t = inf.readInt();
  inf.readEoln();
  for (int test = 1; test <= t; test++) {
    setTestCase(test);
    int n = inf.readInt();
    inf.readEoln();
    string s = ouf.readToken();
    if (s.size() != n) {
      quitf(_wa, "the length of s should be exactly %d", n);
    }
    for (int i = 0; i < n; i++) {
      if (!(s[i] >= 'a' and s[i] <= 'z')) {
        quitf(_wa, "s contains %c which is not an English lowercase character", s[i]);
      }
    }
    auto p = ok(s);
    if (p.first != -1) {
      quitf(_wa, "the substring s[%d, %d] (0-indexed) occurs even number of times in s :\"(", p.first, p.second);
    }
  }
  quitf(_ok, "you are the best problem solver ever UwU");
  return 0;
}

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

const int N = 1e5 + 9, mod = 998244353;

vector<int> g[N];
int dp[N], d, ok, ans[N];
void dfs(int u, int p = 0) {
  if (!ok) return;
  for (auto v: g[u]) {
    if (v ^ p) {
      dfs(v, u);
    }
  }
  if (dp[u] % d != 0) {
    if (p) {
      dp[u]++;
    }
    if (dp[u] % d != 0) {
      ok = 0;
      return;
    }
  }
  else {
    dp[p]++;
  }
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    for (int i = 1; i < n; i++) {
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
      ans[i] = 0;
    }
    ans[1] = 1;
    for (int k = 1; k <= n - 1; k++) {
      ans[1] = (ans[1] + ans[1]) % mod;
    }
    for (d = 2; d <= n - 1; d++) {
      if ((n - 1) % d == 0) {
        ok = 1;
        dfs(1);
        ans[d] = ok;
        for (int i = 0; i <= n; i++) {
          dp[i] = 0;
        }
      }
    }
    for (int i = n; i >= 1; i--) {
      for (int j = i + i; j <= n; j += i) {
        ans[i] = (ans[i] - ans[j] + mod) % mod;
      }
    }
    for (int i = 1; i <= n; i++) {
      if (i > 1) cout << ' ';
      cout << ans[i];
    }
    cout << '\n';
    for (int i = 1; i <= n; i++) {
      g[i].clear();
    }
  }
  return 0;
}

Suffix Array of an integer sequence $$$a_1, a_2, \ldots, a_n$$$ is a permutation $$$p$$$ of size $$$n$$$ where $$$p_i$$$ refers to the suffix starting from index $$$p_i$$$ in $$$a$$$ and all suffixes are in sorted order. So suffix array of $$$[3, 1, 1, 2]$$$ is $$$[2, 3, 4, 1]$$$. It's basically a normal suffix array but here we have an integer sequence.

You are given an undirected graph with $$$n$$$ nodes and $$$m$$$ edges. The graph doesn't contain multi edges or self-loops. You will select every edge and randomly give a direction to it. What is the probability of creating a cycle?

Constraints: $$$1 \leq n \leq 100,$$$ $$$1 \leq m \leq \frac{n * (n - 1)}{2}$$$

You are given a graph with n nodes. The graph doesn't have any edge initially. You will select a random pair $$$(u, v), \; u \neq v$$$ and add a directed edge from $$$u$$$ to $$$v$$$. You will do it $$$k$$$ times. You may select the same edge multiple times. What is the probability of creating a cycle?

Constraints: $$$ 1 \leq n, \;k \leq 100$$$

You are given a graph with n nodes. The graph doesn't have any edge initially. You will select a random pair $$$(u, v), \; u \neq v$$$ and add a directed edge from $$$u$$$ to $$$v$$$. You will do it $$$k$$$ times. You can not select the same edge multiple times. What is the probability of creating a cycle?

Constraints: $$$ 1 \leq n, \;k \leq 100$$$

Here

Note that $$$m \geq 1$$$, so $$$(y+1) > c$$$. So we can say that $$$ (y+1) \; is \; composite: \; y \geq 1$$$

So $$$K^{th}$$$ value of $$$y$$$ is ($$$K^{th}$$$ composite number $$$-1$$$ ). How can we find it given that $$$K \leq 10^9$$$?

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

#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ll long long
#define nl '\n'
#define deb(x) cerr<<#x" = "<<x<<nl
#define in() ( { int a ; scanf("%d",&a); a; } )

const int N = 3e5 + 9;
const int mod = 1e9 + 7;

const int MAX = 10000005;
bool prime[MAX];
int prec[MAX];
vector<int> P;

const int LIM = 250;
int memo[LIM*LIM][LIM];


ll rec(ll N, int K) {
  if (N <= 1 || K < 0) return 0;
  if (N <= P[K]) return N-1;
  if (N < MAX && P[K] * 1LL * P[K] > N) return N-1 - prec[N] + prec[P[K]];

  bool ok = N < LIM*LIM && K < LIM;
  if (ok && memo[N][K]) return memo[N][K];

  ll ret = N/P[K] - rec(N/P[K], K-1) + rec(N, K-1);

  if (ok) memo[N][K] = ret;
  return ret;
}

ll count_primes(ll N) {
  if (N < MAX) return prec[N];
  int K = prec[(int)sqrt(N) + 1];
  return N-1 - rec(N, K) + prec[P[K]];
}

void init_count_primes() {
  prime[2] = true;
  for (int i = 3; i < MAX; i += 2) prime[i] = true;

  for (int i = 3; i*i < MAX; i += 2)
    if (prime[i])
      for (int j = i*i; j < MAX; j += i+i)
        prime[j] = false;

  for(int i=2; i<MAX; i++) if (prime[i]) P.push_back(i);
  for(int i=1; i<MAX; i++) prec[i] = prec[i-1] + prime[i];
}
int32_t main()
{
    init_count_primes();
    int t; cin>>t;
    assert(1<=t<=20);
    while(t--){
        int k; cin>>k;
        assert(1<=k<=1000000000);
        ll l=1, r=2e9;
        ll ans=-1;
        while(l<=r){
            ll mid=(l+r)/2;
            if(mid-count_primes(mid)-1<k) l=mid+1;
            else ans=mid, r=mid-1;
        }
        assert(ans>0);
        cout<<ans-1<<nl;
    }
    return 0;
}

Giveaway. The answer is always the length of the given string.

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

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        cout<<s.size()<<endl;
    }

}

Let $$$X$$$ $$$=$$$ xor of all elements of $$$A$$$.

if $$$X$$$ $$$=$$$ $$$0$$$, output $$$-1$$$.

Otherwise, consider the largest set bit in $$$X$$$. Clearly this bit occurs an odd number of times in the whole array. So if we partition the array at the index where this bit occurs for the first time, then the right part will contain an even number of occurrence of that bit. So that bit will be off in the xor of the remaining elements. So we will have an optimal answer.

Using OR queries and binary search find the first element that has this bit set. Let's call it $$$k$$$. If $$$k$$$ $$$=$$$ $$$n$$$, output $$$-1$$$, otherwise output $$$k$$$.

So we will use at most $$$18$$$ queries.

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

#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ll long long
#define nl '\n'
#define deb(x) cerr<<#x" = "<<x<<nl
#define in() ( { int a ; scanf("%d",&a); a; } )

const int N = 3e5 + 9;
const int mod = 1e9 + 7;


int32_t main()
{
    int n=in();
    cout<<2<<' '<<1<<' '<<n<<nl;
    cout.flush();
    int x; cin>>x;
    int b=-1;
    for(int i=30; i>=0; i--) if((x>>i)&1){
        b=i;
        break;
    }
    if(b==-1){
        cout<<"! -1\n";
        cout.flush();
        return 0;
    }
    int l=1, r=n-1, ans=-1;
    while(l<=r){
        int mid = (l+r)/2;
        cout<<1<<' '<<1<<' '<<mid<<nl;
        cout.flush();
        int o; cin>>o;
        if((o>>b)&1){
            ans=mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    cout<<"! "<<ans<<nl;
    cout.flush();
    return 0;
}

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

#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ll long long
#define nl '\n'
#define deb(x) cerr<<#x" = "<<x<<nl
#define in() ( { int a ; scanf("%d",&a); a; } )

const int N = 3e5 + 9;
const int mod = 1e9 + 7;


int mp[50];
int get(int n)
{
    if(n==0) return 0;
    int i;
    for( i=31;i>=0;i--) if(n&(1<<i)) break;
    n-=(1<<i);
    ll ans=1LL*(i+1)*(n+1);
    return (ans+mp[i])%mod;
}
int32_t main()
{
    int i,j,k,n,m,t,l,r;
    for(i=1;i<32;i++){
        mp[i]=mp[i-1]+1LL*i*(1LL<<(i-1))%mod;
        mp[i]%=mod;
    }
    scanf("%d", &t);
    assert(t>=1&&t<=1e5);
    while(t--){
        scanf("%d %d", &l, &r);
        assert(l>=1&&l<=1e9);
        assert(r>=l&&r<=1e9);
        printf("%d\n", (get(r)-get(l-1)+mod)%mod);
    }
    return 0;
}

If there is a negative cycle then obviously no solution exists. Otherwise, set $$$P_i=$$$ the shortest path to the vertex $$$i$$$ from any vertex (including itself).

So we can use floyd-warshall or bellman-ford to solve the problem.

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

#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ll long long
#define nl '\n'
#define deb(x) cerr<<#x" = "<<x<<nl
#define in() ( { int a ; scanf("%d",&a); a; } )

const int N = 505;
const int mod = 1e9 + 7;

int ans[N];
int d[N][N];
int32_t main()
{
    int i,j,k,n,m,u,v,w;
    cin>>n>>m;
    assert(n>=2&&n<=500);
    assert(m>=1&&m<=min(n*(n-1),(int)1e5));
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) d[i][j]=1e9,d[i][i]=0;
    vector<pii> ed;
    vector<int> we;
    for(i=1;i<=m;i++){
        cin>>u>>v>>w;
        d[u][v]=w;
        ed.eb(u,v);
        we.eb(w);
        assert(u>=1&&u<=n);
        assert(v>=1&&v<=n);
        assert(w>=-1e5&&w<=1e5);
        assert(u!=v);
    }
    for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++){
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    }
    for(i=1;i<=n;i++) if(d[i][i]<0){
        cout<<"NO\n";
        return 0;
    }
    cout<<"YES\n";
    for(i=1;i<=n;i++) ans[i]=1e9;
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) ans[j]=min(ans[j],d[i][j]);
    for(i=0;i<m;i++) assert(ans[ed[i].second]-ans[ed[i].first]<=we[i]);
    for(i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
    return 0;
}
///Before submit=>
///    *check for integer overflow,array bounds
///    *check for n=1

#include <bits/stdc++.h>
#define fs first
#define sc second
#define mx 100005
#define mod 1000000007
#define pii pair<int, int>
#define ll long long
using namespace std;
const double pi = 3.1416;

int main()
{
	int t;
	scanf("%d", &t);
	while(t--){
		int n;
		double l;
		scanf("%d %lf", &n, &l);
		assert(n >= 3);
		double sum = l;
		double nw = l;
		double angle = (n-2)*pi/n;
		double hehe = angle;
		double eqAngle = angle/(n-2);
		for(int i = 1; i<n-1; i++){
			double bahu = sqrt(nw*nw + l*l - cos(angle)*2.0*nw*l);
			sum += bahu;
			//cout << angle << endl;
			angle = hehe - (pi - angle - eqAngle);
			nw = bahu;
			// cout << bahu << " ... " << endl;
		}
		// cout << sum*2 << endl;
		// assert(fabs(nw-l) < 1e-3);
		printf("%.10f\n", (sum*n)/2.0 - ( n%2==1 ? 0: floor((n-2)/2)*l ));
	}	
	return 0;
}

Let

We can rewrite it as

Now the solution to our given product for some $$$l$$$ and $$$r$$$ is $$$\frac{F(r)}{F(l-1)}$$$

#include <bits/stdc++.h>
#define fs first
#define sc second
#define mx 100005
#define mod 1000000007
#define pii pair<int, int>
#define ll long long
#define mkp make_pair
#define all(a) a.begin(),a.end()
using namespace std;
ll bigmod(ll a, ll p){
	ll ret = 1;
	while(p){
		if(p&1) ret = ret * a % mod;
		a = a * a % mod;
		p /= 2;
	}
	return ret;
}
ll fact[2000]={682498929, 491101308, 76479948, 723816384, 67347853, 27368307, 625544428, 199888908, 888050723, 927880474, 281863274, 661224977, 623534362, 970055531, 261384175, 195888993, 66404266, 547665832, 109838563, 933245637, 724691727, 368925948, 268838846, 136026497, 112390913, 135498044, 217544623, 419363534, 500780548, 668123525, 128487469, 30977140, 522049725, 309058615, 386027524, 189239124, 148528617, 940567523, 917084264, 429277690, 996164327, 358655417, 568392357, 780072518, 462639908, 275105629, 909210595, 99199382, 703397904, 733333339, 97830135, 608823837, 256141983, 141827977, 696628828, 637939935, 811575797, 848924691, 131772368, 724464507, 272814771, 326159309, 456152084, 903466878, 92255682, 769795511, 373745190, 606241871, 825871994, 957939114, 435887178, 852304035, 663307737, 375297772, 217598709, 624148346, 671734977, 624500515, 748510389, 203191898, 423951674, 629786193, 672850561, 814362881, 823845496, 116667533, 256473217, 627655552, 245795606, 586445753, 172114298, 193781724, 778983779, 83868974, 315103615, 965785236, 492741665, 377329025, 847549272, 698611116};
ll multfact[2000]={611120140, 17897580,159967943,343237090,592951953,602244843,164013908,893236658,952101451,118482211,209920162,215152598,502381710,324159984,695459226,666860816,975716615,604726097,763034477,379041292,460748324,158354199,508213120,767279289,370470133,987651923,39242596,185475889,981761633,262769826,837005788, 681180371,661100686,908774984,38108703,396223792,793503000,819198011, 933664044,769608345,128783369,939038698,734053167,519165427,507816805,782246763,670871900,695337837,566025613,643867105, 476008438,909547109,980518787,678456808,218366494,992637363,7537905,20980780,379803548,410124767,587218502,463599811, 262065380,382170139,989269458,283943725,896112848,514669474,947602158,862475009,415829023,306830063,519359563,363545474, 758757919,497204956,969569909,39102155,126855068,631173350,6923144,794815151,253495907,554716148,685948839,513720461,309947752,492867651,326211127,657169128,464633342,764165057,613528541,579064017,114865160,794726205,431086582,512549494,460665448,34560};
const int lim = 10000000;
ll fun(ll n){
	// if(n < 1) return 1;
	if(n < lim) {
		ll ret = 1, mult = 1;
		for(int i = 1; i<=n; i++) {
			ret = ret * i % mod;
			mult = mult * ret % mod;
		}
		return bigmod(ret, n+2) * bigmod(mult, mod-2) % mod;
	}
	ll nfact = fact[n/lim-1];
	ll mult = multfact[n/lim-1];
	for(int i = (n/lim)*lim+1; i<=n; i++){
		nfact = nfact * i % mod;
		mult = mult * nfact % mod;
	}
	return bigmod(nfact, n+2) * bigmod(mult, mod-2) % mod;
}
int main()
{
	// ll fact = 1;
	// printf("ll fact[2000]={");
	// vector<int> vt;
	// ll mult = 1;
	// for(int i = 1; i<mod; i++){
	// 	fact = (fact * i) % mod;
	// 	mult = mult * fact % mod;
	// 	if(i%lim == 0){
	// 		vt.push_back(mult);
	// 		if(i/lim!=1) printf(", ");
	// 		printf("%lld",fact);
	// 	}
	// }
	// printf("};\n");
	// printf("ll multfact[2000]={%d", vt[0]);
	// vt.erase(vt.begin());
	// for(int x : vt){
	// 	printf(",%d",x);
	// }
	// printf("};");
	// int fact = 1;
	// int mult = 1;
	// for(int i = 1; i<=lim; i++){
	// 	fact = 1ll * fact * i % mod;
	// 	mult = 1ll * mult * fact % mod;
	// }
	// cout << fact << endl;
	// cout << mult << endl;
	int t;
	scanf("%d", &t);
	while(t--){
		int l, r;
		scanf("%d %d", &l, &r);
		ll mult = 1;

		// for(int i = l; i<=r; i++)
		// {
		// 	mult = mult * bigmod(i, i+1) % mod;
		// }
		// cout << mult << " ";
		cout << fun(r) * bigmod(fun(l-1), mod-2) % mod << endl;
	}
	return 0;
}

Notice that for any two non-negative integers $$$a$$$ and $$$b$$$, $$$a$$$ & $$$b$$$ $$$<$$$ $$$a$$$ and $$$a$$$ & $$$b$$$ $$$<$$$ $$$b$$$.

So the minimum value of all possible subset AND is the bitwise AND of all of the elements of the array. So just check if it less than $$$k$$$ or not.

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



int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n,k,x;
        cin >> n >> k ;
        int an;
        cin >> an;
        n--;
        while(n--)
        {
            cin >> x;
            an&=x;
        }
        if(an<k) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

Dp state for our solution is ( position , $$$c_0$$$ , $$$c_1$$$), here $$$c_0,c_1$$$ indicates the remaining count of zeroes and ones in the second string which we can still use to form a subsequence of the first string. For counting only the distinct permutations, from every position we go to the position of next zero and one and return 1 when we reach the state where $$$c_0=0$$$ and $$$c_1=0$$$.

Here the length of the strings can be up to $$$700$$$. Solutions with $$$O(N^3)$$$ memory won’t pass. So, we need to reduce a state. We can do bottom-up and get rid of the state position. The only difficulty here is that, in our usual bottom-up solutions, for any position, we need the dp values from the previous position. But here we are jumping from current position to the position with next zero or one(not necessarily position$$$+1$$$). For that, we can save dp values for the last one and last zero before current position and use those values to calculate dp for current position.

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

#define N 710
#define mod 1000000007

int dp[2][N][N];
int all[2][N][N];
int pos[2],pre[2][N];
int cnt[2];

int main()
{
    
    string s1,s2;
    cin >> s1 >> s2;
    pos[0]=pos[1]=-1;
    for(int i=0; i<s1.size(); i++)
    {
        pre[0][i]=pos[0];
        pre[1][i]=pos[1];
        pos[s1[i]-'0']=i;
    }
    for(int i=0; i<s2.size(); i++) cnt[s2[i]-'0']++;
    int ans=0;
    for(int p=0; p<s1.size(); p++)
    {
        int nw=s1[p]-'0';
        if(nw==0)
        {
            if(pre[nw][p]==-1)
            {
                dp[0][1][0]=1;
                all[0][1][0]=1;
                for(int i=1; i<=cnt[1]; i++)
                {
                    dp[0][1][i]=all[1][0][i];
                    all[0][1][i]=all[1][0][i];
                }
            }
            else
            {
                for(int i=cnt[0]; i>=0; i--)
                {
                    for(int j=cnt[1]; j>=0; j--)
                    {
                        if(i>0) dp[0][i][j]=dp[0][i-1][j];
                        else dp[0][i][j]=0;
                        if(i>0) dp[0][i][j]+=all[1][i-1][j];
                        dp[0][i][j]%=mod;
                        all[0][i][j]+=dp[0][i][j];
                        all[0][i][j]%=mod;
                    }
                }
            }
            memset(all[1],0,sizeof (all[1]));
            ans+=dp[0][cnt[0]][cnt[1]];
            ans%=mod;

        }
        else
        {
            if(pre[nw][p]==-1)
            {
                dp[1][0][1]=1;
                all[1][0][1]=1;
                for(int i=1; i<=cnt[0]; i++)
                {
                    dp[1][i][1]=all[0][i][0];
                    all[1][i][1]=all[0][i][0];
                }
            }
            else
            {
                for(int i=cnt[0]; i>=0; i--)
                {
                    for(int j=cnt[1]; j>=0; j--)
                    {
                        if(j>0) dp[1][i][j]=dp[1][i][j-1];
                        else dp[1][i][j]=0;
                        if(j>0) dp[1][i][j]+=all[0][i][j-1];
                        dp[1][i][j]%=mod;
                        all[1][i][j]+=dp[1][i][j];
                        all[1][i][j]%=mod;
                    }
                }
            }
            memset(all[0],0,sizeof (all[0]));
            ans+=dp[1][cnt[0]][cnt[1]];
            ans%=mod;
        }
    }
    cout<<ans<<endl;


}

So we need to find the sum of the cost of all possible spanning trees in a complete graph where the weight of an edge from $$$i$$$ to $$$j$$$ is $$$i*j$$$.

Let's find the contribution of an edge $$$(i \rightarrow j)$$$ to the final answer. In how many spanning trees does this edge exist? Let's go deeper in Cayley's Formula. If there are $$$k$$$ connected components in a graph having $$$n$$$ nodes each having size $$$s_1, s_2,...,s_k$$$ then the number of ways to connect them is

Refer to this for proof.

So if we connect edge $$$i \rightarrow j$$$ and disconnect every other edge then the number of ways to connect every component is the same as the number of spanning trees in which this edge is included. And it equals to $$$2*n^{n-3}$$$. As this is a complete graph this value is the same for every other edge.

Let $$$C \; =$$$ sum of the costs of all edges in the graph. So our final answer is $$$2*n^{n-3}*C$$$.

Here $$$2*C \; =$$$ square of the sum of natural numbers up to $$$n$$$ — the sum of squared natural numbers up to $$$n$$$.

So we can solve the problem in $$$O(log \; n)$$$.

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

#define ll long long
#define mod 1000000007

ll bm(ll b,ll p)
{
    ll ret=1;
    b=b%mod;p=p%(mod-1);
    while(p)
    {
        if(p&1) ret=(ret*b)%mod;
        p/=2;
        b=(b*b)%mod;
    }
    return ret;
}

int main()
{
    int t;
    ll n;
    cin >> t;
    while(t--)
    {
        cin >> n;
        if(n==2)
        {
            cout<<"2"<<endl;
            continue;
        }
        ll sum=n%mod*((n+1)%mod)%mod;
        sum=sum*bm(2,mod-2)%mod;

        sum=sum%mod*sum%mod;

        ll tmp=n%mod*((n+1)%mod)%mod*((2LL*n+1)%mod)%mod;
        tmp=tmp%mod*bm(6,mod-2)%mod;

        ll ans=(sum-tmp+mod)%mod;
        ans=ans%mod*bm(2,mod-2)%mod;
        ans=ans%mod*2LL%mod*bm(n,n-3)%mod;
        cout<<ans<<endl;
    }
}

#include <bits/stdc++.h>
#define fs first
#define sc second
#define mx 100005
#define mod 1000000007
#define pii pair<int, int>
#define ll long long
using namespace std;
int ara[mx*10];
ll bigmod(ll a, ll p){
	ll ret = 1;
	while(p){
		if(p&1) ret = ret * a % mod;
		a = a * a % mod;
		p /= 2;
	}
	return ret;
}
void myassert(int x, int l, int r){
	assert(x <= r);
	assert(l <= x);
}
int main()
{
	// freopen("in12.txt", "r", stdin);
	map<int, int> mp;
	int sz = 0;
	int a;
	scanf("%d", &sz);
	for(int i = 0; i<sz; i++)
		scanf("%d", &ara[i]);
	assert(sz <= 1000000);
	assert(1 <= sz);
	int n, m;
	scanf("%d %d", &n, &m);
	myassert(n, 1, 1000000000);
	myassert(m, 1, 1000000000);
	for(int i = 0; i<sz; i++){
		mp[ara[i]%m]++;
	}
	// cout << mp.size() << endl;
	ll ans = 0;
	for(auto p : mp){
		if(p.first == ((m-p.first)%m)) ans = (ans + bigmod(p.second, n)) % mod;
		else{
			if(mp.find((m-p.first)%m) == mp.end()) continue;
			ll nw = mp[(m-p.first)%m];
			ll nwans = bigmod(p.second, n/2) * bigmod(nw, n-(n/2)) % mod;
			ans = (ans + nwans) % mod;
		} 
	}
	printf("%lld\n", ans);
	return 0;
}

TBA

~~~~~

~~~~~