Candies

Solutions This problem can be solved with a greedy approach. First of all, we distribute one candy to every child. Then we can iterate adjacent children from left to right: if one is higher than the other but has less chandies, we give her a candy more. Similarly, we do the same from right to left. Here is a C++ implementation: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int N; cin >> N; vector<int> v, candies; v. [Read More]
greedy 

Hotel Coverage

Solutions This problem falls into the greedy category. A hotel can accomodate all customers in a distance of \(-k\) and \(+k\). We should find the smallest amount of intervals of length \(2k\) that cover all the positions of the customers. First of all, we sort the positions of the customers. We iterate over all the sorted positions and, at each step, we calculate the difference between adjacent positions. We keep track of the interval by incrementing a running sum of the such differences. [Read More]