CF 1234B1 - Social Network (easy version)

CF 1234B1 - Social Network (easy version)

Rating: 1000
Tags: implementation
Solve time: 1m 25s
Verified: yes

Solution

Problem Understanding

We are simulating the behavior of a smartphone chat interface. The smartphone screen can show at most $k$ conversations. Each incoming message comes from a friend identified by a unique ID. If a conversation with that friend is already on the screen, the screen does not change. If the conversation is not on the screen, it is inserted at the top, and if the screen was already full, the conversation at the bottom is removed.

The input gives $n$, the number of messages, $k$, the screen capacity, and a sequence of $n$ friend IDs representing the messages received in order. The output is the final state of the screen: the number of conversations displayed and the list of IDs in order from top to bottom.

The constraints are small: $n, k \le 200$. This means we can afford an $O(nk)$ algorithm without worrying about efficiency. No sophisticated data structures are required. Each ID can be very large ($1 \le id_i \le 10^9$), so using arrays indexed by ID is not feasible. Instead, we track which IDs are on screen using a set or list.

A subtle edge case arises when messages repeat frequently. For example, if $n = 3$, $k = 2$, and the messages are $1, 1, 2$, a naive implementation might insert the second 1 again, but the rules specify that duplicates do not move the conversation if it is already visible. Another edge case occurs when the number of unique messages never exceeds $k$; the screen never needs to evict conversations, but the algorithm must correctly maintain order.

Approaches

The brute-force approach is straightforward. We maintain a list representing the screen in order. For each incoming message, we check if the friend ID is already in the list. If it is, we do nothing. If it is not, we insert it at the front. If the list exceeds size $k$, we remove the last element. This is simple and correct because each operation directly follows the problem's rules. Its complexity is $O(nk)$ because for each of the $n$ messages we may need to search through up to $k$ elements in the list.

The key insight to optimize further would be to maintain both a list and a set. The set allows $O(1)$ checks for membership, while the list maintains the order. This reduces the membership check from $O(k)$ to $O(1)$, but in this problem, the input constraints are so small that the brute-force method is already acceptable. The problem structure-small $n$ and $k$, and insertion always at the front-makes a simple list simulation efficient enough.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n*k)	O(k)	Accepted
List + Set	O(n)	O(k)	Overkill but also correct

Algorithm Walkthrough

1. Initialize an empty list screen to represent the conversations on the screen.
2. Iterate over each message ID id_i in the sequence of incoming messages.
3. If id_i is already in screen, skip to the next message because the screen does not change.
4. Otherwise, check if the length of screen is equal to k. If it is, remove the last element of screen to make space.
5. Insert id_i at the front of screen to represent it appearing at the topmost position.
6. After processing all messages, print the length of screen and the IDs in order from top to bottom.

Why it works: The list screen always represents the current top-to-bottom order of conversations. Invariant: no duplicate IDs exist in screen and its size never exceeds k. The insertion-at-front rule combined with removing from the back when full maintains the correct state. Each decision follows directly from the problem's rules, so correctness is guaranteed.

Python Solution

import sys
input = sys.stdin.readline

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

screen = []

for id_i in ids:
    if id_i in screen:
        continue
    if len(screen) == k:
        screen.pop()
    screen.insert(0, id_i)

print(len(screen))
print(' '.join(map(str, screen)))

The first two lines read input efficiently. The screen list maintains the top-to-bottom order. For each id_i, we first check for duplicates. If the screen is full, pop() removes the bottom conversation. insert(0, id_i) adds the new conversation at the top. Printing the length and contents of screen completes the simulation. Edge cases such as repeated messages or fewer unique messages than k are naturally handled by these operations.

Worked Examples

Sample 1: n = 7, k = 2, messages 1 2 3 2 1 3 2

Message	Screen Before	Action	Screen After
1	[]	insert	[1]
2	[1]	insert	[2,1]
3	[2,1]	full, evict 1	[3,2]
2	[3,2]	already exists	[3,2]
1	[3,2]	full, evict 2	[1,3]
3	[1,3]	already exists	[1,3]
2	[1,3]	full, evict 3	[2,1]

Final output: 2, 2 1. This trace confirms that duplicates do not change the screen and eviction happens correctly when full.

Sample 2: n = 4, k = 3, messages 2 3 2 1

Message	Screen Before	Action	Screen After
2	[]	insert	[2]
3	[2]	insert	[3,2]
2	[3,2]	exists	[3,2]
1	[3,2]	insert	[1,3,2]

Final output: 3, 1 3 2. Demonstrates handling duplicates and filling the screen up to capacity without eviction.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n*k)	For each of the n messages, membership check and insertion/removal may cost up to k operations. Acceptable since n,k ≤ 200.
Space	O(k)	Only the screen list of up to k conversations is stored.

The algorithm easily fits within the 2-second time limit and 256 MB memory constraint due to small $n$ and $k$.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n, k = map(int, input().split())
    ids = list(map(int, input().split()))
    screen = []
    for id_i in ids:
        if id_i in screen:
            continue
        if len(screen) == k:
            screen.pop()
        screen.insert(0, id_i)
    return f"{len(screen)}\n{' '.join(map(str, screen))}"

# Provided samples
assert run("7 2\n1 2 3 2 1 3 2\n") == "2\n2 1", "sample 1"
assert run("4 3\n2 3 2 1\n") == "3\n1 3 2", "sample 2"

# Custom cases
assert run("3 2\n1 1 2\n") == "2\n2 1", "duplicate first"
assert run("5 3\n5 4 3 2 1\n") == "3\n1 2 3", "screen fills and evicts sequentially"
assert run("1 1\n10\n") == "1\n10", "single message fits screen"
assert run("6 6\n1 2 3 4 5 6\n") == "6\n6 5 4 3 2 1", "screen never full"

Test input	Expected output	What it validates
3 2\n1 1 2\n	2\n2 1	Handling repeated messages without duplication
5 3\n5 4 3 2 1\n	3\n1 2 3	Eviction order when screen fills repeatedly
1 1\n10\n	1\n10	Minimum-size input
6 6\n1 2 3 4 5 6\n	6\n6 5 4 3 2 1	Screen fills but never exceeds capacity

Edge Cases

Repeated messages that are already on screen are skipped. For input 3 2\n1 1 2, the first 1 is inserted, the second 1 is ignored because it is already visible, and 2 is inserted at the top.