• Excellent:
• Good:
• Average:
• Bad:
• Terrible:

• A:
• B:
• C1:
• C2:
• D:
• E:
• F:
• G:

• A:
• B:
• C1:
• C2:
• D:
• E:
• F:
• G:

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    string a, b, c;
    int n, m;
    cin >> n >> a;
    cin >> m >> b >> c;
    string add_left = "";
    for (int i = 0; i < m; ++i) {
        if (c[i] == 'V') {
            add_left += b[i];
        } else {
            a += b[i];
        }
    }
    reverse(add_left.begin(), add_left.end());
    cout << add_left + a << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

If Vadim appends $$$k$$$ zeros to the number $$$x$$$, what will be the ratio between $$$n$$$ and $$$x$$$?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        long long r;
        cin >> r;
        
        long long d = 11;
        vector <long long> ans;
        while (r >= d) {
            if (r % d == 0)
                ans.push_back(r / d);
            d = (d - 1) * 10 + 1;
        }
        
        cout << (int)ans.size() << '\n';
        for (int i = (int)ans.size() - 1; i >= 0; --i)
            cout << ans[i] << ' ';
        cout << '\n';
    }
    
    return 0;
}

Does it make sense to use the same type of deal more than 2 times?

The solution with the minimum number of deals is unique.

Ternary numeral system.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    vector <long long> cost;
    long long c = 3;
    long long cnt = 1;
    for (int i = 0; i < 21; ++i) {
        cost.push_back(c);
        c = 3 * c + cnt;
        cnt *= 3;
    }

    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        long long min_k = 0;
        long long min_cost = 0;
        int sz = 0;
        while (n) {
            min_k += n % 3;
            min_cost += (n % 3) * cost[sz];
            n /= 3;
            sz++;
        }
        cout << min_cost << '\n';
    }
    
    return 0;
}

What is more profitable: 3 deals for $$$3^x$$$ watermelons each, or 1 deal for $$$3^{x+1}$$$ watermelons?

Recall the solution to problem C1.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    vector <long long> cost;
    long long c = 3;
    long long cnt = 1;
    for (int i = 0; i < 21; ++i) {
        cost.push_back(c);
        c = 3 * c + cnt;
        cnt *= 3;
    }

    int t;
    cin >> t;
    while (t--) {
        long long n, k;
        cin >> n >> k;
        vector <long long> tr;
        long long min_k = 0;
        while (n) {
            tr.push_back(n % 3);
            min_k += n % 3;
            n /= 3;
        }
        if (min_k > k) {
            cout << -1 << '\n';
            continue;
        }
        k -= min_k;
        k /= 2;
        for (int i = (int)tr.size() - 1; i >= 1; --i) {
            if (tr[i] <= k) {
                tr[i - 1] += 3 * tr[i];
                k -= tr[i];
                tr[i] = 0;
            } else {
                tr[i - 1] += k * 3;
                tr[i] -= k;
                break;
            }
        }
        ll an = 0;
        for (int i = (int)tr.size() - 1; i >= 0; --i)
            an += cost[i] * tr[i];
        cout << an << '\n';
    }
    
    return 0;
}

Find out which number the $$$k$$$-th digit belongs to in the infinite sequence. Let this number be $$$n$$$. Instead of analyzing the sequence, we can calculate the sum of the sums of the digits of all integers from $$$0$$$ to $$$n - 1$$$ and add to this the sum of the required digits of the number $$$n$$$.

Mentally add leading zeros to all numbers from $$$0$$$ to $$$n - 1$$$ so that their lengths become the same. The sum of the sums of the digits will not change, but it will be more convenient to determine the formulas in this case.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        long long k;
        cin >> k;
        long long cur = 9, len = 1;
        while (k - cur * len > 0) {
            k -= cur * len;
            cur *= 10;
            len++;
        }
        string s = to_string(cur / 9 + (k - 1) / len);
        long long ans = 0;
        for (int i = 0; i < (k - 1) % len + 1; i++)
            ans += s[i] - '0';
        long long pr_s = 0;
        for (int i = 0; i < s.length(); i++) {
            int curd = s[i] - '0';
            if (curd)
                ans += curd * (len - 1) * cur / 2 + curd * (2 * pr_s + curd - 1) / 2 * cur / 9;
            cur /= 10, len--;
            pr_s += curd;
        }
        cout << ans << '\n';
    }
    
    return 0;
}

If we know how many specific cards Vadim should take, and how many should take Kostya (for example when $$$x + y = z$$$). How can we then obtain the maximum possible sum?

We need to quickly compute the sum of the $$$x$$$ maximum elements in array $$$a$$$ and the sum of the $$$y$$$ maximum elements in array $$$b$$$. What should we do to be able to compute this for arbitrary $$$x$$$ and $$$y$$$ in $$$O(1)$$$?

How can we solve this problem if $$$x = n$$$ and $$$y = m$$$ — that is, each person can choose any number of cards, as long as their total is $$$z$$$?

If $$$x = n$$$ and $$$y = m$$$, then the optimal set of $$$z$$$ cards consists of $$$x'$$$ maximum cards from Vadim and $$$y'$$$ maximum cards from Kostya (where $$$x' + y' = z$$$). How should we adjust this optimal answer if the optimal number for Vadim or Kostya exceeds their limits (that is, if $$$x \lt x'$$$ or $$$y \lt y'$$$)?

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector <int> a(n), b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());

    vector <long long> pa(n + 1), pb(m + 1);
    for (int i = 0; i < n; i++)
        pa[i + 1] = pa[i] + a[i];
    for (int i = 0; i < m; i++)
        pb[i + 1] = pb[i] + b[i];

    vector <pair <int, int>> ans(n + m + 1);
    int l = 0, r = 0;
    for (int i = 1; i < ans.size(); i++) {
        if (l < n && r < m) {
            if (a[l] < b[r])
                r++;
            else
                l++;
        }
        else if (l == n)
            r++;
        else if (r == m)
            l++;
        ans[i] = { l, r };
    }

    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        l = ans[z].first, r = ans[z].second;
        if (l > x)
            cout << pa[x] + pb[z - x] << '\n';
        else if (r > y)
            cout << pa[z - y] + pb[y] << '\n';
        else
            cout << pa[l] + pb[r] << '\n';
    }
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector <int> a(n), b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
 
    vector <long long> pa(n + 1), pb(m + 1);
    for (int i = 0; i < n; i++)
        pa[i + 1] = pa[i] + a[i];
    for (int i = 0; i < m; i++)
        pb[i + 1] = pb[i] + b[i];
 
    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
 
        int l = max(0, z - y);
        int r = min(z, x);
        while (l + 2 < r) {
            int m1 = (l + l + r) / 3;
            int m2 = (l + r + r) / 3;
            if (pa[m1] + pb[z - m1] > pa[m2] + pb[z - m2]) {
                r = m2;
            } else {
                l = m1;
            }
        }
 
        long long s = 0;
        for (int i = l; i <= r; i++)
            s = max(s, pa[i] + pb[z - i]);
 
        cout << s << '\n';
    }
}
 
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Recall or learn what bridges are and understand how this is related to the lanes that lie on all paths from $$$1$$$ to $$$n$$$.

How to find all the bridges that lie on every path from $$$1$$$ to $$$n$$$?

Solve the problem for the case where $$$n = q$$$ and $$$c_i = i$$$.

How to find the nearest vertex from a given set of vertices $$$S$$$ for each vertex?

#include <bits/stdc++.h>
 
using namespace std;
 
vector <vector <int>> g;
vector <bool> used;
vector <int> d, h;
vector <pair <int, int>> edges;
vector <int> cut, path;
int mark = 1;

void dfs(int v, int p, int n) {
    used[v] = true;
    d[v] = h[v] = (p == -1 ? 0 : d[p] + 1);
    if (v == n) mark = 0;
    for (auto e : g[v]) {
        int to = edges[e].first + edges[e].second - v;
        if (to == p) continue;
        if (used[to])
            h[v] = min(h[v], d[to]);
        else {
            path[e] ^= mark;
            dfs(to, v, n);
            path[e] ^= mark;
            h[v] = min(h[v], h[to]);
            if (h[to] > d[v]) cut[e] = 1;
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        g.assign(n + 1, {});
        used.assign(n + 1, false);
        d.assign(n + 1, 0);
        h.assign(n + 1, 0);
        edges = {};
        cut.assign(m, false);
        path.assign(m, false);
        mark = 1;
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            edges.push_back({a, b});
            g[a].push_back(i);
            g[b].push_back(i);
        }
        
        dfs(1, -1, n);
        
        vector <int> ans(n + 1, n + m);
        vector <int> dist(n + 1, n + m);
        queue <int> q;
        for (int i = 0; i < m; ++i) {
            if (cut[i] && path[i]) {
                ans[edges[i].first] = min(ans[edges[i].first], i + 1);
                ans[edges[i].second] = min(ans[edges[i].second], i + 1);
                if (dist[edges[i].first]) {
                    dist[edges[i].first] = 0;
                    q.push(edges[i].first);
                }
                if (dist[edges[i].second]) {
                    dist[edges[i].second] = 0;
                    q.push(edges[i].second);
                }
            }
        }
        
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto e : g[v]) {
                int to = edges[e].first + edges[e].second - v;
                if (dist[to] > dist[v] + 1) {
                    dist[to] = dist[v] + 1;
                    ans[to] = ans[v];
                    q.push(to);
                }
                else if (dist[to] == dist[v] + 1)
                    ans[to] = min(ans[to], ans[v]);
            }
        }
        
        int Q;
        cin >> Q;
        while (Q--) {
            int v;
            cin >> v;
            if (ans[v] == n + m) cout << -1;
            else cout << ans[v];
            if (t || Q) cout << '\n';
        }
    }
    
    return 0;
}

There is no point in adding new symbols both above and below the original table simultaneously. Similarly, there is no point in adding symbols both to the left and to the right of the table at the same time.

The center of the optimal answer table lies within the original one.

We do not need to construct the answer; it is sufficient to check that an answer exists for the current center. Think about how to do this.

An answer exists for the current center if the subtable, which is the intersection of the original table and the one rotated around the center by $$$180^{\circ}$$$, becomes identical to the original when rotated by $$$180^{\circ}$$$. This subtable must contain at least one of the corners of the original table.

The checking of centers can be replaced by the checking of subtables that contain at least one of the corners of the original table.

To check the subtables to see if they become identical to the original when rotated by $$$180^{\circ}$$$, we can use hashing.

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
const int P[2] = { 107, 61 };
int BP[2];

long long bin_pow(long long a, int n) {
    long long ret = 1;
    while (n) {
        if (n & 1) ret = (ret * a) % MOD;
        a = (a * a) % MOD;
        n >>= 1;
    }
    return ret;
}

inline int add(int a, int b) {
    int res = a + b;
    if (res >= MOD) return res - MOD;
    return res;
}

inline int sub(int a, int b) {
    int res = a - b;
    if (res < 0) return res + MOD;
    return res;
}

inline int mult(int a, int b) {
    long long res = (long long)a * b;
    if (res >= MOD) return res % MOD;
    return res;
}

int main() {
    int t;
    cin >> t;
    
    BP[0] = bin_pow(P[0], MOD - 2);
    BP[1] = bin_pow(P[1], MOD - 2);
    vector <int> pows[2];
    vector <int> bpows[2];
    for (int j = 0; j < 2; j++) {
        pows[j].resize(1e6, 1);
        bpows[j].resize(1e6, 1);
        for (int i = 1; i < 1e6; i++) {
            pows[j][i] = mult(pows[j][i - 1], P[j]);
            bpows[j][i] = mult(bpows[j][i - 1], BP[j]);
        }
    }
    
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        vector <string> f(n);
        for (int i = 0; i < n; i++)
            cin >> f[i];
        
        vector <vector <int>> hash(n + 2, vector <int> (m + 2, 0));
        vector <vector <int>> bhash(n + 2, vector <int> (m + 2, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int cur = mult((f[i - 1][j - 1] - 'a' + 1), mult(pows[0][i - 1], pows[1][j - 1]));
                hash[i][j] = add(sub(add(hash[i - 1][j], hash[i][j - 1]), hash[i - 1][j - 1]), cur);
            }
        }
        for (int i = n; i >= 1; i--) {
            for (int j = m; j >= 1; j--) {
                int cur = mult((f[i - 1][j - 1] - 'a' + 1), mult(pows[0][n - i], pows[1][m - j]));
                bhash[i][j] = add(sub(add(bhash[i + 1][j], bhash[i][j + 1]), bhash[i + 1][j + 1]), cur);
            }
        }
        
        auto isp = [&](int x1, int y1, int x2, int y2) {
            int hsh = add(sub(sub(hash[x2][y2], hash[x1-1][y2]), hash[x2][y1-1]), hash[x1-1][y1-1]);
            int bhsh = add(sub(sub(bhash[x1][y1], bhash[x2+1][y1]), bhash[x1][y2+1]), bhash[x2+1][y2+1]);
            hsh = mult(hsh, mult(bpows[0][x1 - 1], bpows[1][y1 - 1]));
            bhsh = mult(bhsh, mult(bpows[0][n - x2], bpows[1][m - y2]));
            return hsh == bhsh;
        };
        
        int mn = n * m * 4;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (isp(1, 1, i, j)) mn = min(mn, (2 * n - i) * (2 * m - j));
                if (isp(1, j, i, m)) mn = min(mn, (2 * n - i) * (m + j - 1));
                if (isp(i, 1, n, j)) mn = min(mn, (n + i - 1) * (2 * m - j));
                if (isp(i, j, n, m)) mn = min(mn, (n + i - 1) * (m + j - 1));
            }
        }
        
        cout << mn - m * n << '\n';
    }
    
    return 0;
}