CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)

Solutions for CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) (contest 1942). 4/9 problems verified against sample I/O. Difficulty range: 800-3500.

9 items

CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)

Type: Div. 1+2 | Problems: 9 | Verified: 4/9 | Rating range: 800-3500 | Time: 16m 46s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Farmer John's Challenge	800	constructive-algorithms, math	1m 37s	✗
B	Bessie and MEX	1100	constructive-algorithms, math	1m 18s	✗
C1	Bessie's Birthday Cake (Easy Version)	1300	geometry, greedy, math	56s	✓
C2	Bessie's Birthday Cake (Hard Version)	1700	geometry, greedy, math	2m 8s	✗
D	Learning to Paint	2100	binary-search, data-structures, dfs-and-similar	1m 30s	✗
E	Farm Game	2300	combinatorics, games	1m 56s	✓
F	Farmer John's Favorite Function	2700	brute-force, data-structures, implementation	2m 10s	✓
G	Bessie and Cards	2800	combinatorics, dp, math	3m 51s	✓
H	Farmer John's Favorite Intern	3500	data-structures, dp, flows	1m 20s	✗

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942A - Farmer John's Challenge

We need to construct an array of length n such that exactly k of its cyclic shifts are sorted in nondecreasing order. A cyclic shift chooses some position as the new beginning of the array and wraps the remaining elements around.

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942B - Bessie and MEX

We are given an array a of length n, constructed from some unknown permutation p of the integers 0 through n-1. Each element of a satisfies the relation a[i] = MEX(p[1..i]) - p[i]. The task is to reconstruct any valid permutation p that produces this a.

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942C1 - Bessie's Birthday Cake (Easy Version)

We are given a regular polygon with $n$ vertices representing a cake. Some vertices are already selected by Bessie as potential endpoints for drawing diagonals.

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942C2 - Bessie's Birthday Cake (Hard Version)

We have a regular polygon with n vertices arranged on a circle. Some x vertices are already available for use. We may additionally choose at most y more vertices.

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942D - Learning to Paint

We are asked to help Elsie evaluate her paintings on a 1D canvas of n cells. Each cell can be painted or left empty, and the painting's beauty is determined by a 2D array a.

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942E - Farm Game

The cows of the two farmers must appear in alternating order on the line. Once the order of the first cow is chosen, the entire sequence is fixed: either J N J N ... J N or N J N J ... N J. The actual positions are not fixed.

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942F - Farmer John's Favorite Function

We have an array $a$, and a recursively defined value: $$f(1)=sqrt{a1}, qquad f(i)=sqrt{f(i-1)+ai}.$$ After every point update $ak leftarrow x$, we need the integer part of $f(n)$. The first obstacle is that the recurrence uses real numbers.

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942G - Bessie and Cards

The deck contains four kinds of cards. A draw-0 card consumes one playable card from your hand and gives nothing back. A draw-1 card replaces itself. A draw-2 card consumes one card and gives two new cards, so it increases your future drawing power by one.

Practice › Codeforces Solutions › CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) ›

CF 1942H - Farmer John's Favorite Intern

We are asked to maintain a rooted tree where each node starts with zero peaches. Two kinds of operations can happen. In a growth operation at node $x$, we can increase the number of peaches on the parent of $x$ or any node in the subtree of $x$.