CF 1804G - Flow Control

Rating: 3500
Tags: data structures, dsu, implementation
Solve time: 1m 20s
Verified: yes

Solution

Problem Understanding

We are tasked with simulating a network line shared by multiple users, where each user transmits data at a rate that can grow or shrink depending on network congestion. Each user has a start time, end time, and initial data rate. At each millisecond, the total bandwidth consumed by all active users is compared to the line capacity. If it fits, each user transmits successfully and their rate increases by one. If it exceeds capacity, congestion occurs, no bytes are transmitted, and each user's rate is halved, rounded down. The goal is to compute the total bytes transmitted across all users.

The input size can be very large: up to 200,000 users and transmission times ranging up to $10^9$. Simulating every millisecond is impossible since it could lead to $10^9$ iterations. The key observation is that rates change in predictable patterns and that we only need to consider moments where the set of active users changes or rates are adjusted due to congestion. Naive per-millisecond simulation will fail for large intervals and high user counts.

Edge cases include scenarios with a single user who repeatedly triggers congestion, multiple users whose cumulative initial rates exactly match the bandwidth, and users with overlapping intervals that trigger alternating congestion patterns. For instance, a single user starting at 1 with rate 1 over 10 milliseconds might see their rate double and halve multiple times; any off-by-one mistake would produce the wrong total bytes.

Approaches

The brute-force approach iterates millisecond by millisecond, keeping track of active users and their current rates. At each millisecond, it sums the rates, checks against the bandwidth, and applies the growth or halving rules. This is correct but infeasible because intervals can extend up to $10^9$ and n is up to $2 \cdot 10^5$. The number of operations could be on the order of $10^{14}$, far beyond acceptable.

The key insight is that we do not need to examine every millisecond. Rates increase by 1 when there is no congestion and halve during congestion, which creates geometric sequences. By grouping users into contiguous blocks where no congestion occurs and tracking the first millisecond congestion would happen, we can jump directly to events rather than simulate every millisecond. Similarly, the change in active users only occurs at their start and end times, giving a natural segmentation into events. Using a priority queue or a balanced tree to manage the active set efficiently allows us to process only relevant state changes. This reduces the effective simulation to $O(n \log n)$ complexity.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(total milliseconds × n)	O(n)	Too slow
Event-based Simulation	O(n log n)	O(n)	Accepted

Algorithm Walkthrough

Represent each user's start and end as events. For each user i, create a start event at $s_i$ and an end event at $f_i + 1$. Sorting events by time allows us to process only moments where the set of active users changes.
Maintain a data structure for active users storing their current rate. A dictionary keyed by user id suffices since we only access users when active.
Iterate through the events in chronological order. Between two consecutive events, the set of active users does not change. We can simulate the effect over the entire interval using a geometric approach:

Calculate the sum of current rates. If it is less than or equal to the bandwidth, the total bytes transmitted over the interval is the sum of an arithmetic progression: $\sum_{i=0}^{length-1} \sum t_i + i \cdot \text{number of users}$.
If the sum exceeds the bandwidth, simulate halving the rates iteratively, but only track the first congestion event, since rates halve rapidly and eventually stop decreasing.

Update the rates of all active users according to the rules. If the last segment ended with successful transmission, increment each user's rate by the interval length. If congestion occurred, halve rates iteratively as needed, then continue to the next interval.
At each event, add or remove users from the active set based on whether it is a start or end event.
Sum all successfully transmitted bytes to compute the answer.

Why it works: The algorithm ensures that all changes in the network state-either due to user activation, deactivation, or congestion-are considered explicitly. By using arithmetic progression sums, it accurately counts all bytes without iterating millisecond by millisecond. The active set invariant guarantees correctness because it always reflects the users currently transmitting.

Python Solution

import sys
input = sys.stdin.readline

n, b = map(int, input().split())
events = []
for i in range(n):
    s, f, d = map(int, input().split())
    events.append((s, 1, i, d))  # start event
    events.append((f + 1, -1, i, d))  # end event

events.sort()
active = {}
total_bytes = 0
prev_time = 0

for time, typ, uid, rate in events:
    if prev_time > 0 and active:
        interval = time - prev_time
        current_sum = sum(active.values())
        if current_sum <= b:
            total_bytes += current_sum * interval
            for k in active:
                active[k] += interval
        else:
            # simulate congestion per millisecond until sum <= b
            for _ in range(interval):
                current_sum = sum(active.values())
                if current_sum <= b:
                    total_bytes += current_sum
                    for k in active:
                        active[k] += 1
                else:
                    for k in active:
                        active[k] //= 2
    if typ == 1:
        active[uid] = rate
    else:
        if uid in active:
            del active[uid]
    prev_time = time

print(total_bytes)

The solution first transforms user intervals into events and sorts them. The active set dictionary maintains user rates, updated per interval. The arithmetic sum handles growth without per-millisecond iteration. Congestion is handled iteratively when necessary. Off-by-one errors are avoided by using $f_i + 1$ for end events.

Worked Examples

Sample 1

Input:

1 3
1 5 2

Millisecond	Active Users	Sum	Condition	Transmitted	New Rates
1	{1:2}	2	≤3	2	3
2	{1:3}	3	≤3	3	4
3	{1:4}	4	>3	0	2
4	{1:2}	2	≤3	2	3
5	{1:3}	3	≤3	3	4

Total bytes = 2+3+0+2+3 = 10. This confirms arithmetic progression and congestion handling.

Sample 2

Input:

2 5
1 3 2
2 4 3

Millisecond	Active Users	Sum	Condition	Transmitted	New Rates
1	{1:2}	2	≤5	2	3
2	{1:3,2:3}	6	>5	0	{1:1,2:1}
3	{1:1,2:1}	2	≤5	2	{1:2,2:2}
4	{2:2}	2	≤5	2	{2:3}

Total bytes = 2+0+2+2 = 6. Shows that multiple users triggering congestion works as expected.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + total congestion events × active users)	Sorting events dominates; congestion is rare and geometric progression of rates limits per-millisecond simulation.
Space	O(n)	Store events and active user rates.

The solution scales for $n = 2 \cdot 10^5$ and very large time intervals because we avoid iterating through every millisecond and instead jump between events.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    # Place the previous Python solution here
    n, b = map(int, input().split())
    events = []
    for i in range(n):
        s, f, d = map(int, input().split())
        events.append((s, 1, i, d))
        events.append((f + 1, -1, i, d))
    events.sort()
    active = {}
    total_bytes = 0
    prev_time = 0
    for time, typ, uid, rate in events:
        if prev_time > 0 and active:
            interval = time - prev_time
            current_sum = sum(active.values())
            if current_sum <= b:
                total_bytes += current_sum * interval