Since $$$n \leq 100$$$ this problem can be easily solved by iterating over all pairs.

Although, it can be also solved by taking the maximum between the product of the largest or the smallest two numbers.

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

typedef long long ll;

#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
  cout << vars << " = ";
  string delim = "";
  (..., (cout << delim << values, delim = ", "));
  cout << '\n';
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &x : a) cin >> x;
  int ans = -2000000;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      ans = max(ans, a[i] * a[j]);
    }
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  // cin >> t;
  while(t--) {
    solve();
  }
}

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

It's easy to see that the optimal strategy is to sort the queue in ascending or descending order, and then simulate the process.

But it also can be observed that the final answer is always the $$$max(A) - min(A)$$$.

Time complexity, either $$$O(N)$$$ or $$$O(NlogN)$$$ using sort.

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

typedef long long ll;

#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
  cout << vars << " = ";
  string delim = "";
  (..., (cout << delim << values, delim = ", "));
  cout << '\n';
}

void solve() {
  int n;
  cin >> n;
  int mn = 1e9, mx = 0;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    mn = min(mn, x);
    mx = max(mx, x);
  }
  cout << mx - mn << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  // cin >> t;
  while(t--) {
    solve();
  }
}

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

It can be seen that if there is any number greater than the current mex or occured twice in the array, the answer won't change. Otherwise, it's always better to remove the largest number that occurred once and then calculate the mex.

Time complexity $$$O(N)$$$.

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

typedef long long ll;

#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
  cout << vars << " = ";
  string delim = "";
  (..., (cout << delim << values, delim = ", "));
  cout << '\n';
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &x : a) {
    cin >> x;
  }
  vector<int> freq(n);
  sort(a.begin(), a.end());
  int mex = 0;
  int ok = 0;
  for (int x : a) {
    if (x == mex) ++mex;
    if (x < n) ++freq[x];
    else ok = 1;
  }
  for (int x : a) if (x > mex) ok = 1;
  for (int i = 0; i < n; ++i) if (freq[i] > 1) ok = 1;
  if (ok) {
    cout << mex << '\n';
    return;
  }
  for (int i = n - 1; i >= 0; --i) {
    if (freq[i] == 1) {
      cout << i << '\n';
      return;
    }
  }
  assert(false);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  cin >> t;
  while(t--) {
    solve();
  }
}

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

We can see that in order for the OR to be not equal $$$x$$$ there has to be at least $$$1$$$ bit that's in a different state in $$$x$$$ than in the OR.

So assuming that the OR of the array is equal to $$$x$$$ because otherwise the answer is $$$n$$$, we can count the number of times the $$$i$$$-th bit is on in the array, then we take the $$$mn_bit$$$ as the minimum bit of $$$x$$$ occurring in $$$a$$$, we delete all the elements having this bit on and this our answer.

Time complexity $$$O(N * log2(A))$$$, where $$$A$$$ is the maximum element in the array.

#include "bits/stdc++.h"
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
 
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
  cout << vars << " = ";
  string delim = "";
  (..., (cout << delim << values, delim = ", "));
  cout << '\n';
}

const int N = 1e5 * 30;
const int K = 2;
const int mod = 1e9 + 7;
const ll INF = 1e9;
void oh_shit_here_we_go_again() {
	int n, x; cin >> n >> x;
	vector<int> v(n);
	for(auto &x : v) cin >> x;
	for(int i = 0; i < n; ++i) {
		if(v[i] & ~x) {
			cout << n << '\n';
			return;
		}
	}

	vector<int> frq(32);
	for(int i = 0;  i < n; ++i) {
		for(int mask = 0; mask <= 30; mask++) {
			if(v[i] & (1 << mask)) {
				frq[mask]++;
			}
		}
	}

	int mn = INF, mn_bit = -1;
	for(int i = 0; i < 31; ++i) {
		if(x & (1 << i)) {
			if(frq[i] < mn) {
				mn = frq[i];
				mn_bit = i;
			}
		}
	}

	int cnt = 0;
	for(int i = 0; i < n; ++i) {
		if(v[i] & (1 << mn_bit)) continue;
		cnt++;
	}
	cout << cnt << '\n';
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int tt = 1;
	// freopen("cross.in","r",stdin);
	// cin>>tt;
	while(tt--) {
		oh_shit_here_we_go_again();
	}
} 

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

We can see that two balls will attract if they have the same sign but not $$$0$$$, which means in the subarray there can't be more than $$$1$$$ element of each sign $$$-1$$$ and $$$1$$$.

Now we can use two pointers to find the left border for $$$i$$$ from $$$1$$$ to $$$n$$$, any subarray within $$$i$$$, and it's left border is a good subarray so we add $$$i - leftBodrer$$$ to the ans.

We can also solve it using prefix_sum and binary search.

Time complexity: $$$O(N)$$$ two pointers, $$$O(Nlog_2(N))$$$ binary search.

Two Pointers

#include "bits/stdc++.h"
using namespace std;
 
typedef long long ll;
 
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
  cout << vars << " = ";
  string delim = "";
  (..., (cout << delim << values, delim = ", "));
  cout << '\n';
}
 
void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &x : a) cin >> x;
  int j = 0, cp = 0, cn = 0;
  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    cp += (a[i] == 1);
    cn += (a[i] == -1);
    while (max(cp, cn) > 1) {
      cp -= (a[j] == 1);
      cn -= (a[j] == -1);
      ++j;
    }
    ans += (i - j);
  }
  cout << ans << '\n';
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  cin >> t;
  while(t--) {
    solve();
  }
}

Binary Search

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

typedef long long ll;

#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
  cout << vars << " = ";
  string delim = "";
  (..., (cout << delim << values, delim = ", "));
  cout << '\n';
}

void solve() {
  int n;
  cin >> n;
  vector<int> pos(n), neg(n);
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    if (x == 1) pos[i] += 1;
    else if (x == -1) neg[i] += 1;
    if (i > 0) {
      pos[i] += pos[i - 1];
      neg[i] += neg[i - 1];
    }
  }
  auto get = [&] (int l, int r, vector<int> &x) {
    return x[r] - (l ? x[l - 1] : 0);
  };
  auto check = [&] (int l, int r) {
    assert(l <= r && r < n);
    return get(l, r, pos) <= 1 && get(l, r, neg) <= 1;
  };
  ll ans = 0;
  for (int i = 0; i < n - 1; ++i) {
    int l = 2, r = n - i, best = 1;
    while (l <= r) {
      int m = (l + r) / 2;
      if (check(i, i + m - 1)) {
        l = m + 1;
        best = m;
      } else r = m - 1;
    }
    ans += best - 1;
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  cin >> t;
  while(t--) {
    solve();
  }
}

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

A lot of people would think this is a clever a problem that needs a lot of observations, but the only observation that matters is to realize that every turn the length of the array will be halved.

So we can just brute force the game and see who wins, at each turn we can try not reverse and reversing and if any of the ways lead to the other player losing we win, otherwise we lose.

Time Complexity: $$$O(Nlog(N))$$$.

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

typedef long long ll;

#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
  cout << vars << " = ";
  string delim = "";
  (..., (cout << delim << values, delim = ", "));
  cout << '\n';
}

int ans;
bool dfs(vector<ll> a, int turn) {
  int n = a.size();
  if (n == 1) {
    return a[0] % 2 == turn;
  }
  vector<ll> b;
  for (int i = 0; i < n; i += 2) {
    if (i + 1 < n) b.push_back((a[i] + a[i + 1] + 1) / 2);
    else b.push_back(a[i]);
  }
  if (!dfs(b, !turn)) return true;
  b.clear();
  reverse(a.begin(), a.end());
  for (int i = 0; i < n; i += 2) {
    if (i + 1 < n) b.push_back((a[i] + a[i + 1] + 1) / 2);
    else b.push_back(a[i]);
  }
  return !dfs(b, !turn);
}

void solve() {
  int n;
  cin >> n;
  vector<ll> a(n);
  for (ll &x : a) cin >> x;
  cout << (dfs(a, 1) ? "Ahmad" : "Monther") << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  cin >> t;
  while(t--) {
    solve();
  }
}

This problem was supposed to be div3D, but I thought it would be a little harder than that, and some how it seems like it's way harder than div3F too.

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

~~~~~ ~~~~~

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

Will be added soon.

~~~~~ ~~~~~

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

TheForces Rounds are series of unrated contests which are created by a group of CP lovers in the CF community. You can join our discord server with more than 1000 members for more information about the contests: https://discord.gg/h9N2vGmwep

It's the game “Age of Empires”, which some tasks of the contest have it as theme.