Codeforces Round 971 (Div. 4)

Solutions for Codeforces Round 971 (Div. 4) (contest 2009). 3/9 problems verified against sample I/O. Difficulty range: 800-2700.

9 items

Codeforces Round 971 (Div. 4)

Type: Div. 4 | Problems: 9 | Verified: 3/9 | Rating range: 800-2700 | Time: 14m 27s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Minimize!	800	brute-force, math	1m 5s	✓
B	osu!mania	800	brute-force, implementation	2m	✗
C	The Legend of Freya the Frog	1100	implementation, math	55s	✗
D	Satyam and Counting	1400	geometry, math	1m 8s	✗
E	Klee's SUPER DUPER LARGE Array!!!	1400	binary-search, math, ternary-search	1m 16s	✓
F	Firefly's Queries	1700	bitmasks, data-structures, flows	2m 1s	✓
G1	Yunli's Subarray Queries (easy version)	1900	binary-search, data-structures, two-pointers	1m 53s	✗
G2	Yunli's Subarray Queries (hard version)	2200	binary-search, data-structures, dp	2m 15s	✗
G3	Yunli's Subarray Queries (extreme version)	2700	data-structures, dp, implementation	1m 54s	✗

Practice › Codeforces Solutions › Codeforces Round 971 (Div. 4) ›

CF 2009G3 - Yunli's Subarray Queries (extreme version)

We are given an array and many range queries. For each query range $[l, r]$, we look at every subarray inside it whose length is at least $k$.

Practice › Codeforces Solutions › Codeforces Round 971 (Div. 4) ›

CF 2009G2 - Yunli's Subarray Queries (hard version)

We are given an array a of size n. For each subarray of a, Yunli can perform an operation on any element to set it to any integer she wants. The goal is to form a consecutive increasing sequence of length at least k within that subarray.

Practice › Codeforces Solutions › Codeforces Round 971 (Div. 4) ›

CF 2009F - Firefly's Queries

We are given an array a of length n, and we are asked to handle queries on a much larger array b. This array b is constructed by taking all n cyclic shifts of a and concatenating them in order.

Practice › Codeforces Solutions › Codeforces Round 971 (Div. 4) ›

CF 2009G1 - Yunli's Subarray Queries (easy version)

We are given an array of integers and need to answer multiple queries. Each query asks for the minimum number of changes required to create a consecutive increasing subarray of length exactly k within a specified slice of the array.

Practice › Codeforces Solutions › Codeforces Round 971 (Div. 4) ›

CF 2009E - Klee's SUPER DUPER LARGE Array!!!

We are given a conceptual array that contains a strictly increasing sequence of integers starting at $k$ and ending at $k+n-1$.

Practice › Codeforces Solutions › Codeforces Round 971 (Div. 4) ›

CF 2009D - Satyam and Counting

Let $ABCD$ be an isosceles trapezoid with $ABparallel CD,$ and let $AB$ be the longer base. Then $ABCD.$ For a point $P$ in the plane, consider the quantity $S=PA+PB+PC+PD.

Practice › Codeforces Solutions › Codeforces Round 971 (Div. 4) ›

CF 2009B - osu!mania

Each test case describes a small osu!mania beatmap with 4 columns. Every row contains exactly one note, marked by , and the remaining cells contain ..

Practice › Codeforces Solutions › Codeforces Round 971 (Div. 4) ›

CF 2009A - Minimize!

We are given multiple independent queries. Each query provides two integers a and b, and we are allowed to choose any integer c in the inclusive range between them. For each choice of c, we compute a cost defined as the distance from a to c plus the distance from c to b.

Practice › Codeforces Solutions › Codeforces Round 971 (Div. 4) ›

CF 2009C - The Legend of Freya the Frog

Codeforces 2009C: The Legend of Freya the Frog