Mini Editorial - Codeforces 1786

#editorial

Contest Problems Link: Codeforces Round #850 (Div. 2, based on VK Cup 2022 - Final Round)

A1. Non-alternating Deck (easy version)#

We can notice that both players gets 2 * x - 1 (where x is odd) cards alternatively.

Code:

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    // a -> alice's cards, b -> bob's cards
    int a = 0, b = 0, x = 1;
    bool flag = true; // if true then alice's turn else bob's turn
    while (n > 2 * x - 1) {
      if (flag) {
        a += 2 * x - 1;
      } else {
        b += 2 * x - 1;
      }
      n -= 2 * x - 1;
      x += 2;
      flag = !flag;
    }
    // deal remaining n cards
    if (flag) {
      a += n;
    } else {
      b += n;
    }
    cout << a << ' ' << b << '\n';
  }
}

A2. Alternating Deck (hard version)#

Since, the number of cards is odd (2 * x - 1) in each turn (before the last), one of the card will be one more than the other. Alice's card always starts with White, and hence White and Black cards will always be x and x - 1 respectively. Similarly, Bob's card always starts with Black and therefore will be in majority.

Code:

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    // aw -> alice's white, bb -> bob's black
    int aw = 0, ab = 0, bw = 0, bb = 0, x = 1;
    bool flag = true; // if true then alice's turn else bob's turn
    while (n > 2 * x - 1) {
      if (flag) {
        aw += x, ab += x - 1;
      } else {
        bw += x - 1, bb += x;
      }
      n -= 2 * x - 1;
      x += 2;
      flag = !flag;
    }
    // deal remaining n cards
    x = (n + 1) / 2; // = (n - x) or (n - x) + 1
    if (flag) {
      aw += x, ab += n - x;
    } else {
      bw += n - x, bb += x;
    }
    cout << aw << ' ' << ab << ' ' << bw << ' ' << bb << '\n';
  }
}

B. Cake Assembly Line#

We can use binary search to determine the shift (x) in coveyor required to satisfy the condition: "each cake ends up with some chocolate, and no chocolate is outside the cakes" i.e. (a[i] - w + x <= b[i] - h) and (a[i] + w + x >= b[i] + h) for all i = 1 to n.

Each dispenser must cover exactly one cake so if any cake is outside the range of it's respective dispenser then we can simply adjust the value of l and r (if cake is on left then we can shift x to right by setting l to mid + 1).

Code:

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

bool valid(int a, int b, int w, int h) {
  return ((b - h >= a - w) && (b + h <= a + w));
}

bool f(int x, const vector<int>& a, const vector<int>& b, int w, int h, bool& flag) {
  int n = a.size();
  for (int i = 0; i < n; i++) {
    if (!valid(a[i] + x, b[i], w, h)) {
      return (a[i] + x - w < b[i] - w);
    }
  }
  flag = true;
  return true;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, w, h;
    cin >> n >> w >> h;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    int l = -1000000000, r = 1000000000;
    bool flag = false;
    while (l <= r) {
      int mid = l + (r - l) / 2;
      if (f(mid, a, b, w, h, flag)) {
        l = mid + 1;
        if (flag) {
          break;
        }
      } else {
        r = mid - 1;
      }
    }
    cout << (flag ? "YES\n" : "NO\n");
  }
}

C. Monsters (easy version)#

Note that we can only use spell of type 2 atmost once. Total number of casts can only be reduced if spell of type 2 is used. To minimize it, we need to trigger spell 2 as many times as we can. To do this, we will make the health of some (or all) monsters to 1, 2, 3, 4, ... k using spell of type 1 optimally.

To use spell of type 1 optimally, we can simply sort the monsters health and reduce the health only if required while iterating.

Code:

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    ll c = 1, res = 0;
    for (int i = 0; i < n; i++) {
      if (a[i] >= c) {
        res += a[i] - c;
        c++;
      }
    }
    cout << res << '\n';
  }
}