power-scheduling

Power Scheduling

Contest: Cloudflight Coding Contest - October 2020 (33rd CCC) Language: C++17

Problem

You operate an electricity grid. Each minute t in [0, N) has a known price. M tasks need to be powered: each task requires draining a total of P units of power within its allowed window [start, end]. Three global constraints limit what you can schedule each minute:

Constraint	Meaning
max_power	Total power drawn across all tasks in one minute
max_concurrent	Number of distinct tasks that may draw power per minute
max_bill	Total electricity cost must not exceed this value

Cost formula for minute t:

cost(t) = power_at[t] * price[t] * (1 + power_at[t] / max_power)

The quadratic term makes it expensive to overload any single minute.

Input Format

max_power
max_bill
max_concurrent
N
price[0]
...
price[N-1]
M
id power start end
...

Output Format

M
id minute1 amount1 minute2 amount2 ...
...

Algorithm - Greedy Earliest-Cheapest

1. Sort tasks by window width (narrowest first). Narrow tasks have less scheduling freedom and must be placed before wide tasks consume the cheap slots.

2. For each task, repeatedly:

   • Scan the task's window [start, end] for the cheapest non-exhausted minute (a minute is exhausted once it hits max_power or max_concurrent).
   • Drain at most min(remaining_need, 20% of max_power, headroom) units there. The 20 % cap spreads load across several minutes instead of concentrating it, which keeps the quadratic cost term small.
   • Mark the minute exhausted if either hard limit is now reached.

3. Repeat until the task's power requirement is fully satisfied.

Why it works

• Greedy by cheapest available slot is optimal under a linear cost model.
• The 20 % cap trades a slight increase in minutes used for a large reduction in the quadratic overload penalty.
• Scheduling narrow windows first prevents them from being starved out by wide tasks that claimed all the cheap slots.

Complexity

• Sorting: O(M log M)
• Per task: O(P/limit * W) where W = end - start + 1
• Overall: roughly O(M * max_power * N) in the worst case, but fast in practice because tasks are small relative to the grid.

Compile & Run

g++ -std=c++17 -O2 -o solution solution.cpp
./solution < input.in > output.out