codeforces-scrape

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

1038C.md (2678B)


      1 Source: https://codeforces.com/problemset/problem/1038/C
      2 
      3 C. Gambling
      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 players A and B have a list of $n$ integers each. They both want to maximize the subtraction between their score and their opponent's score.
     22 
     23 In one turn, a player can either add to his score any element from his list (assuming his list is not empty), the element is removed from the list afterward. Or remove an element from his opponent's list (assuming his opponent's list is not empty).
     24 
     25 Note, that in case there are equal elements in the list only one of them will be affected in the operations above. For example, if there are elements $\{1, 2, 2, 3\}$ in a list and you decided to choose $2$ for the next turn, only a single instance of $2$ will be deleted (and added to the score, if necessary).
     26 
     27 The player A starts the game and the game stops when both lists are empty. Find the difference between A's score and B's score at the end of the game, if both of the players are playing optimally.
     28 
     29 Optimal play between two players means that both players choose the best possible strategy to achieve the best possible outcome for themselves. In this problem, it means that each player, each time makes a move, which maximizes the final difference between his score and his opponent's score, knowing that the opponent is doing the same.
     30 
     31 Input
     32 
     33 The first line of input contains an integer $n$ ($1 \le n \le 100\,000$) — the sizes of the list.
     34 
     35 The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^6$), describing the list of the player A, who starts the game.
     36 
     37 The third line contains $n$ integers $b_i$ ($1 \le b_i \le 10^6$), describing the list of the player B.
     38 
     39 Output
     40 
     41 Output the difference between A's score and B's score ($A-B$) if both of them are playing optimally.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 2  
     49 1 4  
     50 5 1
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 0
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 3  
     63 100 100 100  
     64 100 100 100
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 0
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 2  
     77 2 1  
     78 5 6
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 -3
     85 ```
     86 
     87 Note
     88 
     89 In the first example, the game could have gone as follows:
     90 
     91 * A removes $5$ from B's list.
     92 * B removes $4$ from A's list.
     93 * A takes his $1$.
     94 * B takes his $1$.
     95 
     96 Hence, A's score is $1$, B's score is $1$ and difference is $0$.
     97 
     98 There is also another optimal way of playing:
     99 
    100 * A removes $5$ from B's list.
    101 * B removes $4$ from A's list.
    102 * A removes $1$ from B's list.
    103 * B removes $1$ from A's list.
    104 
    105 The difference in the scores is still $0$.
    106 
    107 In the second example, irrespective of the moves the players make, they will end up with the same number of numbers added to their score, so the difference will be $0$.