[Codeforces] Round 1011(Div.2) Review(A~D)

https://codeforces.com/contest/2085

I solved 2 problems(A, B), and upsolved 2 problems(C, D).

A - Serval and String Theory

(greedy, implementation)

I struggled with solving A. it took 20 minutes, which is long-time for general A problems.

Approach

Try to move the greatest character to the back for k times.

After doing that, get reversed string r.

If s < r, output “YES”, or “NO” otherwise.

Solution

#include <bits/stdc++.h>

#define pii pair<int, int>
#define ll long long
using namespace std;

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

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

    for (int i = n - 1; k > 0 && i >= 0; i--) {
        int largestIdx = i;
        char largest = s[i];
        for (int j = 0; j < i; j++) {
            if (s[j] > largest) {
                largest = s[j];
                largestIdx = j;
            }
        }
        if (largestIdx != i) {
            swap(s[i], s[largestIdx]);
            k--;
        }
    }

    string r = s;
    reverse(r.begin(), r.end());

    if (s < r) {
        cout << "YES\n";
    } else {
        cout << "NO\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 - Serval and Final MEX

(math, implementation, greedy, constructive)

This was easier than A for me.

Approach

First, We can know that there must be no zeros when last operation performed.

So, what we have to do initially is removing zeros in array.

Then how can we remove them?

In index 1 <= i < a.length, we can combine i with i+1 and replace with MEX value.

Getting MEX value is simple when subarray is [0, x].

• if x is 1, return 2.

• otherwise, return 1.

If the last element in a is zero, combine i with i-1, and replace with MEX value.

While removing like this, print 1-based indexes of (i, i+1) or (i-1, i).

After the iteration, the array does not contain zero.

MEX of the rest of the array will be zero.

So, print the entire remaining array.

Solution

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

int getMex(int lo, int hi) {
    if (hi == 1) {
        return 2;
    }
    return 1;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i : a) {
        cin >> i;
    }

    vector<pii> ans;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == 0) {
            if (i < a.size() - 1) {
                a[i] = getMex(0, a[i + 1]);
                ans.push_back({i + 1, i + 2});
                a.erase(a.begin() + i + 1);
            } else {
                a[i - 1] = getMex(0, a[i - 1]);
                ans.push_back({i, i + 1});
                a.pop_back();
            }
            i--;
        }
    }
    ans.push_back({1, a.size()});

    cout << ans.size() << "\n";
    for (const auto &[l, r] : ans) {
        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;
}

C - Serval and The Formula(Upsolved with Editorial)

(bitmask, constructive, greedy)

I struggled with solving this problem for all rest of the time after solving A, B.

I reached that (x + k) & (y + k) must be 0, but I couldn’t found the method to make the correct answer.

Approach

If the equation below is correct,

$$(x + k) + ( y + k) = (x + k ) \oplus (y + k)$$

(x + k) & (y + k) must be 0.

Since, there must be no carry in addition operation.

To ensure the (x + k) & (y + k) = 0, set k like:

$$k = 2^n - max(x, y) \; | \; 2^n > max(x, y)$$

Examine the situation y > x.

(x + 2^n - y) & (2^n)

\= (2^n + (some negative number, while absolute value is less than 2^n.)) & (2^n)

(some positive value within n bits) & (1 « (n+1)) = 0.

This is correct when x > y.

However, when x == y, It cannot be answer because k & k = k.

So, 2^n - max(x, y) ensures the answer, excepting the case x == y.

Note: Make sure to set n >= 32, to ensure the 2^n must be greater than either x and y.

Solution

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

void solve() {
    ll x, y;
    cin >> x >> y;

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

    ll k = 1LL << 32;
    cout << k - max(x, y) << "\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 - Serval and Kaitenzushi Buffet(Upsolved with Editorial)

(heap, data structures, greedy)

I couldn’t read any paragraph in contest, since I had no time for it.

I thought of knapsack solution, but it wasn’t! So surprising.

Approach

Taking i-th sushi is prohibited when later than (n-i(k+1)+1) minute.

Greedily take the untaken plates which is given is the important.

In total, we can take floor(n/(k+1)) plates!

If remaining time is the multiple of the total consumption time(k+1), we can take the most delicious sushi, which is given after i-th minute.

So, managing with maxheap can make the problem simple.

Solution

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

void solve() {
    int n, k;
    cin >> n >> k;
    priority_queue<int> pq;

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int d;
        cin >> d;
        pq.push(d);

        if ((n - i + 1) % (k + 1) == 0) {
            ans += pq.top();
            pq.pop();
        }
    }

    cout << ans << "\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;
}

Comments

Today, I reached Pupil(1200+), but not satisfying.

When will I ever be able to solve 3+ problems in Div 2?

I thought that this contest was good opportunity, but I failed.
Little being disappointed by my bad growth trending, but I will keep grinding.