“The more you know, the more you realize you know nothing”

Contest

You can find the contest here.

Bouquet

First, notice that the total number of different bouquets is \(2^n - 1\) (the \(-1\) is for not considering the case of taking nothing). Then, if we subtract the number of bouquets with \(a\) flowers and the number of bouquets with \(b\) flowers, we have the answer. But, we can find the number of bouquets with \(x\) flowers using binomial coefficients, so we get this formula:

\[ans = 2^n - 1 - \binom{n}{a} - \binom{n}{b}\]

#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;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  // Preprocess
  const int mod = 1e9 + 7;
  auto add = [&] (int a, int b) { return (a + b) % mod; };
  auto sub = [&] (int a, int b) { return (a - b + mod) % mod; };
  auto mul = [&] (int a, int b) { return (1LL * a * b) % mod; };
  auto mod_pow = [&] (int a, int b) {
    int ret = 1;
    while (b) {
      if (b & 1) ret = mul(ret, a);
      a = mul(a, a);
      b >>= 1;
    }
    return ret;
  };
  auto inv = [&] (int a) { return mod_pow(a, mod - 2); };
  const int N = 2e5 + 1;
  vi fact(N);
  fact[0] = 1;
  for (int i = 1; i < N; i++) fact[i] = mul(fact[i - 1], i);
  auto comb = [&] (int x, int y) {
    int ret = 1;
    for (int i = x - y + 1; i <= x; i++) {
      ret = mul(ret, i);
    }
    ret = mul(ret, inv(fact[y]));
    return ret;
  };
  // Solution
  int n, a, b;
  cin >> n >> a >> b;
  int ans = sub(mod_pow(2, n), 1);
  ans = sub(ans, comb(n, a));
  ans = sub(ans, comb(n, b));
  cout << ans << '\n';
  return (0);
}

Digit Subsequence

The maximum possible answer is low (can you prove it?), then we can just brute force on the answer.

#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;
typedef vector <int> vi;
typedef vector <ll> vll;
 
int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  string s;
  cin >> s;
  vi vis;
  for (int i = 0; i < sz(s); i++) {
    int num = 0;
    for (int j = 0; i + j < sz(s) and j < 5; j++) {
      num = num * 10 + (s[i + j] - '0');
      vis.pb(num);
    }
  }
  sort(all(vis));
  vis.erase(unique(all(vis)), end(vis));
  int ans = 0;
  for (int elem: vis) {
    if (elem != ans) break;
    ans++;
  }
  cout << ans << '\n';
  return (0);
}

C: Duplex Printing

Just analyze by parity.

#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;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  cout << (n + 1) / 2 << '\n';
  return (0);
}

Journey Planning

\[c_{i + 1} - c_i = b_{c_{i + 1}} - b_{c_i}\] \[c_{i + 1} - b_{c_{i + 1}} = c_i - b_{c_i}\]

Let \(x_i = c_i - b_{c_i}\)

Then, we have:

\[x_{i + 1} = x_i\]

So, for each \(i\) we can compute \(x_i\) and get the maximum possible sum for each \(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;
typedef vector <int> vi;
typedef vector <ll> vll;
     
int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  map <int, ll> sum;
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    int b;
    cin >> b;
    sum[i - b] += b;
  }
  for (auto pp: sum) {
    ans = max(ans, pp.second);
  }
  cout << ans << '\n';
  return (0);
}

Contest for Robots

If \(a_i = b_i = 1 \lor a_i = b_i = 0\) there is nothing we can do. Now, let \(x = |\{i: a_i = 1 \land b_j = 0\}|\) and \(y = |\{i: a_i = 0 \land b_i = 1\}|\).

Then, the problem reduce to find \(min(p: 1 \leq p \land x \cdot p > y)\).

#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;
typedef vector <int> vi;
typedef vector <ll> vll;
     
int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector <int> a(n);
  vector <int> b(n);
  for (int& elem: a) cin >> elem;
  for (int& elem: b) cin >> elem;
  int x = 0, y = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] and b[i]) continue;
    if (a[i] == 0 and b[i] == 0) continue;
    if (a[i]) x++;
    if (b[i]) y++;
  }
  if (x == 0) {
    cout << -1 << '\n';
  } else {
    for (int p = 1; ; p++) {
      if (p * x > y) {
        cout << p << '\n';
        return (0);
      }
    }
  }
  return (0);
}

Friendship

Just implement what the problem says.

#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;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;

int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  const int N = 1e6 + 1;
  vi val(N);
  for (int i = 1; i < N; i++) {
    for (int j = i + i; j < N; j += i) {
      val[j] += i;
    }
  }
  int tc;
  cin >> tc;
  while (tc--) {
    int x, y;
    cin >> x >> y;
    bool ok = (val[x] == y and val[y] == x);
    if (ok) cout << "Friendship is ideal\n";
    else cout << "Friendship is not ideal\n";
  }
  return (0);
}

Next

Previous