663295A — Jack and time

This problem is a straightforward one involving conversion of total seconds into hours, minutes, and seconds.

We know:

• 1 hour = 3600 seconds

• 1 minute = 60 seconds

So the conversion goes as: let $$$s$$$ be the seconds, $$$hours = s \div 3600$$$, $$$remaining = s \bmod 3600$$$, $$$minutes = remaining \div 60$$$, $$$seconds = remaining \bmod 60$$$.

The challenge is mostly in formatting: we must print all three components with exactly 2 digits (e.g., 01:09:03, not 1:9:3). You can use if to do that. There are other ways to do this, but this is good enough.

#include <bits/stdc++.h>
#define ll long long

using namespace std;

void solve() {
    ll seccond; 
    cin >> seccond;
    
    ll h = seccond / 3600;
    ll m = (seccond % 3600) / 60;
    ll s = seccond % 60;
    
    if (h < 10) cout << "0";
    cout << h << ":";
    
    if (m < 10) cout << "0";
    cout << m << ":";
    
    if (s < 10) cout << "0";
    cout << s << "\n";
}

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

    ll t; 
    cin >> t;
    while (t--) solve();

    return 0;
}

663295B — Palindromic Subsequence

This problem might look hard if you don't think carefully, but it is actually very easy.

To solve this, you can see a palindrome is the same in both halves of the string, so what if...the string is length $$$2$$$, you have to have $$$2$$$ same character, string "aa" and "bb" is a palindrome.

So the solution is just counting the occurrences of all the characters and if none of them has a count of greater or equal than $$$2$$$, you print $$$-1$$$. Else, print any character of occurrence count greater or equal than $$$2$$$, $$$2$$$ times.

#include<bits/stdc++.h>
#define ll long long

using namespace std;

void solve() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    map<char, ll> occ;
    for (ll i = 0; i < n; i++) {
        occ[s[i]]++;
    }
        
    for (auto it = occ.begin(); it != occ.end(); it++) {
        if (it->second >= 2) {
            char l = it->first;
            cout << l << l << endl;
            return;
        }
    }
    cout << -1 << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll t; cin >> t;
    while (t--) solve();

    return 0;
}

663295C — Palindromic Substring

The solution is just seeing there is a palindromic substring, if there is, you don't need any operations, so print $$$0$$$. If there isn't, you need $$$1$$$ operation to make a substring of length $$$2$$$ a palindrome. This can be easily done in $$$\mathcal{O}(n^3)$$$ and $$$2 \le n \le 20$$$, so the brute force is acceptable.

#include<bits/stdc++.h>
#define ll long long

using namespace std;

void solve() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    for (ll i = 0; i < n - 1; i++) {
        string temp;
        for (ll j = i; j < n; j++) {
            temp += s[i];
            string rev = temp;
            reverse(rev.begin(), rev.end());
            if (rev == temp) {
                cout << 0 << endl;
                return;
            }
        }
    }
    cout << 1 << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    ll t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

663295C — Palindromic Substring

But $$$\mathcal{O}(n^3)$$$ time can be optimized up to $$$\mathcal{O}(n)$$$!

Instead of checking every possible substring, only check substrings of length 2 and 3 If there is for example a substring "abcba" in s, then a 3-length substring "bcb" would also be valid! Proving that the solution is correct!

def solve():
    n = int(input())
    s = input()

    for i in range(n - 1):
        if s[i] == s[i + 1]:
            print(0)
            return
    for i in range(n - 2):
        if s[i] == s[i + 2]:
            print(0)
            return
    print(1)

for i in range(int(input())): solve()

663295D — Dino and Game

This is a math problem involving finding the least $$$n$$$ so that:

If the sum $$$\frac{n(n+1)}{2}$$$ is $$$\textbf{not equal}$$$ to $$$x$$$, we can immediately print $$$-1$$$, since it’s impossible to end the game on that exact move.

Otherwise, we check who made the last move:

• If $$$n$$$ is even, then Dino played last, so Rex wins.
• If $$$n$$$ is odd, then Rex played last, so Dino wins.

How to calculate $$$n$$$:

• Let the sum be $$$y = \frac{n(n+1)}{2}$$$. To make it easier to solve for $$$n$$$, we clear the denominator by multiplying both sides by $$$2$$$:

• We want to find the smallest $$$n$$$ such that:

• We estimate a starting point for $$$n$$$ using:

• To avoid floating-point inaccuracies, we loop from:

...upward until we find the smallest $$$n$$$ such that $$$\frac{n(n+1)}{2} \ge x$$$. Once found, if the sum is exactly equal to $$$x$$$, we check $$$n$$$ to determine the winner or if no one, we output $$$-1$$$.

#include<bits/stdc++.h>
#define ll long long

using namespace std;

void solve() {
    ll n;
    cin >> n;
    ll start = max((ll)sqrtl(n * 2) - 5, 0LL);
    for (ll i = start; true; i++) {
        ll sum = i * (i + 1) / 2;
        if (sum == n) {
            cout << (i % 2 == 0 ? "Rex" : "Dino") << endl;
            return;
        } else if (sum > n) {
            cout << -1 << endl;
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll t; cin >> t;
    while (t--) solve();

    return 0;
}

663295E — Sum Digital Root

The $$$\textit{digital root}$$$ of a number is the value obtained by repeatedly summing the digits of a number until a single-digit number is obtained. Mathematically, we can express the digital root of a positive integer $$$x$$$ as:

This formula follows from the properties of numbers in base 10 and their behavior modulo 9. Using this, we can observe the following: $$$\text{dr}(1) = 1, \text{dr}(2) = 2, \text{dr}(3) = 3,..., \text{dr}(9) = 9, \text{dr}(10) = 1, \text{dr}(11) = 2,...$$$

This clearly shows that the sequence of digital roots follows a cycle:

So the pattern repeats every 9 numbers. This allows us to compute the sum of the digital roots of the first $$$n$$$ numbers efficiently.

Let:

• $$$q = \left\lfloor \frac{n}{9} \right\rfloor$$$ be the number of full blocks,

• $$$r = n \bmod 9$$$ be the number of leftover values.

Each full block has the same digital roots: $$$1 + 2 + \cdots + 9 = 45$$$. So the total contribution from full blocks is $$$45 \cdot q$$$.

The remaining $$$r$$$ numbers have digital roots $$$1, 2, \ldots, r$$$, so they add up to:

Putting it all together, the final formula for the sum is:

Time Complexity: $$$\mathcal{O}(1)$$$

#include<bits/stdc++.h>
#define ll long long

using namespace std;

void solve() {
    ll n;
    cin >> n;
    ll r = n - (ll)(n / 9) * 9;
    cout << 45 * (ll)(n / 9) + (r * (r + 1)) / 2 << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    ll t; cin >> t;
    while (t--) solve();

    return 0;
}

663295F — Elevator

We simulate the elevator's movement:

Let the elevator start at floor 0. For each destination $$$m_i$$$:

• Let $$$f = |m_i - \text{current floor}|$$$ be the number of floors to move.

• If $$$m_i \gt \text{current floor}$$$, then the elevator moves up, taking $$$f \cdot u$$$ seconds.

• Otherwise, it moves down, taking $$$f \cdot d$$$ seconds.

• The number of rest stops is:

• Add $$$\text{rs} \cdot r$$$ to the total time.
• Set the current floor to $$$m_i$$$ and repeat.

Time Complexity: $$$\mathcal{O}(n)$$$ for each test case.

#include<bits/stdc++.h>
#define ll long long

using namespace std;

void solve() {
    ll n, a, b, k, r;
    cin >> n >> a >> b >> k >> r;
    ll ans = 0, curr = 0;
    for (ll i = 0; i < n; i++) {
        ll temp;
        cin >> temp;
        if (temp == curr) continue;
        ll f = abs(curr - temp);
        ll costSteps = (f * (curr > temp ? a : b));
        ll timeStops = (f / k - (!(f % k))) * r;
        ans += costSteps + timeStops;
        curr = temp;
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    ll t; cin >> t;
    while (t--) solve();

    return 0;
}

663295G — Kun and Palindrome

First, check if the length of the number is $$$1$$$. If it is, simply print the number itself since it's already a palindrome.

Otherwise, count the occurrences of each digit in the number. To form a valid palindrome, at most one digit can have an odd frequency, one occurrence of this digit must be placed in the center, and the rest of its occurrences should be evenly divided between the first and second halves of the palindrome.

If there are more than $$$1$$$ type of digits that have odd frequency, print $$$-1$$$ because a valid palindrome can have at most one digit with an odd frequency (in the center).

Next, for each digit, if it is a $$$0$$$, skip it — we will handle it later. Otherwise, take half of the occurrences of each digit. Also, for the digit which has an odd frequency, take $$$\left\lfloor \frac{f_d}{2} \right\rfloor$$$ of its occurrences, and sort them in increasing order. This will be the first half of the palindrome.

If the first half is empty after this step, it means we only had zeros — which would result in a leading zero — so print $$$-1$$$.

Now, insert the skipped zeros at position $$$1$$$ (i.e., after the first digit) in the half if needed. This prevents leading zeros while still using all digits.

Then, form the second half by reversing the first half.

If there was a digit with an odd occurrence, place one of it in the middle.

#include <bits/stdc++.h>
#define ll long long

using namespace std;

void solve() {
    string s;
    cin >> s;
    
    if (s.length() == 1) {
        cout << s << endl;
        return;
    }
    
    ll len = s.length();
    map<char, ll> occ;
    for (ll i = 0; i < len; i++) occ[s[i]]++;
    
    ll oddOcc = 0;
    char mid = '-';
    
    for (auto it = occ.begin(); it != occ.end(); it++) {
        if (it->second % 2 == 1) {
            mid = it->first;
            oddOcc++;
            if (oddOcc > 1) {
                cout << -1 << endl;
                return;
            }
        }
    }
    
    string half;
    for (auto [ch, count] : occ) {
        if (ch == '0') continue;
        half += string(count / 2, ch);
    }
    sort(half.begin(), half.end());
    
    if (half.length() == 0) {
        cout << -1 << endl;
        return;
    }
    string part0;
    auto it2 = occ.begin();
    if (it2->first == '0') {
        for (ll i = 0; i < it2->second / 2; i++) {
            part0 += "0";
        }
        
        half = half[0] + part0 + half.substr(1, half.length());
    }
    
    string half2 = half;
    reverse(half2.begin(), half2.end());
    
    if (mid == '-') cout << half + half2 << endl;
    else cout << half + mid + half2 << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    ll t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

663295H — Mario and pipes

As you can see, this is a classic DP problem.

Let $$$\text{dp}[i]$$$ (1-based) be the minimum total cost needed to reach pipe $$$i$$$.

• Initialize $$$\text{dp}_1 = c_1$$$ (Mario starts here for $$$c_1$$$ (array c is 1-based)).
• For all other $$$i$$$, initialize $$$\text{dp}_i = \infty$$$ (unreachable at first).

Then, for each pipe $$$i$$$ from $$$1$$$ to $$$n - 1$$$, we try all jump lengths $$$a_j$$$ for all $$$j$$$ from $$$0$$$ to $$$m - 1$$$ ($$$0$$$-based):

This transition means: from pipe $$$i$$$, we try jumping to all allowed destinations, and update the cost if it improves.

Final Answer:

After filling the $$$dp$$$ array, the answer is:

• If $$$\text{dp}_n \lt \infty$$$, print $$$\text{dp}_n$$$
• Otherwise, print $$$-1$$$

#include<bits/stdc++.h>
#define ll long long

using namespace std;

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<ll> c(n + 1);
    c[0] = 0;
    c[n] = 0;
    for (ll i = 1; i < n; i++) {
        cin >> c[i];
    }
    vector<ll> a(m);
    for (ll i = 0; i < m; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    
    vector<ll> dp(n + 1, LLONG_MAX);
    dp[1] = c[1];
    for (ll i = 1; i < n; i++) {
        if (dp[i] == LLONG_MAX) {
            continue;
        }
        for (auto x : a) {
            if (i + x > n) {
                break;
            }
            dp[i + x] = min(dp[i + x], dp[i] + c[i + x]);
        }
    }
    cout << (dp[n] == LLONG_MAX ? -1 : dp[n]) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    ll t = 1; cin >> t;
    while (t--) solve();

    return 0;
}

663295I — Magical Box

First, reduce all elements of the array $$$a \bmod m$$$, storing the results in $$$a$$$ new array $$$b$$$. This transformation ensures that all values in $$$b$$$ lie in the range $$$[0, m - 1]$$$.

Notice that $$$b$$$ can contain at most $$$m$$$ distinct values due to the modulo operation. This observation allows us to try a surprisingly efficient brute-force approach: iterate over all possible pairs of values in b and check whether their product is divisible by $$$m$$$.

Time complexit: $$$\mathcal{O}(m^2)$$$ for each test case. Since the number of distinct remainders is at most $$$m$$$, this brute-force method runs very fast.

from collections import defaultdict

def solve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    b = defaultdict(int)
    for i in a:
        b[i % m] += 1
    
    l = len(b)
    pair = ()
    for i in b:
        for j in b:
            if i == j and b[i] == 1:
                continue
            if (i * j) % m == 0:
                pair = (i, j)
                break

        if pair:
            break

    if pair == ():
        print(-1)
    else:
        vali = 0
        valj = 0
        for i in a:
            if vali and valj:
                break

            if i % m == pair[0] and not vali:
                vali = i
            elif i % m == pair[1]:
                valj = i

        print(vali, valj)

def main():
   t = 1
   t = int(input())
   while t:
       t -= 1
       solve()

if __name__ == '__main__':
   main()

663295I — Magical Box

We can see that these are basic maths:

• If any element $$$a[i]$$$ is divisible by $$$m$$$, then: $$$a[i] \cdot a[j] \equiv 0 \pmod{m}$$$ for any $$$j \neq i$$$, so we can return $$$(a[i], a[j])$$$ directly.

• If $$$m$$$ is prime, then only a number divisible by $$$m$$$ can make the product divisible by $$$m$$$.

• If $$$m$$$ is not prime, then we can break $$$m$$$ into smaller factors:

So, we just need to find two elements where one is divisible by one factor and the other is divisible by the other.

Strategy:

Let $$$\text{multiple}$$$ be a vector of size 2 containing the factors of $$$m$$$, if $$$m$$$ is not prime. Otherwise, it will be empty.

Case 1: $$$\text{multiple}$$$ is empty (i.e., $$$m$$$ is prime)

• Scan the array $$$a$$$ for any element divisible by $$$m$$$.

• Return that element along with one of its neighbors.

Case 2: $$$\text{multiple}$$$ is not empty (i.e., $$$m$$$ is composite and has two factors)

• Scan the array $$$a$$$ if any element divisible by any factor and check for the second one.

• Return the two element you found.

Time Complexity: $$$\mathcal{O}(n)$$$ because it scans the entire array once.

#include<bits/stdc++.h>
#define ll long long

using namespace std;

pair<ll, ll> findMultiple(vector<ll> a, ll n, vector<ll> multiple, ll m) { //  length multiple either 0 (prime) or 2
    if (multiple.empty()) {
        for (ll i = 0; i < n; i++) {
            if (a[i] % m == 0) {
                if (i == 0) {
                    //  i + 1 is safe because i = 0 so i + 1 = 1 and n >= 2
                    return {a[i + 1], a[i]};
                } else {
                    return {a[i - 1], a[i]};
                }
            }
        }
        return {-1, -1};
    }
    
    ll firstVal = -1, secondVal = -1, mBothVal = -1;
    bool found1 = false, found2 = false, modBoth = false;
    for (ll i = 0; i < n; i++) {
        if (a[i] % m == 0) {
            if (i == 0) {
                return {a[i + 1], a[i]};
            } else {
                return {a[i - 1], a[i]};
            }
        }

        //  Is divisible by both factors
        if (!modBoth && a[i] % multiple[0] == 0 && a[i] % multiple[1] == 0) {
            modBoth = true;
            mBothVal = a[i];
            if (found1 || found2) {
                return {(found1 ? firstVal : a[i]), (found2 ? secondVal : a[i])};
            }
            continue;
        }

        if (modBoth && (a[i] % multiple[0] == 0 || a[i] % multiple[1] == 0)) {
            return {mBothVal, a[i]};
        } else if (!modBoth) {
            //  Can not be divisible by both factors because already checked
            if (a[i] % multiple[0] == 0) {
                firstVal = a[i];
                found1 = true;
            }
            if (a[i] % multiple[1] == 0) {
                secondVal = a[i];
                found2 = true;
            }
            if (found1 && found2) {
                return {firstVal, secondVal};
            }
        }
    }
    return {-1, -1};
}

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector<ll> multiple = {};
    if (m == 4) {
        multiple = {2, 2};
    } else if (m == 6) {
        multiple = {2, 3};
    } else if (m == 8) {
        multiple = {2, 4};
    } else if (m == 9) {
        multiple = {3, 3};
    } else if (m == 10) {
        multiple = {2, 5};
    } else {
        //  Prime so no need to add anything
    }
    pair<ll, ll> b = findMultiple(a, n, multiple, m);
    if (b.first == -1) {
        cout << -1 << endl;
    } else {
        cout << b.first << " " << b.second << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    ll t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

663295J — Adjacent XORs

We can see if that if we XOR anything with it-self, we get $$$0$$$. If we break up $$$a_i \oplus a_{i + 1}$$$, we would get $$$(b_i \oplus b_{i + 1}) \oplus (b_{i + 1} \oplus b_{i + 2})$$$, $$$b_{i + 1} \oplus b_{i + 1}$$$ would cancel out and leave us with $$$b_i \oplus b_{i + 2}$$$. That's how we calculate $$$b_l \oplus b_r$$$! The same cancellation pattern continues if we XOR a whole block: $$$a_l \oplus a_{l+1} \oplus \dots \oplus a_{r-1} = b_l \oplus b_r$$$.

To optimize each queries, we use a $$$\textbf{0-indexed}$$$ prefix XOR (like prefix sum but XOR):

That means, $$$\text{pref}_i$$$ = $$$b_0 \oplus b_i$$$, then when $$$\text{pref}_{r - 1} \oplus \text{pref}_{l - 1}$$$, we have $$$(b_0 \oplus b_l) \oplus (b_0 \oplus b_r)$$$, $$$b_0$$$ cancels out and we are left with $$$b_l \oplus b_r$$$. That means $$$b_l \oplus b_r = \text{pref}_{r - 1} \oplus \text{pref}_{l - 1}$$$!

#include<bits/stdc++.h>
#define ll long long

using namespace std;

void solve() {
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) cin >> a[i];

    vector<ll> pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] ^ a[i];
    for (ll i = 0; i < q; i++) {
        ll l, r;
        cin >> l >> r;
        l--; r--;
        if (l == r) cout << 0 << endl;
        else if (l + 1 == r) cout << a[l] << endl;
        else cout << (pref[r] ^ pref[l]) << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    ll t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

663295K — Grandmaster and Chessboard

We can see that after connecting adjacent white and black cells, a covering correspond to a perfect matching between black and white cells. One can find the maximum matching and checking if its size equals to one half of the number of uncovered cells (i.e. the matching is perfect). Such a maximum matching may be found in $$$\mathcal{O}(n^3)$$$ using Hopkroft-Karp (the graph is bipartite and has $$$n^2$$$ edges). TC: $$$\mathcal{O}(n^3)$$$

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

struct HopcroftKarp {
    int n, m;
    vector<vector<int>> g;
    vector<int> dist, matchL, matchR;

    HopcroftKarp(int n, int m) : n(n), m(m) {
        g.assign(n, {});
        matchL.assign(n, -1);
        matchR.assign(m, -1);
        dist.resize(n);
    }

    void addEdge(int u, int v) {
        g[u].push_back(v);
    }

    bool bfs() {
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (matchL[i] == -1) {
                dist[i] = 0;
                q.push(i);
            } else dist[i] = -1;
        }

        bool reachable = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                int w = matchR[v];
                if (w != -1 && dist[w] == -1) {
                    dist[w] = dist[u] + 1;
                    q.push(w);
                }
                if (w == -1) reachable = true;
            }
        }
        return reachable;
    }

    bool dfs(int u) {
        for (int v : g[u]) {
            int w = matchR[v];
            if (w == -1 || (dist[w] == dist[u] + 1 && dfs(w))) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }

    int maxMatching() {
        int matching = 0;
        while (bfs()) {
            for (int i = 0; i < n; i++)
                if (matchL[i] == -1 && dfs(i))
                    matching++;
        }
        return matching;
    }
};

void solve() {
    int n;
    cin >> n;

    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<vector<int>> idL(n, vector<int>(n, -1));
    vector<vector<int>> idR(n, vector<int>(n, -1));

    int L = 0, R = 0, dots = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == '.') {
                dots++;
                if ((i + j) % 2 == 0) {
                    idL[i][j] = L++;
                } else {
                    idR[i][j] = R++;
                }
            }
        }
    }

    HopcroftKarp hk(L, R);

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (idL[i][j] != -1) {
                for (int d = 0; d < 4; d++) {
                    int ni = i + dx[d];
                    int nj = j + dy[d];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < n &&
                        idR[ni][nj] != -1) {
                        hk.addEdge(idL[i][j], idR[ni][nj]);
                    }
                }
            }
        }
    }

    int match = hk.maxMatching();
    cout << (match * 2 == dots ? "YES" : "NO") << endl;
}

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

    int t; 
    cin >> t;
    while (t--) solve();
}

663295L — Ducky Learns XORs

We know $$$x \oplus x = 0$$$. So we want to know how many times $$$a_i$$$ appears, if it appears even times we don't do anything (it cancels it self), else, we XOR the answer by $$$a_i$$$. To count how many times $$$i$$$ ($$$\textbf{1-indexed}$$$) appears in the subarrays, there are $$$i$$$ possible starting points for the subarray, and $$$n - i + 1$$$ possible ending points that contains $$$i$$$.

#include <bits/stdc++.h>
#define ll long long

using namespace std;

void solve() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) cin >> a[i];
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        //  i is currently 0-indexed so we use this
        if (((i + 1) * (n - i)) % 2 == 1) ans ^= a[i];
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    ll t = 1;
    cin >> t;
    while (t--) solve();
}

663295M — Palindrome Prefix

Note: the editorial might not be clear, if anyone has a better explanation of this greedy solution, please comment for me :)

Let the longest prefix of $$$s$$$ consisting only of $$$1$$$s have length $$$k$$$. For every $$$i \le k$$$, since $$$s_i = 1$$$, the prefix $$$t[1..i]$$$ must be a palindrome. This forces all characters in $$$t[1..k]$$$ to be equal.

Now consider positions $$$i \gt k$$$.

Now consider any block of consecutive $$$0$$$s in $$$s$$$ starting at position $$$l \gt k$$$, and let its length be $$$len$$$. For every position $$$i$$$ in this block, the prefix $$$t[1..i]$$$ must NOT be a palindrome. This means that for each such $$$i$$$, there must exist at least one index $$$j \le i$$$ such that $$$t_j \ne t_{i-j+1}$$$.

Since the first $$$k$$$ characters of $$$t$$$ are all equal, the only way to guarantee that the palindrome condition is broken for all $$$i$$$ in this block is to ensure that the mismatch happens within the last $$$k$$$ characters of the prefix. For example:

• $$$s = 1110001$$$, $$$t = 1110111$$$

• $$$s = 11100001$$$, $$$t = 11100111$$$

• $$$s = 11100010001$$$, $$$t = 11101110111$$$

• $$$s = 1110000100001$$$, $$$t = 1110011100111$$$

• But if $$$s = 11100010001$$$, notice the first $$$0$$$ block has length $$$3$$$ while the second has length $$$4$$$, it is impossible to construct $$$t$$$.

Therefore, all characters assigned in a block of $$$0$$$ s must be equal, otherwise, an earlier mismatch might disappear when the prefix grows, accidentally restoring the palindrome.

Moreover, the length of each block of $$$0$$$s must be at least $$$k$$$. If $$$len \lt k$$$, then when $$$i = l + len - 1$$$, the suffix of length $$$k$$$ of $$$t[1..i]$$$ lies entirely inside the initial prefix $$$t[1..k]$$$, which is constant. Hence, no mismatch exists, and $$$t[1..i]$$$ becomes a palindrome.

Thus, each block of consecutive $$$0$$$s must have length at least $$$k$$$, and all characters inside the block must be equal.

#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

void solve() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll cnt = 0, first = 0;
    bool found = false;
    for (ll i = 0; i < n; i++) {
        if (!found && s[i] == '1') first++;
        else if (s[i] == '1' && found) {
            cnt++;
            if (cnt == 2) {
                cout << -1 << endl;
                return;
            }
        } else {
            found = true;
            cnt = 0;
        }
    }
    if (first == 0) {
        cout << -1 << endl;
        return;
    }
    vector<ll> block;
    cnt = 0;
    for (ll i = 0; i < n; i++) {
        if (s[i] == '0') cnt++;
        else {
            if (cnt != 0) block.pb(cnt);
            cnt = 0;
        }
    }
    ll si = block.size();
    if (si == 0) {
        string ans;
        for (ll i = 0; i < first; i++) ans.pb('1');
        for (ll i = first; i < n; i++) ans.pb('0');
        cout << ans << endl;
        return;
    }
    if (block[0] < first) {
        cout << -1 << endl;
        return;
    }
    for (ll x : block) {
        if (x != block[0]) {
            cout << -1 << endl;
            return;
        }
    }
    string ans;
    for (ll i = 0; i < first; i++) ans.pb('1');
    for (ll i = 0; i < si; i++) {
        for (ll j = 0; j <= block[i] - first; j++) ans.pb('0');
        for (ll j = block[i] - first + 1; j < block[i] + 1; j++) ans.pb('1');
    }
    while (ans.size() < n) ans.pb('0');
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    ll t = 1;
    cin >> t;
    while (t--) solve();
}