Six problems drawn from a competitive programming rating competition are analysed below. Every solution is accompanied by both C++ and Python implementations. Keep in mind that Python code may run slower and care should be taken with complexity constants.

Problem 1 – Output a Digit Different from the Product

Given two integers a and b, print any digit in the range 0 to 9 that is not equal to a * b. A brute-force loop over all ten possibilities works perfectly.

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    for (int dig = 9; dig >= 0; --dig) {
        if (dig != a * b) {
            cout << dig << '\n';
            return 0;
        }
    }
    return 0;
}

An even shorter solution exploits the fact that the product is zero only when both numbers are non-zero. Therefore we can always output 0 unless both inputs are non-zero, in which case 0 is exactly the product and we must choose a dfiferent digit.

#include <iostream>
using namespace std;

int main() {
    int x, y;
    cin >> x >> y;
    if (x != 0 && y != 0) cout << 0 << '\n';
    else cout << 1 << '\n';
    return 0;
}

Python version:

a, b = map(int, input().split())
print(0 if a and b else 1)

Both approaches run in O(1) time.

Problem 2 – Length of the Longest Common Prefix

We need to compute the number of initial matching characters of two given strings.

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    size_t pos = 0;
    while (pos < s.size() && pos < t.size() && s[pos] == t[pos])
        ++pos;
    cout << pos << '\n';
    return 0;
}

Python code:

s, t = input().split()
i = 0
while i < len(s) and i < len(t) and s[i] == t[i]:
    i += 1
print(i)

The time complexity is O(min(|s|, |t|)).

Problem 3 – Counting Strings Without a Broken Key Character

Given a character d and several strings, count how many strings do not contain d. Instead of using library functions we can manually scan each string.

#include <iostream>
#include <string>
using namespace std;

int main() {
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        string bad;
        cin >> n >> bad;
        int total = 0;
        for (int i = 0; i < n; ++i) {
            string word;
            cin >> word;
            bool valid = true;
            for (char c : word) {
                if (c == bad[0]) {
                    valid = false;
                    break;
                }
            }
            if (valid) ++total;
        }
        cout << total << '\n';
    }
    return 0;
}

Python version:

T = int(input())
for _ in range(T):
    n, d = input().split()
    words = input().split()
    ans = sum(1 for w in words if d not in w)
    print(ans)

The time per test case is O(n · L) where L is the maximum word length.

Problem 4 – Finding an Integer Root

The task is to find an integer X such that X^N = Y. Taking the N‑th root and rounding gives a candidate; we verify it to avoid floating‑point pitfalls.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        double n, y;
        cin >> n >> y;
        double root = pow(y, 1.0 / n);
        long long cand = llround(root);
        if (fabs(pow(cand, n) - y) < 1e-7)
            cout << cand << '\n';
        else
            cout << -1 << '\n';
    }
    return 0;
}

Python:

import sys
import math

T = int(sys.stdin.readline())
for _ in range(T):
    n, y = map(float, sys.stdin.readline().split())
    r = pow(y, 1.0 / n)
    cand = round(r)
    print(cand if math.isclose(pow(cand, n), y) else -1)

Complexity per test case is O(1).

Problem 5 – Inferring Hidden Values from XOR Clues

We are given hints of the form A_i ⊕ A_j = k and know that A_1 = 1. The relation is symmetric, so we can build an undirected graph where each edge weight is the XOR constant. A simple BFS (or DFS) from node 1 fills in all reachable nodes.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    vector<int> value(n + 1, -1);
    value[1] = 1;
    queue<int> q;
    q.push(1);

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (auto &[nxt, w] : g[cur]) {
            if (value[nxt] == -1) {
                value[nxt] = value[cur] ^ w;
                q.push(nxt);
            }
        }
    }

    for (int i = 1; i <= n; ++i)
        cout << value[i] << " \n"[i == n];
    return 0;
}

Python version using a deque:

from collections import deque
import sys

n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, sys.stdin.readline().split())
    g[u].append((v, w))
    g[v].append((u, w))

ans = [-1] * (n + 1)
ans[1] = 1
q = deque([1])
while q:
    cur = q.popleft()
    for nxt, w in g[cur]:
        if ans[nxt] == -1:
            ans[nxt] = ans[cur] ^ w
            q.append(nxt)

print(' '.join(map(str, ans[1:])))

The entire procedure runs in O(n + m) time.

Problem 6 – Maximising Gifts with a Knapsack Optimisation

We have many item, each defined by a lucky number A_i and a gold reward B_i. The cost of an item is the number of "candy sticks" needed to draw its digits (the well-known seven‑segment stick counts). Although there can be up to 10^5 items, the maximum cost is only 63 (the sum for 888888888). Therefore we can compress the items: for each possible cost we keep the maximum gold value among all item having that cost. This reduces the problem to a bounded unbounded knapsack with at most 63 distinct costs.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int cost_sticks[10] = {6,2,5,5,4,5,6,3,7,6};

int sticks_needed(int num) {
    int s = 0;
    while (num) {
        s += cost_sticks[num % 10];
        num /= 10;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<int> A(n), B(n);
        for (int i = 0; i < n; ++i) cin >> A[i];
        for (int i = 0; i < n; ++i) cin >> B[i];

        vector<int> best(101, 0);
        vector<bool> seen(101, false);
        for (int i = 0; i < n; ++i) {
            int cost = sticks_needed(A[i]);
            seen[cost] = true;
            best[cost] = max(best[cost], B[i]);
        }

        vector<int> dp(m + 1, 0);
        for (int c = 1; c <= 100; ++c) {
            if (!seen[c]) continue;
            for (int j = c; j <= m; ++j)
                dp[j] = max(dp[j], dp[j - c] + best[c]);
        }
        cout << dp[m] << '\n';
    }
    return 0;
}

Equivalent Python snippet:

import sys

sticks = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def count_sticks(x):
    total = 0
    while x:
        total += sticks[x % 10]
        x //= 10
    return total

T = int(sys.stdin.readline())
for _ in range(T):
    n, m = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))

    best_gold = [0] * 101
    have = [False] * 101
    for a, b in zip(A, B):
        c = count_sticks(a)
        have[c] = True
        if b > best_gold[c]:
            best_gold[c] = b

    dp = [0] * (m + 1)
    for c in range(1, 101):
        if not have[c]:
            continue
        for j in range(c, m + 1):
            dp[j] = max(dp[j], dp[j - c] + best_gold[c])
    print(dp[m])

The time complexity per test case is O(63 · m), which simplifies to O(m).