Overview

Given a sequence of flowers, remove all flowers that are not contained in any “visually appealing segment” — a segment where the same variety appears \(K\) or more times consecutively — and output the remaining flowers in order.

Analysis

In this problem, we need to determine for each flower: “Does there exist a consecutive subsequence of the same variety with length \(K\) or more that includes this flower?”

A naive approach would be to check for each position \(i\) how many consecutive identical values extend in both directions, but in the worst case this results in \(O(N^2)\) time complexity, which is too slow since \(N\) can be up to \(10^6\).

The key observation is to handle “segments of consecutive identical varieties” as groups. That is, we partition the sequence into groups of consecutive identical values, and simply check whether each group’s length is \(K\) or more. If a group’s length is \(K\) or more, all flowers in that group are kept.

Therefore, the efficient approach is to first split the input array into “segments of consecutive identical values,” check the length of each segment, and if it is \(K\) or more, keep all flowers belonging to that segment.

For example, if the input is 1 1 2 2 2 3 and \(K=3\): - Segment of value 1: length 2 → not kept - Segment of value 2: length 3 → kept - Segment of value 3: length 1 → not kept
The result is 2 2 2.

By thinking in terms of groups like this, we can obtain the answer without individually checking each element.

Algorithm

1. Read the input as a list \(S\).
2. Scan the array \(S\) from the beginning and detect “groups” of consecutive identical values.
   • Each group holds the information (value, start position, length).
3. For each group, if its length is \(K\) or more, set a “keep” flag for the flowers in that range.
4. Collect and output only the flowers with the “keep” flag set.

Specifically, you could use groupby, but here we implement it manually with a loop. This is to accurately obtain the start index and length.

Complexity

• Time complexity: \(O(N)\)
  Since each element is read only once, the processing can be done in linear time.
• Space complexity: \(O(N)\)
  \(O(N)\) is required for the input array and the flag management array keep.

Implementation Notes

• When extracting groups, it is important to accurately record the start position and length.

• By using a flag management array keep, we can easily determine later which flowers should be kept.

• Note that the final output must print “only a newline” even when the result is empty.

  Source Code

import sys
from itertools import groupby

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    S = list(map(int, data[2:]))

    # Group consecutive same elements
    # groups will store (value, start_index, length)
    groups = []
    i = 0
    while i < N:
        val = S[i]
        start = i
        while i < N and S[i] == val:
            i += 1
        length = i - start
        groups.append((val, start, length))
    
    # Create a boolean array to mark whether each flower should be kept
    keep = [False] * N
    for val, start, length in groups:
        if length >= K:
            # Mark all flowers in this group as keep
            for j in range(start, start + length):
                keep[j] = True
    
    # Collect the result
    result = [S[i] for i in range(N) if keep[i]]
    
    if result:
        print(' '.join(map(str, result)))
    else:
        print()

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.