PEG Judge - WC17 Finals - An Interspecific Army

Woburn Challenge 2017-18 Finals Round - Senior Division

Problem 1: An Interspecific Army

The Great Cow-Monkey War of 2017 has left Scarberia in a fragile and unstable state. Interspecies tension is at an all-time high, and both sides are working relentlessly to rebuild their economies, social systems, and militias. Little do the cows and monkeys know that amidst the turmoil, the world is at risk of being taken over by an even more dangerous foe — a group of aliens known as the Party of Extraterrestrial Gangsters (or PEG for short)! PEG has decided that it's the perfect time to divide and conquer Scarberia by exploiting its current internal hostilities. Fortunately, Bo Vine and the Head-Monkey have learned of the impending invasion in time, and an important realization has dawned on them: now is not the time to engage in petty quarrels with one another. All of Scarberia must unite, at least temporarily, to face an even greater evil. The animals have thus formed a truce, and started to plan for the upcoming war!

With an overall battle formation decided, the cows and monkeys are now ready to fight against the incoming alien invaders! …Well, almost. You see, the commanders realized that it is not too effective to simply line up large platoons of uniformly cows or uniformly monkeys. They must work together at a more local scale, with each cow and monkey taking immediate advantage of each others' strengths and weaknesses. As such, the commanders have decided to pair up cows and monkeys to form individual combat units on the battlefield.

Between the united armies, there are N cows and N monkeys (1 ≤ N ≤ 100,000). The i-th cow has a combat skill level of C_i (1 ≤ C_i ≤ 10⁶), while the i-th monkey has a combat skill level of M_i (1 ≤ M_i ≤ 10⁶). Each cow is to be paired up with a monkey to form a combat unit, such that there are N combat units total and each of the 2N animals is a part of exactly one unit.

A combat unit is most effective when the skill levels of its two members don't differ too greatly. More formally, we can define the combat skill differential of a given unit to be the absolute difference between the combat skill levels of the two animals making up that unit. For a given pairing of the 2N animals, let D denote the maximum combat skill differential across all N combat units. Bo Vine and the Head-Monkey would like to pair up the animals such that D ends up being as small as possible. Can you help them determine the minimum possible value of D which can be achieved?

Subtasks

In test cases worth 2/9 of the points, N ≤ 10 and 1 ≤ C_i, M_i ≤ 2 for each i.
In test cases worth another 2/9 of the points, N ≤ 1000 and 1 ≤ C_i, M_i ≤ 2 for each i.
In test cases worth another 4/9 of the points, N ≤ 1000.

Input Format

The first line of input consists of a single integer, N.
The second line consists of N space-separated integers, C₁, …, C_N.
The third line consists of N space-separated integers, M₁, …, M_N.