[Codeforces] Round 1006(Div.3) Review(A~D)

https://codeforces.com/contest/2072

I review for 4 problems, but I passed only 3 problems(A, B, D) in the contest.

If I had more time, I could pass C too..😭 my C submission after 20 minutes from the contest was passed.

A - New World, New Me, New Array

(greedy, math)

Approach

How can we make k with minimum numbers of elements?

The key is maximizing the element as greater as possible.

It is trivial whether the k is negative, just flip the sign.

Because, if k is negative, minimizing the element as smaller as possible is the key.

To make sum of all elements to k, the minimum element required is (k+p-1)/p.

If n >= (k+p-1)/p, output (k+p-1)/p.

else output -1 since it is impossible.

Code

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
using namespace std;

void solve() {
  int n, k, p;
  cin >> n >> k >> p;

  if (k < 0)
    k = -k;

  int res = k / p;
  res += k % p == 0 ? 0 : 1;

  if (res > n) {
    cout << "-1\n";
  } else {
    cout << res << "\n";
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}

B - Having Been a Treasurer in the Past, I Help Goblins Deceive

(combinations, strings)

Approach

To maximize the answer, we have to balance ‘-’ on both sides, and place ‘_’ in the middle.

So, in case of “--_-_-_---”, convert into “----___---”.

Then, calculate all subsequences:

4C1 × 3 × 3C1 = 36.

So, normalized formula is:

(n/2+n&1) * m * n/2. (n is number of dash, m is number of underscore)

From AM-GM inequality, balanced distribution of elements maximizes the products.

Code

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
using namespace std;

void solve() {
  int n;
  string s;
  cin >> n;
  cin >> s;

  int dashCount = 0;
  int underScoreCount = 0;

  for (char ch : s) {
    if (ch == '-') {
      dashCount++;
    } else {
      underScoreCount++;
    }
  }

  if (dashCount < 2 || underScoreCount < 1) {
    cout << "0\n";
    return;
  }

  ll a = dashCount / 2 + (dashCount & 1);
  ll b = dashCount / 2;

  cout << a * b * underScoreCount << "\n";
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}

C - Creating Keys for StORages Has Become My Main Skill

(bitmask, greedy, constructive)

Approach

To maximize MEX(S), we have to fill elements from 0 to biggest as we can.

However, the element in the array must not have the bit that x doesn’t have.

Let

• num is next element to append(initialize to 0).

• orSUM is prefix bitwise OR sum([0:i], initialize to 0).

• flag is boolean such that availability to incrementing num(initialize to true)

So, fill arr[0] ~ arr[n-2] by the following:

1. if flag is true, check num is able to be appended into arr.

   • if num > x or ((orSUM | num) & ~(x)) > 0, set num to 0 and flag to false.

     • num which is greater than x is prohibited.

     • prefix bitwise OR sum must not have the bit that x doesn’t have.

   • it means we can’t increment MEX no more.

   • setting num to 0 is because 0 is absolutely safe number in bitwise OR operation.

2. append num and accumulate orSUM.

3. increment num if available.(flag is true)

Last element(arr[n-1]):

If condition is satisfied just appending num(orSUM | num == x):

• append num. it can also maximize MEX if flag is still true.

Else, x must be added.

• append x.

Code

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
using namespace std;

void solve() {
  int n, x;
  cin >> n >> x;

  if (n == 1) {
    cout << x << "\n";
    return;
  }

  int orSUM = 0;
  int num = 0;
  bool flag = true;
  for (int i = 0; i < n - 1; i++) {
    if (flag) {
      if (num > x || (((orSUM | num) & ~(x)) > 0)) {
        flag = false;
        num = 0;
      }
    }
    cout << num << " ";
    orSUM |= num;
    if (flag)
      num++;
  }
  if ((orSUM | num) == x) {
    cout << num << " ";
  } else {
    cout << x << " ";
  }

  cout << "\n";
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}

D - For Wizards, the Exam Is Easy, but I Couldn't Handle It

(brute force, greedy, implementation)

Approach

Rotating doesn’t change the relation between pair <i, j>, such that i is not in [l, r], j is in [l, r].

So, important thing is profit in where actual rotation is operated.

The profit can be calculated by..

• number of greater elements - number of smaller elements of l in [l, r]

• Update minimum profit for each range [l, r].

So, brute forcing O(n²) can get the solution.

If not rotating any subarray is best,

• Just print “1, 1”. rotating 1-sized subarray makes no changes.

Else,

• Print L, R such that gives minimal profit.

Code

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> arr(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
  }

  int L, R;
  int minProfit = 0;
  for (int l = 1; l <= n; ++l) {
    int smallerCount = 0;
    int greaterCount = 0;
    for (int r = l; r <= n; r++) {
      if (arr[l] < arr[r]) {
        greaterCount++;
      } else if (arr[l] > arr[r]) {
        smallerCount++;
      }
      int profit = greaterCount - smallerCount;
      if (profit < minProfit) {
        L = l;
        R = r;
        minProfit = profit;
      }
    }
  }

  if (minProfit == 0) {
    cout << "1 1\n";
  } else {
    cout << L << " " << R << "\n";
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}

Commnet

I spend 90 minutes to trying C. and failed in contest!

Next goal is to solve A, B, C, D fast and precisely in Div 3.