codeforces-scrape

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

2106C.md (2439B)


      1 Source: https://codeforces.com/problemset/problem/2106/C
      2 
      3 C. Cherry Bomb
      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 Two integer arrays $a$ and $b$ of size $n$ are complementary if there exists an integer $x$ such that $a_i + b_i = x$ over all $1 \le i \le n$. For example, the arrays $a = [2, 1, 4]$ and $b = [3, 4, 1]$ are complementary, since $a_i + b_i = 5$ over all $1 \le i \le 3$. However, the arrays $a = [1, 3]$ and $b = [2, 1]$ are not complementary.
     22 
     23 Cow the Nerd thinks everybody is interested in math, so he gave Cherry Bomb two integer arrays $a$ and $b$. It is known that $a$ and $b$ both contain $n$ non-negative integers not greater than $k$.
     24 
     25 Unfortunately, Cherry Bomb has lost some elements in $b$. Lost elements in $b$ are denoted with $-1$. Help Cherry Bomb count the number of possible arrays $b$ such that:
     26 
     27 * $a$ and $b$ are complementary.
     28 * All lost elements are replaced with non-negative integers no more than $k$.
     29 
     30 Input
     31 
     32 The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     33 
     34 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le 10^9$) — the size of the arrays and the maximum possible value of their elements.
     35 
     36 The second line contains $n$ integers $a_1, a_2, ..., a_n$ ($0 \le a_i \le k$).
     37 
     38 The third line contains $n$ integers $b_1, b_2, ..., b_n$ ($-1 \le b_i \le k$). If $b_i = -1$, then this element is missing.
     39 
     40 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     41 
     42 Output
     43 
     44 Output exactly one integer, the number of ways Cherry Bomb can fill in the missing elements from $b$ such that $a$ and $b$ are complementary.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 7
     52 
     53 3 10
     54 
     55 1 3 2
     56 
     57 -1 -1 1
     58 
     59 5 1
     60 
     61 0 1 0 0 1
     62 
     63 -1 0 1 0 -1
     64 
     65 5 1
     66 
     67 0 1 0 0 1
     68 
     69 -1 1 -1 1 -1
     70 
     71 5 10
     72 
     73 1 3 2 5 4
     74 
     75 -1 -1 -1 -1 -1
     76 
     77 5 4
     78 
     79 1 3 2 1 3
     80 
     81 1 -1 -1 1 -1
     82 
     83 5 4
     84 
     85 1 3 2 1 3
     86 
     87 2 -1 -1 2 0
     88 
     89 5 5
     90 
     91 5 0 5 4 3
     92 
     93 5 -1 -1 -1 -1
     94 ```
     95 
     96 Output
     97 
     98 ```
     99 1
    100 0
    101 0
    102 7
    103 0
    104 1
    105 0
    106 ```
    107 
    108 Note
    109 
    110 In the first example, the only way to fill in the missing elements in $b$ such that $a$ and $b$ are complementary is if $b = [2, 0, 1]$.
    111 
    112 In the second example, there is no way to fill in the missing elements of $b$ such that $a$ and $b$ are complementary.
    113 
    114 In the fourth example, some $b$ arrays that are complementary to $a$ are: $[4, 2, 3, 0, 1], [7, 5, 6, 3, 4],$ and $[9, 7, 8, 5, 6]$.