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

https://codeforces.com/contest/2074

I solved 3 problems(A, B, C), and upsolved 1 problem(D).

I struggled with problem C during the contest.. When I was accepted in C, I only had 8 minutes, which is insufficient for me to come up with a proper idea for problem D.

A - Draw a Square

(geometry, implementation)

Approach

A square can only be drawn if all four given values (l, r, d, u) are identical

So, just check given value l, r, d, u are identical.

Solution

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

void solve() {
    int l, r, d, u;
    cin >> l >> r >> d >> u;

    if (l == r && r == d && d == u) {
        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 - The Third Side

(geometry, greedy, math)

Approach

To get the maximum possible value, we have to append available maximum value in every operation.

To construct segment in every operation, the new longest segment would be (ai + aj - 1).

Because of the property of non-degenerate triangle.

If we iterate for n-1 times to leave behind a single segment, it would be sum of every length - (n - 1).

Solution

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

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

    cout << accumulate(a.begin(), a.end(), 0) - n + 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;
}

C - XOR and Triangle

(geometry, greedy, bitmask, brute force, probabilities)

Approach

If x is less than 5 or x + 1 is a power of 2 (i.e., x consists of all 1s in binary), then a solution is impossible.

Get ms and ls - ms is most significant index of 1 bit, while ls is least significant index of 1 bit.

Intialize y to 11111…111 (1 * ms bits) xor x and set 1 on y’sls bit, to ensure ms-1 bits different from x, while at least one bit turned on commonly.

And, check if greatest segment equals to the sum of the rest.

if equals, it’s imposiible. Because of the property of non-degenerate triangle.

else, output y.

Solution

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

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

    if (x < 5 || ((x + 1) & x) == 0) {
        cout << "-1\n";
        return;
    }

    ll ms = log2(x);
    ll ls = log2(x ^ (x & (x - 1)));

    ll y = ((1LL << (ms + 1)) - 1) ^ x;
    y |= 1LL << ls;

    if ((min({x, y, x ^ y}) ^ max({x, y, x ^ y})) + min({x, y, x ^ y}) ==
        max({x, y, x ^ y})) {
        cout << "-1\n";
        return;
    }
    cout << 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 - Counting Points(Upsolved with Editorial)

(two pointers, geometry, brute force, data structure, implementation)

Approach

y is in circle i when:

$$-\lfloor\sqrt{r_i^2-(x-x_i)^2}\rfloor \le y \le \lfloor\sqrt{r_i^2-(x-x_i)^2}\rfloor$$

Let mp[j] be the maximum available points at x = j.

because range of x can be sparse, map is efficient than array.

In every circle, range for each circle is:

• l = x_i - r_i

• r = x_i + r+i

Update mp[j] largest j 1 + 2 *sqrt((r*r-(j-x_i)(j-x_i)) for j = [l … r].

then, accumulate all mp values.

Solution

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

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

    vector<pll> circles(n);
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        circles[i].first = x;
    }
    for (int i = 0; i < n; i++) {
        ll r;
        cin >> r;
        circles[i].second = r;
    }

    map<ll, ll> mp;
    for (int i = 0; i < n; i++) {
        ll l = circles[i].first - circles[i].second;
        ll r = circles[i].first + circles[i].second;

        for (ll j = l; j <= r; j++) {
            mp[j] = max(
                mp[j], 1 + 2 * (ll)(sqrt(circles[i].second * circles[i].second -
                                         (j - circles[i].first) *
                                             (j - circles[i].first))));
        }
    }
    ll ans = 0;
    for (const auto& elem : mp) {
        ans += elem.second;
    }
    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

I struggled with time management during the contest.

However, I won’t give up. I will keep grinding.