Score: 260 points | Rank: 3rd

• T1: 100 points
• T2: 100 points
• T3: 60 points
• T4: 0 points

Problem Solutiosn

T1 - Sequence Generaiton

Standard simulation problem. For each sequence iteration, count consecutive digits from the previous sequence.

#include <bits/stdc++.h>
using namespace std;

string sequence[30];

int main() {
    int n;
    cin >> n;
    sequence[1] = "1";
    
    for (int i = 2; i <= n; i++) {
        int counter = 0;
        
        for (int j = 0; j < sequence[i-1].size(); j++) {
            counter++;
            
            if (j == sequence[i-1].size()-1 || sequence[i-1][j] != sequence[i-1][j+1]) {
                sequence[i] += to_string(counter) + sequence[i-1][j];
                counter = 0;
            }
        }
    }
    
    cout << sequence[n];
    return 0;
}

T2 - Index Maintenance

Approach 1 - Binary Indexed Tree with Binary Search

Leverages BIT for range updates and binary search for O(log²n) complexity per query.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e7+5;
int tree[MAXN];

int lowbit(int x) {
    return x & -x;
}

void update(int idx, int val) {
    while (idx < MAXN) {
        tree[idx] += val;
        idx += lowbit(idx);
    }
}

int query(int idx) {
    int res = 0;
    while (idx > 0) {
        res += tree[idx];
        idx -= lowbit(idx);
    }
    return res;
}

Approach 2 - Brute Force with Optimization

Exploits the monotonic property of the array after adjustments. Time complexity O(k²logn).

struct Adjustment {
    int left, right, value;
};

int main() {
    int n, k;
    cin >> k >> n;
    vector<int> values(n+1);
    
    for (int i=1; i<=n; i++) {
        cin >> values[i];
        values[i] -= i;
    }
    
    vector<Adjustment> ops(k);
    
    for (int i=0; i<k cin="" i="">> ops[i].left >> ops[i].right >> ops[i].value;
    }
    
    // Binary search implementation follows...
}</k>

T3 - Odd Count Analysis

Prefix sum approach for small constraints (ai ≤ 10). Complete solution handles up to 100,000 elements.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5+5;
int prefix[11][MAXN];

int main() {
    int n, q;
    cin >> n;
    
    for (int i=1; i<=n; i++) {
        int val;
        cin >> val;
        
        for (int d=1; d<=10; d++) {
            prefix[d][i] = prefix[d][i-1];
        }
        
        if (val <= 10) prefix[val][i]++;
    }
    
    cin >> q;
    for (int i=0; i<q cin="" i="" int="" l="" r="">> l >> r;
        int result = 0;
        
        for (int d=1; d<=10; d++) {
            if ((prefix[d][r] - prefix[d][l-1]) % 2 != 0)
                result++;
        }
        
        cout << result << endl;
    }
}</q>

T4 - Binary Tree Enumeration

Combinatorial solution using Catalan numbers and mathematical derivation:

• f(n) = Catalan(n) = (2n)!/(n!(n+1)!))
• g(n) = f(n-1) × n
• Final ratio: g(n)/f(n) = n(n+1)/(2(2n-1))

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 2147483647;

ll fast_power(ll base, ll exp) {
    ll result = 1;
    while (exp) {
        if (exp % 2) result = result * base % MOD;
        base = base * base % MOD;
        exp /= 2;
    }
    return result;
}

int main() {
    ll n;
    cin >> n;
    ll numerator = n * (n + 1) % MOD;
    ll denominator = 2 * (2 * n - 1) % MOD;
    ll inverse_denominator = fast_power(denominator, MOD-2);
    cout << (numerator * inverse_denominator) % MOD;
}