TSECJ106 - Editorial

PROBLEM LINK:

Contest

Author: TSEC CodeCell

DIFFICULTY:

Easy

PROBLEM:

Given a collection of N rods of different lengths L, find the minimum cost to buy all rods if it costs one unit to buy all rods in the range [L,L+6].

EXPLANATION:

Sort rods in a non decreasing order based on length and then iterate through them. Increase cost by one for each rod encountered with length L and then skip any rods with lengths in the range [L,L+6]. The solution employs a simple greedy strategy. If a rod is present of length L, we can immediately skip all rods in the range [L,L+6] and increase cost by only one. Using this technique we can find the optimal cost in O(n) time.

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.

please move all your problems to practice arena,@admin @tseccodecell