Editorial for DMPG '17 S1 - Molly and Difference


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

Subtask 1

For the 40\% subtask, it is possible to iterate over all N^2 pairs of numbers and compare the absolute value of their differences, and print the minimum.

Time Complexity: \mathcal O(N^2)

Subtask 2

For the 60\% subtask, a greedy approach can be used. Sort all the elements, and iterate through each pair of adjacent numbers in the sorted array, and print the minimum absolute value of their difference.

Proof of greedy algorithm:

Let the array S = S_1, S_2, \dots, S_N be the sorted array. The minimum difference between S_i and any number is \min(S_i - S_{i-1}, S_{i+1} - S_i). For the sake of contradiction, assume there exists some S_j, j \ne i, such that |S_i - S_j| < \min(S_i - S_{i-1}, S_{i+1} - S_i) Thus we have two cases:

Case 1: j < i-1

This implies that S_i - S_j < S_i - S_{i-1}.

\because S is sorted, S_j \le S_{i-1}.

\therefore S_j = S_{i-1} - x, for x \ge 0.

Substituting, this gives S_i - (S_{i-1} - x) < S_i - S_{i-1}, which gives:

\displaystyle (S_i - S_{i-1}) + x < S_i - S_{i-1} \displaystyle x < 0

\because x \ge 0, this is a contradiction.

Case 2: j > i+1

This implies that S_j - S_i < S_{i+1} - S_i.

\because S is sorted, S_j \ge S_{i+1}.

\therefore S_j = S_{i+1} + x, for x \ge 0.

Substituting, this gives (S_{i+1} + x) - S_i < S_{i+1} - S_i, which gives:

\displaystyle (S_{i+1} - S_i) + x < S_{i+1} - S_i \displaystyle x < 0

\because x \ge 0, this is a contradiction.

\therefore we have proven that S_j does not exist.

Time Complexity: \mathcal O(N \log N)


Comments

There are no comments at the moment.