codeforces-scrape

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

2108C.md (3134B)


      1 Source: https://codeforces.com/problemset/problem/2108/C
      2 
      3 C. Neo's Escape
      4 
      5 time limit per test
      6 
      7 2 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 Neo wants to escape from the Matrix. In front of him are $n$ buttons arranged in a row. Each button has a weight given by an integer: $a_1, a_2, \ldots, a_n$.
     22 
     23 Neo is immobilized, but he can create and move clones. This means he can perform an unlimited number of actions of the following two types in any order:
     24 
     25 1. Create a clone in front of a specific button.
     26 2. Move an existing clone one position to the left or right.
     27 
     28 As soon as a clone is in front of another button that has not yet been pressed—regardless of whether he was created or moved — he immediately presses it. If the button has already been pressed, a clone does nothing — buttons can only be pressed once.
     29 
     30 For Neo to escape, he needs to press all the buttons in such an order that the sequence of their weights is non-increasing — that is, if $b_1, b_2, \ldots, b_n$ are the weights of the buttons in the order they are pressed, then it must hold that $b_1 \geq b_2 \geq \cdots \geq b_n$.
     31 
     32 Your task is to determine the minimum number of clones that Neo needs to create in order to press all the buttons in a valid order.
     33 
     34 Input
     35 
     36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     37 
     38 The first line of each test case contains one integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of buttons.
     39 
     40 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the weights of the buttons.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, output one integer — the minimum number of clones that need to be created to press all the buttons in a valid order.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 4
     54 
     55 5
     56 
     57 4 3 2 1 5
     58 
     59 3
     60 
     61 1 1 1
     62 
     63 6
     64 
     65 7 8 1 5 9 2
     66 
     67 10
     68 
     69 1 7 9 7 1 10 2 10 10 7
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 2
     76 1
     77 2
     78 3
     79 ```
     80 
     81 Note
     82 
     83 In the first test case, Neo can act as follows:
     84 
     85 1. Create a clone in front of the fifth button (with weight $5$).
     86 2. Create a clone in front of the first button (with weight $4$).
     87 3. Move the second clone from the first button to the second (with weight $3$).
     88 4. Move the second clone from the second button to the third (with weight $2$).
     89 5. Move the first clone from the fifth button to the fourth (with weight $1$).
     90 
     91 Thus, the sequence of button presses will be $5 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 1$, which meets the requirement. It can be shown that the number of clones created is the smallest possible.
     92 
     93 In the second test case, Neo can act as follows:
     94 
     95 1. Create a clone in front of the second button (with weight $1$).
     96 2. Move the clone from the second button to the third (with weight $1$).
     97 3. Move the clone from the third button to the second (already pressed).
     98 4. Move the clone from the second button to the first (with weight $1$).
     99 
    100 Thus, the sequence of button presses will be $1 \rightarrow 1 \rightarrow 1$.