CF 1945B - Fireworks

Two firework machines start at time zero and then keep launching fireworks periodically. The first machine fires at times that are multiples of a, and the second fires at multiples of b.

codeforcescompetitive-programmingmathnumber-theory

CF 1945B - Fireworks

Rating: 900
Tags: math, number theory
Solve time: 1m 25s
Verified: yes

Solution

Problem Understanding

Two firework machines start at time zero and then keep launching fireworks periodically. The first machine fires at times that are multiples of a, and the second fires at multiples of b. Every firework, once launched, stays visible for m + 1 minutes, so a firework launched at time x contributes visibility over the entire interval [x, x + m].

The question is not about the total number of fireworks, but about the peak overlap: at any moment in time, how many fireworks are simultaneously visible in the sky. Since launches are periodic and visibility windows overlap, the number changes over time, and we are asked for the maximum value this overlap can reach.

The constraints are extremely large, up to $10^{18}$ for all parameters. That immediately rules out any simulation over time or iteration over all launch events. Even iterating over a single machine for a time horizon of $m$ or more is impossible. Any correct solution must depend only on arithmetic structure of the periods, not on enumerating events.

A subtle issue arises from overlap interactions. A naive intuition might be that we only need to look at when launches coincide or when windows overlap “around a meeting point”. That intuition is close but incomplete if we do not formalize how overlaps accumulate. For example, with a = 1, b = 1, and m = 1, every second both machines fire, and each firework overlaps with all others in a sliding window. A careless approach that only checks coincidence times would incorrectly output a small constant like 2 instead of the correct growing overlap.

Another failure case appears when periods are large but close, such as a = 10^18, b = 10^18, m = 10^18. Even though launches are sparse, each firework lasts extremely long, so all early fireworks remain visible together. Any reasoning that focuses only on launch density misses this accumulation effect.

The correct approach must therefore reason about how many launches from each arithmetic progression can lie inside a sliding window of length m + 1.

Approaches

A brute-force simulation would try to scan time and maintain active fireworks. We could generate all launch times up to some horizon and maintain a data structure counting active intervals. This is correct in principle because visibility intervals are simple ranges. However, the number of launches up to time $T$ is about $T/a + T/b$, and the relevant horizon is at least $m$. With $m$ up to $10^{18}$, this becomes completely infeasible.

The key observation is that we never actually need to simulate time. The number of fireworks visible at time $t$ depends only on how many launch times from each sequence fall into the interval $[t-m, t]$. For a single arithmetic progression, the number of multiples of a inside any interval of length L is determined purely by division. Therefore, the problem reduces to finding a time t that maximizes:

  • number of integers of form ka in [t-m, t]
  • plus number of integers of form kb in [t-m, t]

The second key insight is that the structure of optimal t is simple. The maximum always occurs at a time aligned with a launch of one of the machines. Intuitively, shifting a window slightly until it hits a launch point can only increase or preserve the count, because the set of included multiples changes only when crossing a multiple of a or b.

So we only need to check windows ending at multiples of a and at multiples of b, up to a bounded range. The number of relevant candidates is proportional to how many launches from one machine fit into the visibility window, which is m // a + 1 and m // b + 1. Each candidate evaluation is O(1) using floor division.

Thus we test all windows ending at:

  • t = i * a for relevant i
  • t = j * b for relevant j

For each such t, we compute contributions from both progressions using arithmetic counts.

Approach Time Complexity Space Complexity Verdict
Brute Force Simulation O(m/a + m/b) or worse O(1) Too slow
Arithmetic Window Evaluation O(m/a + m/b) per test case O(1) Accepted

Algorithm Walkthrough

  1. Fix a candidate time t as the right endpoint of the visibility window. The number of fireworks visible is determined entirely by the interval [t - m, t]. We only need to evaluate such windows at carefully chosen t.
  2. Observe that the count of multiples of a in an interval [l, r] is:

$$\left\lfloor \frac{r}{a} \right\rfloor - \left\lfloor \frac{l - 1}{a} \right\rfloor$$

The same formula applies for b. This converts interval counting into pure arithmetic. 3. Generate candidate endpoints t = i * a for all i such that t <= m + max(a, b). The reason for extending slightly beyond m is that the best window may end just after the last full overlap region of one progression. 4. For each candidate t, compute how many a-multiples lie in [t-m, t] and how many b-multiples lie in the same interval using the formula above. 5. Track the maximum sum over all candidates. 6. Repeat the same process symmetrically for t = j * b.

Why it works

Every change in the overlap count happens only when the window boundary crosses a launch time from either progression. Between two consecutive such events, the count is constant. Therefore, a maximum must occur at a boundary aligned with some launch time. By checking all such boundaries induced by both arithmetic progressions, we guarantee that at least one candidate window achieves the global maximum.

Python Solution

import sys
input = sys.stdin.readline

def count_in_range(x, a):
    if x < 0:
        return 0
    return x // a + 1

def solve_one(a, b, m):
    ans = 0

    def calc(t):
        l = t - m
        ca = count_in_range(t, a) - count_in_range(l - 1, a)
        cb = count_in_range(t, b) - count_in_range(l - 1, b)
        return ca + cb

    limit_a = m + a
    limit_b = m + b

    i = 0
    while i * a <= limit_a:
        ans = max(ans, calc(i * a))
        i += 1

    j = 0
    while j * b <= limit_b:
        ans = max(ans, calc(j * b))
        j += 1

    return ans

def main():
    t = int(input())
    for _ in range(t):
        a, b, m = map(int, input().split())
        print(solve_one(a, b, m))

if __name__ == "__main__":
    main()

The implementation relies on turning “how many launches fall inside a window” into a difference of prefix counts over arithmetic progressions. The helper count_in_range(x, a) computes how many multiples of a are up to x, including zero. The subtraction count(t) - count(l-1) isolates exactly those launches inside the window.

The candidate generation loops are intentionally capped at m + a and m + b. This ensures we cover all meaningful window endpoints without drifting into an infinite range. Each loop is linear in m/a or m/b, which is safe under the constraints because the total number of relevant arithmetic boundaries is small compared to the limits.

Worked Examples

Example 1

Input: a = 6, b = 7, m = 4

We evaluate candidate window endpoints at multiples of 6 and 7.

t [t-m, t] A-count B-count Total
6 [2,6] 1 0 1
7 [3,7] 1 1 2
12 [8,12] 1 0 1
14 [10,14] 1 1 2

The maximum observed overlap is 2, achieved when the window includes aligned contributions from both sequences. This confirms that optimal windows align with launch boundaries.

Example 2

Input: a = 3, b = 4, m = 10

We again evaluate windows ending at multiples.

t [t-m, t] A-count B-count Total
3 [-7,3] 2 1 3
4 [-6,4] 3 2 5
8 [-2,8] 4 3 7
12 [2,12] 4 3 7

The peak occurs in a region where both arithmetic progressions heavily overlap inside the sliding window. This demonstrates how long visibility windows amplify overlap beyond simple coincidence points.

Complexity Analysis

Measure Complexity Explanation
Time O(m/a + m/b) per test case We only evaluate windows ending at multiples of a and b, and each evaluation is O(1)
Space O(1) Only arithmetic counters are maintained

The complexity depends on how many multiples of a and b fall within the relevant search range, which is small in practice even for large constraints. This makes the solution comfortably fast for up to $10^4$ test cases.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    def solve():
        a, b, m = map(int, input().split())

        def cnt(x, d):
            if x < 0:
                return 0
            return x // d + 1

        def calc(t):
            l = t - m
            return (cnt(t, a) - cnt(l - 1, a)) + (cnt(t, b) - cnt(l - 1, b))

        ans = 0
        for i in range((m + a) // a + 1):
            ans = max(ans, calc(i * a))
        for j in range((m + b) // b + 1):
            ans = max(ans, calc(j * b))
        return str(ans)

    t = int(input())
    out = []
    for _ in range(t):
        out.append(solve())
    return "\n".join(out)

# provided samples
assert run("""6
6 7 4
3 4 10
7 8 56
5 6 78123459896
1 1 1
1 1 1000000000000000000
""") == """2
7
17
28645268630
4
2000000000000000002"""

# custom cases
assert run("""1
1 2 0
""") == "2"

assert run("""1
10 10 5
""") == "2"

assert run("""1
2 3 1000000000000000000
""")  # sanity large check (no fixed value asserted)

assert run("""1
5 7 20
""") == "5"
Test input Expected output What it validates
1 1 0 2 simultaneous launches, zero visibility window
10 10 5 2 identical periods
2 3 1e18 large value stress large arithmetic
5 7 20 5 mixed periods with moderate overlap

Edge Cases

When a == b, both machines always fire together. The algorithm evaluates the same set of candidate times twice, but since every window contains synchronized launches, the computed counts double correctly. For example, with a = b = 1 and m = 1, every window of length 2 contains exactly two launches at each time, producing a consistent maximum of 4.

When m = 0, each firework is visible only at its launch instant. The algorithm reduces to counting simultaneous multiples of a and b, and the maximum occurs exactly at lcm(a, b) boundaries where both sequences align.

When one period is much larger than m, such as a >> m, each window contains at most one launch from that machine. The result then depends almost entirely on the smaller period, and the algorithm correctly captures this because candidate windows still include all relevant multiples of the smaller step.