Print FCDS

#include <iostream>

using namespace std;

int main() {
    cout << "FCDS" << endl;
}

Notice that the values of $$$a_i$$$ are bounded: $$$(1 \le a_i \le 100)$$$.

It is easy to see that the $$$O(N^2)$$$ brute-force approach will be too slow for the given constraints. Therefore, we need a faster way to count, for each $$$i$$$, how many indices $$$j \gt i$$$ satisfy $$$(a_i \gt a_j)$$$.

Since that the values of $$$a_i$$$ are bounded: $$$(1 \le a_i \le 100)$$$, we can use a frequency array to count how many numbers smaller than a given value appear to its right.

We process the array from right to left, keeping track of how many times each number has appeared so far. For each $$$a_i$$$, we check all numbers smaller than $$$a_i$$$ in the frequency array and add their counts to the answer.

After counting, we increment the frequency of $$$a_i$$$ by 1.

This works efficiently because the maximum value is only 100, so checking all smaller numbers takes at most 100 steps for each element. The overall complexity is $$$O(N \cdot 100)$$$ which simplifies to $$$O(N)$$$.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(ocate) ocate.begin(), ocate.end()
#define el "\n"
#define deb(x) cerr << #x << "=" << (x) << el;

void solve(const int& TESTCASE) {
    int n;
    cin >> n;

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

    int freq[101] = {0};
    long long ans = 0;

    for (int i = n - 1; i >= 0; --i) {
        int num = 0;
        
        for (int j = 0; j < a[i]; ++j) {
            num += freq[j];
        }

        ans += num;

        ++freq[a[i]];
    }

    cout << ans << el;
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int ___ = 1;
    // cin >> ___;

    for (int t = 1; t <= ___; ++t) solve(t);
}

The game consists of players picking numbers to add $$$(a_i \pmod K)$$$ to their scores. So the original values don't matter—only their remainders modulo $$$K$$$ matter.

First, compute $$$a_i$$$ % $$$K$$$ for each element and fix negative values to be in range $$$[0, K-1]$$$.

Important: The problem statement allows negative numbers. In many programming languages (like C++ , JAVA), the modulo operator % keeps the sign as it is. We must ensure the result is positive using the formula:

Both Mohamed and Kero want to maximize their total score. So the optimal move is always to pick the largest available value. If Mohamed skips the largest value, Kero will simply take it on the next turn, leaving Mohamed with a smaller gain.

Sort these values in descending order since each player always picks the maximum available value.

Mohamed takes values at even indices $$$(0, 2, 4, …)$$$ and Kero takes values at odd indices $$$(1, 3, 5, …)$$$.

If Mohamed’s total score is greater than Kero’s, print YES, otherwise print NO.

Time Complexity: $$$O(N \log N)$$$ for sorting.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    ll n,k;
    cin>>n>>k;
    vector<ll> v(n);
    for (ll i = 0; i < n; i++) cin>>v[i];
    for (ll i = 0; i < n; i++) {
        v[i]=((v[i]%k)+k)%k;
    }
    sort(v.begin(),v.end(),greater<ll>());
    ll suma=0,sumb=0;
    for (ll i = 0; i < n; i++) {
        if (i%2==0) suma+=v[i];
        else sumb+=v[i];
    }
    cout<<(suma>sumb?"YES":"NO")<<endl;
}

Simplify the given equation.

We can simplify the given equation into $$$b = 10^k - 1$$$ as follows

$$$a \cdot b + a = a \cdot 10^k$$$ (Take $$$a$$$ as common factor)

$$$a \cdot (b + 1) = a \cdot 10^k$$$ (Since $$$1 \le a \le 10^9$$$, we can divide both sides by $$$a$$$)

$$$b + 1 = 10^k$$$ (Rearrange)

$$$b = 10^k - 1$$$

This shows that $$$b$$$ must be of the form $$$9, 99, 999,\ldots$$$ (all 9s).

Notice that the value of $$$a$$$ does not affect the equation in this reduced form. Let $$$B$$$ denote the number of integers of the form $$$99\ldots9$$$ that are less than or equal to a given $$$b$$$. Then the final answer is:

$$$\text{Answer} = a \cdot B$$$

Time Complexity: $$$O(T \cdot \log_{10}(b))$$$, Where $$$T$$$ is the number of testcases.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(ocate) ocate.begin(), ocate.end()
#define el "\n"
#define deb(x) cerr << #x << "=" << (x) << el;

void solve(const int& TESTCASE) {
    int a, b;
    cin >> a >> b;
 
    long long cur = 9;
    int B = 0;
    while (cur <= b) {
        ++B;

        // append 9 to the end of cur
        cur *= 10;
        cur += 9;
    }
    
    cout << B * (long long)a << el;
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int ___ = 1;
    cin >> ___;

    for (int t = 1; t <= ___; ++t) solve(t);
}

Try to find the area of the triangle formed by the tangent line to $$$f(x) = \frac{1}{x}$$$ at any point $$$x_i$$$ with the coordinate axes. What do you notice?

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <chrono>
#include <thread>
#include<unordered_set>
#define all(a) (a).begin(),(a).end()
#define Yassin ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
#define e '\n'
#define ll long long 
#define ll long long 
#define lln long long n
#define ld long double
#define mod 1000000007
using namespace std;
const ll N = 2e5+100;

int main()
{
 Yassin
	ll a, b; cin >> a >> b;
	ll sum = b - a + 1;
	if (a <= 0 && b >= 0)sum -= 1;
	cout << sum * 2;
}

Instead of moving letters around, we simply count how many times each character appears in the input. Finally, we loop through the provided alphabet order and print each character as many times as we counted it. (Code 1, Code 2)

This approach Overall Time Complexity: $$$O(M + N)$$$, since $$$M$$$ is constant, therfore the overall Time Complexity is $$$O(N)$$$

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(ocate) ocate.begin(), ocate.end()
#define el "\n"
#define deb(x) cerr << #x << "=" << (x) << el;

void solve(const int& TESTCASE) {
    int n;
    cin >> n;

    int charFreq[26] = {0}, numFreq[10] = {0};
    for (int i = 0; i < n; ++i) {
        char x;
        cin >> x;

        if ('0' <= x && x <= '9') { // or isdigit(x)
            ++numFreq[x - '0'];
        } else {
            ++charFreq[x - 'A'];
        }
    }
    
    const string order = "7AB5CDE6FGHI3JKL1MNO9PQR2ST0UV4WXYZ8"; 
    const int M = order.size();
    for (int i = 0; i < M; ++i) {
        char c = order[i];
        if (isdigit(c)) {
            while (numFreq[c - '0']) {
                cout << c;

                --numFreq[c - '0'];
            }
        } else {
            while (charFreq[c - 'A']) {
                cout << c;
                
                --charFreq[c - 'A'];
            }
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int ___ = 1;
    // cin >> ___;

    for (int t = 1; t <= ___; ++t) solve(t);
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(ocate) ocate.begin(), ocate.end()
#define el "\n"
#define deb(x) cerr << #x << "=" << (x) << el;

void solve(const int& TESTCASE) {
    int n;
    cin >> n;

    // Instead of 2 separate arrays and handling indecies and if-else etc..
    // just allocate larger memory space and access with the ascii value of the char, A=65, 0=48 etc..
    // https://www.ascii-code.com/characters/printable-characters
    int freq[100] = {0};
    for (int i = 0; i < n; ++i) {
        char x;
        cin >> x;

        ++freq[x];
    }
    
    const string order = "7AB5CDE6FGHI3JKL1MNO9PQR2ST0UV4WXYZ8"; 
    const int M = order.size();
    for (int i = 0; i < M; ++i) {
        char c = order[i];
        while (freq[c]) {
            cout << c;
                
            --freq[c];
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int ___ = 1;
    // cin >> ___;

    for (int t = 1; t <= ___; ++t) solve(t);
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(ocate) ocate.begin(), ocate.end()
#define el "\n"
#define deb(x) cerr << #x << "=" << (x) << el;

int id[100] = {0};
bool compare(int a , int b){
    return id[a] < id[b]
}

void solve(const int& TESTCASE) {
    int n;
    string s;
    cin >> n >> s;

    const string order = "7AB5CDE6FGHI3JKL1MNO9PQR2ST0UV4WXYZ8"; 
    const int M = order.size();
    for (int i = 0; i < M; ++i) {
        id[order[i]] = i;
    }

    sort(s.begin(), s.end(), compare);

    cout << s << el;
}   

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int ___ = 1;
    // cin >> ___;

    for (int t = 1; t <= ___; ++t) solve(t);
}

At first, it may seem that we can simply sort the strings lexicographically then concatenating them.

However, this does not always produce the smallest possible concatenated string.

Why?

Because lexicographical comparison only compares strings individually, not based on how they behave when placed next to other strings.

When deciding whether string $$$s_1$$$ should come before string $$$s_2$$$, we must consider both possible concatenations: $$$s_1 + s_2$$$ and $$$s_2 + s_1$$$

• If $$$s_1 + s_2$$$ is smaller, then $$$s_1$$$ should come before $$$s_2$$$.
• Otherwise, $$$s_2$$$ should come before $$$s_1$$$.

Time Complexity: $$$O(n \log n)$$$

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(ocate) ocate.begin(), ocate.end()
#define el "\n"
#define deb(x) cerr << #x << "=" << (x) << el;

bool compare(string &a , string &b){
	return a+b < b+a;
}

void solve(const int& TESTCASE) {
    int n;
    cin >> n;

    string s[n];

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

    sort(s, s + n, compare);

    for (int i = 0; i < n; ++i) {
        cout << s[i];
    }
    cout << el;
}   

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int ___ = 1;
    // cin >> ___;

    for (int t = 1; t <= ___; ++t) solve(t);
}

Since we want to kill the maximum number, it makes total sense to start with the weakest ones. So we sort them ascendingly to get the weakest first, then we get the sum of their powers so we can maximize the number of kills as in the following example:

If they're in $$${5, 3, 1, 2}$$$ and our power is $$$6$$$:

So we should sort them to be: $$${1, 2, 3, 5}$$$ and then and only then we get the sum of their powers: $$${0, 1, 3, 6, 11}$$$ (There's $$$0$$$ in the beginning as it's prefix sum).

If our power is $$$5$$$, then we can kill the ones with powers $$$1$$$ and $$$2$$$.

We can get this number by getting the upper_bound of the prefix sum where the target is $$$5$$$:

This returns an iterator where it gets its reference in memory. Since we want to get the index, we should get it as following:

Algorithm time complexity:

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD_MAX = 1000000007;
// ONLY NEEDED IF IT'S FILE BASED PROBLEM
#define REDIRECT_FILE_TO_CIN freopen("problemname.in", "r", stdin);
#define REDIRECT_FILE_TO_COUT freopen("problemname.out", "w", stdout);

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;
    int arr[n];
    ll pref[n + 1];
    pref[0] = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    sort(arr, arr + n);
    for (int i = 1; i <= n; i++)
    {
        pref[i] = pref[i - 1] + arr[i - 1];
    }

    int q;
    cin >> q;

    while (q--)
    {
        ll power;
        cin >> power;
        auto it = upper_bound(pref, pref + n + 1, power);
        cout << (it - pref - 1) << '\n';
    }

    return 0;
}

Each ball contributes a cost equal to the distance it moves, so the total cost for box $$$i$$$ is the snumber of distances from all boxes containing balls to $$$i$$$.

We can compute this efficiently using two passes: from left to right to count balls and cost on the left, and from right to left for the right side.

At each position, we combine the cost from the left and the right to get the total operations needed.

This avoids the brute force solution and works in linear time $$$O(n)$$$.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    ll n; cin>>n;
    string s; cin>>s;
    vector<ll> pre(n), suf(n);
    ll cnt=0, sum=0;
    for(ll i=0;i<n;i++) {
        pre[i]=sum;
        if (s[i]=='1') cnt++;
        sum+=cnt;
    }
    cnt=0,sum=0;
    for(ll i=n-1;i>=0;i--) {
        suf[i]=sum;
        if (s[i]=='1') cnt++;
        sum+=cnt;
    }
    for(ll i=0;i<n;i++) cout<<pre[i]+suf[i]<<" ";
}

For each "closed bracket" $$$)$$$, we need another "open bracket" $$$($$$ for it so when we reverse the subsequence, we get a valid sequence.

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

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    string s;
    cin >> s;
    int open_needed = 0;
    int total_length = 0;
    for (char c : s)
    {
        if (c == ')')
        {
            open_needed++;
        }
        else
        {
            if (open_needed)
            {
                total_length += 2;
                open_needed--;
            }
        }
    }
    if (total_length)
    {
        cout << total_length;
    }
    else
    {
        cout << -1;
    }
    return 0;
}

Print FCDS

#include <iostream>

using namespace std;

int main() {
    cout << "FCDS" << endl;
}

The goal is to determine if we can find two integers $$$x, y \gt 1$$$ such that their sum equals $$$n$$$ and their greatest common divisor $$$gcd(x, y)$$$ is greater than $$$1$$$.

We can rewrite the equation $$$x + y = n$$$ by expressing $$$x$$$ and $$$y$$$ as multiples of their $$$gcd$$$ $$$(g)$$$:

• $$$x = g \cdot a$$$

• $$$y = g \cdot b$$$

Substituting these into the equation gives us:

Dividing both sides by $$$g$$$:

The problem provides two critical constraints:

1. The divisor condition: Since the problem states $$$g \gt 1$$$, $$$n$$$ must have a divisor larger than $$$1$$$.

2. The boundary condition: Since $$$x, y \gt 1$$$, then $$$a \neq 0$$$ and $$$b \neq 0$$$, so the smallest possible $$$(a + b) \ge 2$$$.

This implies that $$$g \neq n$$$, because if $$$g = n$$$, then $$$a + b = 1$$$, which would force one of the variables to be $$$0$$$.

Therefore, $$$g$$$ must be a proper divisor $$$(1 \lt g \lt n)$$$.

Conclusion

For a valid $$$g$$$ to exist, $$$n$$$ must be a composite number.

• If $$$n$$$ is prime, its only divisors are $$$1$$$ and $$$n$$$, which does not satisfy the constraints for $$$(1 \lt g \lt n)$$$.

• If $$$n$$$ is composite, we can always pick its smallest prime factor as $$$g$$$ and $$$a, b$$$ can be any two numbers that sum to $$$\frac{n}{g}$$$.

• Special Case: $$$n = 1$$$ is neither prime nor composite, but it cannot be split into two integers $$$ \gt 1$$$, so the answer is NO.

For example, if $$$n = 35$$$, $$$g = 5$$$, then $$$a = 1$$$ and $$$b = 6$$$ will result in $$$x = 5$$$ and $$$y = 30$$$ which is a valid pair since $$$gcd(5, 30) = 5 \gt 1$$$.

Complexity

Since $$$n$$$ can be up to $$$10^{12}$$$, we check for primality by searching for any divisor from $$$2$$$ up to $$$\sqrt{n}$$$ which result in $$$O(T \cdot \sqrt{n})$$$.

#include <iostream>

using namespace std;

// Standard primality test that returns true if n is prime or n = 1
bool is_prime(long long n) {
    if (n == 1) return true;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

void solve() {
    long long n;
    cin >> n;
    
    // The answer is NO only if n is prime or equal to 1
    if (is_prime(n)) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

If we have an array of an even number of elements, how do we pair them to minimize the sum of absolute differences?

The Naive Approach

For every $$$W_k$$$ (out of $$$M$$$ options), we add it to $$$H$$$, sort the $$$N+1$$$ elements, and calculate the cost. Time Complexity: $$$O(M \cdot N \log N)$$$. Given $$$N, M \le 2 \times 10^5$$$, this will result in Time Limit Exceeded (TLE). We need a faster way to evaluate each $$$W_k$$$

The Optimization

Instead of sorting from scratch every time, we can sort the array $$$H$$$ once at the beginning. Because $$$H$$$ is sorted, we can use Binary Search (like lower_bound in C++) to find the exact position where $$$W_k$$$ would be inserted in $$$O(\log N)$$$ time.Let $$$idx$$$ be the index where $$$W_k$$$ is inserted (i.e., the number of elements in $$$H$$$ strictly less than $$$W_k$$$).

adding $$$W_k$$$ affects the pairing of the already sorted elements in $$$H$$$.

The array splits into three parts:

1. Elements before $$$W_k$$$
2. $$$W_k$$$ itself paired with one adjacent element.
3. Elements after $$$W_k$$$

the pairing depends on whether the insertion index $$$idx$$$ is even or odd (assuming 0-based indexing for array $$$H$$$).

Case 1: $$$idx$$$ is even

There is an even number of elements before $$$W_k$$$. This means they pair up perfectly with each other.$$$W_k$$$ will end up at an even index, so it must pair with the element immediately after it (which is $$$H[idx]$$$).

The elements after $$$H[idx]$$$ will also pair up perfectly among themselves.

Cost formula: (Cost of pairing $$$H[0 \dots idx-1]$$$) + $$$(H[idx] - W_k)$$$ + (Cost of pairing $$$H[idx+1 \dots N-1]$$$).

Case 2: $$$idx$$$ is odd

There is an odd number of elements before $$$W_k$$$. The elements $$$H[0 \dots idx-2]$$$ pair perfectly.The leftover element $$$H[idx-1]$$$ will pair with $$$W_k$$$.The remaining elements after $$$W_k$$$ ($$$H[idx \dots N-1]$$$) will pair up perfectly among themselves.

Cost formula: (Cost of pairing $$$H[0 \dots idx-2]$$$) + $$$(W_k - H[idx-1])$$$ + (Cost of pairing $$$H[idx \dots N-1]$$$).

To make the formulas above $$$O(1)$$$ after finding the index, we can use Prefix and Suffix arrays for the pairing costs.

• pref[i]: Cost of pairing the prefix up to index $$$i-1$$$ (where $$$i$$$ is even).

• suff[i]: Cost of pairing the suffix starting from index $$$i$$$ (where $$$N-i$$$ is even).

Time Complexity: $$$O(N \log N)$$$ to sort $$$H$$$, $$$O(N)$$$ to build prefix/suffix arrays, and $$$O(M \log N)$$$ to binary search for every $$$W_k$$$.

Total: $$$\mathcal{O}((N + M) \log N)$$$.

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
const int mod = 1e9+7;
const long long oo=1e18;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    //freopen("input.txt", "r", stdin);
    //freopen("guess.out", "w", stdout);
    
    int n,m; cin>>n>>m;
    long long H[n] , W[m];
    for(int i=0 ; i<n ; i++) cin>>H[i];
    for(int i=0 ; i<m ; i++) cin>>W[i];
    sort(H , H+n);
    
    long long prefix[n+1]{} , suff[n+1]{};
    for(int i=2 ; i<n ; i+=2) prefix[i] = prefix[i-2] + H[i-1] - H[i-2];
    for(int i = n-2 ; i>=1 ; i-=2) suff[i] = suff[i+2] + H[i+1] - H[i];
	
    long long ans = oo;
    for(int i=0 ; i<m ; i++){
	int idx = lower_bound(H , H+n , W[i]) - H;
	if(idx&1) ans = min(ans , prefix[idx-1] + suff[idx] + W[i] - H[idx-1] );
	else ans = min(ans , prefix[idx] + suff[idx+1] + H[idx] - W[i]);
     }
     cout<<ans;
}

To maximize the sum of distances from one node to two others, you should look toward the furthest reaches of the tree. Start by finding the tree's diameter endpoints $$$u$$$ and $$$v$$$.

The goal is to pick three distinct nodes — Ashraf $$$A$$$ and his two teammates $$$T_1, T_2$$$ — to maximize the total distance:

The Core Logic

Intuitively, to get the largest possible distances in a tree, you must involve the Diameter (the longest path between any two nodes). Let the endpoints of this diameter be $$$u$$$ and $$$v$$$.

For any other node $$$i$$$ in the tree, we consider the trio $$${u, v, i}$$$. Any one of these three nodes could be Ashraf to maximize our sum. We evaluate these three distinct cases for every node $$$i$$$:

1. Ashraf is at diameter endpoint $$$u$$$: $$$\textit{Sum} = dist(u, v) + dist(u, i)$$$

2. Ashraf is at the other diameter endpoint $$$v$$$: $$$\textit{Sum} = dist(v, u) + dist(v, i)$$$

3. Ashraf is at the branching node $$$i$$$: $$$\textit{Sum} = dist(i, u) + dist(i, v)$$$

By iterating through all possible nodes $$$i$$$ and evaluating these scenarios, we ensure we find the absolute maximum sum possible.

Example Walkthrough

Imagine a tree where the diameter endpoints are $$$1$$$ and $$$6$$$ ($$$dist = 5$$$). Let's look at a side node $$$9$$$:

• $$$dist(1, 6) = 5$$$

• $$$dist(1, 9) = 4$$$

• $$$dist(6, 9) = 5$$$

Who should be Ashraf?

1. If Ashraf is 1: $$$5 + 4 = 9$$$

2. If Ashraf is 6: $$$5 + 5 = 10$$$ (This is our winner!)

3. If Ashraf is 9: $$$5 + 4 = 9$$$

Complexity

We use a standard 3-BFS approach to calculate everything in $$$O(N)$$$ time:

1. First BFS: Run from an arbitrary node to find the furthest node, which will be diameter endpoint $$$u$$$.

2. Second BFS: Run from $$$u$$$ to find the other endpoint $$$v$$$ and store $$$dist(u, i)$$$ for all $$$i$$$.

3. Third BFS: Run from $$$v$$$ to store $$$dist(v, i)$$$ for all $$$i$$$.

This keeps the complexity at $$$O(N)$$$, which is perfect for $$$N = 2 \cdot 10^5$$$.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// BFS to find distances from a source node
vector<int> get_dist(int start, int n, const vector<vector<int>> &adj) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

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

    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 1. Find diameter endpoint u
    vector<int> d_init = get_dist(1, n, adj);
    int u = 1;
    for (int i = 1; i <= n; ++i) if (d_init[i] > d_init[u]) u = i;

    // 2. Find diameter endpoint v and distances from u
    vector<int> dist_u = get_dist(u, n, adj);
    int v = 1;
    for (int i = 1; i <= n; ++i) if (dist_u[i] > dist_u[v]) v = i;

    // 3. Get distances from v
    vector<int> dist_v = get_dist(v, n, adj);

    long long max_sum = -1;
    int best_ashraf = -1, t1 = -1, t2 = -1;
 
    for (int i = 1; i <= n; ++i) {
        if (i == u || i == v) continue;
        
        long long d_uv = dist_u[v];
        long long d_ui = dist_u[i];
        long long d_vi = dist_v[i];
 
        // Check Case 1: Ashraf is u
        if (d_uv + d_ui > max_sum) {
            max_sum = d_uv + d_ui;
            best_ashraf = u;
            t1 = v; t2 = i;
        }
        // Check Case 2: Ashraf is v
        if (d_uv + d_vi > max_sum) {
            max_sum = d_uv + d_vi;
            best_ashraf = v;
            t1 = u; t2 = i;
        }
        // Check Case 3: Ashraf is i
        if (d_ui + d_vi > max_sum) {
            max_sum = d_ui + d_vi;
            best_ashraf = i;
            t1 = u; t2 = v;
        }
    }

    cout << best_ashraf << "\n";
    cout << t1 << " " << t2 << "\n";

    return 0;
}

Case 1 — Not all values 1..n appear in the full array: Count the frequency of each value from 1 to n. If any value i has frequency 0, it is missing from the entire array — so it is trivially missing from every subarray. Output i for all queries.

Case 2 — All values 1..n appear (each exactly once, by pigeonhole): Since every value appears exactly once, for any query [l, r] where r-l+1 < n, at least one element lies outside the subarray. - If r == n: the last element is inside the subarray, so the first element a[0] is guaranteed outside → output it. - If r < n: the last element is outside the subarray → output a[n-1].

This works because it is guaranteed an answer always exists, so the subarray can never cover all n positions.

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <chrono>
#include <thread>
#include<unordered_set>
#define all(a) (a).begin(),(a).end()
#define Yassin ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
#define e '\n'
#define ll long long 
#define ll long long 
#define lln long long n
#define ld long double
#define mod 1000000007
using namespace std;
const ll N = 2e5+100;
ll arr[N];
void solve()
{
    ll n, q;
    cin >> n >> q;
    vector<ll>ve(n); ll ans = -1;
    for (auto &it : ve)cin >> it,arr[it]++;
    for (int i = 1; i <= n; i++)if (!arr[i])ans = i;
    while (q--)
    {
        ll l, r;
        cin >> l >> r;
        cout << (ans==-1?(r == n ? ve[0] : ve[n - 1]):ans)<<e;
    }
}
int main()
{
    Yassin
        ll t=1; //cin >> t;
    while (t--)
    {
        solve();
    }
}

the problem asks for the bitwise-AND of all possible subarray ORs. At first glance, this might seem complex, but there's a clever observation that simplifies it significantly.

Letus consider any bit position $$$b$$$. For this bit to be set in the final answer, it must be set in every subarray OR. When would a bit be set in every subarray OR? It means that no matter which subarray we pick, at least one element in that subarray has this bit set.

Now think about the smallest subarrays possible — subarrays of length 1 (single elements). If a bit is set in every subarray OR, it must also be set in every single-element subarray. This means every element in the array must have that bit set.

conversely, if every element in the array has a particular bit set, then every subarray (no matter its length) will have that bit set in its OR. Why? Because even the smallest subarray (a single element) already has this bit set, so all larger subarrays will also have it set.

Therefore, the final answer is simply the bitwise-AND of all elements in the array. This is because: - If a bit is $$$1$$$ in all elements, it will be $$$1$$$ in all subarray ORs, and thus $$$1$$$ in the final AND. - If a bit is $$$0$$$ in any element, that element alone (as a subarray) will have that bit $$$0$$$ in its OR, so the final AND across all subarray ORs will also have that bit $$$0$$$.

Example

For the sample $$$[1, 4]$$$: - $$$1$$$ in binary: $$$01$$$ - $$$4$$$ in binary: $$$100$$$ - AND of all elements: $$$01 &amp; 100 = 000 = 0$$$

Complexity

• Time: $$$O(n)$$$
• Space: $$$O(1)$$$

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

void solve(){
    int n;
    cin>>n;
    int ans = ~0;  //initialize with all bits set to 1
    for(int i=0;i<n; i++){
        int x;
        cin>>x;
        ans &= x;
    }
    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Look at E in the level 1 contest, it's the same problem.

We need to choose $$$B_1, B_2, ..., B_N$$$ such that for all $$$i \lt j$$$: $$$A_i B_i = A_j B_j$$$. This means the product $$$A_i \cdot B_i$$$ must be the same constant for all $$$i$$$. Let's call this constant $$$K$$$.

So for each $$$i$$$, we have $$$A_i \cdot B_i = K$$$, which means $$$B_i = \frac{K}{A_i}$$$. Since $$$B_i$$$ must be a positive integer, $$$K$$$ must be divisible by every $$$A_i$$$. Therefore, $$$K$$$ must be a common multiple of all $$$A_i$$$'s.

We want to minimize $$$B_1 + B_2 + ... + B_N = \sum_{i=1}^N \frac{K}{A_i}$$$.

Since $$$K$$$ appears in the numerator of each term, to minimize the sum we want the smallest possible $$$K$$$ that is a common multiple of all $$$A_i$$$'s. The smallest such $$$K$$$ is the Least Common Multiple (LCM) of all $$$A_i$$$'s.

Let $$$L = \text{lcm}(A_1, A_2, ..., A_N)$$$. Then the minimum sum is:

Example

For the sample $$$[1, 2, 3, 4, 5, 6]$$$: - $$$L = \text{lcm}(1, 2, 3, 4, 5, 6) = 60$$$ - Sum = $$$60/1 + 60/2 + 60/3 + 60/4 + 60/5 + 60/6 = 60 + 30 + 20 + 15 + 12 + 10 = 147$$$

Complexity

• Computing LCM iteratively: $$$O(N \log M)$$$ where $$$M$$$ is the maximum value in $$$A$$$
• Summation: $$$O(N)$$$
• Note: Since $$$A_i \le 20$$$, the LCM will not exceed the product of primes up to 20 which fits in 64-bit integer.

#define ll long long int
  #include<bits/stdc++.h>
  using namespace std;

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

     ll L = 1;
      for(int i=0; i <n;i++)
          L = L / __gcd(L, (long long)a[i]) *a[i];

      ll ans =0;
      for(int i= 0;i<n; i++)
          ans += L / a[i];

      cout<<ans<<"\n";
  }

  int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
      solve();
      return 0;
  }

Think in terms of Divide and Conquer.

If a square is not uniform (i.e all $$$0$$$ or all $$$1$$$ values), can you split it into smaller squares and solve each one independently?

Represent a square submatrix using three parameters:

(x, y, sideLength)

where (x, y) is the top-left corner.

Use these as the state of a recursive function.

The problem can be solved using a recursive (divide-and-conquer) approach. Since all submatrices are square, we can represent any submatrix using three parameters:

• x: starting row index
• y: starting column index
• len: side length of the square

Therefore, the entire matrix of size N × N is initially defined as:

$$$(0, 0, N)$$$

Dividing into Quadrants

For any square submatrix (x, y, len), we divide it into four equal quadrants of size len / 2. The four resulting submatrices are:

1. Top-left: $$$(x, y, len / 2)$$$

2. Top-right: $$$(x, y + len / 2, len / 2)$$$

3. Bottom-left: $$$(x + len / 2, y, len / 2)$$$

4. Bottom-right: $$$(x + len / 2, y + len / 2, len / 2)$$$

For example, if N = 8, the initial state (0, 0, 8) is divided into:

(0, 0, 4)
(0, 4, 4)
(4, 0, 4)
(4, 4, 4)

as illustrated here:

For each submatrix (x, y, len):

• Check whether all elements inside it have the same value.
• If they are all equal, we stop dividing this submatrix and return $$$1$$$.
• Otherwise, we recursively divide it into its four quadrants and repeat the same process and accumulate the size resulted from each quadrant.

Further Optimizations

While the problem constrains would pass the solution with $$$len^2$$$ uniform check loop in each recursive call, other optimizations can be done

a = rec(top-left)
b = rec(top-right)
c = rec(bottom-left)
d = rec(bottom-right)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(ocate) ocate.begin(), ocate.end()
#define el "\n"
#define deb(x) cerr << #x << "=" << (x) << el;

vector<vector<int>> g;

int rec(int x, int y, int len) {
    bool isUniform = true;
    for (int i = x; i < x + len; ++i) {
        for (int j = y; j < y + len; ++j) {
            if (g[x][y] != g[i][j]) {
                isUniform = false;
                break;
            }
        }
    }

    if (isUniform) return 1;

    int h = len / 2;
    return 1 
       + rec(x, y, h) 
       + rec(x, y + h, h) 
       + rec(x + h, y, h) 
       + rec(x + h, y + h, h);
}

void solve(const int& TESTCASE) {
    int n;
    cin >> n;

    g.assign(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
        }
    }

    cout << rec(0, 0, n) << el;
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int ___ = 1;
    // cin >> ___;

    for (int t = 1; t <= ___; ++t) solve(t);
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(ocate) ocate.begin(), ocate.end()
#define el "\n"
#define deb(x) cerr << #x << "=" << (x) << el;

vector<vector<int>> g;

int getSum(int x, int y, int len) {
    return g[x + len][y + len] &mdash; g[x][y + len] &mdash; g[x + len][y] + g[x][y];
}

int rec(int x, int y, int len) {
    int sum = getSum(x, y, len);
    bool isUniform = sum == 0 || sum == (len * len);

    if (isUniform) return 1;

    int h = len / 2;
    return 1 
       + rec(x, y, h) 
       + rec(x, y + h, h) 
       + rec(x + h, y, h) 
       + rec(x + h, y + h, h);
}

void solve(const int& TESTCASE) {
    int n;
    cin >> n;

    g.assign(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> g[i][j];
            g[i][j] += g[i][j - 1] + g[i - 1][j] - g[i - 1][j - 1];
        }
    }

    cout << rec(0, 0, n) << el;
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int ___ = 1;
    // cin >> ___;

    for (int t = 1; t <= ___; ++t) solve(t);
}

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(ocate) ocate.begin(), ocate.end()
#define el "\n"
#define deb(x) cerr << #x << "=" << (x) << el;

vector<vector<int>> g;

pair<int, int> rec(int x, int y, int len) {
    if (len == 1) {
        return {1, g[x][y]};
    }

    int h = len / 2;

    auto a = rec(x, y, h);
    auto b = rec(x, y + h, h);
    auto c = rec(x + h, y, h);
    auto d = rec(x + h, y + h, h);

    bool allAreUniform = a.first == 1 && b.first == 1 && c.first == 1 && d.first == 1;
    bool allAreSameParity = a.second == b.second && a.second == c.second && a.second == d.second;
    
    if (allAreUniform && allAreSameParity) {
        return {1, g[x][y]}; // merge all nodes into one node
    }

    return {1 + a.first + b.first + c.first + d.first, -1};
}

void solve(const int& TESTCASE) {
    int n;
    cin >> n;

    g.assign(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
        }
    }

    cout << rec(0, 0, n).first << el;
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int ___ = 1;
    // cin >> ___;

    for (int t = 1; t <= ___; ++t) solve(t);
}

Step 1: Precomputing Divisor XOR Sums:

We need to find the bitwise XOR sum of divisors for every number up to $$$V = 10^6$$$.A naive approach would be to iterate all divisors for each number, which takes $$$O(V \sqrt{V})$$$ time and might be too slow.Instead, we use a technique similar to the Sieve of Eratosthenes. We can iterate through every integer $$$i$$$ from $$$1$$$ to $$$V$$$ and assume $$$i$$$ is a divisor. Then, we update all multiples of $$$i$$$ (i.e., $$$i, 2i, 3i, \dots$$$) by XORing them with $$$i$$$.Let xor_sum[x] store the XOR sum of divisors of $$$x$$$.

for (int i = 1; i <= MAX_VAL; i++) {
    for (int j = i; j <= MAX_VAL; j += i) {
        xor_sum[j] ^= i;
    }
}

Complexity:

The inner loop runs $$$\frac{V}{1} + \frac{V}{2} + \frac{V}{3} + \dots + \frac{V}{V}$$$ times. This is the Harmonic Series, which sums to approximately $$$O(V \log V)$$$.

Once we have the xor_sum array, we can determine if the $$$i$$$-th person is a spy. A person holding number $$$A_i$$$ is a spy if:

Step 2:Answering Queries

We need to count spies in ranges $$$[l, r]$$$. this is a static range sum query.We can build a prefix sum array $$$P$$$, where $$$P[i]$$$ stores the number of spies among the first $$$i$$$ people.

If person $$$i$$$ is a spy, $$$P[i] = P[i-1] + 1$$$. Otherwise, $$$P[i] = P[i-1]$$$.

The answer for each query $$$[l, r]$$$ is simply $$$P[r] - P[l-1]$$$.

Time Complexity: $$$O(V \log V + N + Q)$$$

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
const int mod = 1e9+7;
const long long oo=1e18;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    //freopen("input.txt", "r", stdin);
    //freopen("guess.out", "w", stdout);
	
    int sieve[1000001];
    sieve[1] = 1;
    for(int i=2 ; i<1000001 ; i++) sieve[i] = 1^i;
    for(int i=2 ; i<1000001 ; i++){
	for(int j = i+i ; j<1000001 ; j+=i) sieve[j] ^= i;
    }
	
    int n,q,k; cin>>n>>q>>k;
    int prefix[n]{};
    for(int i=0 ; i<n ; i++){
	int a; cin>>a;
	if(sieve[a] % k == 0) prefix[i] = 1;
		
	if(i) prefix[i] += prefix[i-1]; 
    }
	
    for(int i=0 ; i<q ; i++){
	int l,r; cin>>l>>r;
	l--;r--;
	cout<<prefix[r] - (l? prefix[l-1] : 0)<<'\n';
    }
}

Let $$$lcm(a_i, a_j) = v$$$ and $$$v$$$ will be every value from $$$x$$$ to $$$y$$$ (More formally, we will fix the value of $$$lcm(a_i, a_j)$$$).

There is an important observation here that $$$a_i$$$ and $$$a_j$$$ must be divisors of this value $$$v$$$ as it is their $$$lcm$$$ (By the definition of lcm which is least common multiple so multiple means that both numbers are divisors of $$$lcm$$$).

From this observation we can just loop through all divisors in $$$O(divisors(v)^2)$$$ and the summation of all divisors squared for every number from $$$1$$$ to $$$10^5$$$ will not exceed $$$2 * 10 ^ 6$$$ so it will fit in the problem's constraints.

#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const ll N = 1e5 + 10;
vector<ll> divs[N];

int main() {
    baraa
    for (ll i = 1; i < N; i++)
        for (ll j = i; j < N; j += i)
            divs[j].push_back(i);
    ll n, x, y;
    cin >> n >> x >> y;
    vector<ll> a(n), have(N, 0);
    for (ll &i: a)cin >> i, have[i]++;
    if (x > y) {
        cout << 0 << nl;
        return 0;
    }
    ll res = 0;
    for (ll lc = x; lc <= y; lc++) {
        vector<ll> cur;
        for (ll d: divs[lc])
            if (have[d])cur.push_back(d);
        for (ll i = 0; i < cur.size(); i++)
            for (ll j = i; j < cur.size(); j++) {
                ll ai = cur[i], aj = cur[j], g = gcd(ai, aj);
                if (g < x or (ai * aj / g) != lc)continue;
                if (ai == aj)res += (have[ai] * (have[ai] - 1)) / 2;
                else res += have[ai] * have[aj];
            }
    }
    cout << res << nl;
    return 0;
}