Codeforces Round 495 (Div. 2)

6 problems from Codeforces Round 495 (Div. 2) (contest 1004), difficulty 900-2600. 2/6 solutions verified against sample I/O.

6 items

Codeforces Round 495 (Div. 2)

Div. 2 | 6 problems | 2/6 verified | Difficulty 900-2600 | 11m 39s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Sonya and Hotels	900	implementation	11,853	1m 38s	✓
B	Sonya and Exhibition	1300	constructive-algorithms, greedy, implementation	9,935	2m 1s
C	Sonya and Robots	1400	constructive-algorithms, implementation	7,880	1m 14s	✓
D	Sonya and Matrix	2300	brute-force, constructive-algorithms, implementation	1,499	1m 59s
E	Sonya and Ice Cream	2400	binary-search, data-structures, dp	1,239	2m 8s
F	Sonya and Bitwise OR	2600	bitmasks, data-structures, divide-and-conquer	928	2m 39s

Practice › Codeforces Solutions › Codeforces Round 495 (Div. 2) ›

CF 1004F - Sonya and Bitwise OR

We are given an array that changes over time and we must repeatedly answer queries about subarrays inside a given segment. For any segment $[l, r]$, we consider every contiguous subarray $[L, R]$ fully contained inside it.

Practice › Codeforces Solutions › Codeforces Round 495 (Div. 2) ›

CF 1004E - Sonya and Ice Cream

We are given a weighted tree with up to $10^5$ vertices. Each edge has a positive length, so distances are standard shortest-path distances on the tree. We must choose a set of vertices that forms a single simple path in the tree, containing at most $k$ vertices.

Practice › Codeforces Solutions › Codeforces Round 495 (Div. 2) ›

CF 1004D - Sonya and Matrix

We are given a multiset of integers that is known to come from a very specific geometric construction. Somewhere on an unknown grid of size $n times m$, there is exactly one cell containing a zero. Every other cell is filled with its Manhattan distance to that zero cell.

Practice › Codeforces Solutions › Codeforces Round 495 (Div. 2) ›

CF 1004B - Sonya and Exhibition

We are given a row of positions, each of which must be filled with one of two possible types. You can think of this as constructing a binary string of length $n$, where each position is either type A or type B.

Practice › Codeforces Solutions › Codeforces Round 495 (Div. 2) ›

CF 1004A - Sonya and Hotels

We are given a set of existing hotels placed on integer points along an infinite number line. We want to open one additional hotel at some integer coordinate. The requirement is that the closest existing hotel to this new one must be at distance exactly $d$.

Practice › Codeforces Solutions › Codeforces Round 495 (Div. 2) ›

CF 1004C - Sonya and Robots

We are given an array of integers laid out on a line. Two robots start just outside the array, one at the far left moving rightward and one at the far right moving leftward.