codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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...