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

https://codeforces.com/contest/2092

I solved only one problem(A)…, and upsolved 3 problems(B, C, D).

Even though I got the great intuition for B, C, I couldn’t solve it.

A - Kamilka and the Sheep

(greedy, math, number theory, sorting)

I solved in 15 minutes, it was longer than I expected.

Approach

Increasing d too large is not important.

The largest gcd the x, y can get is max(x, y) - min(x, y)

So, picking the greatest and smallest and subtracting them is always the answer.

Solution

#include <bits/stdc++.h>

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

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

    int mx = *max_element(a.begin(), a.end());
    int mn = *min_element(a.begin(), a.end());
    cout << mx - mn << "\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 - Lady Bug(Upsolved)

(brute force, implementation)

I thought of zigzag approach, but my mental was fallen down because of the conditional mistake.

Then, I couldn’t solve it.

Approach

There are two parts in the input.

The first zigzag - (a[0], b[1], a[2], b[3], ….)

The second zigzag - (b[0], a[1], b[2], a[3], ….)

Elements in the same zigzag are swappable.

If the number of ‘0’s in zigzag 1 is >= (n+1)/2

and the number of ‘0’s in zigzag2 is >= n/2

Because Zigzag1 has (n+1)/2 slots and zigzag has n/2 slots.

Solution

#include <bits/stdc++.h>

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

void solve() {
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    int cnt1 = 0, cnt2 = 0;

    for (int i = 0; i < n; i++) {
        if (i & 1) {
            cnt2 += a[i] == '0';
            cnt1 += b[i] == '0';
        } else {
            cnt1 += a[i] == '0';
            cnt2 += b[i] == '0';
        }
    }

    cout << (cnt1 >= (n + 1) / 2 && cnt2 >= n / 2 ? "YES" : "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;
}

C - Asuna and the Mosquitoes(Upsolved)

(greedy, math, constructive algorithms)

I 98% solved this, but I couldn’t.

Approach

Case 1. If array consists of only odd numbers or only even numbers, then the answer is max element of array. Because operation cannot be performed.

Case 2.

Let’s imagine that we have to feed one odd number.

One odd number can eat even numbers

(odd number x and even number y → odd number (x+y), even number 0).

All the odd numbers can be even number by giving any 0’s to 1. so, odd x can be (x-1), which is even number.

So, they can be eaten!

And they also became 0.

So, the answer is (sum of all elements) - (number of all odd numbers) + 1(adding 1 because first odd number do not leave 1.).

Solution

#include <bits/stdc++.h>

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    ll oddCount = 0;
    ll ans = 0;
    for (auto &i : a) {
        cin >> i;
        ans += i;
        oddCount += (i & 1);
    }
    if (!oddCount || oddCount == n) {
        cout << *max_element(a.begin(), a.end()) << "\n";
    } else {
        cout << ans - oddCount + 1 << "\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 - Mishkin Energizer(Upsolved with editorial)

(brute force, greedy, implementation, strings, constructive algorithms)

Approach

Case 1. If the elements are all the same, then we can’t do any operation.

Case 2.

Balanced string can be made within 2n operations.

let a,b,c in {‘L’, ‘I’, ‘T’} is cnt(a) <= cnt(b) <= cnt(c).

To increment the number of a's by 1(relatively):

if bc or cb:

• it can be bac or cab. (1-step)

if ca or ac:

• ac → bca → cbca → cabaca (4-step)

It can be observed that after each operation, the value of 2*cnt(c) - cnt(b) - cnt(a) decreases by one.

If this value became 0, it is terminated.

Assume x = cnt(a), y = cnt(b), z = cnt(c). x + y + z = n.

while(x < y), incrementing x by 1 takes 4 step.

So, 4*(y-x) operations to make x == y.

Afterwards, making cnt(a) and cnt(b) to cnt(c) takes 2(z-y)+3 operations.

4-step operation performed at most once.

So, total number of operation is: 2z+2y-4x+3. which is <= 2n.

To make a answer, just simulation greedily.

Solution

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pic = pair<int, char>;

string base = "LIT";

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

    if (count(s.begin(), s.end(), s[0]) == n) {
        cout << "-1\n";
        return;
    }

    vector<int> ans;

    while (true) {
        vector<pic> cnt;
        for (auto i : base) {
            cnt.emplace_back(count(s.begin(), s.end(), i), i);
        }
        sort(cnt.begin(), cnt.end());

        if (cnt[0].first == cnt[1].first && cnt[1].first == cnt[2].first) break;

        auto op = [&](int i) -> void {
            string z = base;
            z.erase(find(z.begin(), z.end(), s[i]));
            z.erase(find(z.begin(), z.end(), s[i + 1]));
            ans.push_back(i);
            s = s.substr(0, i + 1) + z[0] + s.substr(i + 1);
        };

        bool done = false;
        for (int i = 0; i < s.size() - 1; i++) {
            if (s[i] == s[i + 1]) continue;
            if (s[i] != cnt[0].second && s[i + 1] != cnt[0].second) {
                op(i);
                done = true;
                break;
            }
        }
        if (done) continue;
        for (int i = 0; i < s.size() - 1; i++) {
            if (s[i] == s[i + 1]) continue;
            if (s[i] == cnt[2].second) {
                op(i);
                op(i + 1);
                op(i);
                op(i + 2);
                done = true;
                break;
            } else if (s[i + 1] == cnt[2].second) {
                op(i);
                op(i);
                op(i + 1);
                op(i + 3);
                done = true;
                break;
            }
        }
    }

    cout << ans.size() << "\n";
    for (const auto &elem : ans) {
        cout << elem + 1 << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) solve();

    return 0;
}

Comments

I ruined my contest…

I lost my points too much.

Maybe I am not talented Competitive Programmer.

But, there’s no way without keep grinding.

I will challenge contests, again and again.

There’s no a bed of roses. There’s no shortcut.