spoj 8132. Street Trees | STREETR

problem statement can be found here

this is really a cool problem. the problem asks us to find find the minimum number of terms(integers) to add to the set of sorted integers in order to obtain an Arithmetic Progression.

let d be the difference of the arithmetic progression.

as we know that Pi – Pi-1 is k*d so any common factor for all the differences between the given adjacent terms can be our d, but since we have to add minimum number of terms d should be as large as possible so the common factor…

once we obtain the d it is easy to find the number of missing terms..



Randomized Selection Algorithm

the key idea is to use the quicksort partitioning scheme in which we reduce our selection problem size into half(just the expectation).

T(n) = O(n) + T(n // 2)

the resulting algrithm is a O(n) algo…
if anyone faced a problem similar to RMID2 but having very less queries but large data stream then it is better to use the randomized selection’s O(1) insertion and O(n) query rather than two priority queue method’s O(log(n)) insertion and O(log(n)) query..

here’s my implementation..