codeforces-scrape

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

1515D.md (2365B)


      1 Source: https://codeforces.com/problemset/problem/1515/D
      2 
      3 D. Phoenix and Socks
      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 To satisfy his love of matching socks, Phoenix has brought his $n$ socks ($n$ is even) to the sock store. Each of his socks has a color $c_i$ and is either a left sock or right sock.
     22 
     23 Phoenix can pay one dollar to the sock store to either:
     24 
     25 * recolor a sock to any color $c'$ $(1 \le c' \le n)$
     26 * turn a left sock into a right sock
     27 * turn a right sock into a left sock
     28 
     29 The sock store may perform each of these changes any number of times. Note that the color of a left sock doesn't change when it turns into a right sock, and vice versa.
     30 
     31 A matching pair of socks is a left and right sock with the same color. What is the minimum cost for Phoenix to make $n/2$ matching pairs? Each sock must be included in exactly one matching pair.
     32 
     33 Input
     34 
     35 The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     36 
     37 The first line of each test case contains three integers $n$, $l$, and $r$ ($2 \le n \le 2 \cdot 10^5$; $n$ is even; $0 \le l, r \le n$; $l+r=n$) — the total number of socks, and the number of left and right socks, respectively.
     38 
     39 The next line contains $n$ integers $c_i$ ($1 \le c_i \le n$) — the colors of the socks. The first $l$ socks are left socks, while the next $r$ socks are right socks.
     40 
     41 It is guaranteed that the sum of $n$ across all the test cases will not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, print one integer — the minimum cost for Phoenix to make $n/2$ matching pairs. Each sock must be included in exactly one matching pair.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 4
     53 6 3 3
     54 1 2 3 2 2 2
     55 6 2 4
     56 1 1 2 2 2 2
     57 6 5 1
     58 6 5 4 3 2 1
     59 4 0 4
     60 4 4 4 3
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 2
     67 3
     68 5
     69 3
     70 ```
     71 
     72 Note
     73 
     74 In the first test case, Phoenix can pay $2$ dollars to:
     75 
     76 * recolor sock $1$ to color $2$
     77 * recolor sock $3$ to color $2$
     78 
     79 There are now $3$ matching pairs. For example, pairs $(1, 4)$, $(2, 5)$, and $(3, 6)$ are matching.
     80 
     81 In the second test case, Phoenix can pay $3$ dollars to:
     82 
     83 * turn sock $6$ from a right sock to a left sock
     84 * recolor sock $3$ to color $1$
     85 * recolor sock $4$ to color $1$
     86 
     87 There are now $3$ matching pairs. For example, pairs $(1, 3)$, $(2, 4)$, and $(5, 6)$ are matching.