Codeforces Round 109 (Div. 1)

Solutions for Codeforces Round 109 (Div. 1) (contest 154). 4/4 problems verified against sample I/O. Difficulty range: 1600-2400.

4 items

Codeforces Round 109 (Div. 1)

Type: Div. 1 | Problems: 4 | Verified: 4/4 | Rating range: 1600-2400 | Time: 6m 30s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Hometask	1600	greedy	1m 15s	✓
B	Colliders	1600	math, number-theory	2m 4s	✓
C	Double Profiles	2300	graphs, hashing, sortings	1m 37s	✓
D	Flatland Fencing	2400	games, math	1m 34s	✓

Practice › Codeforces Solutions › Codeforces Round 109 (Div. 1) ›

CF 154A - Hometask

The problem asks us to take a string that represents a sentence in a fictional language, and a list of forbidden pairs of letters. Each forbidden pair consists of two distinct letters that cannot appear next to each other in the string in any order.

Practice › Codeforces Solutions › Codeforces Round 109 (Div. 1) ›

CF 154B - Colliders

We maintain a set of currently active colliders. Each collider is identified by an integer from 1 to n. The system is safe only if every pair of active colliders is coprime. In other words, no prime factor may appear in two different active numbers at the same time.

Practice › Codeforces Solutions › Codeforces Round 109 (Div. 1) ›

CF 154C - Double Profiles

We are working with an undirected graph where each vertex represents a social network profile. Two profiles are considered "doubles" if every other profile sees them identically. For any third vertex k, either both i and j are connected to k, or neither is connected to k.

Practice › Codeforces Solutions › Codeforces Round 109 (Div. 1) ›

CF 154D - Flatland Fencing

Two players stand on integer points of a number line. On each turn, the current player chooses a new integer coordinate inside a fixed interval relative to their current position. If the first player is at position x, he may move to any integer point in [x + a, x + b].