#greedy

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]

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]

Solutions This problem simulates the situation when you need some additional “domain knowledge” to find a solution. In this case the domain is “geometry” and you have to find (or recall) the Triangle inequality: for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side In other terms, for any three sticks \(a, b, c\), the following must be true: [Read More]