In this problem I am having trouble understanding why we use concept like sliding window instead of trying all combinations+DP ? Especially the bold line in below paragraph which is from the Editorial.
However, the second sample test case shows that when n>m there is a possibility that purchasing items from the first m shops will take more time than skipping one or more shops. We'll need to calculate the amount of time for each possible combination of shops and choose the combination that takes the least amount of time. It's important that we can calculate all of these times optimally. If we were to create an array of each of the combinations and then use the loop above for each combination, we'd be forgetting that each combination is only different from the next by one shop.
Can you please explain proof for the statement ?
Pseudo codes from editorial here.
Thanks.
It basically means that whatever shops we choose to buy from, will be contiguous. To prove this, let's assume that it is not contiguous then the shops will look as { 1 1 0 ... [1] ... 1 }, where [1] indicates shop form which we could have taken but we did not, then as an exchange argument we can say that we can remove one of the corner ones and have a better answer as then we reduce the cost which we are adding to the final answer.
BTW, its Trouble*
Nicely explained! :D