1839.md (1789B)
1 Source: https://codeforces.com/blog/entry/116963 2 3 [1839A - The Good Array](/contest/1839/problem/A "Codeforces Round 876 (Div. 2)") 4 5 **Hint** 6 7 The first and last elements are always equal to $1$. 8 9 **Hint** 10 11 There are at least $\lceil \frac{n - 1}{k} \rceil$ ones among the first $n - 1$ elements. 12 13 **Solution** 14 15 Tutorial is loading... 16 17 [1839B - Lamps](/contest/1839/problem/B "Codeforces Round 876 (Div. 2)") 18 19 **Hint** 20 21 Try to solve the problem if all $a_i$ are equal. 22 23 **Solution** 24 25 Tutorial is loading... 26 27 [1839C - Insert Zero and Invert Prefix](/contest/1839/problem/C "Codeforces Round 876 (Div. 2)") 28 29 **Hint** 30 31 After every operation, the last element of $b$ is equal to $0$. 32 33 **Hint** 34 35 If the last element of $a$ is $0$, then you can always achieve $b = a$ with some sequence of operations. 36 37 **Hint** 38 39 Try to solve the problem if $a$ consists of $k$ ones followed by single zero. 40 41 **Solution** 42 43 Tutorial is loading... 44 45 [1839D - Ball Sorting](/contest/1839/problem/D "Codeforces Round 876 (Div. 2)") 46 47 **Hint** 48 49 Consider the set of balls that were never moved by operations of type 2. 50 51 **Hint** 52 53 The relative order of these balls never changes, so their colors must form an increasing sequence. 54 55 **Solution** 56 57 Tutorial is loading... 58 59 [1839E - Decreasing Game](/contest/1839/problem/E "Codeforces Round 876 (Div. 2)") 60 61 **Hint** 62 63 Consider the graph with $n$ vertices $1, 2, \ldots, n$, and on each round of the game, connect vertices $i$ and $j$. What can you say about this graph? 64 65 **Hint** 66 67 This graph is a tree. 68 69 **Hint** 70 71 Vertices of a tree can be divided into two parts, such that all edges connect vertices from different parts. 72 73 **Hint** 74 75 If the second player won the game, then sums of elements in both parts were equal in initial array $a$. 76 77 **Solution** 78 79 Tutorial is loading...