Codeforces Round 869 (Div. 1)

6 problems from Codeforces Round 869 (Div. 1) (contest 1817), difficulty 1500-3500. 3/6 solutions verified against sample I/O.

6 items

Codeforces Round 869 (Div. 1)

Div. 1 | 6 problems | 3/6 verified | Difficulty 1500-3500 | 14m 54s

#	Problem	Rating	Tags	Accepted	Time	✓
A	Almost Increasing Subsequence	1500	binary-search, data-structures, greedy	12,754	2m 35s	✓
B	Fish Graph	1900	brute-force, constructive-algorithms, dfs-and-similar	5,100	2m 40s
C	Similar Polynomials	2400	combinatorics, math	1,227	1m 21s	✓
D	Toy Machine	2700	constructive-algorithms, games, implementation	1,034	1m 9s	✓
E	Half-sum	3400	brute-force, divide-and-conquer, greedy	321	2m 24s
F	Entangled Substrings	3500	string-suffix-structures, strings	328	4m 45s

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

CF 1817F - Entangled Substrings

We are given a single string and we are asked to count how many ordered pairs of non-empty substrings $(a, b)$ satisfy a very rigid structural property: every occurrence of $a$ inside the string must always be followed by the same fixed middle string $c$ and then $b$, and…

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

CF 1817B - Fish Graph

We are given an undirected simple graph and asked whether we can select a subset of its edges that forms a very specific structure called a Fish Graph. The target structure consists of two parts. First, there must be a simple cycle.

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

CF 1817A - Almost Increasing Subsequence

We are working with an array where we need to answer many independent range queries. Each query gives a segment of the array, and for that segment we want the maximum possible length of a subsequence that avoids a very specific forbidden pattern: three chosen elements that…

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

CF 1817E - Half-sum

We start with a multiset of real values, initially all integers. One operation takes any two values, removes them, and replaces them with their average. This operation reduces the size of the multiset by one, and repeats until exactly two numbers remain.

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

CF 1817D - Toy Machine

We are given a two-row toy machine with an odd number $n$ of cells in each row. The top row initially holds $n-2$ toys, placed in all cells except the two corners. The bottom row is mostly empty, with the exception that its leftmost, rightmost, and central cells are blocked.

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

CF 1817C - Similar Polynomials

We are given two polynomials, $A(x)$ and $B(x)$, of the same degree $d$. Instead of the coefficients, we are provided their evaluations at the first $d+1$ integers, i.e., $A(0), A(1), dots, A(d)$ and $B(0), B(1), dots, B(d)$, all modulo $10^9+7$.