COCI '18 Contest 1 #3 Cipele

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type

After spending most of his money on various projects, Nadan decided to afford high quality shoes for his software developers. Luckily for Nadan, he found N left shoes and M right shoes in his basement. Since their origin is unknown, the shoes come in various sizes.

Nadan asked you to pair as many shoes as possible (it's important that a new pair cannot be selected after pairing all the shoes). Each pair should consist of one left shoe and one right shoe. While pairing the shoes, you should make sure that the ugliness is minimized. The ugliness of one pairing is defined as the maximal absolute difference of the shoe sizes between all pairs of shoes.

Input Specification

The first line contains two positive integers N and M (1 \le N, M \le 100\,000), the number of left shoes and right shoes, in that order.

The second line contains N numbers L_i (1 \le L_i \le 10^9), the sizes of the left shoes.

The third line contains M numbers R_i (1 \le R_i \le 10^9), the sizes of the right shoes.

Output Specification

Output the minimal ugliness between all possible shoe pairings.


In test cases worth 20\% of the total points, it will hold that N = M.

In test cases worth an additional 50\% of the total points, it will hold that N, M \le 5\,000.

Sample Input 1

2 3
2 3
1 2 3

Sample Output 1


Sample Input 2

4 3
2 39 41 45
39 42 46

Sample Output 2


Explanation of Sample Output 2

Nadan has 4 left and 3 right shoes, the maximal number of pairs that can be obtained is 3. One possible pairing is:

39-46, 41-42, 45-39, but the ugliness of such pairing is 7 because of the first pair.

A better pairing would be:

39-39, 41-42, 45-46, with ugliness being equal to 1, which is minimal possible ugliness that can be obtained.

Sample Input 3

5 5
7 6 1 2 10
9 11 6 3 12

Sample Output 3



There are no comments at the moment.