Codeforces Round 539 (Div. 1)

Solutions for Codeforces Round 539 (Div. 1) (contest 1109). 4/6 problems verified against sample I/O. Difficulty range: 1600-3200.

6 items

Codeforces Round 539 (Div. 1)

Type: Div. 1 | Problems: 6 | Verified: 4/6 | Rating range: 1600-3200 | Time: 12m 1s

Problem	Name	Rating	Tags	Solve Time	Verified
A	Sasha and a Bit of Relax	1600	dp, implementation	1m 10s	✓
B	Sasha and One More Name	1800	constructive-algorithms, hashing, strings	1m 13s	✓
C	Sasha and a Patient Friend	2800	binary-search, data-structures, implementation	5m 14s	✗
D	Sasha and Interesting Fact from Graph Theory	2400	brute-force, combinatorics, dp	1m 43s	✗
E	Sasha and a Very Easy Test	2700	data-structures, number-theory	1m 21s	✓
F	Sasha and Algorithm of Silence's Sounds	3200	data-structures, trees	1m 20s	✓

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

CF 1109C - Sasha and a Patient Friend

The problem models a “patience bowl” which has an initial amount of patience that can grow or shrink over time depending on the tap’s speed. The tap’s speed can be changed at discrete times by events.

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

CF 1109F - Sasha and Algorithm of Silence's Sounds

We are given an $n times m$ grid where every cell contains a unique value from $1$ to $nm$. These values impose a global order on the cells, and we should think of the grid as being revealed gradually: first the cell with value 1 appears, then 2, and so on.

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

CF 1109D - Sasha and Interesting Fact from Graph Theory

We are asked to count how many different weighted trees can be built on $n$ labeled vertices when every edge weight is an integer between $1$ and $m$, under a single global constraint involving two distinguished vertices $a$ and $b$.

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

CF 1109E - Sasha and a Very Easy Test

We are maintaining an array of integers that is repeatedly modified and queried. The array starts fixed, but over time we apply operations that either scale a contiguous segment, shrink a single element by dividing it, or ask for the sum over a segment.

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

CF 1109B - Sasha and One More Name

We are given a string that is already a palindrome, and our goal is to transform it into a different palindrome by cutting it into some number of contiguous pieces and then reordering these pieces. The task is to find the minimum number of cuts required to achieve this.

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

CF 1109A - Sasha and a Bit of Relax

We are asked to find "funny pairs" in an array of integers. A pair of indices $(l, r)$ is funny if the subarray from $l$ to $r$ has even length and the XOR of the first half equals the XOR of the second half.