DCOWS - Dancing Cows


It's the spring dance and, in a rare occurrence, the N (1 ≤ N ≤ 5000) bulls have been invited to dance with the M (N < M ≤ 5000) cows (as long as they stay on their very best behavior).

Farmer John, almost obsessive-compulsive in his organization of dances, wants the spectacle to be as visually attractive as possible. Thus, he wants to pair up the N bulls with cow partners such that the total of all the magnitudes of differences in height is minimized. Bulls have heights B_i (1 ≤ B_i ≤ 1,000,000) and cows have height C_i (1 ≤ C_i ≤ 1,000,000). Of course, some cows will be unmatched since N-M of them will have no partners; ignore their heights.

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M.
* Lines 2..N+1: Line i+1 contains a single integer: B_i.
* Lines N+2..M+N+1: Line i+N+1 contains a single integer: C_i.

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum of the sum of the absolute value of the height differences that can be achieved.

SAMPLE INPUT :

5 7
10
16
12
10
13
7
17
12
10
9
6
11

SAMPLE OUTPUT :

4

INPUT DETAILS:

Five bulls + seven cows with various heights:
   Bulls:   10 10 12 13 16
   Cows:    6 7 9 10 11 12 17

OUTPUT DETAILS :

Here is one way to achieve a total difference of 4:
   Bulls:        10 10 12 13 16
   Cows:    6 7   9 10 11 12 17


hide comments
sahil_1994: 2017-09-21 14:38:10

Do you have to consider the case N>M ?

kshubham02: 2017-08-30 09:10:20

@awesome_me the possible answer can be as large as 5000*10^6, so make sure your limiting variable is at least that big.

shubham8_: 2017-06-23 12:03:23

Those getting wa also check for the case when n = m :)

j_nash: 2017-06-02 21:29:58

make sure you are taking min variable long enough to handle all values in dp array(hint for those who are getting WA on test case 15)

Last edit: 2017-06-02 21:56:11
Sigma Kappa: 2017-05-28 22:39:42

Somehow my assert (m > n) failed, but never mind, got Accepted with O(n^2). Does not look like Gold problem at all, hmm...

deepak_bulani1: 2017-03-27 08:55:05

take dp array as long long int!!

samyak3: 2016-12-08 17:15:51

@theph0enix : Greedy approach will not work when a bull has two choices of pairing with same height difference on different sides. i.e a Bull of height H has a choice to pair with two cows of height H-d and H+d . You will never know which choice will give you optimal solution.

theph0enix: 2016-07-19 10:18:25

Why doesn't the greedy approach work here?

awesome_me: 2016-07-14 14:27:38

getting wrong ans after or on case 15. Tried using long and scanf and without scanf as well. Simple O(m*n) approach. Somebody please help.

avs_ashutosh: 2016-05-27 08:26:26

do not use scanf .WA


Added by:Se7s
Date:2013-05-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ADA95 ASM32 ASM64 GAWK BASH BF CLPS CLOJURE LISP clisp LISP sbcl D ERL FSHARP GO ICON ICK LUA NEM NICE NODEJS OCAML PERL6 PIKE PRLG-swi SCALA SCM guile SCM qobi SED ST TCL WHITESPACE
Resource:USACO 2008 Gold