A cell $$$(i, j)$$$ has a wall to stop a bullet only if:

1. It hit the Right Edge: $$$j = n - 1$$$ (the right border of the board).

2. It hit the Bottom Edge: $$$i = n - 1$$$ (the bottom border of the board).

3. It hit another 1: There is already a 1 sitting at $$$(i, j+1)$$$ or at $$$(i+1, j)$$$.

The Check : Look at every cell containing a 1. Ask yourself: "How did this 1 manage to stop here?"If it is on the bottom row or rightmost column: It stopped because of the border. $$$\rightarrow$$$ Valid!If it is NOT on the border: At least one of these MUST be true:The cell below it $$$(i+1, j)$$$ is a 1.The cell to its right $$$(i, j+1)$$$ is a 1.

Starting reverse iteration from the bottom right of the grid.

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

Target Score ($$$m$$$):Let $$$m$$$ be the second smallest missing non-negative integer in $$$S$$$. When Dewansh adds $$$\text{MEX}(S)$$$ on the first move, the new MEX of the set becomes $$$m$$$.Maintaining the State:Because Aditya can only remove a number $$$y \lt x$$$ (where $$$x$$$ is the number Dewansh just played):On the first move, Dewansh plays $$$x = \text{MEX}(S)$$$. Aditya can only remove $$$y \lt \text{MEX}(S)$$$.Dewansh immediately responds by playing $$$x' = y$$$.Aditya must now remove a strictly smaller number $$$y' \lt y$$$.This forces a strictly decreasing sequence of removals by Aditya ($$$y \gt y' \gt y" \gt \dots \ge 0$$$).

#include <iostream>
#include <vector>

using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> s(n);
	for (int i = 0; i < n; ++i)
		cin >> s[i];
	int mex = -1;
	for (int i = 0; i < n; ++i) {
		if (i == 0 && s[i] != 0) {
			mex = 0;
			break;
		}
		if (i > 0 && s[i] != s[i - 1] + 1) {
			mex = s[i - 1] + 1;
			break;
		}
	}
	if (mex == -1)
		mex = s[n - 1] + 1;
	cout << mex << endl;
	int y;
	cin >> y;
	while (y != -1) {
		cout << y << endl;
		cin >> y;
	}
}

int main() {
	int t;
	cin >> t;
	while (t--)
		solve();

	return 0;
}

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

Digits are independent to each other and order does not matter

Define dp[i][j] length of digit i if i do j operations on it Transitions : dp[i][j] = dp[i+1][j-1] when 0<=i<=8 = dp[0][j-1] + dp[1][j-1] when i==9 because when i==9 and u do one more operation then it will be 10 so add the contribution of 1 and 0

Precompute this otherwise TC will be m*t which will TLE After precomputing dp[i][j] just multiply it with the number of its occcurences in the given number n

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD1 998244353
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
const int nMax = 2 * 1e5 + 10;

ll dp[10][nMax];
void solve() {
	int t;
	cin >> t;
	for (int i = 0; i <= 9; i++) {
		dp[i][0] = 1;
	}
	for (int i = 1; i < nMax; i++) {
		for (int j = 0; j <= 8; j++) {
			dp[j][i] = dp[j + 1][i &mdash; 1];
		}
		dp[9][i] = mod_add(dp[0][i &mdash; 1], dp[1][i &mdash; 1], MOD);
	}
	while (t--) {
		int n, m;
		cin >> n >> m;
		vector<ll> occ(10, 0);
		while (n > 0) {
			occ[n % 10]++;
			n /= 10;
		}
		ll ans = 0;
		for (int i = 0; i < 10; i++) {
			ll x = dp[i][m];
			ll y = occ[i];
			ans = mod_add(mod_mul(x, y, MOD), ans, MOD);
		}
		cout << ans << endl;
	}
}

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

#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);
        loop(i,n) a[i] = abs(a[i]);
        sort(all(a));
        int ans=0;
        for(int i=0;i<n-1;i++){
            auto it = upper_bound(all(a),2*a[i]);
            int idx = -1;
            if(it!=a.begin()){
                it--;
                idx = it-a.begin();
            }
            if(idx>i) ans+=(idx-i);
        }
        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:

The total amount of magic powder required across all $$$n$$$ ingredients to bake $$$M$$$ cookies is:

Aditya can bake $$$M$$$ cookies if and only if the total magic powder required does not exceed his available supply $$$k$$$:

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

The problem defines $$$f(b)$$$ on an array $$$b = [b_1, b_2, \dots, b_m]$$$ as:

Defining DP State: dp[i][j]:dp[i][j] operates on two parameters:i (Row index): Represents the length offset of the subarray (i.e., $$$\text{Length} - 1$$$). So row i corresponds to subsegments of length $$$i + 1$$$.j (Column index): Represents the 0-based starting index of the subarray.Therefore, dp[i][j] directly addresses the subsegment $$$a[j \dots j + i]$$$.

Subsegments of Length 1 ($$$a[j \dots j]$$$).

Subsegments of Length i + 1 ($$$a[j \dots j+i]$$$).

Now just Overwriting dp[i][j] to store Maximum Value

You can see this transition by considering the subsegment $$$[x, y, z]$$$ of length 3: Direct computation of $$$f(x, y, z)$$$:

$$\text

DP view: * Left pair $$$[x, y]$$$ has $$$f(x, y) = x \oplus y \quad \rightarrow \text{dp}[2][j]$$$ * Right pair $$$[y, z]$$$ has $$$f(y, z) = y \oplus z \quad \rightarrow \text{dp}[2][j+1]$$$

For subarray of length 3 ($$$i=3$$$):

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

const int N = 5000;

int a[N];
int dp[N][N];

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

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

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            dp[i][j] = max({dp[i][j], dp[i - 1][j], dp[i - 1][j + 1]});
        }
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        --l; 
        int len = r - l - 1; 
        cout << dp[len][l] << '\n';
    }
    return 0;
}

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

    run();
    return 0;
}