Summer 2024 Friendly Competition - Warmup Session 2A - Beautiful Reflections

CodeForces - 1265E

Problem Statement

Creatnx has n (1 ≤ n ≤ 2×10^5) magical mirrors. Each day she asks one mirror: "Am I beautiful?" The i-th mirror tells Creatnx she is beautiful with probability p_i/100 (1 ≤ p_i ≤ 100).

Creatnx starts from mirror 1 and asks one mirror per day. For the i-th mirror, two scenarios occur:

• If the mirror confirms she is beautiful:
  • If this is mirror n, Creatnx becomes very happy and stops asking.
  • Otherwise, Creatnx will ask mirror i+1 the next day.
• Otherwise, Creatnx becomes very sad and starts over from mirror 1 the next day.

Find the expected number of days until Creatnx becomes happy, modulo 998,244,353.

Solution Approach

Consider using dynamic programming for expectation.

Let dp_i denote the expected number of days to become happy starting from day i. When asking mirror i:

• With probability p_i/100 (mirror says yes), we contribute p_i × (dp_{i-1} + 1), where dp_{i-1} represents the expected days before reaching mirror i, plus 1 for the current day.
• With probability (1 - p_i/100) (mirror says no), we return to the beginning. The contribution is (1 - p_i/100) × (dp_{i-1} + 1 + dp_i), accounting for the days before reaching i, the current day, and the expected remaining days dp_i to reach happiness from mirror i again.

The recurrence relation becomes:

[dp_i = \frac{p_i}{100}(dp_{i-1}+1) + \left(1-\frac{p_i}{100}\right)(dp_{i-1}+1+dp_i)]

Simplifying:

[dp_i = \frac{100(dp_{i-1}+1)}{p_i}]

This gives us a linear recurrence that can be computed iteratively.

Implementation

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const i64 MOD = 998244353;

i64 modPow(i64 base, i64 exp) {
    i64 result = 1;
    while (exp > 0) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

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

    i64 numMirrors;
    cin >> numMirrors;

    vector<i64> dp(numMirrors + 1), prob(numMirrors + 1);

    for (int i = 1; i <= numMirrors; i++) {
        cin >> prob[i];
        dp[i] = ((dp[i - 1] + 1) * 100 % MOD * modPow(prob[i], MOD - 2)) % MOD;
    }

    cout << dp[numMirrors] << '\n';
    return 0;
}

D - Equation with Three Fractions

AtCoder - tenka1_2017_c

Problem Statement

Given a positive integer N, find any solution (h, n, w) that satisfies:

[\frac{4}{N} = \frac{1}{h} + \frac{1}{n} + \frac{1}{w}]

Output the values h, n, w.

Solution Approach

Enumerate two variables and determine if the third satisfies the equation.

From the equation:

[\frac{4}{N} = \frac{1}{h} + \frac{1}{n} + \frac{1}{w}]

Rearranging for w:

[\frac{1}{w} = \frac{4}{N} - \frac{1}{h} - \frac{1}{n}]

[\frac{1}{w} = \frac{4hn - N(h + n)}{Nhn}]

[w = \frac{Nhn}{4hn - N(h + n)}]

We iterate over reasonable bounds for h and n, checking if w is a positive integer.

Implementation

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

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

    int targetN;
    cin >> targetN;

    const int UPPER_BOUND = 3500;

    for (int first = 1; first <= UPPER_BOUND; first++) {
        for (int second = 1; second <= UPPER_BOUND; second++) {
            i64 numerator = 1LL * first * second * targetN;
            i64 denominator = 4 * first * second - targetN * (first + second);
            
            if (denominator <= 0) continue;
            if (numerator % denominator == 0) {
                cout << first << ' ' << second << ' ' << numerator / denominator << '\n';
                return 0;
            }
        }
    }

    return 0;
}

E - Counting Box Combinations

AtCoder - diverta2019_b

Problem Statement

Snuke visits a shop selling boxes containing balls. The shop offers three types of boxes:

• Red boxes, each containing R red balls
• Green boxes, each containing G green balls
• Blue boxes, each contaniing B blue balls

Snuke wants to buy r red boxes, g green boxes, and b blue boxes to obtain exactly N balls total. How many non-negative integer pairs (r, g, b) satisfy this condition?

Solution Approach

Precompute the number of ways to purchase one type of box, then enumerate the other two types. For each combination, check if the remaining balls can be purchased using the precomputed box type.

Implementation

#include <bits/stdc++.h>

using namespace std;

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

    int redCount, greenCount, blueCount, totalBalls;
    cin >> redCount >> greenCount >> blueCount >> totalBalls;

    const int MAX_RANGE = 3010;
    vector<int> feasible(MAX_RANGE, 0);
    
    int mult = 0;
    while (mult * blueCount <= totalBalls) {
        feasible[mult * blueCount] = 1;
        mult++;
    }

    int result = 0;
    for (int i = 0; i <= MAX_RANGE; i++) {
        for (int j = 0; j <= MAX_RANGE; j++) {
            int ballsUsed = i * redCount + j * greenCount;
            if (ballsUsed > totalBalls) break;
            result += feasible[totalBalls - ballsUsed];
        }
    }

    cout << result << '\n';
    return 0;
}

F - Maximizing Substring Occurrences

AtCoder - diverta2019_c

Problem Statement

Given n strings, find the maximum number of "AB" substrings that can appear when concatenating them in any order.

Solution Approach

Count strings starting with 'B' and ending with 'A' (BA-type strings). The intuitive solution takes the minimum of these counts, but this misses a crucial case.

When a string both starts with 'B' and ends with 'A' (BA-string), if we have k such strings, they can only produce k-1 "AB" pairs when connected together, like (B...A|B...A).

However, we can pair one BA-string with one A-ending string and one B-starting string to create 2 "AB" occurrences, converting the BA-string into a non-BA string. With m BA-strings, they contribute m-1 "AB" pairs when all connected, plus additional pairs from mixing.

Implementation

#include <bits/stdc++.h>

using namespace std;

int prefixCount[30], suffixCount[30], hybridCount[30][30];

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

    int numStrings;
    cin >> numStrings;

    vector<string> strs(numStrings);
    for (auto &s : strs) cin >> s;

    int baseCount = 0;
    for (const auto &s : strs) {
        for (size_t i = 0; i + 1 < s.size(); i++) {
            if (s.substr(i, 2) == "AB") baseCount++;
        }
        
        int firstChar = s.front() - 'A';
        int lastChar = s.back() - 'A';
        
        if (firstChar == 1 && lastChar == 0) {
            hybridCount[firstChar][lastChar]++;
        } else {
            prefixCount[firstChar]++;
            suffixCount[lastChar]++;
        }
    }

    if (hybridCount[1][0] > 0) {
        if (prefixCount[1] > 0 && suffixCount[0] > 0) {
            prefixCount[1]--;
            suffixCount[0]--;
            baseCount += 2;
        }
        hybridCount[1][0]--;
    }

    cout << baseCount + min(prefixCount[1], suffixCount[0]) + hybridCount[1][0] << '\n';
    return 0;
}

G - Summing Valid Divisors

AtCoder - diverta2019_d

Problem Statement

Given a positive integer n, find the sum of all positive integers m such that the quotient of n divided by m equals the remainder of n divided by m.

Solution Approach

Let the quotient be k. Since quotient equals remainder, we have: n = k × m + k = k × (m + 1)

Thus, m = n/k - 1.

Since the divisor must be greater than the remainder: m > k.

Therefore: n = k(m+1) > k(k+1)

We iterate k while k(k+1) < n, checking if n is divisible by k.

Implementation

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

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

    i64 target;
    cin >> target;

    i64 sum = 0;
    for (i64 k = 1; k * (k + 1) < target; k++) {
        if (target % k == 0) {
            sum += (target / k - 1);
        }
    }

    cout << sum << '\n';
    return 0;
}

H - Longest Valid Subsequence

AtCoder - abl_d

Problem Statement

Given a sequence A_1, A_2, ..., A_N and an integer K. Let B be a subsequence of A where the absolute difference between any two adjacent elements in B is at most K. Find the maximum possible length of B.

Solution Approach

Define dp_i as the length of the longest valid subsequence ending at position i.

The transition requires finding the maximum dp_j for all j < i where |A_i - A_j| ≤ K.

This is equivalent to querying the maximum value in the range [A_i - K, A_i + K], then updating position A_i with dp_i = max_in_range + 1.

Both operations (range maximum query and point update) are efficiently supported by a segment tree.

Implementation

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

#define LEFT_CHILD node << 1
#define RIGHT_CHILD node << 1 | 1

const int MAX_VALUE = 300000 + 10;

struct SegTree {
    int l, r, maxVal;
} tree[MAX_VALUE << 2];

void mergeNode(int node) {
    tree[node].maxVal = max(tree[LEFT_CHILD].maxVal, tree[RIGHT_CHILD].maxVal);
}

void build(int node, int l, int r) {
    tree[node] = {l, r, 0};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(LEFT_CHILD, l, mid);
    build(RIGHT_CHILD, mid + 1, r);
    mergeNode(node);
}

void update(int node, int position, int value) {
    if (tree[node].l == tree[node].r) {
        tree[node].maxVal = value;
        return;
    }
    int mid = (tree[node].l + tree[node].r) >> 1;
    if (position <= mid) update(LEFT_CHILD, position, value);
    else update(RIGHT_CHILD, position, value);
    mergeNode(node);
}

int query(int node, int left, int right) {
    if (left <= tree[node].l && tree[node].r <= right) {
        return tree[node].maxVal;
    }
    int result = 0;
    int mid = (tree[node].l + tree[node].r) >> 1;
    if (left <= mid) result = max(result, query(LEFT_CHILD, left, right));
    if (right > mid) result = max(result, query(RIGHT_CHILD, left, right));
    return result;
}

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

    int length, threshold;
    cin >> length >> threshold;

    const int VALUE_RANGE = 300000;
    build(1, 1, VALUE_RANGE);

    for (int i = 1; i <= length; i++) {
        int currentVal;
        cin >> currentVal;
        
        int queryLeft = max(0, currentVal - threshold);
        int queryRight = min(VALUE_RANGE, currentVal + threshold);
        update(1, currentVal, query(1, queryLeft, queryRight) + 1);
    }

    cout << tree[1].maxVal << '\n';
    return 0;
}