It's raining outside
Practice
4 (4 votes)
Dynamic programming
Algorithms
3 dimensional
Hard
Problem
10% Success 370 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code

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.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
60 votes
Tags:
Dynamic ProgrammingCombinatoricsHardNumber TheoryBrute-force searchOpenApproved
Points:50
2 votes
Tags:
AlgorithmsDynamic ProgrammingOpenApprovedHard
Points:50
4 votes
Tags:
String3D dynamic programmingDynamic ProgrammingAlgorithms