Binary search - Sagheer and Nubian Market (Codeforces)

help
,
1

Problem here

I am having trouble understanding the last part of the editorial:

" For each value k , we will compute the new prices, sort them and pick the minimum k prices to find the best minimum cost for k items. "

How can we prove this ? That for each value of k, it’s cost will be minimum when we sort it and find the minimum value subarray of k elements ?
Since the cost also depends on the index of the value ie cost = v[i]+index[v[i]]*k

Shouldn’t we find all the possible sub sequence of length k, and then find the minimum among them?

2

No It’s not like that. Read the statement carefully.

For each index i the increase in the cost due to choosing k items is i * k.

So for each k create new prices and sort and choose the k smallest.

1 Like
3

Got it, Thanks…!!!