USACO MAR07 Problem 'expense' Analysis

by by Kaan Soral, Onur Soral and Cihat Imamoglu from Turkey

Problem: On first impression, this might appear to be a set partitioning problem, which is NP-Complete. Fortunately, the fact that days cannot be swapped, i.e., have fixed positions, makes the problem easy. The solution turns out to be simple binary search on the values of 'monthly spending limit'.

Solution: Firstly, let's call the 'monthly spending limit' a 'value'.

For a given value X, we check if we can make an assignment (of the days to fajamonths) to spend X value at most, for every K fajamonths. This is greedy and very simple,

while total is not bigger than X, (total <= X)
     add as many days as possible to that month, and increase total
accordingly (greedy)
else total=0, start a new month (total months++)

If total months exceeds K limit, it's not possible with an X value to make arrangement, otherwise it's possible.

And the important points are:

• for X and Y values X>Y if it's possible to make an arrangement with a Y value, it's also possible to make it with an X value.
• for X and Y values X>Y if it's not possible to make an arrangement with X value, it's also not possible to make it with a Y value.

These properties make it possible for this problem to be solved by using binary search.

We start with A=0 and B=(the total of all day values) and binary search for the min Value.

Complexity: Checking for an X value if it's possible to make an arrangement takes O(N) time. Binary Search between 0 and MAXVAL is O(log(MAXVAL)). MAXVAL is approximately ~10,000*N~, call AV the average value of day values. The total complexity is: ~O(N*log(N*AV))~