Problem Link:
Difficulty:
Cakewalk
Pre-requisites:
Ad Hoc
Problem:
Given N sticks of lengths L[1], L[2], … L[N] and a positive integer D.
Two sticks can be paired if the difference of their lengths is at most D.
Pair up as many sticks as possible such that each stick is used at most once.
Quick Explanation:
Sort the sticks by their lengths and let L be the sorted array.
If L[1] and L[2] cannot be paired, then the stick L[1] is useless.
Otherwise, there exists an optimal pairing where L[1] gets paired with L[2].
This gives rise to the following algorithm:
numpairs = 0
for ( i = 1; i < N; )
if (L[i] >= L[i+1] -D) // L[1] and L[2] can be paired
numpairs++, // pair them up
i += 2;
else
i++; // eliminate L[1]
Justifications:
-
If L[1] and L[2] cannot be paired then
L[1] < L[2] - D
But, L[2] <= L[i] for every i > 1
So L[1] < L[i] - D for every i > 1
Hence, L[1] cannot be paired with anyone. -
If L[1] and L[2] can be paired.
Consider any optimal pairing and it can be transformed to a pairing where L[1] and L[2] are paired.
a) If the optimal pairing pairs L[1] with L[2] then we are done.
b) If only one of L[1] and L[2] is paired with someone, then we can replace that pair by (L[1], L[2]).
c) If both L[1] and L[2] are paired and L[1] is paired with L[n] and L[2] with L[m], then we might as well form pairs (L[1], L[2]) and (L[n], L[m]).
This is because
L[2] <= L[m] <= L[2] + D
L[2] <= L[n] <= L[1] + D <= L[2] + D
⇒ -D <= L[m] - L[n] <= D
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here