Editorial for COCI '15 Contest 6 #5 Krumpirko
Submitting an official solution before solving the problem yourself is a bannable offence.
The solution worth of points is trivial and implements precisely what is required in the task: from all possible choices of divisions of potato bags in the stores, which is , choose the one with the minimal product of average prices where at least one half is of size . The complexity of this solution is . Let's now try to solve the task for all points.
Let's denote the total price of the potatoes in the first store as and the total number of potatoes as , and analogously in the second store as and , the product of the average prices is equal to . Given the fact that the sum of prices and the sum of the number of potatoes is constant, we can modify this expression as . If we fix the parameter , we can notice that this expression is minimal when is minimal as well. Now our task is to find the minimal for each such that the first store contains exactly or bags of potatoes. The minimal such is found using dynamic programming. Let be the smallest price when choosing exactly bags of potatoes out of the first bags of potatoes so that the chosen bags contain exactly potatoes. The relation in this dynamic is left as an exercise to the reader. The total complexity of the solution is .
Comments