The Cleveland Pothole Problem Brick roads evidently not being bumpy enough, Litt
ID: 3741710 • Letter: T
Question
The Cleveland Pothole Problem Brick roads evidently not being bumpy enough, Little Italy’s Mayfield Road has recently developed several potholes. The potholes this year are very bizarre – they are zero-dimensional points which send cars passing over them to a place nobody 1 knows. 1 Unfortunately, the city does not have enough money to hire construction workers, but fortunately, the city does have an enormous reserve supply of 24’x24’ 2 metal covering plates to prevent cars from entering the underworld. Suppose that you are given an array of the positions of these potholes 3 {s1, ...sn} where each si represents the distance along the road from the intersection of Euclid and Mayfield to a pothole. Give an algorithm which returns the minimum number of metal plates required to cover all potholes, and prove its correctness. (**)
Explanation / Answer
Problem statement: Identify the minimum number of metal plates required to cover all potholes
Given:
1. The city does not have enough money to hire construction workers, but fortunately, the city does have an enormous reserve supply of 24’x24’
2. Metal covering plates to prevent cars from entering the underworld
3. an array of the positions of these potholes, {s1, ...sn} where each si represents the distance along the road from the intersection of Euclid and Mayfield to a pothole
Algorithm:
1. For each si in array {s1, ...sn}
2. Calculate the size of the pothole, which is width of the array - si
3. If the size < 24 x 24, then, check the next nearest pothole and calculate its size.
4. Repeat step 1, till the sum of size of the potholes in less than or equal to 24x24
5. Add a metal plate for covering 24 x 24 size of holes
6. Check the size and add the number of metal plate to cover a hole bigger than 24 x 24
7 Return the number of metal plates used