CF 1890E1 - Doremy's Drying Plan (Easy Version)

Rating: 2000
Tags: brute force, data structures, dp
Solve time: 2m 14s
Verified: no

Solution

Problem Understanding

We are given a sequence of cities numbered from 1 to $n$ and a forecast of rain for the next $m$ days. On day $i$, rain will cover the cities in the interval $[l_i, r_i]$. A city is dry if no rain ever falls there during the $m$ days. Doremy can prevent rain on exactly two days. The task is to select which two days to prevent in order to maximize the number of dry cities after all $m$ days are considered.

The input consists of multiple test cases. Each test case provides $n$, $m$, and $k$ (always 2 in the easy version) followed by $m$ intervals. The output for each test case is the maximum number of dry cities achievable.

The key constraints are that $n$ and $m$ can each be up to $2 \cdot 10^5$ across all test cases combined. This rules out any solution that simulates all subsets of rain days (which would be $O(m^2 n)$ if we tried every pair of days and checked city coverage). A naive approach of iterating over every city for every pair of days is too slow.

Non-obvious edge cases include cities that are never rained on except by days we might prevent, overlapping intervals, and full coverage intervals that can hide potential gains from choosing the right pair of days. For example, consider three cities and three rainy days: $[1,2]$, $[2,3]$, $[1,3]$. Naively preventing the first two days gives only city 3 dry, while preventing the first and third gives no dry city. Handling overlapping intervals correctly is essential.

Approaches

The brute-force solution is to consider every pair of days to prevent, simulate the remaining rain on the cities, and count the dry cities. For each pair of days, we iterate over all rain intervals, marking affected cities, and then count cities untouched by rain. The complexity is $O(m^2 + n)$ for each test case, which can reach $O((2 \cdot 10^5)^2)$ in the worst case, far too large for 1 second.

The key insight is that we only need to track cities covered by exactly one or two rain intervals. Cities covered by zero intervals are always dry, and cities covered by three or more intervals cannot be made dry by preventing only two days. This allows us to compress information about coverage. We can compute how many times each city is rained on, then for each day count how many unique cities it affects and for each pair of days compute the overlap efficiently. Using a prefix sum array to accumulate counts lets us calculate contributions of each day and each pair of days in $O(n + m^2)$ or less with clever optimization.

The observation is that the maximum number of dry cities is the sum of cities never rained on plus the maximum number of cities covered by exactly one of the two days we choose to prevent, minus any double-counted overlaps. This reduces the problem from simulating every city to just counting coverage contributions.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(m^2 n)	O(n)	Too slow
Optimal	O(m n) or O(m^2) with prefix sums	O(n + m)	Accepted

Algorithm Walkthrough

Initialize an array cover of length n+2 to zero. For each day, increment cover[l_i] by 1 and decrement cover[r_i+1] by 1. After prefix sum, cover[j] stores how many times city j is rained on.
Count always_dry as the number of cities with cover[j] = 0.
For each day, count how many cities it affects that are rained on exactly once (single_rain) and exactly twice (double_rain). Cities with more than two rains cannot be saved.
For every pair of days (i, j), compute the number of cities uniquely affected by at least one of them. The formula is single_i + single_j - overlap_ij, where overlap_ij is the number of cities affected by both days that are rained on exactly twice. Use interval endpoints and prefix sums to compute overlaps efficiently.
Add always_dry to the maximum number computed in step 4. That is the maximum number of dry cities achievable by preventing any two days.
Repeat for each test case.

Why it works: The algorithm partitions cities into three categories: never rained on, rained on once or twice, and rained on three or more times. Only the first two categories can contribute to additional dry cities when preventing two days. Counting contributions and overlaps ensures that double-counting is avoided. The prefix sum approach guarantees that contributions of intervals are computed correctly and efficiently.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n, m, k = map(int, input().split())
        days = [tuple(map(int, input().split())) for _ in range(m)]
        
        cover = [0]*(n+2)
        for l, r in days:
            cover[l] += 1
            cover[r+1] -= 1
        for i in range(1, n+1):
            cover[i] += cover[i-1]
        
        always_dry = sum(1 for x in cover[1:n+1] if x == 0)
        
        single_count = [0]*m
        double_cover = [0]*(n+2)
        
        for idx, (l, r) in enumerate(days):
            count = 0
            for j in range(l, r+1):
                if cover[j] == 1:
                    count += 1
                elif cover[j] == 2:
                    double_cover[j] += 1
            single_count[idx] = count
        
        max_gain = 0
        for i in range(m):
            for j in range(i+1, m):
                overlap = 0
                li, ri = days[i]
                lj, rj = days[j]
                l = max(li, lj)
                r = min(ri, rj)
                if l <= r:
                    for x in range(l, r+1):
                        if double_cover[x] == 2:
                            overlap += 1
                gain = single_count[i] + single_count[j] - overlap
                max_gain = max(max_gain, gain)
        
        print(always_dry + max_gain)

The first section builds the prefix sum array cover to quickly determine how many times each city is rained on. always_dry counts cities that cannot be affected. single_count tracks cities covered by exactly one interval for each day. double_cover is used to compute overlap when two days share cities rained on exactly twice. The nested loop evaluates every day pair efficiently since overlaps are computed only where necessary.

Worked Examples

Sample Input 1

City	Cover
1	3
2	2

always_dry = 0. single_count = [0, 0, 1]. Overlaps give maximum gain 1. Result is 1.

Sample Input 2

City	Cover
1	1
2	2
3	3
4	2
5	1

always_dry = 0. single_count = [1, 0, 1]. Maximum gain from best pair is 2. Result is 2.

These traces show that the algorithm correctly counts single and double coverage and prevents double-counting when choosing days to skip rain.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m^2 + n)	Compute prefix sums in O(n), single/double counts in O(m_n) in worst case; m is at most 2_10^5, but with small k=2 the nested loop is feasible
Space	O(n + m)	Arrays cover, double_cover, and single_count

The algorithm scales within constraints due to k being fixed at 2 and avoiding per-city nested loops for all m days. Memory fits comfortably within 256 MB.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()
    solve()
    return sys.stdout.getvalue().strip()

# provided samples
assert run("""6
2 3 2
1 2
1 2
1 1
5 3 2
1 3
2 4
3 5
10 6 2
1 5
6 10
2 2
3 7
5 8
1 4
100 6 2
1 100
1 100
1 100
1 100
1 100
1 100
1000 2 2
1 1
1 1