codeforces-scrape

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

2170B.md (2197B)


      1 Source: https://codeforces.com/problemset/problem/2170/B
      2 
      3 B. Addition on a Segment
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You start with an integer array $a$, which initially consists of $n$ zeros. You have to perform the following action exactly $n$ times:
     22 
     23 * choose two integers $l$ and $r$ ($1 \le l \le r \le n$) and assign $a_{i} = a_{i} + 1$ for each $i$ such that $l \le i \le r$.
     24 
     25 You are given an array $b$, consisting of $n$ integers. Your task is to choose such values $l$ and $r$ for each action that:
     26 
     27 * after all $n$ actions are performed, it's possible to reorder the elements in such a way that $a$ becomes equal to $b$;
     28 * the maximum value of $r - l + 1$ over all actions is as large as possible.
     29 
     30 What's the maximum possible value of $r - l + 1$?
     31 
     32 Input
     33 
     34 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.
     35 
     36 The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^{5}$) — the length of the array $b$.
     37 
     38 The second line of each test case contains $n$ integers $b_{i}$ ($0 \le b_{i} \le n$) — the elements of the array $b$.
     39 
     40 Additional constraints on the input:
     41 
     42 * there exists at least one way to choose $l$ and $r$ for each action and reorder the elements at the end so that $a$ becomes equal to $b$;
     43 * the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, output one integer — the answer to the problem.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 3
     55 
     56 5
     57 
     58 0 5 1 0 1
     59 
     60 3
     61 
     62 3 2 1
     63 
     64 5
     65 
     66 1 1 1 1 1
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 3
     73 
     74 3
     75 
     76 1
     77 ```
     78 
     79 Note
     80 
     81 Consider the first test case. If the $n$ actions were as follows:
     82 
     83 * $l = 3$ and $r = 3$
     84 * $l = 1$ and $r = 3$
     85 * $l = 3$ and $r = 3$
     86 * $l = 3$ and $r = 3$
     87 * $l = 3$ and $r = 3$
     88 
     89 The array $a = [1, 1, 5, 0, 0]$, so you can reorder the elements to make it equal to $[0, 5, 1, 0, 1]$. As can be seen in this case, the maximum value of $r - l + 1$ is $3$. It can be shown that this is the optimal answer.
     90 
     91 In the second test case:
     92 
     93 * $l = 1$ and $r = 3$
     94 * $l = 2$ and $r = 3$
     95 * $l = 3$ and $r = 3$
     96 
     97 The answer is $3$.