CF 1234B2 - Social Network (hard version)

Rating: 1300
Tags: data structures, implementation
Solve time: 5m 19s
Verified: yes

Solution

Problem Understanding

We are simulating a dynamic list of conversations ordered by “recency of appearance on screen”, with a hard cap on how many conversations can be shown at once. Each incoming message is tied to a single friend ID, and every ID corresponds to exactly one conversation.

When a message arrives, we check whether that friend’s conversation is already visible on the screen. If it is not, we may need to evict the least recent visible conversation to keep the total count within the limit, and then we insert the new conversation at the top. If it is already visible, nothing changes at all, neither the order nor the set of visible conversations.

The final state is simply the list of visible conversations in top-to-bottom order after processing all messages.

The constraints allow up to 200,000 messages and a screen size also up to 200,000. That immediately rules out any solution that shifts arrays or searches linearly for each message. A naive simulation that scans the current screen list for membership and then performs insertions and deletions inside a Python list would degrade to quadratic time in the worst case, which is far beyond the time limit.

A few edge cases are worth making explicit.

If all messages come from the same friend, for example 1 1 1 1, then after the first insertion the screen never changes again. A correct solution must avoid re-inserting or reordering in this case, otherwise it will incorrectly push the same ID repeatedly.

If every message comes from a distinct friend and k = 1, only the most recent unique message should survive. For input 1 2 3 4 with k = 1, the answer is [4]. Any approach that forgets to evict properly or that keeps older items because it does not enforce capacity strictly will fail.

Another subtle case is repeated alternation like 1 2 1 2 1 2 with k = 2. The structure oscillates, and correctness depends on correctly detecting membership in the current screen state in constant time.

Approaches

A direct simulation maintains the screen as a list and processes each message by scanning to see whether the ID is already present. If not present, we remove the last element if needed and insert at the front.

This approach is correct because it mirrors the rules exactly, but each step can cost linear time in the current screen size. Over n messages this becomes O(nk), and in the worst case k is O(n), giving O(n²). With n up to 200,000, this is too slow.

The key observation is that we need two operations to be fast: membership testing (“is this ID currently visible?”) and maintaining an ordered list of at most k elements where we frequently move elements to the front and possibly remove the last element.

This is exactly the structure of an LRU cache. We maintain:

A doubly linked order (or Python OrderedDict) representing the screen order from most recent (front) to least recent (back).
A hash set or dictionary for O(1) membership checks.

When a new message arrives:

If it exists, we do nothing.
If it does not exist, we insert it at the front and evict the last element if size exceeds k.

This reduces all operations to amortized O(1), because both membership checks and reordering are constant-time operations in the chosen data structure.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(nk)	O(k)	Too slow
Optimal (LRU-style structure)	O(n)	O(k)	Accepted

Algorithm Walkthrough

We simulate the screen using a structure that preserves order and allows fast membership checks. In Python, an OrderedDict is ideal because it supports insertion, deletion, and reordering in constant time.

Initialize an empty ordered structure representing the screen.

The structure stores friend IDs in order from most recent to least recent. 2. Iterate through each incoming message ID in sequence.

Each step updates the current state of the visible conversations. 3. For the current ID, check if it already exists in the structure.

If it exists, do nothing because the problem states repeated visibility does not change order. 4. If it does not exist, insert it at the front of the structure.

This represents that the conversation becomes most recently active. 5. If the size of the structure exceeds k, remove the least recent element from the back.

This enforces the screen capacity constraint. 6. After processing all messages, output the structure in order from front to back.

The non-trivial part is the reordering step. When a new ID is inserted, it is always placed at the front because the most recent message defines recency ordering, not frequency or any historical average.

Why it works

At any point in time, the structure maintains exactly the set of conversations that would appear on the screen after processing the current prefix of messages. The ordering invariant is that among all visible conversations, the most recently inserted or updated one is always at the front, and the least recent is at the back. Since only new unseen IDs affect the structure and repeated IDs do nothing, the relative order among existing elements only changes when a new element is added at the front, which preserves correctness of recency ordering.

Python Solution

import sys
input = sys.stdin.readline

from collections import OrderedDict

def solve():
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))

    screen = OrderedDict()

    for x in arr:
        if x in screen:
            continue
        screen[x] = None
        screen.move_to_end(x, last=False)

        if len(screen) > k:
            screen.popitem(last=True)

    res = list(screen.keys())
    print(len(res))
    print(*res)

if __name__ == "__main__":
    solve()

The core of the implementation is the OrderedDict. It simultaneously handles membership checks, ordering, and efficient updates. The move_to_end(x, last=False) call ensures insertion at the front, which is necessary because new conversations must always become most recent.

The eviction step popitem(last=True) removes the least recent conversation when capacity is exceeded.

A common mistake is inserting an element at the front even when it already exists. That would incorrectly change the recency ordering, but the problem explicitly states that repeated messages do not modify the screen state at all.

Worked Examples

Example 1

Input:

7 2
1 2 3 2 1 3 2

We track the screen after each message.

Step	Message	Screen state
1	1	[1]
2	2	[2, 1]
3	3	[3, 2]
4	2	[3, 2]
5	1	[1, 3]
6	3	[1, 3]
7	2	[2, 1]

The final state [2, 1] matches the expected output. The trace shows that repeated messages (like step 4 and 6) produce no structural change, while unseen messages both insert at the front and may trigger eviction.

Example 2

Input:

4 1
1 2 3 4

Step	Message	Screen state
1	1	[1]
2	2	[2]
3	3	[3]
4	4	[4]

Each new message replaces the only slot available. This confirms strict enforcement of capacity k = 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each message triggers at most one dictionary lookup, one insertion, and possibly one deletion, all O(1) amortized
Space	O(k)	The structure stores at most k active conversations at any time

The constraints allow up to 200,000 operations, so a linear-time solution with constant-time updates comfortably fits within both time and memory limits.

Test Cases

import sys, io
from collections import OrderedDict

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from collections import OrderedDict

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

    screen = OrderedDict()

    for x in arr:
        if x in screen:
            continue
        screen[x] = None
        screen.move_to_end(x, last=False)
        if len(screen) > k:
            screen.popitem(last=True)

    res = list(screen.keys())
    return str(len(res)) + "\n" + " ".join(map(str, res))

# provided sample
assert run("7 2\n1 2 3 2 1 3 2\n") == "2\n2 1"

# all same values
assert run("5 3\n7 7 7 7 7\n") == "1\n7"

# k = 1
assert run("4 1\n1 2 3 4\n") == "1\n4"

# k equals n
assert run("3 3\n1 2 3\n") == "3\n3 2 1"

# alternating pattern
assert run("6 2\n1 2 1 2 1 2\n") == "2\n1 2"

Test input	Expected output	What it validates
all same values	1 element	repeated messages do not reorder
k = 1	last element	strict eviction behavior
k = n	full reverse order	full capacity retention
alternating pattern	stable 2-state LRU	membership and ordering correctness

Edge Cases

For the input where all messages are identical, such as 5 3 / 7 7 7 7 7, the first insertion creates [7], and every subsequent message is ignored because the ID is already present. The structure never grows beyond size 1, confirming that repeated messages do not cause re-insertion or unnecessary eviction.

For k = 1, such as 4 1 / 1 2 3 4, each new unseen ID replaces the previous one. After processing, only the last message remains. The algorithm enforces this by always popping the last element whenever a new insertion occurs.

For alternating inputs like 1 2 1 2 1 2 with k = 2, the screen stabilizes after the first two unique inserts. Subsequent repeats do not disturb ordering, showing that the membership check is correctly preventing structural updates for already-visible conversations.