[Codeforces] Round 1013(Div.3) Review(A~E)

https://codeforces.com/contest/2091

I solved 4 problems(A, B, C, D), and upsolved 1 problems(E).

A - Olympiad Date

(greedy, implementation)

I was spend 10 minutes! because of a simple mistake. Setting up frequencies wrong make me struggle.. even if it was such a simple problem.

Approach

There is always fixed frequencies, so setup required frequencies.

The date 01.03.2025’s required digit frequencies are:

• 0 → 3 times

• 1 → 1 time

• 2 → 2 times

• 3 → 1 time

• 5 → 1 time

Iterating through an array a, reduce frequencies.

• If all frequencies are became zero, output the index

If impossible, output 0.

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> freq(10, 0);
    freq[0] = 3;
    freq[1] = 1;
    freq[2] = 2;
    freq[3] = 1;
    freq[5] = 1;
    int remains = 8;

    vector<int> a(n);
    for (auto &i : a) cin >> i;
    for (int i = 0; i < n; i++) {
        int x = a[i];
        if (freq[x] > 0) {
            freq[x]--;
            remains--;
            if (remains == 0) {
                cout << i + 1 << "\n";
                return;
            }
        }
    }
    cout << 0 << "\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 - Team Training

(greedy, sorting)

Easy problem too, but I was having an index mistake of grouping with sliding window.

Approach

To form as many strong team as possible, we should

• Prefer smaller teams

• Form solo teams whenever a student’s individual skill is already >= x.

Sort the skill array in non-decreasing order.

Count all students with ai >= x - they - can form solo teams

For the remaining students, try to group them from strongest to weakest:

• Always start with the strongest remaining student

• Try to form the smallest team posible.

• Once a valid team is formed, count it and skip those students

• Repeat until you can no longer form a strong team.

Solution

#include <bits/stdc++.h>

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

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

    sort(a.begin(), a.end());
    int ans = 0;
    int lb = lower_bound(a.begin(), a.end(), x) - a.begin();
    ans = n - lb;

    for (int i = lb - 1; i >= 0; i--) {
        int j = i;
        while (j > 0 && (i - j + 1) * a[j] < x) j--;
        if ((i - j + 1) * a[j] >= x) ans++;
        i = j;
    }

    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;
}

C - Combination Lock

(constructive, greedy)

I struggled to solving this. In contest, I solved this with my intuition, So I read the editorial after the contest.

Approach

Let after k cyclic shifts the element pi be at position(i+k) mod n.

For this point to be fixed, it is necessary that (i+k)mod n = pi.

Let assume that permutation p is starting from 0, [0, 1, 2, .., n-1].

From this, we can get k = p_i - i(mod n).

For any cyclic shift to be a fixed point, it must be possible to obtain any k from 0 to n-1.

$$\Sigma^{n-1}_{k=0} \frac{n*(n-1)}{2} \; = \; \Sigma^{n-1}_{i=0}(p_i - i) (= 0)$$

$$\frac{n(n-1)}{2} \equiv 0(mod \;n)$$

$$ \frac{n-1}{2} \equiv 0 (mod\; 1)$$

So, if n is even, then unavailable.

Instead, There are some construction rules to make the vaild permutation.

My solution was: matching started from n-3-th idx, and increasing k by 1.

So, i-th matching occurs (k+i) % n -th idx.

Meanwhile, Editorial suggested [x, x-1, … 1].

Solution(My Submission)

#include <bits/stdc++.h>

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

void solve() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << "1\n";
        return;
    } else if (n % 2 == 0) {
        cout << "-1\n";
        return;
    }
    vector<int> a(n), freq(n + 1, 0);
    int offset = n - 3;
    for (int i = 0; i < n; i++) {
        int idx = (offset + i) % n;
        a[idx] = (i + idx) % n;
    }

    for (const auto &x : a) cout << x + 1 << " ";
    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 - Place of the Olympiad

(parametric search, binary search)

I could solve it quite fast, but I struggled and dwelled 20minutes over than estimated, because of integer overflow, with 3 wrong submissions..

Approach

This is the minimize the maximum problem → It’s parametric search because of ‘minimize the maximum’.

Initialize lo = 1, hi = m.

While lo <= hi:

• Check if the benches can be placed with maximum length in a row: mid(median of [lo, hi]).

  • in a row, maximum number of bench can be placed is mid * (m/(mid+1)) + m % (mid+1).

    • which is considering minimum intervals. (mid+1 means the intervals: +1)

    • mid * (m/(mid+1) is full segment.

    • m % (mid+1) for leftover part.

  • if n * maximum number of bench in a row is >= k, then available.

• if available, update ans = mid, and try smaller for the minimum bound: [lo : mid-1]

• otherwise, try for the larger bound: [mid+1 : hi]

• return ans, which is last available length.

Solution

#include <bits/stdc++.h>

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

bool check(int mid, int n, int m, ll k) {
    ll benches_in_a_row = 1LL * mid * (m / (mid + 1)) + m % (mid + 1);
    return benches_in_a_row * n >= k;
}

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

    int lo = 1, hi = m;
    int ans = m;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (check(mid, n, m, k)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

    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;
}

E - Interesting Ratio (Upsolved)

(number theory, binary search, math, brute force)

I found approach 5 minutes before the end, so I couldn’t solved it in contest.

Maybe I could solve it if I didn't mess up D..

Approach

If lcm / gcd is prime, pair (a, b) for F(a, b) must be (a, a*prime).

For time complexity, we have to precompute Eratosthenes’s sieve 0 to 1e7.

And, store pure primes in primes array.

For each n:

accumulate the possible number of b for a: 1 … n-1.

• maximum posible b is lower_bound + 1 of n // a in primes.

  • However, if p * a > n, to avoid counting, reduce lowerbound by 1.

Solution

#include <bits/stdc++.h>

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

vector<bool> sieve(1e7 + 1, true);
vector<int> primes;

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

    ll ans = 0;
    for (int a = 1; a < n; a++) {
        int lb =
            lower_bound(primes.begin(), primes.end(), n / a) - primes.begin();
        if (lb == primes.size() || primes[lb] * a > n) ans--;
        ans += lb + 1;
    }

    cout << ans << "\n";
}

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

    for (int i = 2; i <= 1e7; i++) {
        if (sieve[i] == false) continue;
        primes.emplace_back(i);
        for (int j = i * 2; j <= 1e7; j += i) {
            sieve[j] = false;
        }
    }

    while (t--) solve();
    return 0;
}

Comments

When I solved 4 problems, I felt really good, Because it was the first time solving 4 problems in div3.

That alone felt like a personal milestone.

But after the contest, I couldn’t help feeling frustrated when I checked the standings.

Because of D, my ranking ended up much lower than I expected.

I have to reduce my mistakes and focus more… and keep grinding