The standings include only official Div. 3 participants, whose maximum peak rank was Specialist or lower when the contest started.

Try to extract the individual digits of the 3-digit number and check the given conditions directly using a basic if statement.

Let the three-digit password be $$$s$$$. We can extract its digits $$$d_1$$$, $$$d_2$$$, and $$$d_3$$$ from left to right using integer division and modulo operations:

• $$$d_3 = s \bmod 10$$$ (the 3rd digit)
• $$$d_2 = \lfloor s / 10 \rfloor \bmod 10$$$ (the 2nd digit)
• $$$d_1 = \lfloor s / 100 \rfloor$$$ (the 1st digit)

(Alternatively, you can read the input as a 3-character string $$$S$$$ and convert each character to a digit).

Once we have all three digits, we check if either condition is satisfied:

1. $$$d_1 + d_3 = d_2$$$
2. $$$d_2 = d_3$$$

If at least one condition is true, output YES. Otherwise, output NO.

Complexity:

• Time Complexity: $$$O(1)$$$ per testcase, since extracting digits and checking condition takes constant operations.

• Space Complexity: $$$O(1)$$$, as we only need a few integer variables.

#include <iostream>
using namespace std;

int main() {
    int s; cin >> s;
    int d3 = s % 10;
    int d2 = (s / 10) % 10;
    int d1 = s / 100;
    if ((d1 + d3 == d2) || (d2 == d3)) cout << "YES" << endl;
    else cout << "NO" << endl;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Sorting the array helps process elements in order. Once sorted, what is the smallest valid value each coin can take to remain unique?

To minimize the number of operations, we can use a greedy approach.

1. First, sort the array $$$A$$$ in non-decreasing order.
2. Iterate through the sorted array from index $$$2$$$ to $$$N$$$ (1-based).
3. For each coin $$$A_i$$$, if its value is less than or equal to the previous coin's value $$$A_{i-1}$$$, we must increase $$$A_i$$$ until it is strictly greater than $$$A_{i-1}$$$.
4. The optimal new value for $$$A_i$$$ is $$$A_{i-1} + 1$$$. The number of operations required for this coin is $$$(A_{i-1} + 1) - A_i$$$.
5. Update $$$A_i = A_{i-1} + 1$$$ and add the operations to the total counter.

Important Note:

In the worst case (e.g., all $$$N = 2 \cdot 10^5$$$ elements are initially equal), the total number of operations can reach roughly $$$\frac{N(N-1)}{2} \approx 2 \cdot 10^{10}$$$. This exceeds the 32-bit integer limit, so we must use 64-bit integers (long long in C++) for the total operations counter and array values.

Complexity:

• Time Complexity: $$$O(N \log N)$$$ due to sorting the array. The linear scan takes $$$O(N)$$$ time.

• Space Complexity: $$$O(N)$$$ to store the initial array.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n; cin >> n;
    vector<long long> coins(n);
    for (int i = 0; i < n; i++) cin >> coins[i];
    sort(coins.begin(), coins.end());
    long long ops = 0;
    for (int i = 1; i < n; i++) {
        if (coins[i] <= coins[i - 1]) {
            long long target_year = coins[i - 1] + 1;
            ops += (target_year - coins[i]);
            coins[i] = target_year;
        }
    }
    cout << ops << "\n";
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Notice that if a length $$$L$$$ allows us to cut at least $$$K$$$ segments, any smaller length $$$L' \lt L$$$ will also yield at least $$$K$$$ segments. Can we use this monotonic property to binary search the maximum length $$$L$$$?

Let $$$f(L)$$$ be the maximum number of segments of length $$$L$$$ that Bob can cut from all $$$N$$$ ribbons:

Notice that $$$f(L)$$$ is a non-increasing function: as the requested length $$$L$$$ increases, the total number of segments $$$f(L)$$$ decreases or stays the same.

This monotonic property allows us to perform binary search on the answer:

1. We set our search range for $$$L$$$ to $$$[1, 10^9]$$$.
2. For a middle value $$$\text{mid}$$$, we count how many segments of length $$$\text{mid}$$$ can be produced in total.
3. If $$$f(\text{mid}) \ge K$$$, then length $$$\text{mid}$$$ is valid. We save $$$\text{mid}$$$ as our current best answer and search in the higher half ($$$[\text{mid} + 1, \text{right}]$$$) to check if a larger length is possible.
4. If $$$f(\text{mid}) \lt K$$$, then $$$\text{mid}$$$ is too large, so we search in the lower half ($$$[\text{left}, \text{mid} - 1]$$$).

If no length $$$L \ge 1$$$ satisfies the condition, the answer remains $$$0$$$.

Complexity:

• Time Complexity: $$$O(N \log(\max A_i))$$$ — calculating $$$f(\text{mid})$$$ takes $$$O(N)$$$ time, and binary search takes $$$O(\log(\max A_i))$$$ iterations.

• Space Complexity: $$$O(N)$$$ to store the ribbon lengths.

#include <iostream>
#include <vector>
using namespace std;

bool check(int n, int k, vector<long long>& ribbons, long long mid) {
    long long count = 0;
    for (long long& x : ribbons) {
        count += (x / mid);
    }
    return count >= k;
}

int main() {
    int n, k; cin >> n >> k;
    vector<long long> ribbons(n);
    for (int i = 0; i < n; i++) cin >> ribbons[i];
    long long left = 1, right = 1000000000, L = 0;
    while (left <= right) {
        long long mid = right - (right - left) / 2;
        if (check(n, k, ribbons, mid)) {
            left = mid + 1;
            L = mid;
        }
        else right = mid - 1;
    }
    cout << L << "\n";
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Since $$$A_i \le 2 \cdot 10^5$$$, can we iterate over all possible target lengths $$$L$$$? How can we quickly calculate the max profit for a fixed $$$L$$$ without iterating through all $$$N$$$ ribbons individually?

For a chosen segment length $$$L$$$, let's analyze the net happiness gained from a single ribbon of length $$$A_i$$$:

1. The number of obtainable pieces is $$$k = \lfloor A_i / L \rfloor$$$.
2. The gross happiness gained from these pieces is $$$k \cdot L$$$.
3. The number of cuts depends on whether there is a leftover piece:
   • Exact match ($$$A_i = k \cdot L$$$): Bob needs $$$k - 1$$$ cuts. The net profit is $$$P_{\text{exact}} = k \cdot L - (k - 1) \cdot C$$$.
   • Has remainder ($$$k \cdot L \lt A_i \lt (k + 1) \cdot L$$$): Bob needs $$$k$$$ cuts. The net profit is $$$P_{\text{remain}} = k \cdot L - k \cdot C$$$.

Since Bob can choose which ribbons to cut, he will only cut a ribbon if its net profit is strictly positive ($$$P \gt 0$$$). Otherwise, he simply ignores it.

Notice that for a fixed length $$$L$$$, all ribbons with lengths falling in the same range $$$[k \cdot L + 1, (k + 1) \cdot L - 1]$$$ yield the exact same profit $$$P_{\text{remain}}$$$, and all ribbons with length exactly $$$k \cdot L$$$ yield $$$P_{\text{exact}}$$$.

This allows us to optimize the check for each $$$L$$$:

1. Build a frequency array $$$\text{cnt}[v]$$$ counting how many ribbons have length $$$v$$$, and construct a prefix sum array over $$$\text{cnt}$$$.
2. For a fixed $$$L$$$, iterate over all multipliers $$$j$$$ such that $$$j \cdot L \le M$$$ (where $$$M = \max(A_i)$$$):
   • Add $$$P_{\text{exact}} \times \text{cnt}[j \cdot L]$$$ to the total profit if $$$P_{\text{exact}} \gt 0$$$.
   • Use prefix sums to efficiently count how many ribbons lie in the range $$$[j \cdot L + 1, \min((j + 1) \cdot L - 1, M)]$$$. If $$$P_{\text{remain}} \gt 0$$$, multiply this count by $$$P_{\text{remain}}$$$ and add it to the total profit.

By iterating over all $$$L \in [1, M]$$$ and their multiples $$$j$$$, the total number of iterations bound by the Harmonic series:

Complexity:

• Time Complexity: $$$O(N + M \log M)$$$, where $$$M = \max(A_i)$$$. Building frequency and prefix arrays takes $$$O(N + M)$$$ time, and iterating over all pairs $$$(L, j)$$$ takes $$$O(M \log M)$$$ time.

• Space Complexity: $$$O(N + M)$$$ to store the array, frequency counts, and prefix sums.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    long long n, c; cin >> n >> c;
    vector<long long> ribbons(n);
    for (long long& x : ribbons) cin >> x;
    long long maxA = *max_element(ribbons.begin(), ribbons.end());
    vector<long long> cnt(maxA + 1, 0), pref(maxA + 1, 0);
    for (long long x : ribbons) cnt[x]++;
    for (int i = 1; i <= maxA; i++) pref[i] = pref[i - 1] + cnt[i];
    long long cost = 0;
    for (long long l = 1; l <= maxA; l++) {
        long long selection = 0;
        for (long long j = 1; l * j <= maxA; j++) {
            long long P_exact = j * l - (j - 1) * c, P_remain = j * l - j * c;
            if (P_exact > 0) selection += P_exact * cnt[j * l];
            if (P_remain > 0 && min((j + 1) * l - 1, maxA) >= j * l + 1) selection += P_remain * (pref[min((j + 1) * l - 1, maxA)] - pref[j * l]);
        }
        cost = max(cost, selection);
    }
    cout << cost << "\n";
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Notice that the total cost to save Bob by choosing hospital $$$i$$$ consists of two independent parts:

1. The shortest travel cost from city $$$0$$$ to city $$$id_i$$$.
2. The total treatment cost at hospital $$$i$$$.

How much health does Bob actually need to recover?

First, let's determine the exact amount of health Bob needs:

1. Bob currently has $$$X$$$ health points, which represents $$$20\%$$$ of his max capacity.
2. Therefore, his maximum health capacity is $$$100\% = 5 \times X$$$.
3. The amount of health Bob needs to restore is $$$5 \times X - X = 4 \times X$$$.

Now we can break the problem down into two steps:

1. Shortest Paths (Dijkstra's Algorithm):

We need to find the minimum travel cost from starting city $$$0$$$ to all other cities. Since all edge weights $$$w \ge 1$$$ are non-negative, we can run Dijkstra's algorithm starting from node $$$0$$$. Let $$$\text{dist}[u]$$$ be the shortest distance from node $$$0$$$ to city $$$u$$$.

2. Evaluating Hospitals:

For each hospital $$$i$$$ located at city $$$id_i$$$:

• If $$$\text{dist}[id_i] = \infty$$$, this hospital is unreachable.
• Otherwise, the number of days required to restore $$$4X$$$ health is:

• The treatment cost for $$$D_i$$$ days is $$$D_i \times (Hotel_i + Hospital_i)$$$
• The total cost to use this hospital is $$$\text{dist}[id_i] + \text{treatment_cost}$$$

We iterate through all $$$K$$$ hospitals, compute their total costs, and output the minimum total cost. If no hospital is reachable, we output -1.

Complexity:

• Time Complexity: $$$O((N + M) \log N)$$$ for running Dijkstra's algorithm. Iterating over $$$K$$$ hospitals takes $$$O(K)$$$ time.
• Space Complexity: $$$O(N + M)$$$ to store the adjacency list, distance array, and priority queue.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const long long INF = 4e18;

struct Hospital {
    int id;
    long long hotel;
    long long hosp;
    long long h;
};

struct Edge {
    int to;
    long long weight;
};

int main() {
    int n, m; cin >> n >> m;
    long long x; cin >> x;
    int k; cin >> k;
    vector<Hospital> hospitals(k);
    for (int i = 0; i < k; ++i) cin >> hospitals[i].id >> hospitals[i].hotel >> hospitals[i].hosp >> hospitals[i].h;
    vector<vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    vector<long long> dist(n + 1, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    dist[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (d > dist[u]) continue;
        for (auto edge : adj[u]) {
            if (dist[u] + edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[u] + edge.weight;
                pq.push({dist[edge.to], edge.to});
            }
        }
    }
    long long ans = INF;
    long long needed_health = 4LL * x;
    for (auto b : hospitals) {
        if (dist[b.id] == INF) continue;
        long long days = (needed_health + b.h - 1) / b.h;
        long long treatment_cost = days * (b.hosp + b.hotel);
        long long total_cost = dist[b.id] + treatment_cost;
        ans = min(total_cost, ans);
    }
    if (ans == INF) cout << -1 << "\n";
    else cout << ans << "\n";
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

If the elevator stops at floor $$$i$$$ and then next stops at floor $$$j$$$ ($$$i \gt j$$$), $$$m = i - j - 1$$$ floors are skipped. Can you find a closed formula for the total sadness of all residents on those skipped floors? After that, try Dynamic Programming.

Let's first calculate the total sadness generated between two consecutive elevator stops at floor $$$i$$$ and floor $$$j$$$ ($$$i \gt j$$$):

1. The number of skipped floors between $$$i$$$ and $$$j$$$ is $$$m = i - j - 1$$$.
2. The resident at floor $$$j + 1$$$ walks $$$1$$$ floor down (sadness $$$\frac{1 \times 2}{2} = 1$$$).
3. The resident at floor $$$j + 2$$$ walks $$$2$$$ floors down (sadness $$$\frac{2 \times 3}{2} = 3$$$).
4. In general, the resident at floor $$$j + d$$$ walks $$$d$$$ floors down and has sadness $$$\frac{d(d + 1)}{2}$$$.

Summing this up for all $$$d$$$ from $$$1$$$ to $$$m$$$:

With this formula, we can calculate the sadness between any two stops in $$$O(1)$$$ time.

Dynamic Programming Approach

Let $$$\text{dp}[i]$$$ be the minimum total cost (energy + sadness) for servicing all floors from $$$n$$$ down to $$$i$$$, assuming that the elevator must stop at floor $$$i$$$.

• Base Case: $$$\text{dp}[n] = c_n$$$ (the elevator always stops at floor $$$n$$$).

• Transitions: From floor $$$i$$$, we iterate over all possible next lower stops $$$j$$$ ($$$1 \le j \lt i$$$):

  • The transition is valid if $$$i - j \ge k$$$, or if $$$j = 1$$$ (since the 1st floor is an exception and can be stopped at regardless of distance).
  • If valid, we update $$$\text{dp}[j]$$$:

The final answer will be stored in $$$\text{dp}[1]$$$.

Complexity:

• Time Complexity: $$$O(n^2)$$$ — there are $$$n$$$ DP states, and for each state $$$i$$$ we iterate over up to $$$n$$$ previous states $$$j$$$.

• Space Complexity: $$$O(n)$$$ to store the DP array and costs array.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n, k; cin >> n >> k;
    vector<long long> c(n);
    for (long long& x : c) cin >> x;
    vector<long long> dp(n + 1, 1e18);
    dp[n] = c[n - 1];
    for (int i = n; i >= 2; i--) {
        if (dp[i] == 1e18) continue;
        for (int j = i - 1; j >= 1; j--) {
            if (i - j >= k || j == 1) {
                long long m = i - j - 1;
                long long sadness = m * (m + 1) * (m + 2) / 6;
                dp[j] = min(dp[j], dp[i] + c[j - 1] + sadness);
            }
        }
    }
    cout << dp[1] << "\n";
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve