Please help in a possible DP problem .

#	User	Rating
1	tourist	3856
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3462
9	ecnerwala	3451
10	heuristica	3431

#	User	Contrib.
1	cry	167
2	-is-this-fft-	162
3	Dominater069	160
4	Um_nik	158
5	atcoder_official	157
6	Qingyu	156
7	djm03178	152
7	adamant	152
9	luogu_official	151
10	awoo	147

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.

Comments (1)

Show archived | Write comment?

Dan4Life

3 years ago, # |

← Rev. 3 →

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

Unable to parse markup [type=CF_MATHJAX]

(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

one. At the $$$ith$$$ bus stop, its possible that in the optimal answer, there could be

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

for all

)

At $$$0$$$ capacity resizes, you can easily calculate $$$dp[i][0]$$$ for all

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

+uselessness of subarray[i-k+1...i]).

Answer = mininimum of $$$dp[n][j]$$$ where

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 =

. 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

which is fast enough as

. 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.

→ Reply

helloworld1102's blog