All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

Akatsuki vs Leaf
Tag(s):

Bitmask, Dynamic Programming, Easy-Medium, Matching

Problem
Editorial
Analytics

Akatsuki is planning to attack the Leaf Village to capture Naruto. The Hokage ( Head of the Village ), came to know about the plan and also the number of members, $$N$$, in Akatsuki who are going to attack. So, Hokage planned an ambush.

enter image description here

Hokage selected a team of $$N$$ members ( one for each Akatsuki member ) and named it Leaf. Each member of Leaf can attack exactly one Akatsuki member and an Akatsuki member is NOT attacked by more than one Leaf member. In the ambush there will be $$N$$ fights ( one of each $$N$$ members of Leaf and $$N$$ members of Akatsuki ). You are the leader of Leaf. You know the positions ( x-coordinates and y-coordinates ) of all the Akatsuki members and Leaf members. Your task is to assign each member of Leaf to exactly one member of Akatsuki team such that the sum of the distance between them is minimum. Distance between two points $$(x_1, y_1)$$ and $$(x_2, y_2)$$ will be equal to $$|x_1 - x_2| + |y_1 - y_2|$$.

Input:
First line contains one integer $$N$$, number of Akatsuki members who are going to attack the village.
Next $$N$$ lines will contain two integers each, $$X$$ and $$Y$$, x-coordinate and y-coordinate of the Akatsuki members.
Next $$N$$ lines will contain two integers each, $$X$$ and $$Y$$, x-coordinate and y-coordinate of the Leaf members.

Output:
Print the required minimum sum of the distance.

Constraints:
$$1 \le N \le 20$$
$$-10^6 \le X, Y \le 10^6$$

SAMPLE INPUT
2
0 0
8 8
1 1
6 6
SAMPLE OUTPUT
6
Explanation

$$N = 2$$
So there are 2 Akatsuki members at position $$(0, 0)$$ and $$(8, 8)$$ and 2 Leaf members at position $$(1, 1)$$ and $$(6, 6)$$. There are 2 cases:
Case 1:
Leaf member at $$(1, 1)$$ will fight Akatsuki member at $$(0, 0)$$ and Leaf member at $$(6, 6)$$ will fight Akatsuki member at $$(8, 8)$$.
Sum of distances = $$((|1-0| + |1-0|) + (|6-8| + |6-8|)) = (2 + 4) = 6$$

Case 2:
Leaf member at $$(1, 1)$$ will fight Akatsuki member at $$(8, 8)$$ and Leaf member at $$(6, 6)$$ will fight Akatsuki member at $$(0, 0)$$.
Sum of distances = $$((|1-8| + |1-8|) + (|6-0| + |6-0|)) = (14 + 12) = 26$$

So Case 1 is optimal and minimum sum of distances is 6.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

June Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications