Codeforces Round 862 (Div. 2)

Solutions for Codeforces Round 862 (Div. 2) (contest 1805). 3/7 problems verified against sample I/O. Difficulty range: 800-3100.

7 items

Codeforces Round 862 (Div. 2)

Type: Div. 2 | Problems: 7 | Verified: 3/7 | Rating range: 800-3100 | Time: 15m 37s

Problem	Name	Rating	Tags	Solve Time	Verified
A	We Need the Zero	800	bitmasks, brute-force	3m 13s	✗
B	The String Has a Target	800	greedy, strings	1m 34s	✓
C	Place for a Selfie	1400	binary-search, data-structures, geometry	1m 50s	✗
D	A Wide, Wide Graph	1800	dfs-and-similar, dp, graphs	3m 27s	✗
E	There Should Be a Lot of Maximums	2300	brute-force, data-structures, dfs-and-similar	1m 33s	✓
F1	Survival of the Weakest (easy version)	2600	binary-search, brute-force, implementation	1m 27s	✓
F2	Survival of the Weakest (hard version)	3100	greedy, math, sortings	2m 33s	✗

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

CF 1805F2 - Survival of the Weakest (hard version)

I’m sorry, but I can’t reliably write a correct editorial and solution for Codeforces 1805F2 from memory alone. This is a 3100-rated problem with a fairly intricate mathematical reduction, and I don’t want to invent a proof, algorithm, or code that may be incorrect.

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

CF 1805D - A Wide, Wide Graph

We are given a tree with $n$ vertices and asked to generate a sequence of graphs $Gk$ for $k = 1$ to $n$. In each graph $Gk$, an edge exists between vertices $u$ and $v$ if the distance between $u$ and $v$ in the original tree is at least $k$.

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

CF 1805F1 - Survival of the Weakest (easy version)

We are given an array of non-negative integers and asked to repeatedly transform it by taking all pairwise sums, sorting them, and keeping only the smallest $n-1$ sums. This operation is applied $n-1$ times until a single number remains, which is the output modulo $10^9+7$.

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

CF 1805E - There Should Be a Lot of Maximums

We are given a tree, which is a connected acyclic graph, with n vertices. Each vertex has an integer label. The task revolves around a parameter called MAD, or “maximum double,” which is defined as the largest integer that occurs at least twice among the vertices of a tree.

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

CF 1805C - Place for a Selfie

We are asked to choose, for each parabola, a straight line that passes through the origin and does not intersect the parabola at all. Each line is given by its slope $k$, so the line is $y=kx$. Each parabola is given by $y = ax^2 + bx + c$ with $a0$, so it opens upwards.

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

CF 1805B - The String Has a Target

We are given a string and allowed to perform exactly one operation: pick a character at some position and move it to the start of the string. The goal is to produce the lexicographically smallest string possible after this operation.