Math, Implementation

First check if the sum of the array is divisible by its size.

If not, think about removing one element and what happens to the sum and the size.

The element you remove must have the right remainder when divided by (n−1).

We are given an array of size n with total sum S. If S is divisible by n, the array is already balanced and the answer is "YES". Otherwise, we can try deleting one element ai. After deletion, the new sum becomes S — ai and the new size becomes n — 1. For the new array to be balanced, (S — a[i]) must be divisible by (n — 1), which is the same as saying that ai must have the same remainder as S when divided by (n — 1). Thus, it is enough to check if there exists at least one element such that a[i] % (n — 1) == S % (n — 1). A special case is when n = 1, where the answer is always "YES" since deleting the single element leaves an empty array, which is considered balanced. The solution only requires scanning the array once, giving a time complexity of O(n) per test case.

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

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        long long S = 0;

        // Read the array and calculate total sum S
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            S += a[i];
        }

        // Special case: if array has only 1 element,
        // we can always remove it -> empty array is balanced
        if (n == 1) {
            cout << "YES\n";
            continue;
        }

        // Case 1: Already balanced (S % n == 0)
        if (S % n == 0) {
            cout << "YES\n";
            continue;
        }

        // Case 2: Try deleting one element
        bool ok = false;
        for (int i = 0; i < n; i++) {
            // After removing a[i], check if new array is balanced
            // Condition: (S - a[i]) % (n - 1) == 0
            if ((S - a[i]) % (n - 1) == 0) {
                ok = true;
                break;
            }
        }

        cout << (ok ? "YES\n" : "NO\n");
    }
    return 0;
}

Sorting + greedy

We always want to choose the cheapest item available.

Think of data structure used to maintain the cheapest item.

Use Minheap

Push all the elements into a minheap while also storing their index. Then pop out the cheapest fruit and we buy it (decrease the remaining budget). Then we push the updated price of the fruit back into the heap. The updated price = price of fruit + index.

We repeat the above process till the cheapest fruit that we get is costlier than the remaining budget.

Time Complexity :- Initially one might think that we can get TLE because budget <= 1e9.

But lets consider a worst case scenario :- B = 1e9 N = 1 A[1] = 1 In this case we add in the series 1 + 2+ 3 + 4 + — — — — +x such that x is the last price at which we buy.

Here we can use the formula x*(x+1)/2 <= B.

So approximately x = sqrt(B) ~ sqrt(1e9) ~ 1e5

Also x is the number of times we pop an element from the heap and add another so the final time complexity :-

O(sqrt(B)*log(n)).

Space complexity = O(n). We only need to use the space used in the heap.

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

using namespace std;

int main() {
    /* I might use long long when int works and I suggest at least when learning competitive programming you should ignore space complexity most of the time.
                                            Not that it is not important but currently let's focus on problem solving. */

    long long B;
    cin >> B;

    int n;
    cin >> n;

    vector<long long> a(n); // using long long for safety
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // Min heap declaration
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    for (int i = 0; i < n; ++i) {
        pq.push({a[i], i + 1}); // pushing all the elements
    }

    long long ans = 0;
    while (!pq.empty()) {
        if (B < pq.top().first) { // base condition when cheapest > remaining budget
            break;
        } else {
            long long cur = pq.top().first; // get the cheapest fruit
            long long ind = pq.top().second; // get the index
            pq.pop(); // remove the chosen fruit

            B -= cur; // decrease budget
            ++ans; // One more fruit bought

            pq.push({cur + ind, ind}); // Update the minheap with new value
        }
    }

    cout << ans << endl; // Done output the answer

    return 0;
}

Bitmask, Data structure, Constructive algorithm, Math

Think about the bitwise AND condition for a query (l, r, q). If a bit is 1 in q, then every element in [l, r] must have that bit set. If a bit is 0 in q, then at least one element in [l, r] must have that bit unset.

Can you use difference array concept?

Key Observations

For the bitwise AND of numbers in a range [l, r] to equal q, two properties must hold. Every bit that is set in q must also be set in all numbers within the segment [l, r]. Also, every bit that is not set in q must be absent in at least one number within the segment [l, r]. This allows for bit-by-bit thinking. Instead of dealing with entire numbers, we can check the conditions independently for each of the 30 bits. If a query requires bit j to be 1, we must set bit j to 1 for all positions in the range [l, r]. If a query requires bit j to be 0, it simply means that not all positions in the range [l, r] can have bit j set to 1.

Constructive Strategy

The strategy is to first force all required 1s. We can use a difference array, pref[j][i], to mark ranges where a bit must be set. For each query (l, r, q) and each bit j, if the j-th bit of q is 1, we increment pref[j][l] and decrement pref[j][r+1]. After computing prefix sums for each bit, a value of pref[j][i] > 0 means bit j must be set at position i.

Next, we build a candidate array. For each position i, the value A[i] is formed by setting all bits j for which pref[j][i] is greater than 0.

Finally, a verification step is needed. Our constructed array satisfies the conditions for bits that must be 1, but it might accidentally violate a condition where a bit needed to be 0. So, we must re-check all original queries. For each query (l, r, q), we compute the bitwise AND of the elements in our constructed array from l to r. If it does not match q, then an answer is not possible. If all queries match, we have a valid array.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define all(x) (x).begin(), (x).end()

using namespace __gnu_pbds;
using namespace std;

using ull = unsigned long long;
using ll = long long;
template <typename T> using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const int N = 1e5 + 5;

int n, m, pref[30][N];
vector<pair<pair<int, int>, int>> queries;

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

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int l, r, q;
        cin >> l >> r >> q;

        for (int j = 0; j < 30; j++) {
            if (q & (1 << j)) {
                pref[j][l]++;
                pref[j][r+1]--;
            }
        }
        queries.push_back({{l, r}, q});
    }

    for (int i = 0; i < 30; i++) {
        for (int j = 1; j <= n; j++)
            pref[i][j] += pref[i][j-1];
    }

    for (int i = 0; i < 30; i++) {
        for (int j = 1; j <= n; j++)
            pref[i][j] = (pref[i][j] > 0);
    }

    for (int i = 0; i < 30; i++) {
        for (int j = 1; j <= n; j++)
            pref[i][j] += pref[i][j-1];
    }

    for (auto &p : queries) {
        int l = p.first.first, r = p.first.second, q = p.second;
        int ans = 0;

        for (int i = 0; i < 30; i++) {
            if (pref[i][r] - pref[i][l-1] == r - l + 1)
                ans |= (1 << i);
        }

        if (ans != q) {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";
    for (int i = 1; i <= n; i++) {
        int ans = 0;
        for (int j = 0; j < 30; j++) {
            if (pref[j][i] - pref[j][i-1] == 1)
                ans |= (1 << j);
        }
        cout << ans << " ";
    }
    return 0;
}

Graphs, DFS, BFS, Grid traversal

Try to think from the end position E instead of the start S.

Imagine a situation like a narrow tunnel — once you enter, you can give the wrong direction to manipulate Elektra into reaching the exit. Example:

#####
#E..#
###.#
###S#
#####

If we give the directions DDDR, Elektra will still reach E. Hence, in this case, we can set k = 0.

From E, only extend into cells that have at most one free neighbor, and mark them. These cells form such tunnel-like paths. Finally, find the shortest distance from S to any marked position. If it’s not possible to reach, then the answer is -1.

To solve the problem, we first read the grid and identify the positions of the start S and the exit E. The idea is to work backward from the exit rather than forward from the start. From the exit E, we perform a depth-first search (DFS) into neighboring '.' cells. However, this DFS is restricted: we only continue into a cell if it has at most one open neighbor. This condition ensures that the traversal follows tunnel-like paths without branching. All such valid cells are marked with '+'. Once this marking step is done, we check the position of S. If the start cell is itself marked '+', it means Elektra can be manipulated to the exit immediately, so the answer is 0. Otherwise, we need to compute how far S is from any marked path or directly from E. For this, we use a breadth-first search (BFS) starting from S. The BFS explores all adjacent cells that are either '.', '+', or E, and maintains a distance matrix to track the number of steps taken. The BFS terminates as soon as it reaches a marked cell or the exit E, and at that point we print the corresponding distance. If no such path exists, the answer is -1. This process is repeated independently for each test case.

Complexity: DFS and BFS each run in O(n*m) since every cell is visited at most once.

Memory usage is also O(n*m) for storing the grid and distance matrix.

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

typedef long long ll;
typedef vector<string> vstr;

bool ch(ll x, ll y, vstr& s) {
   ll count = 0;
   ll n = s.size();
   ll m = s[0].size();

   if ((x-1 >= 0) && (s[x-1][y] == '.')) count++;
   if ((y-1 >= 0) && (s[x][y-1] == '.')) count++;
   if ((x+1 < n) &&  (s[x+1][y] == '.')) count++;
   if ((y+1 < m) && (s[x][y+1] == '.')) count++;

   return (count <= 1);
}

void dfs(ll x , ll y , vstr &s) {
   if (ch(x,y,s)) {
       s[x][y] = '+';
       ll n = s.size();
       ll m = s[0].size();

       if ((x-1 >= 0) && s[x-1][y] == '.' ) dfs(x-1,y,s);
       if ((y-1 >= 0) && s[x][y-1] == '.' ) dfs(x,y-1,s);
       if ((x+1 < n) &&  s[x+1][y] == '.' ) dfs(x+1,y,s);
       if ((y+1 < m) && s[x][y+1] == '.' ) dfs(x,y+1,s);
   }
}

ll bfs(vector<string>& s , ll xs , ll ys , ll n , ll m) {
   vector<pair<int,int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};
   queue<pair<int,int>> q;
   vector<vector<int>> dist(n, vector<int>(m, -1));

   q.push({xs, ys});
   dist[xs][ys] = 0;

   while (!q.empty()) {
       auto [x, y] = q.front();
       q.pop();

       if (s[x][y] == '+' || s[x][y] == 'E') {
           return dist[x][y];
       }

       for (auto [dx, dy] : directions) {
           int nx = x + dx, ny = y + dy;
           if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) {
               if (s[nx][ny] == '.' || s[nx][ny] == '+' || s[nx][ny] == 'E') {
                   dist[nx][ny] = dist[x][y] + 1;
                   q.push({nx, ny});
               }
           }
       }
   }
   return -1;
}

void solve() {
   ll n, m;
   cin >> n >> m;
   vstr s(n);
   for (ll i = 0; i < n; i++) cin >> s[i];

   ll xs, ys, xe, ye;
   for (ll i = 0; i < n; i++) {
       for (ll j = 0; j < m; j++) {
           if (s[i][j] == 'S') {
               xs = i; ys = j;
               s[i][j] = '.';
           }
           if (s[i][j] == 'E') {
               xe = i; ye = j;
           }
       }
   }

   if ((xe-1 >= 0) && s[xe-1][ye] == '.') dfs(xe-1,ye,s);
   if ((ye-1 >= 0) && s[xe][ye-1] == '.') dfs(xe,ye-1,s);
   if ((xe+1 < n) &&  s[xe+1][ye] == '.') dfs(xe+1,ye,s);
   if ((ye+1 < m) && s[xe][ye+1] == '.') dfs(xe,ye+1,s);

   if (s[xs][ys] == '+') {
       cout << 0;
   } else {
       s[xs][ys] = 'S';
       cout << bfs(s , xs , ys , n , m);
   }
   cout << "\n";
}

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

   ll tt = 1;
   cin >> tt;
   while (tt--) {
       solve();
   }
   return 0;
}

Number Theory, Inclusion-Exclusion, Mobius Function, GCD

If gcd(a[i], a[j]) = k, then both a[i] and a[j] must be divisible by k.

Divide all numbers by k. Now the problem reduces to counting pairs with gcd = 1.

To count gcd = 1 pairs, we can use the Möbius function (μ) and inclusion-exclusion principle.

Step 1: Normalization
Since we need gcd(a[i], a[j]) = k, we first check only numbers divisible by k.
Let’s define b[i] = a[i] / k for all a[i] divisible by k.

Now, our task is:Count pairs (i, j) such that gcd(b[i], b[j]) = 1.

Step 2: Using Möbius Function
The video link for learning Mobius Function: https://www.youtube.com/live/znENoVN73G8?t=4207s

Complexity Analysis Time Complexity: O(NlogN) for N=10^6 (fast enough). Space Complexity: O(N) (arrays for LPF, Möbius, frequency).

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

typedef long long ll;

// Arrays to store least prime factor and Möbius function values
ll lpf[1000001],mobius[1000001];

// Function to compute least prime factor for every number up to 1e6
void least_prime_factor() {
   for (int i=2;i<1000001;i++) {
       if (!lpf[i]) { // if i is prime
           for (int j=i;j<1000001;j+=i) {
               if (!lpf[j])lpf[j]=i; // mark i as the smallest prime factor of j
           }
       }
   }
}

// Function to compute the Möbius function using least prime factors
void Mobius() {
   for (int i = 1; i < 1000001; i++) {
       if (i == 1) mobius[i] = 1; // μ(1) = 1
       else {
           // If i has a squared prime factor, μ(i) = 0
           if (lpf[i/lpf[i]]==lpf[i])mobius[i] = 0;
           // Otherwise, μ(i) = -μ(i / smallest prime factor)
           else mobius[i] = -1 * mobius[i / lpf[i]];
       }
   }
}

int main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   ll n, k;
   cin >> n >> k;

   ll s = 0;
   ll p[n];
   ll cnt[1000001] = {}; // frequency array for input numbers

   // Read input and count frequency of each number
   for (int i = 0; i < n; i++) {
       cin >> p[i];
       if(p[i]%k==0)
       cnt[p[i]/k]++;
       s++;
   }

   // Precompute least prime factors and Möbius function
   least_prime_factor();
   Mobius();

   ll ans = 0;

   // Apply inclusion-exclusion using Möbius function
   for (int i = 1; i < 1000001; i++) {
       if (mobius[i] == 0) continue; // skip numbers with squared prime factor

       ll d = 0;
       // Count how many numbers are divisible by i
       for (int j = i; j < 1000001; j += i) {
           d += cnt[j];
       }

       // Add contribution to answer using Möbius function
       ans += (d * (d - 1)) / 2 * mobius[i];
   }

   cout << ans;
}