A. Omkar and Password

Given a sequence of integres, we can merge adjacent disitnct elements into their sum. The goal is to minimize the final sequence length.

If all elements are equal, no merges are possible and the result is the original length. Otherwise, we can always reduce the sequence to a single element by repeatedly merging with the maximum value. The solution checks for uniform values and returns 1 or n according.

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        
        bool all_equal = true;
        for (int i = 1; i < n; ++i) {
            if (a[i] != a[0]) {
                all_equal = false;
                break;
            }
        }
        
        cout << (all_equal ? n : 1) << endl;
    }
    return 0;
}

B. Omkar and Infinity Clock

After k operations, each element a[i] transforms based on the max and min values in the sequence. The transformation alternates between (max - a[i]) and (a[i] - min) for odd and even k respectively.

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        
        int max_val = *max_element(a.begin(), a.end());
        int min_val = *min_element(a.begin(), a.end());
        
        if (k % 2 == 1) {
            for (int i = 0; i < n; ++i) cout << max_val - a[i] << " ";
        } else {
            for (int i = 0; i < n; ++i) cout << a[i] - min_val << " ";
        }
        cout << endl;
    }
    return 0;
}

C. Omkar and Waterslide

We need to count how many operations are required to make the sequence non-decreasing, where each operation increases a non-decreasing subsegment by 1.

The solution works by calculating the required increases between adjacent elements where the sequence decreases.

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        
        long long ans = 0;
        for (int i = 1; i < n; ++i) {
            if (a[i] < a[i-1]) {
                ans += a[i-1] - a[i];
            }
        }
        cout << ans << endl;
    }
    return 0;
}

D. Omkar and Bed Wars

We need to find the minimum number of changes to make a circular attack pattern valid. Valid patterns include "RL", "RLL", "RRL", and "RRLL".

The solution uses dynamic programming to track minimum changes needed for valid patterns up to each position.

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

int count_changes(const string& a, const string& b) {
    int changes = 0;
    for (int i = 0; i < a.size(); ++i)
        if (a[i] != b[i]) ++changes;
    return changes;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        
        int min_changes = INT_MAX;
        for (int shift = 0; shift < 4; ++shift) {
            vector<int> dp(n+2, INT_MAX);
            dp[0] = 0;
            
            for (int i = 2; i <= n; ++i) {
                if (i-2 >= 0) 
                    dp[i] = min(dp[i], dp[i-2] + count_changes("RL", s.substr(i-2, 2)));
                
                if (i-3 >= 0) {
                    dp[i] = min(dp[i], dp[i-3] + min(
                        count_changes("RRL", s.substr(i-3, 3)),
                        count_changes("RLL", s.substr(i-3, 3))
                    ));
                }
                
                if (i-4 >= 0)
                    dp[i] = min(dp[i], dp[i-4] + count_changes("RRLL", s.substr(i-4, 4)));
            }
            min_changes = min(min_changes, dp[n]);
            rotate(s.begin(), s.begin()+1, s.end());
        }
        cout << min_changes << endl;
    }
    return 0;
}

E. Omkar and Duck

For this interactive problem, we need to construct a matrix that allows us to find a unique path for any given sum x from the top-left to bottom-right corner.

We construct the matrix using powers of 2 in a specific pattern that ensures each path gives a unique sum. For queries, we follow a path based on the binary representation of x.

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

const int MAXN = 30;
int matrix[MAXN][MAXN];

int main() {
    int n;
    cin >> n;
    
    // Construct matrix
    for (int i = n-1; i >= 0; --i) {
        for (int j = n-1; j >= 0; --j) {
            if (j == 0 || i == n-1) 
                matrix[i][j] = 1 << (i + j);
            else if (j == 1 || i == n-2) 
                matrix[i][j] = 0;
            else 
                matrix[i][j] = matrix[i+2][j-2];
        }
    }
    
    // Output matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    
    int q;
    cin >> q;
    
    while (q--) {
        int x;
        cin >> x;
        
        int r = 0, c = 0;
        cout << r+1 << " " << c+1 << endl;
        
        for (int i = 0; i < 2*n - 2; ++i) {
            if ((x >> i & 1) == (matrix[r+1][c] >> i & 1)) ++r;
            else ++c;
            cout << r+1 << " " << c+1 << endl;
        }
    }
    return 0;
}