Codeforces Round 189 (Div. 1)

5 problems from Codeforces Round 189 (Div. 1) (contest 319), difficulty 1600-3000. 3/5 solutions verified against sample I/O.

5 items

Codeforces Round 189 (Div. 1)

Div. 1 | 5 problems | 3/5 verified | Difficulty 1600-3000 | 7m 5s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Malek Dance Club	1600	combinatorics, math	3,024	1m 14s	✓
B	Psychos in a Line	1900	data-structures, implementation	4,745	1m 13s	✓
C	Kalila and Dimna in the Logging Industry	2100	dp, geometry	6,586	1m 40s
D	Have You Ever Heard About the Word?	2800	greedy, hashing, string-suffix-structures	777	1m 27s
E	Ping-Pong	3000	data-structures	739	1m 31s	✓

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

CF 319A - Malek Dance Club

We are given a binary string that we interpret as an integer, and from it we construct a fixed pairing between two ordered sets of size $2^n$.

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

CF 319C - Kalila and Dimna in the Logging Industry

We are given a sequence of trees with strictly increasing heights. Each tree can be cut down one unit at a time using a chainsaw. The chainsaw requires recharging after each cut, and the recharge cost depends on which trees have already been fully cut.

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

CF 319E - Ping-Pong

We are asked to maintain a dynamic set of intervals and answer reachability queries between them. Each interval is represented by two integers $(x, y)$ where $x < y$. Intervals are added one by one, and each new interval is guaranteed to be strictly longer than all previous ones.

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

CF 319D - Have You Ever Heard About the Word?

We are given a single string and we repeatedly compress certain patterns inside it. The only pattern that matters is a substring that consists of two identical halves placed back to back, so a segment of the form X + X, where X is any non-empty string.

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

CF 319B - Psychos in a Line

We are given a permutation of the numbers from 1 to n arranged in a line. Each position represents a “psycho” with a unique strength value, and the line evolves in discrete rounds. In one round, every psycho compares himself with the person immediately to his right.