helloworld1102's blog

By helloworld1102, history, 3 years ago, In English

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.

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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.