For tests up to 10 you can solve manually.

For second group you can solve by brute force: check all possible $$$i$$$, $$$j$$$ and check condition. $$$O(n^2)$$$

For third group you can see, that for fixed $$$i$$$ $$$j = n - i$$$. $$$O(n)$$$

For full solution you can see, that for every number from $$$0$$$ to $$$n$$$ we can find pair. The answer is $$$n + 1$$$. $$$O(1)$$$.

#include <bits/extc++.h>
#define int int64_t

using namespace std;

int32_t main() {
      int n;
      scanf("%lld", &n);
      n++;
      printf("%lld", n);
}

For the first group it was enough to note that the answer is always $$$k$$$.

For the second group it was necessary to find the number of ones and twos and solve similarly to the first case.

For the third group it was necessary to be able to find the minimum in the array.

For the fourth group, you could sort the array for $$$O(n^2)$$$ (for example, by bubble sorting) and output the sum $$$k$$$ of the first elements.

For a complete solution, simply sort the array by $$$O(n \log(n))$$$ sorting (either your own or built into your programming language).

#include<bits/stdc++.h>
#define int int64_t

using namespace std;

int32_t main(){
    int n, k;
    cin >> n >> k;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    int s = 0;
    for (int i = 0; i < k; i++)
        s += a[i];
    cout << s;
}

For the first group it was enough to parse the tests manually.

For the second group it was possible to output the answer itself, not the remainder of the division.

For the third group of tests it was possible to write the algorithm that was specified in the condition. $$$O(n)$$$

The fourth group of tests is a big clue to the complete solution. We simply output 0.

For the complete solution, combine the usual enumeration from the condition and the cutoff for what $$$p \le n$$$. The asymptotics of $$$O(min(p, n))$$$

#include <bits/extc++.h>
#define int int64_t

using namespace std;

//#define getchar() getchar_unlocked()
#define _CRT_DISABLE_PERFCRIT_LOCKS

int readInt() {
	int x;
	char ch;
	int sgn = 1;
	while (!isdigit(ch = getchar())) {
		if (ch == '-') {
			sgn *= -1;
		}
	}
	x = ch - '0';
	while (isdigit(ch = getchar())) {
		x = x * 10 + (ch - '0');
	}
	return x * sgn;
}

string readString() {
    string s;
    char ch;
    while (isalpha(ch = getchar())) {
        s += ch;
    }
    return s;
}

int32_t main() {
      int n = readInt(), p = readInt();
      if (p <= n) {
            cout << 0;
            return 0;
      }
      int ans = 1;
      for (int i = n; i >= 1; i -= 2) {
            ans = ans * i % p;
      }
      cout << ans;
}

For the first group, check that $$$|p| \le |s|$$$ ($$$|x|$$$ — the length of line $$$x$$$). If the condition holds, output $$$|p|$$$, otherwise — $$$-1$$$.

For the second group we can use the solution for the first subgroup, but we need to additionally check that $$$p$$$ consists of the same characters, and the same as $$$s$$$.

For the third group we had to precalculate the number of occurrences of each character on the prefix and use this to answer queries.

The fourth group needed to be able to find the first occurrence of a single character. This could be done, for example, by prefetching.

For the fifth group we can write a brute check. $$$O(q \cdot n \cdot \log(n))$$$

For a complete solution, it was necessary to combine the prefetching from the third group and the binning search or keeping in the prefetching the indices of occurrences of each symbol, by which we simply solve the problem of finding the maximum of the values at the positions of the number of occurrences of the current symbol in $$$|p|$$$. The asymptotics $$$O(q \cdot 26)$$$ or $$$O(q \cdot \log(n) \cdot 26)$$$

#include <bits/extc++.h>
#define int int64_t

using namespace std;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> arr[26];
    for(int i = 0; i < n; i++) {
        arr[s[i] - 'a'].push_back(i + 1);
    }
    int q;
    cin >> q;
    while(q--) {
        int ptr[26]{};
        string nm;
        cin >> nm;
        int ans = 0;
        bool can = true;
        for(int i = 0; i < nm.size(); i++) {
            if (arr[nm[i] - 'a'].size() <= ptr[nm[i] - 'a']) {
                can = false;
                break;
            }
            ans = max(ans, arr[nm[i] - 'a'][ptr[nm[i] - 'a']]);
            ptr[nm[i] - 'a']++;
        }
        if (!can)
            cout << "-1\n";
        else
            cout << ans << '\n';
    }
}

For the first group, the answer is always $$$0$$$.

For the second group, the answer can be $$$1$$$ if there is $$$2$$$ to the left of $$$1$$$. Otherwise the answer is $$$0$$$.

For the third group you could go through all possible subsets. $$$O(2^n \cdot n)$$$

There are several variations on the complete solution:

• Note that since the answer is equal to the sum of the differences of the neighbors in the subset, this answer is $$$x - y$$$, where $$$x$$$ is-- the leftmost and $$$y$$$ is-- the rightmost number of the subset. Then we can either find by trying $$$O(n^2)$$$, 60 points, or notice that we actually have to actually for a fixed $$$y$$$ just maintain the maximum on the prefix, which prefix sums know how to do.

• Solve by dynamic programming. $$$dp_i$$$ — the answer for the prefix $$$i$$$ processed. $$$dp_i = max_{j < i}(dp_j + a_j - a_i)$$$. We get the solution for $$$O(n^2)$$$, in which we could observe that $$$a_i$$$ does not change as $$$j$$$ changes, and so we just need to know the maximum on the prefix from $$$dp_j + a_j$$$, which is done similarly by prefix sums.

#include<bits/stdc++.h>
#define int int64_t

using namespace std;

int32_t main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int mn = INT_MAX, ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, a[i] - mn);
        mn = min(mn, a[i]);
    }
    cout << ans;
}

For the first three groups, it was enough to write what is asked in the condition (adding to the set and checking that its size < r — l + 1). $$$O(q \cdot n \cdot \log(n))$$$

For the fourth group we have the same solution, but set is too slow, so we use a hash table (unordered set or gp hash table). $$$O(q \cdot n)$$$

For the next two groups, the solution to the fourth subgroup was sufficient, but it was still necessary to stop the algorithm as soon as we found the answer. $$$O(q \cdot min(n, A))$$$.

For the next group it was necessary to solve the problem offline: sort the queries in the order of the algorithm Mo and solve the problem using it. You can read more here: https://ru.algorithmica.org/cs/decomposition/mo. $$$O((q + n) \cdot \sqrt n)$$$

For a complete solution, we needed to notice this fact:

Let's find for each index $$$i$$$ such an index $$$j$$$ that $$$j < i$$$, $$$a_i = a_j$$$ and $$$|j - i|$$$ is minimal. If such $$$j$$$ does not exist, put its value $$$-1$$$. Then it is easy to see that the answer is a check for the maximum on the segment $$$[l, r]$$$ in the resulting array $$$\ge l$$$.

Now this problem can be solved for 80 points by a regular segment tree (the recursive tree runs on par with the nonrecursive tree).

To solve for 100 you should also have noticed that you can actually answer not $$$max(l, r) \ge l$$$ but $$$max(0, r) \ge l$$$, because the segment $$$[0, l - 1]$$$ has no effect on the answer (the maximal value there could be $$$l - 2$$$). Now the problem is reduced to a maximum on the prefix, which is solved by the usual prefix maxima.

#include<bits/stdc++.h>

using namespace std;

const int N = 2e6 + 5e5 + 1;
const int A = 5e6 + 1;

int n, q;
int a[N];
int last[A];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        int cur = a[i];
        a[i] = max(a[i - 1], last[cur]);
        last[cur] = i;
    }
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << (a[r] >= l ? "Yes\n" : "No\n");
    }
}

For the first three groups, it was enough to write what is asked in the condition (adding to the set and checking that its size < r — l + 1). $$$O(q \cdot n \cdot \log(n))$$$

For the fourth group we have the same solution, but set is too slow, so we use a hash table (unordered set or gp hash table). $$$O(q \cdot n)$$$

For the next two groups, the solution to the fourth subgroup was sufficient, but it was still necessary to stop the algorithm as soon as we found the answer. $$$O(q \cdot min(n, A))$$$.

For the next group it was necessary to solve the problem offline: sort the queries in the order of the algorithm Mo and solve the problem using it. You can read more here: https://ru.algorithmica.org/cs/decomposition/mo. $$$O((q + n) \cdot \sqrt n)$$$

For a complete solution, we needed to notice this fact:

Let's find for each index $$$i$$$ such an index $$$j$$$ that $$$j < i$$$, $$$a_i = a_j$$$ and $$$|j - i|$$$ is minimal. If such $$$j$$$ does not exist, put its value $$$-1$$$. Then it is easy to see that the answer is a check for the maximum on the segment $$$[l, r]$$$ in the resulting array $$$\ge l$$$.

Now this problem can be solved for 80 points by a regular segment tree (the recursive tree runs on par with the nonrecursive tree).

To solve for 100 you should also have noticed that you can actually answer not $$$max(l, r) \ge l$$$ but $$$max(0, r) \ge l$$$, because the segment $$$[0, l - 1]$$$ has no effect on the answer (the maximal value there could be $$$l - 2$$$). Now the problem is reduced to a maximum on the prefix, which is solved by the usual prefix maxima.

#include <bits/extc++.h>

#define int int64_t

using namespace std;

const int mod = 1e9 + 7;

int binpow(int x, int y) {
    if (y == 0)
        return 1;
    if (y & 1)
        return binpow(x, y - 1) * x % mod;
    int z = binpow(x, y / 2);
    return z * z % mod;
}

int add(int x, int y) {
    return (x + y + mod) % mod;
}

int mul(int x, int y) {
    return x * y % mod;
}

int divd(int x, int y) {
    return mul(x, binpow(y, mod - 2));
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string l;
    cin >> l;
    int cnt = 0;
    while (!l.empty() && l.back() == '1')
        l.pop_back(), cnt++;
    if (!l.empty())
        l.pop_back();
    l.push_back('1');
    while (cnt--)
        l.push_back('0');
    int ans = 0, cur = 1;
    for (int i = 0; i + 1 < l.size(); i++) {
        ans = add(ans, cur);
        cur = mul(cur, 3);
    }
    for (int i = 1; i < l.size(); i++) {
        if (l[i] == '1') {
            ans = add(ans, mul(divd(cur, 3), 2));
            cur = divd(cur, 3);
        }
        else
            cur = mul(divd(cur, 3), 2);
    }
    cout << ans;
}