Hello, Hi there , if anyone know the below problem solution please tell. I thought this problem using binary search , greedy, but no use. So finally i think it will be possible by DP. (but not getting possible states and transitions). If anyone helps, that would be very nice of you. So the problem goes like this -->
A bus stops at n bus stops, each bus stop having a[i] people. The bus needs to take in all the people on the bus. People from 1 bus stop get down before the next bus stop arrives. They use a resizing tech which allows the bus to be resized to whatever capacity they want. This action can be done only b times at max. The uselessness of the bus is the summation of a total number of unoccupied seats across n stops. Find the minimum uselessness the bus can achieve if the resizing tech is used optimally.
1<=a[i]<=10^6, 1<=b<=n<=400
Ex 1: a = [10 20] b = 0 Ans:10 Explanation – the resizing tech cannot be applied. hence the capacity of the bus is 20 initially. in the first stop, 20-10 seats were unused. in the second stop 20 – 20 seats are unused. Total unused seats = 10
Ex 2: a = [10 20 30] b = 1 Ans: 10 Explanation – the resizing tech can be applied only once. The capacity of the bus is 10 initially. In the first stop 10-10 seats unused = 0. in the second stop, the tech is used to resize to 30. 30 – 20 seats unused.
In the third stop, 30-30 seats unused
Total unused seats = 10.
If anyone know how to do it, please explain .
THANK YOU.
A very similar problem
Observations
This problem can be reduced to dividing the bus stops into at most $$$b+1$$$ subarrays such that each subarray contains a capacity i.e the new capacity the bus resizes to.
For a given subarray, the capacity that gives the minimum uselessness is the max number in the subarray. (prove)
let $$$m$$$ = subarray size, $$$s$$$ = subarray sum, $$$c$$$ = bus capacity(i.e max element in the subarray). Formula for calculating minimum uselessness of subarray $$$= c*m-s$$$ (why?)
Solution
Let $$$dp[i][j] =$$$ minimum uselessness after $$$i$$$ bus stops and $$$j$$$ bus capacity resizes.
This means there are $$$j+1$$$ subarrays and the $$$ith$$$ bus is the last element in the last subarray which is the $$$(j+1)th$$$ one. At the $$$ith$$$ bus stop, its possible that in the optimal answer, there could be $$$1,2,3...i$$$ elements in the last subarray. So check all possible sizes of last subarray and update $$$dp[i][j]$$$ to smallest uselessness among them.
Base cases
Obviously at $$$0$$$ bus stops, minimum uselessness $$$= 0$$$, (i.e $$$dp[0][i]=0$$$ for all $$$i = {0...b}$$$)
At $$$0$$$ capacity resizes, you can easily calculate $$$dp[i][0]$$$ for all $$$i = {1...n}$$$ with the formula above(read last 2 paragraphs to do this in $$$O(1)$$$ per subarray)
Transition
Denote $$$k$$$ as the size of the last subarray. Then,
for each $$$i = {1...n}$$$, $$$j = {1...b}$$$, $$$k = {1..i}$$$, $$$dp[i][j] = min(dp[i][j], dp[i-k][j-1]$$$+uselessness of subarray[i-k+1...i]).
Answer = mininimum of $$$dp[n][j]$$$ where $$$j = 0...b$$$
Uselessness of a subarray requires the max element in a subarray and the subarray sum. Using the normal $$$O(N)$$$ approach to get them results in TLE as time complexity = $$$O(N^3B)$$$. To fix this, they can be gotten in $$$O(1)$$$ with $$$O(N)$$$ precomputation using sparse tables(or segment Tree in $$$O(log N)$$$) for maximum, and prefix sums for sum. This reduces the time complexity to $$$O(N^2B)$$$ which is fast enough as $$$N,B<=400$$$. My solution to problem in link above:
Note: It is worth noting there is a clever way to get the max element in a subarray in $$$O(1)$$$ in this problem which is shown in the editorial of the link above.
UPD: From June 1 2023, Usaco Guide moved to a new IDE, so I've updated the link to my code.