K-th Gutab (Анализа на решението)

Add the number $0$ to the set. Then perform $k$ steps:

• Find the smallest element $x$ in the set and remove it.

• For each $i$ from $1$ to $n$, add the element x + a_i to the set.

After performing $k$ steps, the smallest element in the set will be equal to the $k$-th smallest price Huseyn can pay.

Algorithm implementation

Read the input data.

scanf("%d %d", &n, &k);
for (i = 0; i < n; i++)
  scanf("%d", &m[i]);

Add the number $0$ to the set $s$.

s.insert(0);

Perform $k$ iterations.

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

Find and remove the smallest element $x$ from the set.

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

For each $i$ from $1$ to $n$, add the element x + a_i to the set.

  for (j = 0; j < n; j++)
    s.insert(x + m[j]);
}

Print the answer: the $k$-th smallest price, which is equal to the smallest element in the set.

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

Python implementation — TLE

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

In Python, sets are unordered collections, so min() cannot take advantage of any internal ordering or structure. Instead, it checks each element individually to determine the minimum, which results in 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 an internal sorted list.

Accessing an element by index (for example, $s[0]$ for the smallest element) is done in constant time, since SortedSet directly retrieves the element at the given index without any additional computations.

The add() operation in SortedSet from the sortedcontainers library runs in O(log n) time, 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])