#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]

Solutions A brute force solution to this problem involves checking every possible pair of numbers in the array and calculating their product. To do this, we use two nested loops: the outer loop selects the first number, and the inner loop selects the second number, which comes after the first. For each pair, we compute the product and check if it exceeds the current maximum product found. This approach guarantees finding the pair with the highest product, but it is inefficient because it examines all pairs, resulting in a quadratic time complexity. [Read More]