Codeforces Round 496 (Div. 3)

7 problems from Codeforces Round 496 (Div. 3) (contest 1005), difficulty 800-2400. 5/7 solutions verified against sample I/O.

7 items

Codeforces Round 496 (Div. 3)

Div. 3 | 7 problems | 5/7 verified | Difficulty 800-2400 | 13m 24s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Tanya and Stairways	800	implementation	27,444	3m 1s	✓
B	Delete from the Left	900	brute-force, implementation, strings	27,371	1m 15s	✓
C	Summarize to the Power of Two	1300	brute-force, greedy, implementation	13,050	1m 47s
D	Polycarp and Div 3	1500	dp, greedy, number-theory	11,283	1m 12s	✓
E1	Median on Segments (Permutations Edition)	1800	sortings	4,343	1m 41s
E2	Median on Segments (General Case Edition)	2400	sortings	1,533	1m 21s	✓
F	Berland and the Shortest Paths	2100	brute-force, dfs-and-similar, graphs	2,104	3m 7s	✓

Practice › Codeforces Solutions › Codeforces Round 496 (Div. 3) ›

CF 1005F - Berland and the Shortest Paths

We are given a connected undirected graph of cities where city 1 is the capital. From this graph we must select exactly $n-1$ roads so that the selected edges still connect all cities, meaning they form a spanning tree.

Practice › Codeforces Solutions › Codeforces Round 496 (Div. 3) ›

CF 1005E2 - Median on Segments (General Case Edition)

We are given a sequence of integers and a fixed value $m$. The task is to count how many contiguous subarrays have the property that when you sort the subarray, its median equals exactly $m$, where for even-length subarrays the median is defined as the left middle element.

Practice › Codeforces Solutions › Codeforces Round 496 (Div. 3) ›

CF 1005E1 - Median on Segments (Permutations Edition)

We are given a permutation of the integers from 1 to n, and a distinguished value m that appears exactly once somewhere in the array. The task is to count how many contiguous subarrays have the property that, if we sort that subarray, the median element equals m.

Practice › Codeforces Solutions › Codeforces Round 496 (Div. 3) ›

CF 1005A - Tanya and Stairways

We are given a single sequence of integers that represents what Tanya says while climbing stairs in a building. Each time she starts a new stairway, she always begins counting from 1 and increases by 1 for each step until she reaches the last step of that stairway.

Practice › Codeforces Solutions › Codeforces Round 496 (Div. 3) ›

CF 1005D - Polycarp and Div 3

We are given a very long decimal string and we are allowed to insert cuts between adjacent digits, splitting it into contiguous chunks.

Practice › Codeforces Solutions › Codeforces Round 496 (Div. 3) ›

CF 1005C - Summarize to the Power of Two

We are given a multiset of integers, and we are allowed to delete any subset of them. After deletions, we want the remaining elements to satisfy a pairing condition: every remaining value must be able to find at least one other remaining value such that their sum equals a…

Practice › Codeforces Solutions › Codeforces Round 496 (Div. 3) ›

CF 1005B - Delete from the Left

We are given two strings, and we are allowed to repeatedly delete only the leftmost character from either string. Each deletion shortens one of the strings by exactly one character.