11460. K-th Gutab

In ADA University, n kinds of gutab are sold. Gutab of the i-th kind is sold for a_i qəpik.

Gutab is an Azerbaijani dish made from thinly rolled dough that is cooked briefly on a convex griddle known as a saj. There are many variations of qutab: usually, pumpkin and greens are used as fillings. There are also Shamakhy qutab, Yashyl Qutab and Qarın qutabı, quzu qutabı (lamb), deve qutabi specific for Jorat settlement. They are regional variations of qutab in Azerbaijan.

Huseyn will buy at least one gutab in total. He is allowed to buy multiple gutabs of the same kind.

Find the k-th lowest price that Huseyn may pay. Here, if there are multiple sets of gutabs that cost the same price, the price is counted only once.

Input. The first line contains two numbers: n (1 ≤ n ≤ 10) and k (1 ≤ k ≤ 2 ⋅ 10⁵).

The second line contains the prices for different kinds of gutabs: a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Output. Print the k-th lowest price that Huseyn may pay.

Example. The six lowest prices that Huseyn may pay are

· 5 qəpik

· 10 qəpik

· 11 qəpik

· 15 qəpik

· 11 + 5 = 16 qəpik

· 20 qəpik

Thus, the answer is 20.

Sample input	Sample output
5 6 5 10 11 15 20	20

SOLUTION

data structures – set

Algorithm analysis

Insert number 0 into the set. Then perform the following k steps:

· Let x be the minimum element in the set. Delete x from the set.

· Add to the set all elements x + a_i (1 ≤ i ≤ n);

After performing k steps, the smallest element in the set will be the k-th lowest price that Hussein can pay.

Algorithm implementation

Read the inpt data.

scanf("%d %d", &n, &k);

for (i = 0; i < n; i++)

scanf("%d", &m[i]);

Insert number 0 into the set.

s.insert(0);

Execute k iterations.

for (i = 0; i < k; i++)

{

Find and delete the smallest element x from the set.

x = *s.begin(); s.erase(x);

Add to the set all elements x + a_i (1 ≤ i ≤ n);

for (j = 0; j < n; j++)

s.insert(x + m[j]);

}

Print the answer – the k-th lowest price is the smallest element in the set.

printf("%lld\n", *s.begin());

Python implementation – TLE

The min() function works in O(n) time complexity because it iterates through all the elements of the set to find the smallest one.

In Python, sets are unordered collections, so min() cannot take advantage of any pre-existing order or structure. Instead, it has to check each element individually to determine the minimum, resulting in a linear time complexity proportional to the number of elements in the set.

n, k = map(int, input().split())

m = list(map(int, input().split()))

s = set({0})

for _ in range(k):

x = min(s)

s.remove(x)

for value in m:

s.add(x + value)

print(min(s))

Python implementation

SortedSet maintains its elements in sorted order using a sorted list internally.

Accessing an element by index (e.g., s[0] for the smallest element) is performed in constant time because SortedSet directly retrieves the element at the specified index from its internal sorted list without any additional computations.

The time complexity for the add() operation in SortedSet from the sortedcontainers library is O(log n), where n is the number of elements in the set.

from sortedcontainers import SortedSet

n, k = map(int, input().split())

m = list(map(int, input().split()))

s = SortedSet([0])

for _ in range(k):

x = s[0]

s.discard(x)

for value in m:

s.add(x + value)

print(s[0])