D. On AtCoder Conference

Problem Statement

There is a circular pond with circumference (M). A hut and (N) people are located around the pond.

For a real number (x) ((0\leq x < M)), the point (x) is defined as the position clockwise at distance (x) from the hut. The (i)-th person is at point (A_i). Multiple people may stand at the same point.

An integer (C) not exceeding (N) is given. For (i=0,1,\ldots,M-1), define (X_i) as follows:

1. Takahashi starts at point ((i+0.5)) and moves clockwise.
2. He continues moving as long as the total number of people he encounters is less than (C). He stops when the total reaches or exceeds (C). "Encountering a person at point (y)" means Takahashi arrives at point (y).
3. Let (X_i) be the total number of people he encounters before stopping. If multiple people are at the point where he stops, all of them count, so (X_i) may be greater than (C).

Find the sum of (X_i) over (i=0,1,\ldots,M-1), i.e., (\displaystyle\sum_{i=0}^{M-1} X_i).

Constraints

• (1\leq N\leq 5\times 10^5)
• (1\leq M\leq 10^{12})
• (0\leq A_i\leq M-1)
• (1\leq C\leq N)
• All inputs are integers.

Input

Input is given from Standard Input in the following format:

N M C
A_1 A_2 ... A_N

Output

Print the sum of (X_i) over (i=0,1,\ldots,M-1) on a single line.

Sample Input 1

5 3 2
1 2 1 0 1

Sample Output 1

9

Explanation of Sample 1

For (i=0), Takahashi starts at point 0.5 and moves clockwise:

• At point 1, he meets persons 1, 3, and 5 (three people). Total encountered is 3, which is not less than (C=2), so he stops. Hence, (X_0=3).

For (i=1), starting at 1.5:

• At point 2, he meets person 2. Total is 1, so he continues.
• At point 0, he meets person 4. Total becomes 2, so he stops. Hence, (X_1=2).

For (i=2), starting at 2.5:

• At point 0, he meets person 4. Total is 1, so he continues.
• At point 1, he meets persons 1, 3, and 5 (three people). Total becomes 4, so he stops. Hence, (X_2=4).

Thus, answer is (3+2+4=9).

Sample Input 2

1 1000000000000 1
1

Sample Output 2

1000000000000

Regardless of the starting position, Takahashi stops when he encounters the only person standing at point 1. Thus, (X_i=1) for all (i), and the answer is (10^{12}).

Solution for D

This problem is essentially about circular counting combined with prefix sums and two-pointer technique. Below is a step-by-step explanation.

1. Problem Restatement

We have a circular pond (circumference (M)) with (N) people at integer positions (A_i) ((0 \le A_i < M)).

For each starting point (i + 0.5) ((i = 0, 1, \dots, M-1)), Takahashi walks clockwise until the number of people encountered is at least (C). Let (X_i) be that number.

We need to compute:

[\sum_{i=0}^{M-1} X_i]

2. Key Observations

Circular to Linear

Since the pond is circular, we can duplicate the array of positions by adding (M) to each element, effectively converting the circle into a line segment of length (2M).

For example:

• Original array (A = [1, 2, 1, 0, 1])
• Duplicated: ([1, 2, 1, 0, 1, 4, 5, 4, 3, 4]) (when (M=3))

Now, traveling one full circle from any starting point corresponds to a contiguous interval in this extended array.

Problem Transformation

For start point (i+0.5), we need to find the first position (p) in the extended array such that the number of people in the interval ([i+0.5, p]) is at least (C). Then (X_i) equals the population count in that interval.

Efficient Computation

Enumerating (i) from (0) to (M-1) is impossible because (M) can be as large as (10^{12}).

However, note that (X_i) only depends on which two consecutive people's positions the start point falls between. Thus, (X_i) is constant over a contiguous range of start points.

Therefore, we can:

1. Sort the distinct positions of people (with multiplicities).
2. Duplicate the sorted list with added (M).
3. For each interval between consecutive distinct positions (on the original circle), compute the answer for one representative start point and multiply by the length of the interval.

3. Algorithm

• Read (N, M, C) and the array (A).
• Sort (A).
• Compress consecutive duplicates into pairs of (position, count).
• Create duplicated arrays of positions and counts.
• Compute prefix sums of counts.
• Use two pointers to find, for each distinct position, the index where the cumulative count from that position first reaches (C).
• For each interval between consecutive distinct positions (the distance between them), add (interval length) (\times) (total count from start to stop index) to the answer.

This reduces complexity to (O(N)).

4. Implementation

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m, c;
    cin >> n >> m >> c;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a.begin(), a.end());

    // compress positions
    vector<ll> pos, cnt;
    for (int i = 0; i < n; ) {
        ll p = a[i];
        ll ct = 0;
        while (i < n && a[i] == p) {
            ++ct; ++i;
        }
        pos.push_back(p);
        cnt.push_back(ct);
    }

    ll sz = pos.size();
    // duplicate
    vector<ll> pos2(2*sz), cnt2(2*sz);
    for (int i = 0; i < sz; ++i) {
        pos2[i] = pos[i];
        cnt2[i] = cnt[i];
        pos2[i+sz] = pos[i] + m;
        cnt2[i+sz] = cnt[i];
    }

    // prefix sums
    vector<ll> pref(2*sz+1, 0);
    for (int i = 0; i < 2*sz; ++i) pref[i+1] = pref[i] + cnt2[i];

    // for each start interval, find corresponding stop index
    vector<int> stop(sz);
    int idx = 0;
    for (int j = 0; j < sz; ++j) {
        while (idx < 2*sz && pref[idx+1] - pref[j] < c) ++idx;
        stop[j] = idx;
    }

    ll ans = 0;
    for (int j = 0; j < sz; ++j) {
        ll len;
        if (j == 0) {
            len = m - pos[sz-1] + pos[0];
        } else {
            len = pos[j] - pos[j-1];
        }
        ans += len * (pref[stop[j]+1] - pref[j]);
    }

    cout << ans << endl;
    return 0;
}

5. Summary

The core ideas:

1. Circular to linear: duplicate the array.
2. Segment processing: distinct intervals have the same answer.
3. Prefix sums + two pointers: quickly find stop positions.
4. Avoid enumeration: compute directly per interval, reducing complexity from (O(M)) to (O(N)).

---

E. Hit and Away

Problem Statement

You are given a simple connected undirected graph (G) with (N) vertices and (M) edges. The vertices are numbered (1,2,\ldots,N), and the edges are numbered (1,2,\ldots,M). Edge (i) connects vertices (U_i) and (V_i). You can move bidirectionally along edges.

Each vertex is either safe or dangerous, represented by a string (S) of length (N) consisting of S (safe) and D (dangerous). It is guaranteed that there are at least two safe vertices and at least one dangerous vertex.

For each dangerous vertex (v), compute the value:

The minimum time required to start from some safe vertex, pass through (v), and end at a different safe vertex.

Constraints

• (3\leq N\leq 2\times 10^5)
• (N-1\leq M\leq 2\times 10^5)
• (1\leq U_i,V_i\leq N)
• (U_i\neq V_i)
• If (i\neq j), then ({ U_i,V_i }\neq { U_j,V_j }).
• (S) is a string of length (N) consisting of S and D.
• (N,M,U_i,V_i) are integers.
• (G) is connected.
• At least two safe vertices exist.
• At least one dangerous vertex exists.

Input

Input is given from Standard Input in the following format:

N M
U_1 V_1
U_2 V_2
...
U_M V_M
S

Output

Let (K) be the number of dangerous vertices. Print (K) lines. The (i)-th line should contain the answer for the (i)-th dangerous vertex when they are sorted by vertex number in ascending order.

Sample Input 1

5 5
1 2
1 3
2 3
3 4
4 5
SSDDS

Sample Output 1

2
3

Explanation of Sample 1

Dangerous vertices are vertices 3 and 4.

For vertex 3, a path like 1 → 3 → 2 works (time 2). For vertex 4, a path like 1 → 3 → 4 → 5 works (time 3).

Sample Input 2

3 2
1 2
2 3
SSD

Sample Output 2

3

Explanation of Sample 2

Dangerous vertex is vertex 3. A path 1 → 2 → 3 → 2 works (time 3). Note that 2 → 3 → 2 would end at the same safe vertex and thus is invalid.

Solution for E

1. Problem Restatement

For each dangerous vertex (v), find the minimum value of: [ \text{dist}(s_1, v) + \text{dist}(v, s_2) ] where (s_1) and (s_2) are distinct safe vertices.

2. Key Observation

The optimal solution corresponds to finding, for each vertex (v), the nearest safe vertex and the second nearest safe vertex (from a different origin). The answer is simply the sum of these two distances. This is because any path from one safe vertex to another passing through (v) can be split into two legs: (s_1 \to v) and (v \to s_2). Minimizing the sum requires choosing the closest safe vertex for one leg and the next closest distinct safe vertex for the other.

3. Multi-Source Dijkstra

We can run Dijkstra's algorithm starting from all safe vertices simultaneously. For each node, we maintain:

• The shortest distance to a safe vertex.
• The second shortest distance to a safe vertex from a different origin.
• The ID of the origin (safe vertex) for both distances.

Algorithm Details

• Initialize distance arrays ((d1), (d2)) with infinity, and source arrays ((s1), (s2)) with -1.
• Push all safe vertices into a priority queue with distance 0 and their own ID as sourrce.
• While the priority queue is not empty:
  • Pop the state with smallest distance.
  • If this distance does not match stored (d1) or (d2), skip (outdated).
  • For each neighbor (v) of current node (u):
    • Candidate distance = current distance + 1 (unit edge weight).
    • Update (d1), (s1), (d2), (s2) accordingly, ensuring the two best distances come from different sources.

Complexity

Time: (O((N+M)\log N)), Space: (O(N+M)).

4. Correctness

The algorithm correctly computes the shortest and second shortest distances from distinct safe vertices due to the properties of Dijkstra's algorithm plus careful maintenance of the two best solutions.

5. Implementation

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n+1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    string s;
    cin >> s;
    s = " " + s;  // 1-indexed

    vector<ll> d1(n+1, INF), d2(n+1, INF);
    vector<int> s1(n+1, -1), s2(n+1, -1);

    // (distance, vertex, source)
    priority_queue<tuple<ll,int,int>, vector<tuple<ll,int,int>>, greater<tuple<ll,int,int>>> pq;

    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'S') {
            d1[i] = 0;
            s1[i] = i;
            pq.push({0, i, i});
        }
    }

    while (!pq.empty()) {
        auto [d, u, src] = pq.top();
        pq.pop();
        if (d != d1[u] && d != d2[u]) continue;

        for (int v : g[u]) {
            ll nd = d + 1;
            if (nd < d1[v]) {
                if (s1[v] != src) {
                    d2[v] = d1[v];
                    s2[v] = s1[v];
                }
                d1[v] = nd;
                s1[v] = src;
                pq.push({nd, v, src});
            } else if (nd == d1[v]) {
                if (s1[v] != src && nd < d2[v]) {
                    d2[v] = nd;
                    s2[v] = src;
                    pq.push({nd, v, src});
                }
            } else if (nd < d2[v]) {
                if (s1[v] != src) {
                    d2[v] = nd;
                    s2[v] = src;
                    pq.push({nd, v, src});
                }
            }
        }
    }

    vector<int> dangerous;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'D') dangerous.push_back(i);
    }
    sort(dangerous.begin(), dangerous.end());

    for (int v : dangerous) {
        if (d2[v] == INF) cout << -1 << endl;  // should not happen per constraints
        else cout << d1[v] + d2[v] << endl;
    }

    return 0;
}

6. Summary

The problem reduces to computing the sum of the distances to the two closest distinct safe vertices for each dangerous node. Multi-source Dijkstra efficiently computes these distances for all vertices simultaneously.

Key takeaways:

1. Transform the problem into finding nearest and second-nearest safe vertices from different origins.
2. Use multi-source Dijkstra to compute both distances in one pass.
3. Handle the second-best distance carefully with proper source tracking.