Zonal Computing Olympiad 2011, 4 Dec 2010
2:00 pm–5:00 pm IST
Problem 2 : Balancing Act
Your team is playing a chess tournament against a visiting team. Your opponents have arrived with a team of M players, numbered 1,2,…,M. You have N players, numbered 1,2,…,N from which to choose your team, where N ≥ M.
Each of the M players from the visiting team must be paired up with one of your N players. The tournament rules insist that the pairings must respect the order that has been fixed for both teams. That is, when you pick players i1, i2,…,iM, to play against opponents numbered 1,2,…,M, it must be the case that i1<i2<…<iM, in terms of the order 1,2,…,N in which your players are listed.
You want to ensure a good fight, so you plan to pick your team so that the teams are as evenly balanced as possible. Each player j on your team has a numerical score YS(j) that represents his or her playing ability. Likewise, each player i in the opponent team has a playing ability indicated by a numerical score OS(i). The difference in strength between a player ij from your team and his or her opponent j on the visiting team is the absolute value |YS(ij) - OS(j)|. The imbalance of a pairing is the sum of these differences across all M match-ups in the pairing. Your aim is to minimize this imbalance.
For instance suppose you have six players, whose strengths are as follows.
| Home Team | ||||||
| i | 1 | 2 | 3 | 4 | 5 | 6 | YS(i) | 2 | 3 | 4 | 1 | 5 | 7 |
Also, suppose that the visiting team has three players, whose strengths are as follows.
| Visiting Team | |||
| i | 1 | 2 | 3 | OS(i) | 2 | 9 | 2 |
In this situation, the most balanced pairing is (1,1), (3,2) and (4,3), which yields an imbalance of |YS(1)-OS(1)|+|YS(3)-OS(2)|+|YS(4)-OS(3)|= |2-2|+|4-9|+|1-2| = 6.
Your task is to read a description of the two teams and calculate the overall imbalance in the most balanced pairing.
Input format
The first line of input contains two integers N and M, N ≥ M, the number of players on the home team and the visiting team, respectively. The second line of input contains N positive integers, the strengths of the home team players in the order 1,2,…,N. The third line of input contains M integers, the strengths of the visiting team players in the order 1,2,…,M.
Output format
A single line with a single integer indicating the sum of the differences in strengths in the most balanced pairing.
Testdata
You may assume that 1 ≤ M ≤ N ≤ 2000. All players' strengths are in the range [1,2000].
Sample Input
6 3 2 3 4 1 5 7 2 9 2
Sample Output
6
Time and memory limits
The time limit for this task is 2 seconds. The memory limit is 64MB.
Copyright (c) IARCS 2003-2024; Last Updated: 28 Oct 2011