[Contest Invitation Link](https://codeforces.me/contestInvitation/5b1cf34ceffdff36594de2635d90277adf694a5c) ↵
↵
[Problem A : Tarun and the Cannon Range](https://codeforces.me/gym/709639/problem/A) <br>↵
↵
↵
<spoiler summary="Solution">↵
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 continueA 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 itsflright. Thus, it is necessary and sufficient to verify that the matrix satisfies the condition above $(i, j+1)$ is a 1.↵
↵
Starting reverse iteration from the bottom right of the grid.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[Problem B : Aditya's Apple Tree](https://codeforces.me/gym/709639/problem/B) <br>↵
↵
↵
<spoiler summary="Hint 1">↵
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?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
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:$$\text{Total Pairs} = (\text{leaf count in subtree of } x) \times (\text{leaf count in subtree of } y)$$↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
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:$$\text{Ans} = C[x] \cdot C[y]$$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[Problem C : Dewansh and the MEX Game](https://codeforces.me/gym/709639/problem/C) <br>↵
↵
↵
<spoiler summary="Solution">↵
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 < x$ (where $x$ is the number Dewansh just played):On the first move, Dewansh plays $x = \text{MEX}(S)$. Aditya can only remove $y < \text{MEX}(S)$.Dewansh immediately responds by playing $x' = y$.Aditya must now remove a strictly smaller number $y' < y$.This forces a strictly decreasing sequence of removals by Aditya ($y > y' > y'' > \dots \ge 0$).↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[Problem D : Jai, Tarun, and the Parentheses Game](https://codeforces.me/gym/709639/problem/D) <br>↵
↵
↵
<spoiler summary="Solution">↵
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 minax and so on.....↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[Problem E : Dewansh and the Growing Digits](https://codeforces.me/gym/709639/problem/E) <br>↵
↵
↵
<spoiler summary="Hint">↵
Digits are independent to each other and order does not matter↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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 ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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 — 1];↵
}↵
dp[9][i] = mod_add(dp[0][i — 1], dp[1][i — 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();↵
}↵
~~~~~↵
</spoiler>↵
↵
[Problem F : Aditya and Vectorland](https://codeforces.me/gym/709639/problem/F) <br>↵
↵
↵
<spoiler summary="Solution">↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[Problem G : Aditya and the Magic Powder](https://codeforces.me/gym/709639/problem/G) <br>↵
↵
↵
<spoiler summary="Hint 1">↵
↵
Is the function $f(M) = \text{"Can we bake } M \text{ cookies?"}$ monotonic?↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
↵
Binary Search↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
<spoiler summary="spoiler">↵
See Solution↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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:↵
↵
$$\text{Deficit}_i(M) = \max\left(0, M \cdot a_i - b_i\right)$$↵
↵
The total amount of magic powder required across all $n$ ingredients to bake $M$ cookies is:↵
↵
$$P(M) = \sum_{i=1}^{n} \max\left(0, M \cdot a_i - b_i\right)$$↵
↵
Aditya can bake $M$ cookies if and only if the total magic powder required does not exceed his available supply $k$:↵
↵
$$P(M) \le 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.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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 — 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;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[Problem H : Tarun and the rolling circle](https://codeforces.me/gym/709639/problem/H) <br>↵
↵
↵
<spoiler summary="Solution">↵
↵
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.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[Problem I : Dewansh and the Secret Numbers](https://codeforces.me/gym/709639/problem/I) <br>↵
↵
↵
<spoiler summary="Solution">↵
↵
$$\begin{aligned} a &= S - (b + c) = x_4 - x_3 \\ b &= S - (a + c) = x_4 - x_2 \\ c &= S - (a + b) = x_4 - x_1 \end{aligned}$$↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[Problem J : Jai's Permutation](https://codeforces.me/gym/709639/problem/J) <br>↵
↵
<spoiler summary="Solution">↵
↵
We construct the array starting with $P_1 = 1$. Each subsequent term $P_i$ ($1 < i \le N$) is formed by alternatingly applying step sizes (jumps) of $N$ and $N+2$:<br><br>↵
↵
$P_i = \vert{}N - P_{i-1}\vert{}$ if $i$ is odd,<br>↵
$P_i = \vert{}(N + 2) - P_{i-1}\vert{}$ if $i$ is even.<br><br>↵
↵
Modulo $(N+1)$, notice that:<br>↵
$N \equiv -1 \pmod{N+1}$<br>↵
$N+2 \equiv +1 \pmod{N+1}$<br><br>↵
↵
<b>2. Jump Sum Analysis ($L$):</b><br><br>↵
↵
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:<br><br>↵
↵
$\text{Type 1 (starts with } N \text{)}: N + (N+2) + N + (N+2) + \dots$<br>↵
$\text{Type 2 (starts with } N+2 \text{)}: (N+2) + N + (N+2) + N + \dots$<br><br>↵
↵
For example, when $k = 3$:<br>↵
$\text{Type 1: } N + (N+2) + N = 3N + 2$<br>↵
$\text{Type 2: } (N+2) + N + (N+2) = 3N + 4$<br><br>↵
Let L be the above value ↵
↵
<b>3. Parity & Impossibility Proof:</b><br><br>↵
↵
Let's analyze $L$ and $N+1$ based on the parity of $N$:<br><br>↵
It will be different in both the cases either n = even or odd which implies L%(N+1) can never be equals to zero↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[Problem K : Dewansh and the XOR-pyramid](https://codeforces.me/gym/709639/problem/K) <br>↵
↵
↵
<spoiler summary="Solution">↵
The problem defines $f(b)$ on an array $b = [b_1, b_2, \dots, b_m]$ as:$$f(b) = f(b_1 \oplus b_2, \; b_2 \oplus b_3, \; \dots, \; b_{m-1} \oplus b_m)$$↵
↵
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]$).$$\text{dp}[0][j] = a[j]$$↵
Subsegments of Length i + 1 ($a[j \dots j+i]$).$$\text{dp}[i][j] = \text{dp}[i-1][j] \oplus \text{dp}[i-1][j+1]$$↵
↵
Now just Overwriting dp[i][j] to store Maximum Value↵
$$\text{dp}[i][j] = \max\Big(\text{dp}[i][j], \; \text{dp}[i-1][j], \; \text{dp}[i-1][j+1]\Big)$$↵
You can see this transition by considering the subsegment $[x, y, z]$ of length 3:↵
Direct computation of $f(x, y, z)$:$$\text{Step 1 reduction: } [x \oplus y, \; y \oplus z]$$$$\text↵
$$\text{Step 2 reduction: } (x \oplus y) \oplus (y \oplus z)$$↵
↵
**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$):↵
↵
$$\text{dp}[3][j] = \text{dp}[2][j] \oplus \text{dp}[2][j+1] = (x \oplus y) \oplus (y \oplus z)$$↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
[Problem A : Tarun and the Cannon Range](https://codeforces.me/gym/709639/problem/A) <br>↵
↵
↵
<spoiler summary="Solution">↵
↵
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
↵
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
↵
Starting reverse iteration from the bottom right of the grid.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[Problem B : Aditya's Apple Tree](https://codeforces.me/gym/709639/problem/B) <br>↵
↵
↵
<spoiler summary="Hint 1">↵
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?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
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:$$\text{Total Pairs} = (\text{leaf count in subtree of } x) \times (\text{leaf count in subtree of } y)$$↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
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:$$\text{Ans} = C[x] \cdot C[y]$$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[Problem C : Dewansh and the MEX Game](https://codeforces.me/gym/709639/problem/C) <br>↵
↵
↵
<spoiler summary="Solution">↵
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 < x$ (where $x$ is the number Dewansh just played):On the first move, Dewansh plays $x = \text{MEX}(S)$. Aditya can only remove $y < \text{MEX}(S)$.Dewansh immediately responds by playing $x' = y$.Aditya must now remove a strictly smaller number $y' < y$.This forces a strictly decreasing sequence of removals by Aditya ($y > y' > y'' > \dots \ge 0$).↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[Problem D : Jai, Tarun, and the Parentheses Game](https://codeforces.me/gym/709639/problem/D) <br>↵
↵
↵
<spoiler summary="Solution">↵
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 m
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
</spoiler>↵
↵
[Problem E : Dewansh and the Growing Digits](https://codeforces.me/gym/709639/problem/E) <br>↵
↵
↵
<spoiler summary="Hint">↵
Digits are independent to each other and order does not matter↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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 ↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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 — 1];↵
}↵
dp[9][i] = mod_add(dp[0][i — 1], dp[1][i — 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();↵
}↵
~~~~~↵
</spoiler>↵
↵
[Problem F : Aditya and Vectorland](https://codeforces.me/gym/709639/problem/F) <br>↵
↵
↵
<spoiler summary="Solution">↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[Problem G : Aditya and the Magic Powder](https://codeforces.me/gym/709639/problem/G) <br>↵
↵
↵
<spoiler summary="Hint 1">↵
↵
Is the function $f(M) = \text{"Can we bake } M \text{ cookies?"}$ monotonic?↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
↵
Binary Search↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
<spoiler summary="spoiler">↵
See Solution↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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:↵
↵
$$\text{Deficit}_i(M) = \max\left(0, M \cdot a_i - b_i\right)$$↵
↵
The total amount of magic powder required across all $n$ ingredients to bake $M$ cookies is:↵
↵
$$P(M) = \sum_{i=1}^{n} \max\left(0, M \cdot a_i - b_i\right)$$↵
↵
Aditya can bake $M$ cookies if and only if the total magic powder required does not exceed his available supply $k$:↵
↵
$$P(M) \le 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.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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 — 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;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[Problem H : Tarun and the rolling circle](https://codeforces.me/gym/709639/problem/H) <br>↵
↵
↵
<spoiler summary="Solution">↵
↵
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.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[Problem I : Dewansh and the Secret Numbers](https://codeforces.me/gym/709639/problem/I) <br>↵
↵
↵
<spoiler summary="Solution">↵
↵
$$\begin{aligned} a &= S - (b + c) = x_4 - x_3 \\ b &= S - (a + c) = x_4 - x_2 \\ c &= S - (a + b) = x_4 - x_1 \end{aligned}$$↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[Problem J : Jai's Permutation](https://codeforces.me/gym/709639/problem/J) <br>↵
↵
<spoiler summary="Solution">↵
↵
We construct the array starting with $P_1 = 1$. Each subsequent term $P_i$ ($1 < i \le N$) is formed by alternatingly applying step sizes (jumps) of $N$ and $N+2$:<br><br>↵
↵
$P_i = \vert{}N - P_{i-1}\vert{}$ if $i$ is odd,<br>↵
$P_i = \vert{}(N + 2) - P_{i-1}\vert{}$ if $i$ is even.<br><br>↵
↵
Modulo $(N+1)$, notice that:<br>↵
$N \equiv -1 \pmod{N+1}$<br>↵
$N+2 \equiv +1 \pmod{N+1}$<br><br>↵
↵
<b>2. Jump Sum Analysis ($L$):</b><br><br>↵
↵
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:<br><br>↵
↵
$\text{Type 1 (starts with } N \text{)}: N + (N+2) + N + (N+2) + \dots$<br>↵
$\text{Type 2 (starts with } N+2 \text{)}: (N+2) + N + (N+2) + N + \dots$<br><br>↵
↵
For example, when $k = 3$:<br>↵
$\text{Type 1: } N + (N+2) + N = 3N + 2$<br>↵
$\text{Type 2: } (N+2) + N + (N+2) = 3N + 4$<br><br>↵
Let L be the above value ↵
↵
<b>3. Parity & Impossibility Proof:</b><br><br>↵
↵
Let's analyze $L$ and $N+1$ based on the parity of $N$:<br><br>↵
It will be different in both the cases either n = even or odd which implies L%(N+1) can never be equals to zero↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[Problem K : Dewansh and the XOR-pyramid](https://codeforces.me/gym/709639/problem/K) <br>↵
↵
↵
<spoiler summary="Solution">↵
The problem defines $f(b)$ on an array $b = [b_1, b_2, \dots, b_m]$ as:$$f(b) = f(b_1 \oplus b_2, \; b_2 \oplus b_3, \; \dots, \; b_{m-1} \oplus b_m)$$↵
↵
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]$).$$\text{dp}[0][j] = a[j]$$↵
Subsegments of Length i + 1 ($a[j \dots j+i]$).$$\text{dp}[i][j] = \text{dp}[i-1][j] \oplus \text{dp}[i-1][j+1]$$↵
↵
Now just Overwriting dp[i][j] to store Maximum Value↵
$$\text{dp}[i][j] = \max\Big(\text{dp}[i][j], \; \text{dp}[i-1][j], \; \text{dp}[i-1][j+1]\Big)$$↵
You can see this transition by considering the subsegment $[x, y, z]$ of length 3:↵
Direct computation of $f(x, y, z)$:$$\text{Step 1 reduction: } [x \oplus y, \; y \oplus z]$$$$\text↵
$$\text{Step 2 reduction: } (x \oplus y) \oplus (y \oplus z)$$↵
↵
**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$):↵
↵
$$\text{dp}[3][j] = \text{dp}[2][j] \oplus \text{dp}[2][j+1] = (x \oplus y) \oplus (y \oplus z)$$↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#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;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
