Divisibility and Digit Extraction

The objective is to determine if a given integer $N$ is either divisible by 3 or contains the digit '3'.

A direct approach involves checking the modulo and then iteratively extracting digits. The time complexity for this is $O(\log_{10} N)$.

bool is_lucky(long long val) {
    if (val % 3 == 0) return true;
    std::string s = std::to_string(val);
    return s.find('3') != std::string::npos;
}

Mathematical Note: Divisibility Rules

A number is divisible by 3 (or 9) if and only if the sum of its digits is divisible by 3 (or 9). This is because any power of 10 can be expressed as $10^k = (10^k - 1) + 1$, where $10^k - 1$ is always a sequence of $9$s (e.g., $99, 999$), wich is divisible by both 3 and 9.

Extended Variation: Counting up to N

If the problem asks for the count of non-negatiev integers $m \le n$ that satisfy the condition, we can use Digit Dynamic Programming. We calculate the complement: the count of numbers that are NOT divisible by 3 and do NOT contain the digit '3'.

long long solve_digit_dp(int n) {
    std::string s = std::to_string(n);
    int len = s.size();
    long long memo[20][2][3];
    memset(memo, -1, sizeof(memo));

    auto dfs = [&](auto self, int pos, bool is_less, int remainder) -> long long {
        if (pos == len) return remainder != 0;
        if (memo[pos][is_less][remainder] != -1) return memo[pos][is_less][remainder];

        long long count = 0;
        int limit = is_less ? 9 : s[pos] - '0';
        for (int d = 0; d <= limit; ++d) {
            if (d == 3) continue;
            count += self(self, pos + 1, is_less || (d < limit), (remainder * 10 + d) % 3);
        }
        return memo[pos][is_less][remainder] = count;
    };
    return n - dfs(dfs, 0, false, 0);
}

Efficient Calculation of the Tribonacci Sequence

Given the recurrence $f(n) = f(n-1) + f(n-2) + f(n-3)$ with base cases $f(1)=0, f(2)=0, f(3)=1$, compute $f(n) \pmod{10007}$.

Linear Time Approach

For $n \le 10^6$, an iterative $O(n)$ solution is sufficient:

int get_tribonacci(int n) {
    if (n <= 2) return 0;
    if (n == 3) return 1;
    std::vector<int> dp(n + 1);
    dp[1] = dp[2] = 0; dp[3] = 1;
    for (int i = 4; i <= n; ++i) {
        dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % 10007;
    }
    return dp[n];
}

Logarithmic Time Approach

For very large $n$, we use matrix exponentiation. The state transition can be represented as:

$$\begin{bmatrix} f_{i+1} \ f_{i} \ f_{i-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \ 1 & 0 & 0 \ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} f_{i} \ f_{i-1} \ f_{i-2} \end{bmatrix}$$

By computing $M^{n-3}$ where $M$ is the transformation matrix, we can find $f(n)$ in $O(3^3 \log n)$.

Linear Systems for Counting Leg Combinations

With $N$ individuals consisting of adults (2 legs), elders (3 legs), and babies (4 legs), given total legs $M$, find any valid count $(a, b, c)$.

Let $a, b, c$ be the counts for adults, elders, and babies respectively:

1. $a + b + c = N$
2. $2a + 3b + 4c = M$

Subtracting twice the first equation from the second: $(2a + 3b + 4c) - 2(a + b + c) = M - 2N$ $b + 2c = M - 2N$

We can iterate through possible values of $c$ and solve for $b$ and $a$:

void solve_legs(int n, int m) {
    for (int c = 0; c <= n; ++c) {
        int b = m - 2 * n - 2 * c;
        int a = n - b - c;
        if (b >= 0 && a >= 0 && (2 * a + 3 * b + 4 * c == m)) {
            std::cout << a << " " << b << " " << c << std::endl;
            return;
        }
    }
    std::cout << "-1 -1 -1" << std::endl;
}

Sorting with Minimum Moves and Longest Increasing Subsequence

Given a permutation of $N$ cards, find the minimum number of cards to move to make the sequence ascending. A single move consists of picking a card and inserting it anywhere.

The minimum number of moves requierd to sort an array by moving elements is $N - L$, where $L$ is the length of the Longest Increasing Subsequence (LIS). Elements belonging to the LIS remain fixed, while all other elements are repositioned around them.

Binary Search Optimization ($O(N \log N)$)

We maintain an array tails where tails[i] is the smallest tail of all increasing subsequences of length i+1.

int min_moves_to_sort(int n, const std::vector<int>& cards) {
    std::vector<int> tails;
    for (int x : cards) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    return n - tails.size();
}

Segment Tree / Fenwick Tree Approach ($O(N \log M)$)

If the values are within a specific range, we can use a Fenwick tree to store the maximum LIS length ending at a certain value. For each element $x$, we query the range $[1, x-1]$ for the maximum value $v$ and update the tree at position $x$ with $v+1$.