CF 250C - Movie Critics

CF 250C - Movie Critics

Rating: 1600
Tags: greedy
Solve time: 3m 12s
Verified: no

Solution

Problem Understanding

We are given a sequence of movie genres scheduled over n days, with exactly one movie per day. There are k genres, and each genre appears at least once. Valentine, a critic, experiences stress whenever the genre of consecutive movies he watches changes. He plans to skip all movies of a single genre to minimize his total stress. The task is to identify which genre he should skip to achieve the minimum stress. If multiple genres yield the same stress reduction, we pick the genre with the smallest number.

The key constraint is that n can be up to 10^5, meaning any solution must run in roughly linear time. An O(n*k) approach, where we simulate removing each genre separately, would require about 10 billion operations in the worst case and is therefore too slow. We need an O(n + k) solution or close to it. A subtle edge case arises when the first or last movie is of the skipped genre, which can change the stress count at boundaries, and also when multiple genres yield the same minimum stress.

For example, if n=3 and genres are 1 2 1, skipping genre 1 leaves 2 only, with zero stress, skipping genre 2 leaves 1 1 also with zero stress, and skipping any other genre would be invalid. A naive algorithm may mishandle the first and last movie or underestimate the stress reduction when adjacent skipped movies occur.

Approaches

The brute-force method would try skipping each genre from 1 to k individually, simulate the resulting sequence of watched movies, and count the stress as the number of times the genre changes between consecutive movies. This is correct but requires O(n*k) operations. For n up to 10^5, it could take up to 10 billion operations, which is too slow.

The key insight is that we do not need to actually construct the new sequence for each genre. The stress for a sequence is determined by the number of boundaries where consecutive genres differ. If we precompute the number of boundaries each genre participates in, we can efficiently calculate the stress reduction for skipping that genre. Specifically, skipping a genre eliminates stresses that occur at transitions where that genre is involved. We also need to account for the first and last movie, because they have only one adjacent neighbor. By processing the original sequence once and recording contributions of each genre to the stress, we can compute the total stress after skipping any genre in O(1) time per genre, giving an overall O(n + k) solution.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n*k)	O(n)	Too slow
Optimal	O(n + k)	O(k)	Accepted

Algorithm Walkthrough

1. Initialize an array stress_contrib of size k+1 to zero. This array will count how many stress instances each genre contributes to in the original sequence.
2. Iterate over the sequence from the second movie to the last. For each pair of consecutive movies (a[i-1], a[i]), if the genres differ, increment the stress contribution for both a[i-1] and a[i] by 1. This counts each transition as contributing to the stress of both genres involved.
3. Initialize min_stress to infinity and best_genre to -1.
4. For each genre g from 1 to k, compute the total stress after skipping g as the original total stress minus the stress contributions of genre g. If the first movie is of genre g, decrement the stress by 1 because the boundary at the start is removed. Similarly, if the last movie is of genre g, decrement the stress by 1.
5. Compare this stress value with min_stress. If it is smaller, update min_stress and best_genre. If it is equal, choose the smaller genre number to satisfy the problem's tie-breaking rule.
6. Output best_genre.

The invariant is that each stress is contributed by exactly two genres at its boundary. By subtracting all contributions of the skipped genre, and adjusting for edges, we capture the exact stress after skipping that genre without reconstructing the sequence. This ensures correctness for any sequence, including edge cases where skipped movies are at the start or end or occur consecutively.

Python Solution

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a = list(map(int, input().split()))

stress_contrib = [0] * (k + 1)
total_stress = 0

for i in range(1, n):
    if a[i] != a[i-1]:
        stress_contrib[a[i-1]] += 1
        stress_contrib[a[i]] += 1
        total_stress += 1

min_stress = float('inf')
best_genre = -1

for g in range(1, k + 1):
    stress = total_stress - stress_contrib[g]
    if a[0] == g:
        stress -= 1
    if a[-1] == g:
        stress -= 1
    if stress < min_stress:
        min_stress = stress
        best_genre = g

print(best_genre)

The first loop computes all stress contributions for each genre, and total_stress counts the number of transitions in the original sequence. When iterating over genres, we subtract contributions of the skipped genre and adjust for boundaries at the start and end, which prevents undercounting stress removed by skipping first or last movies.

Worked Examples

Sample 1:

i	a[i]	a[i-1]	Stress contributed	stress_contrib
1	1	1	0	1:0
2	2	1	1	1:1, 2:1
3	3	2	1	2:2, 3:1
4	2	3	1	3:2, 2:3
5	3	2	1	2:4, 3:3
6	3	3	0
7	1	3	1	3:4,1:2
8	1	1	0
9	3	1	1	1:3,3:5

Original total stress = 7. Stress after skipping each genre:

• Skip 1: 7 - 3 - adjust first (a[0]==1) -1, last not 1 => stress = 3
• Skip 2: 7 - 4, first/end not 2 => stress=3
• Skip 3: 7 - 5, first/end not 3 => stress=2

Best genre to skip is 3.

Sample 2 (edge case):

Input: n=5, k=2, a=[1,2,1,2,1]

Transitions: 1→2,2→1,1→2,2→1 → total 4 stresses

stress_contrib[1]=4, stress_contrib[2]=4

• Skip 1: 4-4, first=1 → -1, last=1 → -1 → stress=2
• Skip 2: 4-4, first/end not 2 → stress=0

Best genre = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + k)	Single pass to compute stress contributions O(n), another pass over k genres O(k)
Space	O(k)	Array to store stress contributions of each genre

This linear complexity is sufficient for n up to 10^5 and k ≤ n.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    stress_contrib = [0] * (k + 1)
    total_stress = 0
    for i in range(1, n):
        if a[i] != a[i-1]:
            stress_contrib[a[i-1]] += 1
            stress_contrib[a[i]] += 1
            total_stress += 1
    min_stress = float('inf')
    best_genre = -1
    for g in range(1, k + 1):
        stress = total_stress - stress_contrib[g]
        if a[0] == g:
            stress -= 1
        if a[-1] == g:
            stress -= 1
        if stress < min_stress:
            min_stress = stress
            best_genre = g
    return str(best_genre)

# provided samples
assert run("10 3\n1 1 2 3 2 3 3 1 1 3\n") == "3", "sample 1"

# custom cases
assert run("5 2\n1 2 1 2 1\n") == "2", "alternating sequence"
assert run("2 2\n1 2\n") == "1", "minimal case