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 N2 pairs of numbers and compare the absolute value of their differences, and print the minimum.

Time Complexity: O(N2)

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=S1,S2,,SN be the sorted array. The minimum difference between Si and any number is min(SiSi1,Si+1Si). For the sake of contradiction, assume there exists some Sj, ji, such that |SiSj|<min(SiSi1,Si+1Si) Thus we have two cases:

Case 1: j<i1

This implies that SiSj<SiSi1.

S is sorted, SjSi1.

Sj=Si1x, for x0.

Substituting, this gives Si(Si1x)<SiSi1, which gives:

(SiSi1)+x<SiSi1 x<0

x0, this is a contradiction.

Case 2: j>i+1

This implies that SjSi<Si+1Si.

S is sorted, SjSi+1.

Sj=Si+1+x, for x0.

Substituting, this gives (Si+1+x)Si<Si+1Si, which gives:

(Si+1Si)+x<Si+1Si x<0

x0, this is a contradiction.

we have proven that Sj does not exist.

Time Complexity: O(NlogN)


Comments

There are no comments at the moment.