If you currently have a set, and its answer is equal to $$$x$$$.

How can you increase $$$x$$$ by possibly changing existing elements and adding new ones?

Try to think about invariants to follow when building the set.

An invariant which might help:

All the numbers of our current set are less than $$$2^b$$$ for some $$$b$$$.

Now how can we benefit from this invariant to increase $$$x$$$ by one in an easy way?

How can we increase $$$x$$$ quicker than this?

Let's try to figure out a way to double the current set's answer and a way to increase it by one.

Our set is initially empty, and while building it, all numbers must be less than $$$2^b$$$ for some $$$b$$$.

Increasing the answer by one is easy, as we can add a new element equals $$$2^{b + 1} - 1$$$.

Doubling the answer is also not that hard. We will modify the existing elements of our current set.

We will first add a new (unused before) bit to all the existing numbers in our current set. Following our invariant, this bit will be $$$2^b$$$. Then we will add a new number that will have the newly added bit turned off and all other bits used before turned on. This way, every subset that doesn't include the newly added number will have the new bit turned on, and all subsets that include it will have the new bit turned off.

Knowing how to double the answer and increase it by one, we can build the set in a way similar to binary exponentiation.

In the implementation below, the global variable bit represents the lowest bit that is still unused in the current set.

#include <bits/stdc++.h>

using namespace std;

int K, s, bit;
vector<long long> res;

void bld(int k) {
  if (k & 1) {
    if (k - 1 > 0) {
      bld(k - 1);
    }
    bit += 1;
    res.push_back((1LL << bit) - 1);
    return;
  }
  bld(k >> 1);
  for (int i = 0; i < (int) res.size(); i++) {
    res[i] |= (1LL << bit);
  }
  res.push_back((1LL << bit) - 1);
  bit += 1;
}

int main() {
  scanf("%d %d", &K, &s);
  bld(K);
  printf("%d\n", (int) res.size());
  for (int i = 0; i < (int) res.size(); i++) {
    if (i > 0) {
      printf(" ");
    }
    printf("%lld", res[i]);
  }
  puts("");
  return 0;
}

The first thing that I thought about after I've read the problem was: $$$k=$$$ knapsack capacity.

Do segments really intersect?

Imagine this: ()()()()()...

This pairing is the one that covers the minimal distance.

We can change ()() to (()), which adds the distance between the second and the third ones to the answer.

So now we want to choose a subset of the brackets and join them together.

The problem now became a 0/1 knapsack problem, and to fit in the memory limit, we will use bitsets to store our choices since we need them to construct the pairings.

#include <bits/stdc++.h>

using namespace std;

int n, k, x[14004];

bitset<30001> dp, pd, c[7003];

int main() {
  scanf("%d %d", &n, &k);
  for (int i = 0; i < 2 * n; i++) {
    scanf("%d", &x[i]);
  }
  vector<int> a;
  for (int i = 1; i < 2 * n; i += 2) {
    a.push_back(x[i] - x[i - 1]);
  }
  vector<int> b(1, 0);
  for (int i = 3; i < 2 * n; i += 2) {
    b.push_back(x[i] - x[i - 2]);
  }
  dp[0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = k; j >= 0; j--) {
      pd[j] = 0;
      if (i > 0 && j >= b[i] && dp[j - b[i]]) {
        pd[j] = 1;
        c[i][j] = 1;
      }
      if (j >= a[i] && dp[j - a[i]]) {
        pd[j] = 1;
        c[i][j] = 0;
      }
    }
    swap(dp, pd);
  }
  if (!dp[k]) {
    puts("NO");
    return 0;
  }
  vector<pair<int, int>> res;
  for (int i = n - 1; i >= 0; i--) {
    if (c[i][k] == 0) {
      res.push_back({2 * (i + 1) - 1, 2 * (i + 1)});
      k -= a[i];
      continue;
    }
    int j = i - 1;
    k -= b[i];
    while (c[j][k] == 1) {
      res.push_back({2 * (j + 1), 2 * (j + 1) + 1});
      k -= b[j];
      j -= 1;
    }
    res.push_back({2 * (j + 1), 2 * (j + 1) + 1});
    k -= a[j];
    res.push_back({2 * (j + 1) - 1, 2 * (i + 1)});
    i = j;
  }
  puts("YES");
  for (auto [f, s] : res) {
    printf("%d %d\n", f, s);
  }
  return 0;
}

We are minimizing a summation of products. What number best minimizes products?

If we want to use as much of that number as we can, what are the values of the number of stones we are putting in each stove?

It's not obvious how we can use a greedy strategy to arrange the stones and the bounds aren't that big. What can we do?

It's most advantageous to (if possible) not put any stones, but we must use all of them.

We will still not put any stones, but only in some of the stoves, not all. So for sure, we want to have as many empty stoves as we can. So how can we achieve this?

We will put $$$v$$$ stones in non-empty stoves.

So now we are only choosing from three different options (instead of $$$v$$$) for each stove (i.e. $$$0$$$, $$$v$$$, and $$$s \space mod \space v$$$).

A straightforward dynamic programming solution would be for each stove to try all possible amounts of stones. The DP state will be:

$$$i$$$ is the current stove, $$$left$$$ is how many stones we must put in the remaining stoves, and $$$last$$$ is the number of stones in the previous stove. The answer for our problem will be: $$$min_{0 \le x \le min(v, s)}dp[n][0][x]$$$.

Since we noticed that we will only put $$$0$$$, $$$v$$$ or $$$s \space mod \space v$$$ stones in each stove our dp becomes:

The only difference is that $$$last$$$ is $$$0/1/2$$$ representing the values $$$0/v/s \space mod \space v$$$ respectively, and $$$smodv$$$ is a boolean flag that indicates whether we used the value $$$s \space mod \space v$$$ until now or not.

#include <bits/stdc++.h>

using namespace std;

const long long inf = (long long) 4e18L;

int N, S, V, p[1003];
long long dp[1003][1003][2][3];

long long sol(int i, int j, int k, int l) {
  if (j == 0 && k == 1) {
    return 0;
  }
  if (i == N) {
    return inf;
  }
  long long& ret = dp[i][j][k][l];
  if (ret != -1) {
    return ret;
  }
  long long last = (l == 1) * V + (l == 2) * (S % V);
  ret = sol(i + 1, j, k, 0);
  if (j > 0) {
    ret = min(ret, (i ? p[i - 1] * last * V : 0) + sol(i + 1, j - 1, k, 1));
  }
  if (k == 0) {
    ret = min(ret, (i ? p[i - 1] * last * (S % V) : 0) + sol(i + 1, j, 1, 2));
  }
  return ret;
}

int main() {
  scanf("%d %d %d", &N, &S, &V);
  for (int i = 0; i < N; i++) {
    scanf("%d", &p[i]);
  }
  int C = S / V;
  memset(dp, -1, sizeof dp);
  cout << sol(0, C, (S % V) == 0, 0) << '\n';
  return 0;
}

What cases are there if $$$n = 2$$$?

Try to express other operations in terms of the operators allowed by the problem statement (e.i. {$$$+, -, *, /, abs$$$}).

What does the "K-th order statistic" actually mean?

By looking at the cases when $$$n = 2$$$, it's easy to notice that we need to represent the $$$max(a, b)$$$ and $$$min(a, b)$$$ functions in terms of $$$a$$$ and $$$b$$$. They are trivial:

The first idea that came to my mind is that the $$$k$$$-th order statistics is the minimum of all maximums of subsets of size $$$k$$$. We can implement this idea by iterating over all the subsets of size $$$k$$$ and nesting $$$max$$$ and $$$min$$$. The resulting string will exceed $$$10^5$$$ characters on the max tests, but it is enough to score 49.

Another thing to notice is that the $$$k$$$-th order statistics will win exactly $$$k$$$ (since the numbers are distinct) $$$max$$$ battels against other elements.

How to check if an element $$$a$$$ is winning a max battle against some other element $$$b$$$?

We need to check if $$$a == max(a, b)$$$. Thus we need the $$$==$$$ operator.

One can notice that two elements are equal if their difference is $$$0$$$, so taking the minimum between their difference and $$$1$$$ will give us the opposite of what we want. We can subtract that from $$$1$$$ and get our desired result.

$$$eq(a, b)$$$ will return $$$1$$$ if $$$a == b$$$ and $$$0$$$ otherwise.

Now for each element, we will test it against all the elements and sum up the results of the comparisons and check if it's equal to $$$k$$$ then we got our answer.

The only thing left is to count how many characters our resulting string will have in the max test. Here is the usage of characters for each of our functions in the implementation below:

$$$min/max(a, b): 12 + 2|a| + 2|b|$$$

$$$eq: 28 + 2|a| + 2|b|$$$

Where $$$|x|$$$ is the length of the string $$$x$$$.

#include <bits/stdc++.h>

using namespace std;

string max(const string& a, const string& b) {
  return "(" + a + "+" + b + "+abs(" + a + "-" + b + "))/2";
}

string min(const string& a, const string& b) {
  return "(" + a + "+" + b + "-abs(" + a + "-" + b + "))/2";
}

string eq(const string& a, const string& b) {
  return "1-" + min(string(1, '1'), "abs(" + a + "-" + b + ")");
}

int n, k;

int main() {
  scanf("%d %d", &n, &k);
  string res = "", K = to_string(k);
  for (char c = 'a'; c < char('a' + n); c++) {
    if (c > 'a') {
      res += '+';
    }
    string tmp = "", C(1, c);
    for (char d = 'a'; d < char('a' + n); d++) {
      if (!tmp.empty()) {
        tmp += '+';
      }
      string D(1, d);
      tmp += eq(C, max(C, D));
    }
    res += C + "*(" + eq(tmp, K) + ")";
  }
  puts(res.c_str());
  return 0;
}