codeforces-scrape

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

1883G1.md (2390B)


      1 Source: https://codeforces.com/problemset/problem/1883/G1
      2 
      3 G1. Dances (Easy version)
      4 
      5 time limit per test
      6 
      7 3 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 This is the easy version of the problem. The only difference is that in this version $m = 1$.
     22 
     23 You are given two arrays of integers $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$. Before applying any operations, you can reorder the elements of each array as you wish. Then, in one operation, you will perform both of the following actions, if the arrays are not empty:
     24 
     25 * Choose any element from array $a$ and remove it (all remaining elements are shifted to a new array $a$),
     26 * Choose any element from array $b$ and remove it (all remaining elements are shifted to a new array $b$).
     27 
     28 Let $k$ be the final size of both arrays. You need to find the minimum number of operations required to satisfy $a_i \lt b_i$ for all $1 \leq i \leq k$.
     29 
     30 This problem was too easy, so the problem author decided to make it more challenging. You are also given a positive integer $m$. Now, you need to find the sum of answers to the problem for $m$ pairs of arrays $(c[i], b)$, where $1 \leq i \leq m$. Array $c[i]$ is obtained from $a$ as follows:
     31 
     32 * $c[i]_1 = i$,
     33 * $c[i]_j = a_j$, for $2 \leq j \leq n$.
     34 
     35 Input
     36 
     37 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) - the number of sets of input data. This is followed by their description.
     38 
     39 The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 10^5$, $m = 1$) - the size of arrays $a$ and $b$ and the constraints on the value of element $a_1$.
     40 
     41 The second line of each test case contains $n - 1$ integers $a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$).
     42 
     43 The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq 10^9$).
     44 
     45 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     46 
     47 Output
     48 
     49 For each test case, output the total number of minimum operations for all pairs of arrays $(c_i, b)$.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 4
     57 
     58 2 1
     59 
     60 1
     61 
     62 3 2
     63 
     64 4 1
     65 
     66 5 1 5
     67 
     68 3 8 3 3
     69 
     70 8 1
     71 
     72 4 3 3 2 2 1 1
     73 
     74 1 1 1 1 3 3 3 3
     75 
     76 9 1
     77 
     78 9 2 8 3 7 4 6 5
     79 
     80 1 2 3 2 1 4 5 6 5
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 0
     87 1
     88 4
     89 4
     90 ```
     91 
     92 Note
     93 
     94 In the first test case for the pair of arrays $([1, 1], [3, 2])$, the answer is $0$. No operations or reordering of elements are needed.