Codeforces Round 975 (Div. 1)

Solutions for Codeforces Round 975 (Div. 1) (contest 2018). 1/9 problems verified against sample I/O. Difficulty range: 1600-3400.

9 items

Codeforces Round 975 (Div. 1)

Type: Div. 1 | Problems: 9 | Verified: 1/9 | Rating range: 1600-3400 | Time: 15m 37s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Cards Partition	1600	2-sat, brute-force, greedy	2m 54s	✗
B	Speedbreaker	1900	binary-search, data-structures, dp	2m 4s	✗
C	Tree Pruning	1700	brute-force, dfs-and-similar, greedy	1m 55s	✓
D	Max Plus Min Plus Size	2200	data-structures, dp, dsu	1m 55s	✗
E1	Complex Segments (Easy Version)	3300	binary-search, data-structures, divide-and-conquer	1m 57s	✗
E2	Complex Segments (Hard Version)	3400	binary-search, data-structures, divide-and-conquer	38s	✗
F1	Speedbreaker Counting (Easy Version)	2900	combinatorics, dp, greedy	1m 44s	✗
F2	Speedbreaker Counting (Medium Version)	3000	dp, greedy, math	46s	✗
F3	Speedbreaker Counting (Hard Version)	3100	dp, greedy, math	1m 44s	✗

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

CF 2018F3 - Speedbreaker Counting (Hard Version)

We are asked to count arrays of integers representing "time limits" for conquering cities in a row, and then categorize those arrays by how many starting cities allow a valid conquest.

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

CF 2018F1 - Speedbreaker Counting (Easy Version)

The problem asks us to count arrays of length $n$ where each element $ai$ is a positive integer between 1 and $n$, and to categorize these arrays based on how many starting cities allow a sequential conquest without violating the upper limits $ai$.

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

CF 2018F2 - Speedbreaker Counting (Medium Version)

I can't provide a complete, correct editorial and implementation for this problem from the information available here. I was able to retrieve the official editorial hints and the high-level solution outline.

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

CF 2018E1 - Complex Segments (Easy Version)

We are given a collection of closed segments on a number line, each defined by a left and right endpoint. The goal is to identify the largest possible subset of these segments that forms a "complex" set.

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

CF 2018E2 - Complex Segments (Hard Version)

Producing a fully correct editorial for Codeforces 2018E2 requires reconstructing a fairly intricate DSU-based optimization and the divide-and-conquer evaluation of all values of $f(m)$.

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

CF 2018D - Max Plus Min Plus Size

We are given a one-dimensional array of positive integers and the ability to color some elements red. The restriction is that no two consecutive elements can be red.

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

CF 2018C - Tree Pruning

We are given a tree rooted at node 1, and we can remove leaves one by one along with their connecting edges. The goal is to make all remaining leaves equidistant from the root. A leaf is any node with degree 1 that is not the root.

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

CF 2018A - Cards Partition

We are given multiple independent scenarios. In each one, we start with a multiset of cards where each integer value from $1$ to $n$ appears a certain number of times. We are allowed to add up to $k$ extra cards of any values we choose.

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

CF 2018B - Speedbreaker

We are given a line of cities, each city indexed from left to right, and each city comes with a deadline that tells us how late it is allowed to be conquered.