codeforces-scrape

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

1168A.md (1685B)


      1 Source: https://codeforces.com/problemset/problem/1168/A
      2 
      3 A. Increasing by Modulo
      4 
      5 time limit per test
      6 
      7 2.5 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Toad Zitz has an array of integers, each integer is between $0$ and $m-1$ inclusive. The integers are $a_1, a_2, \ldots, a_n$.
     22 
     23 In one operation Zitz can choose an integer $k$ and $k$ indices $i_1, i_2, \ldots, i_k$ such that $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n$. He should then change $a_{i_j}$ to $((a_{i_j}+1) \bmod m)$ for each chosen integer $i_j$. The integer $m$ is fixed for all operations and indices.
     24 
     25 Here $x \bmod y$ denotes the remainder of the division of $x$ by $y$.
     26 
     27 Zitz wants to make his array non-decreasing with the minimum number of such operations. Find this minimum number of operations.
     28 
     29 Input
     30 
     31 The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 300\,000$) — the number of integers in the array and the parameter $m$.
     32 
     33 The next line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \lt m$) — the given array.
     34 
     35 Output
     36 
     37 Output one integer: the minimum number of described operations Zitz needs to make his array non-decreasing. If no operations required, print $0$.
     38 
     39 It is easy to see that with enough operations Zitz can always make his array non-decreasing.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 5 3
     47 0 0 0 1 2
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 0
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 5 7
     60 0 6 1 3 2
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 1
     67 ```
     68 
     69 Note
     70 
     71 In the first example, the array is already non-decreasing, so the answer is $0$.
     72 
     73 In the second example, you can choose $k=2$, $i_1 = 2$, $i_2 = 5$, the array becomes $[0,0,1,3,3]$. It is non-decreasing, so the answer is $1$.