Let's see how the matrix looks like after some sequence of shoots:

The matrix consists of 0, or There is at least one 1 at position (n,i) or (i,n), and any 1 not at position (n,j) or (j,n) must have 1 below or right.If the second condition is violated, then the 1 in the corresponding cell would continue its flight. Thus, it is necessary and sufficient to verify that the matrix satisfies the condition above.

#include <bits/stdc++.h>

using namespace std;

bool a[50][50];

int main() {
  int tests;
  cin >> tests;
  while (tests--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        char c;
        cin >> c;
        a[i][j] = c - '0';
      }
    }

    bool ans = true;
    for (int i = n - 2; i >= 0; --i) {
      for (int j = n - 2; j >= 0; --j) {
        if (a[i][j] && !a[i + 1][j] && !a[i][j + 1]) {
          ans = false;
        }
      }
    }

    cout << (ans ? "YES" : "NO") << endl;
  }
}

If an apple starts at vertex $$$u$$$, it can move down to any leaf node located within $$$u$$$'s subtree. How many total possible leaf nodes can an apple at $$$u$$$ reach?

Since choices for the movement of the apple starting at $$$x$$$ and the apple starting at $$$y$$$ are completely independent of each other, the total number of ordered pairs $$$(a, b)$$$ of final leaf vertices is simply:

The problem asks us to find the number of pairs $$$(a, b)$$$ where $$$a$$$ is a possible leaf that an apple at vertex $$$x$$$ can reach, and $$$b$$$ is a possible leaf that an apple at vertex $$$y$$$ can reach.Leaf Vertices: A vertex $$$u$$$ (other than the root $$$1$$$) is a leaf if it has a degree of $$$1$$$ (i.e., no children in the rooted tree). The root $$$1$$$ is a leaf only if $$$n = 1$$$, but here $$$n \ge 2$$$.Subtree Leaf Count: Let $$$C[u]$$$ denote the number of leaf nodes contained in the subtree rooted at vertex $$$u$$$.If $$$u$$$ is a leaf node, $$$C[u] = 1$$$.If $$$u$$$ is an internal node, $$$C[u] = \sum_{v \in \text{children}(u)} C[v]$$$.Query Evaluation: For each query $$$(x, y)$$$, the apple at $$$x$$$ can land on any of the $$$C[x]$$$ leaves in $$$x$$$'s subtree, and the apple at $$$y$$$ can land on any of the $$$C[y]$$$ leaves in $$$y$$$'s subtree. By the fundamental counting principle, the total number of distinct pairs $$$(a, b)$$$ is:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define loop(i, n) for (int i = 0; i < n; i++)
#define loop1(i, n) for (int i = 1; i <= n; i++)
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
#define vin(a) for (int i = 0; i < (a).size(); i++) cin >> a[i];
#define sz(x) ((int)(x).size())
#define endl '\n'
#define pb push_back
const int N = 2e5+2;
vvi adj(N);
vi ans(N);
void dfs(int strt,int par){
    int enter = 0;
    for(auto child:adj[strt]){
        if(child == par) continue;
        enter = 1;
        dfs(child,strt);
        ans[strt]+=ans[child];
    }
    if(enter==0) ans[strt] = 1; // leaf node
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int n; cin >> n;
        loop1(i,n) ans[i] = 0,adj[i].clear(); // clear
        loop(i,n-1){
            int u,v;
            cin>>u>>v;
            adj[u].pb(v);
            adj[v].pb(u);
        }
        dfs(1,-1);
        int q;
        cin>>q;
        while(q--){
            int u,v;
            cin>>u>>v;
            cout<<ans[v]*ans[u]<<endl;
        }
    }
    return 0;
}

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";
    }
}

Jai wants to maximize the score, while Tarun wants to minimize it. Note : 1st position is always occupied by '(' and last position is occupied by ')' So, Jai will place biggest element in the very start if the array to maximise score Now since, Tarun wants to minimize the score will now place '(' in the second max element of the array

This concludes ans = 1st max — 2nd max + 3rd max — 4th min and so on.....

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(), v.end()
#define loop(i, n) for (int i = 0; i < n; i++)
typedef vector<int> vi;
#define vin(a) for (int i = 0; i < (a).size(); i++) cin >> a[i];
#define sz(x) ((int)(x).size())

signed main() {
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t=1;
    // cin >> t;
    while (t--) {
        int n; cin >> n;
        vi a(n);
        vin(a);
        sort(all(a),greater<int>());
        int ans=0;
        for(int i=0;i<n;i+=2) ans+=(a[i]-a[i+1]);
        cout<<ans<<endl;
        
    }
    return 0;
}

Is the function $$$f(M) = \text{"Can we bake } M \text{ cookies?"}$$$ monotonic?

Binary Search

To bake $$$M$$$ cookies, the $$$i$$$-th ingredient requires a total of $$$M \cdot a_i$$$ grams.Aditya already possesses $$$b_i$$$ grams of the $$$i$$$-th ingredient. Therefore, the deficit (extra amount needed) for ingredient $$$i$$$ is:

Monotonicity:If we can bake $$$x$$$ cookies, we can also bake $$$x - 1$$$ cookies. The predicate function $$$f(x) = \text{"Can bake } x \text{ cookies?"}$$$ forms a monotonic pattern: $$$\text{TTTT}\dots\text{FFFF}\dots$$$. We simply binary search for the rightmost $$$\text{True}$$$ to get the maximum possible cookies.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(), v.end()
#define loop(i, n) for (int i = 0; i < n; i++)
typedef vector<int> vi;
#define vin(a) for (int i = 0; i < (a).size(); i++) cin >> a[i];
#define pb push_back
#define sz(a) (int)a.size()
bool good(vi& a, vi& b, int mid, int k) {
    int n = sz(a);
    int dec = 0;
    loop(i, n) {
        int req = a[i] * mid;
        if (req > b[i]) {
            dec += (req &mdash; b[i]);
        }
        if (dec > k) return 0;
    }
    return 1;
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t=1;
    // cin >> t;
    while (t--) {
        int n,k; cin >> n >> k;
        vi a(n),b(n);
        vin(a);vin(b);
        // Binary search -> ttttfff.. <- pattern
        int l=0,r=2e9;
        int ans=0;
        while(l<=r){
            int m = l+(r-l)/2;
            if(good(a,b,m,k)) ans=max(ans,m),l=m+1;
            else r=m-1;
        }
        cout<<ans<<endl;

    }
    return 0;
}

In 1 step, we can move the center by any distance $$$x \in (0, 2r]$$$ by choosing an appropriate rotation angle $$$\theta = 2 \arcsin\left(\frac{x}{2r}\right)$$$.Therefore, if $$$d \% 2r \neq 0$$$, we take $$$\lfloor \frac{d}{2r} \rfloor$$$ steps of length $$$2r$$$ plus 1 smaller step of length $$$d \bmod 2r$$$, totaling $$$\lceil \frac{d}{2r} \rceil$$$ steps.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define loop(i, n) for (int i = 0; i < n; i++)
#define print_vec(a) for (int i = 0; i < a.size(); i++) cout << a[i] << " ";
#define endl '\n'
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int r, x, y, xf, yf;
    cin >> r >> x >> y >> xf >> yf;
    int dx = xf - x;
    int dy = yf - y;
    
    int d2 = dx*dx + dy*dy;
    double d = sqrtl(d2);

    int ans = ceil(d/(2.0*r));
    
    cout << ans << "\n";


    return 0;
}

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

using namespace std;

void solve() {
    vector<long long> x(4);
    for (int i = 0; i < 4; ++i) {
        cin >> x[i];
    }
    sort(x.begin(), x.end());

    // S = x[3] = a + b + c
    long long a = x[3] - x[2];
    long long b = x[3] - x[1];
    long long c = x[3] - x[0];

    cout << a << " " << b << " " << c << "\n";
}

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

We construct the array starting with $$$P_1 = 1$$$. Each subsequent term $$$P_i$$$ ($$$1 \lt i \le N$$$) is formed by alternatingly applying step sizes (jumps) of $$$N$$$ and $$$N+2$$$:

$$$P_i = \vert{}N - P_{i-1}\vert{}$$$ if $$$i$$$ is odd,
$$$P_i = \vert{}(N + 2) - P_{i-1}\vert{}$$$ if $$$i$$$ is even.

Modulo $$$(N+1)$$$, notice that:
$$$N \equiv -1 \pmod{N+1}$$$
$$$N+2 \equiv +1 \pmod{N+1}$$$

2. Jump Sum Analysis ($$$L$$$):

For a contiguous block of length $$$k$$$, the jump sum $$$L_k$$$ alternates between terms of $$$N$$$ and $$$N+2$$$. The possible jump sums $$$L$$$ take two forms:

$$$\text{Type 1 (starts with } N \text{)}: N + (N+2) + N + (N+2) + \dots$$$
$$$\text{Type 2 (starts with } N+2 \text{)}: (N+2) + N + (N+2) + N + \dots$$$

For example, when $$$k = 3$$$:
$$$\text{Type 1: } N + (N+2) + N = 3N + 2$$$
$$$\text{Type 2: } (N+2) + N + (N+2) = 3N + 4$$$

Let L be the above value

3. Parity & Impossibility Proof:

Let's analyze $$$L$$$ and $$$N+1$$$ based on the parity of $$$N$$$:

It will be different in both the cases either n = even or odd which implies L%(N+1) can never be equals to zero

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define loop(i, n) for (int i = 0; i < n; i++)
#define print_vec(a) for (int i = 0; i < a.size(); i++) cout << a[i] << " ";
#define endl '\n'
signed main() {
    int t=1;
    // cin >> t;
    while (t--) {
        int n; cin >> n;
        int s = (n*(n+1))/2;
        if(s%(n+1)){
            vi ans(n);
            ans[0] = 1;
            for(int i=1;i<n;i++){
                if(i&1) ans[i] = abs(n-ans[i-1]);
                else ans[i] = abs(n+2-ans[i-1]);
            }
            print_vec(ans);
            cout<<endl;
        }else cout<<-1<<endl;

    }
    return 0;
}