It's raining outside

4

4 votes
Dynamic Programming, Algorithms, 3 Dimensional, Hard
Problem

Problem statement:
A bunch of friends after watching a game of football were driven to play a game themselves. Unfortunately, it was raining outside and they had to settle for an indoor sport - LUDO. Considering the traditional ludo board as trivial they decided to play on an infinite linear ludo board in which two players (say A and B) can play at a time. The rules of the game are simple.Initially, N tokens of player A and M tokens of players B are placed on the board according to B's wishes. It is not allowed to place two tokens (of any player)at the same position initially. Now only A will make moves, and in one move he can choose any one of his tokens and place it to its right adjacent or its left adjacent cell.One token of B gets removed when a token of A steps on the same cell. A has to remove all tokens of B as soon as possible. Help A in finding the minimum number of steps in which he can do so.

Constraints:
1<= T <= 1000
1<= N,M <= 1000
-1000000000 <= positions of tokens <= 1000000000

Input:
line1: Number of test cases T.
Each test case contains lines 2,3,4
line2: N and M.
line3: N-space separated integers denoting positions of tokens of A.
line4: M space separated integers denoting positions of tokens of B.
Output:
Print one line for each test case: The minimum number of moves required by A to remove all tokens of B.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

If every token of A removes its closest B-token, then in 54 moves all tokens of B will be removed. This answer cannot be improved as can be easily observed.

Editor Image

?