Contest

El contest lo puedes encontrar aquí.

A: Fifty-Fifty

Si ordenas las letras del string solo necesitas chequear que las primeras dos letras son iguales, que las últimas dos letras son iguales y que la segunda y tercera letra son distintas. Así, tenemos una solución en \(O(1)\).

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  string s;
  cin >> s;
  sort(all(s));
  if (s[0] == s[1] and s[2] == s[3] and s[1] != s[2]) cout << "Yes\n";
  else cout << "No\n";
  return (0);
}

B: Gathering Children

Primero resuelve el problema si solo hubiera strings de la forma \(RRR \dots RLLLL \dots L\). Es sencillo determinar cuántos elementos quedaran en cada posición si la cantidad de movimientos es muy grande. Ahora, cada string lo podemos poder como la unión de strings de la anterior forma y así podemos saber la respuesta en todo el segmento en \(O(|s|)\). Ver el código para más detalles.

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  string s;
  cin >> s;
  vector <int> arr;
  for (int l = 0; l < sz(s);) {
    int r = l;
    while (r + 1 < sz(s) and s[l] == s[r + 1]) r++;
    arr.push_back(r - l + 1);
    l = r + 1;
  }
  vector <int> ans(sz(s));
  int cur = 0;
  for (int pos = 0; pos < sz(arr); pos += 2) {
    cur = cur + arr[pos];
    int l = cur - 1;
    int r = cur;
    ans[l] += (arr[pos] + 1) / 2;
    ans[r] += arr[pos] / 2;
    ans[r] += (arr[pos + 1] + 1) / 2;
    ans[l] += arr[pos + 1] / 2;
    cur += arr[pos + 1];
  }
  for (int i = 0; i < sz(s); i++) cout << ans[i] << " \n"[i == sz(s) - 1];
  return (0);
}

C: DivRem Number

\[\text{Sea }k = \lfloor \frac{N}{m} \rfloor = N \mod m\]

Sabemos que:

\[N = \lfloor \frac{N}{m} \rfloor \cdot m + N \mod m\]

\[\to N = k m + k\] \[\to N = k * (m + 1)\]

Esto es \(m + 1\) debe ser un divisor de N. Así, podemos generar todos los divisores de \(N\) y comprobar si se cumple la condición del problema en \(O(\sqrt{N})\).

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define sz(A) int(A.size())

using namespace std;

typedef long long ll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  ll n;
  cin >> n;
  vector <ll> div;
  for (ll d = 1; d * d <= n; d++) {
    if (n % d == 0) {
      if (d != 1) div.push_back(d);
      if (d != n / d) div.push_back(n / d);
    }
  }
  ll ans = 0;
  for (ll d: div) {
    ll m = d - 1;
    if (n % m == n / m) {
      ans += m;
    }
  }
  cout << ans << endl;
  return (0);
}

D: Takahashi Calendar

Solo busca todas las opciones con fuerza bruta en \(O(MD)\).

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int M, D;
  cin >> M >> D;
  int ans = 0;
  for (int m = 1; m <= M; m++) {
    for (int d = 20; d <= D; d++) {
      int d1 = d / 10;
      int d2 = d % 10;
      if (d1 >= 2 and d2 >= 2 and d1 * d2 == m) ans++;
    }
  }
  cout << ans << '\n';
  return (0);
}

E: Kleene Inversion

Puedes hacer fuerza bruta para fijar \(B_j\). Si ya tienes fijo \(B_j\) solo necesitas saber cuantos elementos en \([0, j)\) son mayores a \(B_j\), llamemos \(x\) a este valor. Luego, sea \(gt\) la cantidad de elementos mayores a \(B_j\) en \([0, n)\). Entonces \(B_{n + j}\) aporta a la respuesta \(x + gt\). \(B_{2 * n + j}\) aporta a la respuesta \(x + 2 * gt\). Y así seguimos hasta \(B_{2 * (k - 1) + j}\). De este modo, \(B_j, B_{n + j}, B_{2 * n + j}, \dots, B_{(k - 1) * n + j}\) aporta a la respuesta: \(k \cdot x + \frac{(k - 1) * k}{2} \cdot gt\). Esta solución podemos implementarla en \(O(N \cdot \max{A_i})\).

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  ll n, k;
  cin >> n >> k;
  const ll MOD = 1e9 + 7;
  vector <ll> arr(n);
  const int MX = 2010;
  vector <int> cnt(MX, 0);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    cnt[arr[i]]++;
  }
  vector <int> vis(MX, 0);
  ll ans = 0;
  for (int j = 0; j < n; j++) {
    ll x = 0;
    ll gt = 0;
    for (int i = arr[j] + 1; i < MX; i++) {
      x += vis[i];
      gt += cnt[i];
    }
    ll add1 = (k * x) % MOD;
    ll add2 = ((k - 1) * k / 2) % MOD;
    ll add = (add1 + gt * add2) % MOD;
    ans = (ans + add) % MOD;
    vis[arr[j]]++;
  }
  cout << ans << '\n';
  return (0);
}

F: GCD on Blackboard

Supongamos que cambiaremos el elemento \(A_i\). Entonces

\[g = \gcd(\gcd(A_1, A_2, \dots, A_{i - 1}), \gcd(A_{i + 1}, A_{i + 2}, \dots, A_{n}))\]

Sabemos que:

\[\gcd(a, b) \leq \min\{a, b\}\] \[gcd(a, a) = a\]

Entonces, podemos escoger que \(A_i = g\) y tenemos que \(g = \gcd(g, A_i)\) sería el máximo divisor de todos los elementos. Entonces, podemos probar que valor sale iterando por cada \(i\) y tomando el máximo \(g\). Además, usando la idea de prefix sums conseguimos una solución en \(O(N \log N)\).

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define sz(A) int(A.size())

using namespace std;

typedef long long ll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector <int> arr(n);
  vector <int> l(n), r(n);
  for (int i = 0; i < n; i++) cin >> arr[i];
  l[0] = arr[0];
  for (int i = 1; i < n; i++) l[i] = __gcd(l[i - 1], arr[i]);
  r[n - 1] = arr[n - 1];
  for (int i = n - 2; i >= 0; i--) r[i] = __gcd(r[i + 1], arr[i]);
  int ans = max(l[n - 2], r[1]);
  for (int i = 1; i + 1 < n; i++) ans = max(ans, __gcd(l[i - 1], r[i + 1]));
  cout << ans << endl;
  return (0);
}

G: RGB Boxes

Reconoce el espacio de búsqueda. Obtendrás una equación con 3 variables, itera sobre dos de ellas, obtén la tercera despejando y comprueba si cumple las condiciones. Así tienes una solución en \(O(N^2)\).

#include <bits/stdc++.h>

#define all(A) begin(A), end(A)
#define sz(A) int(A.size())

using namespace std;

typedef long long ll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int r, g, b, n;
  cin >> r >> g >> b >> n;
  int ans = 0;
  for (int i = 0; i <= n / r + 1; i++) {
    for (int j = 0; j <= n / g + 1; j++) {
      int k = n - i * r - j * g;
      if (k >= 0 and k % b == 0) {
        ans++;
      }
    }
  }
  cout << ans << endl;
  return (0);
}