Codeforces Round 172 (Div. 1)

5 problems from Codeforces Round 172 (Div. 1) (contest 280), difficulty 1800-3000. 4/5 solutions verified against sample I/O.

5 items

Codeforces Round 172 (Div. 1)

Div. 1 | 5 problems | 4/5 verified | Difficulty 1800-3000 | 10m 1s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Rectangle Puzzle	2000	geometry	1,586	1m 57s	✓
B	Maximum Xor Secondary	1800	data-structures, implementation, two-pointers	5,251	1m 39s	✓
C	Game on Tree	2200	implementation, math, probabilities	5,126	2m 1s	✓
D	k-Maximum Subsequence Sum	2800	data-structures, flows, graphs	1,653	2m 27s	✓
E	Sequence Transformation	3000	brute-force, data-structures, dp	261	1m 57s

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

CF 280B - Maximum Xor Secondary

We are given an array of distinct positive integers, and our task is to find the largest possible "lucky number" obtainable from any contiguous subarray of length at least two. A "lucky number" is defined as the bitwise XOR of the largest and second largest element in a subarray.

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

CF 280C - Game on Tree

We are given a tree with root at vertex 1. A game is played on this rooted tree until every node disappears. At each move, one of the currently remaining vertices is chosen uniformly at random.

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

CF 280E - Sequence Transformation

We are given a sequence of numbers that is already sorted in non-decreasing order. We need to produce another sequence of the same length such that each consecutive difference lies within a specified range, and each element is between 1 and an upper bound q.

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

CF 280D - k-Maximum Subsequence Sum

We maintain an array that changes over time. There are two kinds of operations. One operation updates a single position. The other asks for the maximum total sum obtainable by selecting at most k pairwise disjoint subarrays inside a given interval [l, r].

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

CF 280A - Rectangle Puzzle

We are given a rectangle centered at the origin with sides parallel to the coordinate axes, having width w along the x-axis and height h along the y-axis. Another rectangle of the same dimensions is rotated around the origin by an angle α (given in degrees).