We are given three pile sizes $$$a$$$, $$$b$$$, and $$$c$$$. We need to check if the sum of any two piles is equal to the remaining one.We check the three possible cases:

• $$$a + b = c$$$
• $$$a + c = b$$$
• $$$b + c = a$$$

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

void solve() {
    int a, b, c;
    cin >> a >> b >> c;

    if (a + b == c || a + c == b || b + c == a) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Pick any two frogs that are currently in adjacent buckets (for example, at index $$$i$$$ and index $$$i+1$$$). If they both jump at the same time, is it possible for them to land in the same bucket? Try to sketch their possible moves.

You will find that neighbors can never meet. They either swap places or move further apart. This means a frog starting at index $$$1$$$ can never be in the same bucket as a frog starting at index $$$2$$$. However, a frog from $$$1$$$ can meet a frog from $$$3$$$.

The frogs effectively belong to two separate "teams" based on their starting positions. Team A: Frogs starting at $$$1, 3, 5 \dots$$$ Team B: Frogs starting at $$$2, 4, 6 \dots$$$

Let's analyze the movement based on the parity of the bucket indices (Odd vs Even).

1. The Parity Constraint
When a frog jumps from bucket $$$i$$$, it moves to $$$i-1$$$ or $$$i+1$$$. In both cases, the parity of the index changes (Odd $$$\to$$$ Even, or Even $$$\to$$$ Odd).

• At $$$t=0$$$, frogs are at indices $$$\{1, 2, \dots, n\}$$$.
• At $$$t=1$$$, frogs starting at Odd indices move to Even indices.
• At $$$t=1$$$, frogs starting at Even indices move to Odd indices.

This implies that a frog starting at an odd position and a frog starting at an even position can never be in the same bucket at the same time. They will always be on buckets of different parities.

2. Two Independent Groups
The frogs are divided into two disjoint sets that never mix:

1. The Odd Set: Frogs starting at $$$\{1, 3, 5, \dots\}$$$.
2. The Even Set: Frogs starting at $$$\{2, 4, 6, \dots\}$$$.

The maximum number of frogs we can gather in one bucket is limited by the size of these sets. We just need to find which set is larger.
Count of Odd indices in $$$[1, n]$$$: $$$\lceil \frac{n}{2} \rceil$$$
Count of Even indices in $$$[1, n]$$$: $$$\lfloor \frac{n}{2} \rfloor$$$

Since $$$\lceil \frac{n}{2} \rceil \ge \lfloor \frac{n}{2} \rfloor$$$, the answer is always the count of odd numbers.

Formula:

Note: Since $$$n \le 10^{18}$$$, use 64-bit integers (long long).

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

#define int long long

void solve() {
    int n;
    cin >> n;
    cout << (n + 1) / 2 << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Every valid move increases the Y-coordinate by exactly 1. If the target Y is smaller than the start Y, is it possible?

Let $$$dx$$$ be the absolute difference of X-coordinate and $$$dy$$$ be the absolute difference of Y-coordinate The maximum horizontal distance you can travel is equal to the number of vertical steps (using only diagonal moves). What happens if $$$dx \gt dy$$$?

You need to cover the horizontal distance $$$dx$$$. Since only diagonal moves change x, and you must move diagonally to change X, you should perform at least $$$dx$$$ diagonal moves.

After fixing the X-coordinate, you have some vertical distance $$$R = dy - dx$$$ left. You need to cover this height without changing X.

To move up by 2 units without changing your horizontal position ($$$x$$$), you have two choices:

1. Move Straight Up twice: This costs $$$B + B = 2B$$$.
2. Zig-Zag (Left then Right): Move Up-Left once and Up-Right once. This costs $$$A + A = 2A$$$.

Let $$$dx = |x_1 - x_2|$$$ be the horizontal distance and $$$dy = y_2 - y_1$$$ be the vertical distance.

1. Feasibility Check
First, we must check if the destination is reachable:

• Since every move increases the $$$y$$$-coordinate by exactly 1, we must have $$$dy \ge 0$$$.
• The maximum horizontal distance we can travel is bounded by the vertical steps (using only diagonals). Therefore, we must have $$$dx \le dy$$$.

If either condition fails, the answer is $$$-1$$$.

2. Greedy Strategy
To minimize the total time, we prioritize necessary movements and then handle the remaining distance greedily.

Step A: Mandatory Horizontal Moves
We must cover the horizontal distance $$$dx$$$. The optimal way is to take $$$dx$$$ diagonal moves towards the target.
Cost: $$$dx \cdot A$$$
This covers $$$dx$$$ units of vertical distance as well. The remaining vertical distance is $$$R = dy - dx$$$.

Step B: Covering Remaining Vertical Distance ($$$R$$$)
We need to cover $$$R$$$ vertical steps without changing our $$$x$$$-coordinate. We process these steps in pairs:

• Option 1 (Straight Up): Move Up twice. Cost: $$$2 \cdot B$$$.
• Option 2 (Zig-Zag): Move Up-Left then Up-Right. Cost: $$$2 \cdot A$$$.

For every pair of steps, we take the cheaper option: $$$\min(2A, 2B)$$$.
If $$$R$$$ is odd, we have 1 step leftover. We are forced to use a single Up move (Cost $$$B$$$).

Final Formula:

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

void solve() {
    int A, B;
    cin >> A >> B;
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int dx = abs(x1 - x2);
    int dy = y2 - y1;
    if (dy < 0 || dx > dy) {
        cout << -1 << endl;
        return;
    }
    int cost = dx * A;
    int rem = dy - dx;
    int pairs = rem / 2;
    int leftover = rem % 2;
    cost += pairs * 2 * min(A, B);
    cost += leftover * B;
    cout << cost << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Instead of minimizing the number of bakers to remove, try to maximize the number of bakers to keep ($$$k$$$).

If we keep $$$k$$$ bakers, they must all end up with equal pastries (say $$$x$$$). This requires: 1. Total pastries needed ($$$k \cdot x$$$) $$$\le$$$ Total sum ($$$S$$$). 2. Every kept baker must start with $$$A_i \le x$$$ (counts can only increase).

To make it easier to satisfy $$$A_i \le x$$$, we should greedily keep the $$$k$$$ bakers with the smallest initial amounts.

Sort $$$A$$$. For each $$$k$$$ from $$$1$$$ to $$$N$$$, check if the largest among the smallest $$$k$$$ ($$$A_{k-1}$$$) satisfies:

Find the maximum valid $$$k$$$.

We want to find the minimum number of bakers to remove. This is equivalent to finding the maximum number of bakers we can keep, say $$$k$$$.

Let $$$S$$$ be the total sum of pastries owned by all $$$N$$$ bakers initially.
Suppose we decide to keep $$$k$$$ bakers. We need to reach a state where all $$$k$$$ remaining bakers have exactly $$$x$$$ pastries each.

Conditions for a valid solution:

• Supply Constraint: The total pastries required for the final state ($$$k \cdot x$$$) cannot exceed the total supply available ($$$S$$$). The removed bakers can only give away what they have, so the total sum decreases or stays same. $$$k \cdot x \le S \implies x \le \left\lfloor \frac{S}{k} \right\rfloor$$$
• Demand Constraint: The removed bakers can distribute pastries to the remaining ones, the pastry count held by a remaining baker can only increase. Therefore, if a baker $$$i$$$ stays, their initial count $$$A_i$$$ must be less than or equal to the target $$$x$$$. $$$A_i \le x \quad \text{for all retained bakers}$$$

Greedy Strategy:

To maximize our chances of satisfying the conditions for a fixed $$$k$$$, we should greedily keep the $$$k$$$ bakers who have the smallest initial number of pastries.

Why? Because the bottleneck in the second condition is the baker with the largest $$$A_i$$$ among those kept. By picking the smallest ones, we minimize this maximum value.

Time Complexity

Sorting the array takes $$$O(N \log N)$$$. The iteration takes $$$O(N)$$$.
Total time complexity is $$$O(N \log N)$$$, which fits within the limits.

#include<bits/stdc++.h>
#define int long long
#define zero 0LL
#define pb push_back
using namespace std;

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

    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;

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

        sort(a.begin(), a.end());

        int kmax = 0;
        for(int k = 1; k <= n; k++){
            if(a[k - 1] <= sum / k){
                kmax = k;
            }
        }

        cout << (n - kmax) << '\n';
    }
}

The answer is monotonic: if capacity $$$T$$$ works, any $$$T' \gt T$$$ works. Use Binary Search on the Answer.

Check Function: Greedily add people to the current trip. Start a new trip only when adding the next person would exceed the limit $$$T$$$.

Update Logic:

• If check(mid) is true, then mid is possible. Try to find a smaller answer: ans = mid, r = mid — 1.
• If check(mid) is false, we need more capacity: l = mid + 1.

The problem asks us to partition the array of people $$$m_1, m_2, \dots, m_N$$$ into at most $$$K$$$ contiguous subarrays (trips) such that the maximum tension required for any single trip is minimized. The tension for a group with total mass $$$M_{load}$$$ is given by $$$T = M_{load} \cdot G_{eff}$$$.

This is a classic "Minimize the Maximum" problem, which can often be solved using Binary Search on the Answer.

1. Monotonicity
Let's define a predicate function check(T) which returns true if it is possible to rescue all people in $$$\le K$$$ trips using a cable with tension rating $$$T$$$, and false otherwise.
If a tension rating $$$T$$$ is sufficient to rescue everyone, then any rating $$$T' \gt T$$$ is definitely sufficient as well. This monotonicity allows us to binary search for the minimum valid $$$T$$$.

2. The Check Function (Greedy Strategy)
For a fixed tension capacity $$$T_{limit}$$$, how do we determine the minimum number of trips required? Since the order of people is fixed, we can use a greedy approach:

• Start the first trip with the first person.
• Continue adding the next person in the queue to the current trip as long as the total tension does not exceed $$$T_{limit}$$$.
• If adding the next person would exceed $$$T_{limit}$$$, we must finalize the current trip and start a new one with that person.
• If any single individual requires a tension greater than $$$T_{limit}$$$ on their own ($$$m_i \cdot G_{eff} \gt T_{limit}$$$), then this $$$T_{limit}$$$ is immediately invalid.

After iterating through all people, if the number of trips used is less than or equal to $$$K$$$, then $$$T_{limit}$$$ is feasible.
We perform binary search within the range $$$[L, R]$$$. In each step, if check(mid) is true, we store mid as a potential answer and try smaller values ($$$R = mid - 1$$$). Otherwise, we look for larger values ($$$L = mid + 1$$$).

3. Time Complexity
The check function iterates through the array once, taking $$$O(N)$$$ time. The binary search runs for $$$O(\log(\sum m_i \cdot G_{eff}))$$$ iterations.
The total time complexity is $$$O(N \cdot \log(\text{Total Mass} \cdot G_{eff}))$$$, which fits comfortably within the time limit for $$$N \le 2 \cdot 10^5$$$.

#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
 
 
bool ok(int n,int k,int g,vector<int>&a,int m){
    int c=1,cur=0;
    for(int i=0;i<n;i++){
        int w=a[i]*g;
        if(w>m) return 0;
        if(cur+w<=m){
            cur+=w;
        }else{
            c++;
            cur=w;
        }
    }
    return c<=k;
}
 
 
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
 
    int t;
    cin>>t;
    while(t--){
        int n,k,g;
        cin>>n>>k>>g;
 
 
        vector<int>a(n);
        int mx=0,sum=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            mx=max(mx,a[i]);
            sum+=a[i];
        }
 
 
        int l=mx*g,r=sum*g,ans=r;
        while(l<=r){
            int m=l+(r-l)/2;
            if(ok(n,k,g,a,m)){
                ans=m;
                r=m-1;
            }else{
                l=m+1;
            }
        }
        cout<<ans<<"\n";
    }
}

The alphabet size is small (26). Can we solve the problem independently for each character type?

If we fix the support material to be a specific character $$$c$$$ (e.g., 'a'), we need to find the longest substring $$$s[l \dots r]$$$ such that $$$s[l] = s[r] = c$$$ and the count of $$$c$$$ inside is at most $$$k$$$.

For a fixed character $$$c$$$, as we extend the right endpoint $$$r$$$, the number of $$$c$$$'s increases monotonically. This suggests we can use a Two Pointers (Sliding Window) approach.

Maintain a window $$$[l, r]$$$. Expand $$$r$$$; if the count of $$$c$$$ exceeds $$$k$$$, advance $$$l$$$.

Crucially, a valid bridge must start with $$$c$$$. So, whenever $$$s[l] \neq c$$$, increment $$$l$$$ until $$$s[l] == c$$$ (or $$$l \gt r$$$). Update the answer only when $$$s[r] == c$$$.

The problem asks us to find the longest substring $$$s[l \dots r]$$$ such that $$$s[l] = s[r] = c$$$ (for some character $$$c$$$) and the number of occurrences of $$$c$$$ in that substring is at most $$$k$$$.

Since the set of possible materials is small (lowercase Latin letters 'a' through 'z'), we can iterate through each character from 'a' to 'z' and treat it as the potential "support material" $$$c$$$. For a fixed character $$$c$$$, we want to maximize $$$r - l + 1$$$ subject to the constraints.

Sliding Window Approach:

For a fixed character $$$c$$$, we can use the Two Pointers (or Sliding Window) technique to find the optimal segment:

1. Initialize two pointers, l (left) and r (right), both at 0, and a counter cnt to 0.
2. Iterate r from $$$0$$$ to $$$n-1$$$:
   • If $$$s[r] == c$$$, we increment cnt.
   • Constraint 1 (Safety): If cnt exceeds $$$k$$$, we must shrink the window from the left. We increment l until cnt drops back to $$$k$$$. (Don't forget to decrement cnt if we pass an occurrence of $$$c$$$ at $$$s[l]$$$).
   • Constraint 2 (Structure): A valid bridge must start with the support material ($$$s[l] == c$$$). If $$$s[l] \neq c$$$, we can safely advance l forward because a valid bridge cannot start there. We repeat this until $$$s[l] == c$$$ or $$$l$$$ catches up to $$$r$$$.
   • Update Answer: If the current window is valid (meaning cnt $$$\le k$$$ and the window actually starts and ends with $$$c$$$), we update the maximum length answer with $$$r - l + 1$$$. Note: We only need to check if $$$s[r] == c$$$ to trigger an update, because our logic ensures $$$s[l]$$$ is valid.

After checking all characters 'a' through 'z', the global maximum is our answer.

Time Complexity

We iterate through the string 26 times (once for each lowercase letter). Inside each iteration, the two pointers l and r traverse the string at most once.
The total time complexity is $$$O(26 \cdot N)$$$, which simplifies to $$$O(N)$$$. Given $$$N \le 2 \cdot 10^5$$$, this fits easily within the time limit.

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

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

    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;

        string s;
        cin >> s;

        int ans = 0;

        for(char c = 'a'; c <= 'z'; c++){
            int l = 0, cnt = 0;
            for(int r = 0; r < n; r++){
                if(s[r] == c){
                    cnt++;
                }
                while(cnt > k){
                    if(s[l] == c){
                        cnt--;
                    }
                    l++;
                }
                while(l < r && s[l] != c){
                    l++;
                }
                if(s[r] == c){
                    ans = max(ans, r - l + 1);
                }
            }
        }

        if(k == 0){
            cout << 0 << '\n';
        }else{
            cout << ans << '\n';
        }
    }
}

Analyze the bitwise difference for small numbers manually.
$$$1 (01) \to 2 (10)$$$: Difference is 2 bits. (Ends in 1 one)
$$$3 (011) \to 4 (100)$$$: Difference is 3 bits. (Ends in 2 ones)
$$$7 (0111) \to 8 (1000)$$$: Difference is 4 bits. (Ends in 3 ones)

Do you see the relationship between the number of trailing ones and the bitwise difference?

If a number ends in exactly $$$p$$$ ones, adding 1 will flip those $$$p$$$ ones to zeros and flip the next zero to a one. The total change is $$$p+1$$$ bits.
To get a difference of exactly $$$k$$$, the number must end in exactly $$$k-1$$$ ones.

We need to count numbers $$$i \lt n$$$ that end in the pattern ...011...1 (with $$$k-1$$$ ones).
This pattern repeats every $$$2^k$$$ numbers.

We need to count how many integers $$$i$$$ in the range $$$[0, n-1]$$$ change exactly $$$k$$$ bits when incremented to $$$i+1$$$.

Mathematical Derivation

1. The Bitwise Property
When we add $$$1$$$ to an integer $$$i$$$, the number of bits that flip is determined by the number of trailing ones in $$$i$$$.
Specifically, if $$$i$$$ ends with $$$z$$$ ones (e.g., $$$\dots 0\underbrace{11\dots1}_{z}$$$), adding $$$1$$$ will flip all those $$$z$$$ ones to zeros, and flip the zero immediately to their left to a one.
The total bits changed (the bitwise difference) is $$$z + 1$$$.

2. The Condition
We are given that the difference is $$$k$$$.

3. The Formula
This pattern repeats with a period of $$$2^k$$$. The first number satisfying this is $$$2^{k-1} - 1$$$.
To count how many such numbers exist strictly less than $$$n$$$, we can use the direct formula for counting arithmetic progressions:

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

void solve() {
    int n, k;
    cin >> n >> k;
    if (k == 0) {
        cout << 0 << endl;
        return;
    }
    int ans = (n + (1ll << (k - 1))) >> k;
    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Use the property that $$$\lfloor a/i \rfloor$$$ takes at most $$$2\sqrt{a}$$$ distinct values.
This is often called the Harmonic Lemma.

You can find all ranges $$$[l, r]$$$ where $$$\lfloor a/i \rfloor$$$ is constant using the standard loop:
for(l=1; l<=n; l=r+1) r=n/(n/l);
The number of $$$i$$$'s yielding a specific floor value in this range is $$$r - l + 1$$$.

Store the frequency of each floor value for $$$a$$$ in a map (or a vector of pairs).
Do the same for $$$b$$$.
Finally, iterate through the stored values. If a value $$$k$$$ appears in both, add $$$(\text{freq}_a[k] \times \text{freq}_b[k])$$$ to the answer.

The total answer is the sum over all possible values of $$$k$$$:

1. The Harmonic Lemma
A key property of the floor function is that the value $$$\lfloor n/i \rfloor$$$ takes at most $$$2\sqrt{n}$$$ distinct values as $$$i$$$ ranges from $$$1$$$ to $$$n$$$.
Furthermore, these values remain constant over contiguous ranges of $$$i$$$. We can iterate through these ranges efficiently using the standard "Square Root Decomposition" loop (also called the Harmonic Lemma loop):
for (l=1; l<=n; l=r+1) r=n/(n/l)
In each iteration, the floor value $$$val = \lfloor n/l \rfloor$$$ is constant for all $$$i \in [l, r]$$$. The number of such $$$i$$$'s is simply the length of the range: $$$r - l + 1$$$.

2. The Strategy
We can compute the frequency of every floor value produced by $$$a$$$ and store it in a map (or a list). We do the same for $$$b$$$.
Then, we iterate through the values generated by $$$a$$$. If a value $$$k$$$ is also generated by $$$b$$$, we multiply their frequencies and add to the total.

Time Complexity: $$$O(\sqrt{a} + \sqrt{b})$$$ (or with log factor if using maps). Given the constraint on the sum of square roots, this fits comfortably within the time limit.

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

#define int long long
#define MOD 1000000007

void solve(){
    int a , b ;
    cin >> a >> b ;
    map<int,int> mp1;
    for (int l=1; l<=a; ){
        int val = a/l;
        if (val == 0) break; 
        int r = a/val;
        if (r > a) r = a;
        int count = (r &mdash; l + 1) % MOD;
        mp1[val] = (mp1[val] + count) % MOD;
        l = r + 1;
    }
    int ans = 0;
    for (int l=1; l<=b; ){
        int val = b/l;
        if (val == 0) break;
        int r = b/val;
        int countB = (r &mdash; l + 1) % MOD;
        if (mp1.count(val)) {
            int countA = mp1[val];
            int pairs = (countA * countB) % MOD;
            ans = (ans + pairs) % MOD;
        }
        
        l = r + 1;
    }
    
    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}