Congratulations to all the wizards and witches who participated in Codewarts!↵
↵
Here is the official editorial for all the problems.↵
↵
Round 1↵
------------------↵
↵
<spoiler summary="Problem-A: Tom Riddle's Diary">↵
↵
<spoiler summary="Hint-1">↵
Since $N$ is always even, try visualizing the array as $N/2$ non-overlapping pairs of adjacent elements.<br>↵
$(A_1,A_2), (A_3,A_4), \dots$↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
If every pair must sum to a multiple of $P$, what must the total sum $M$ be a multiple of?↵
Given that numbers must be positive, what is the absolute minimum possible total sum?↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
To build the array, try repeating a simple pair like $(1,P-1)$ for most of the array, and put all the remaining required sum into the very last element.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
**When to print NO:**↵
↵
- Because $N$ is even, we can split the array into exactly $N/2$ disjoint pairs. The problem requires every adjacent pair to sum to a multiple of $P$. Therefore, the sum of the entire array, $M$, must also be a multiple of $P$ ($M \bmod P = 0$).↵
↵
- Additionally, since the array requires strictly positive integers ($A_i \ge 1$), the smallest valid sum for any pair is $P$. With $N/2$ pairs, the absolute minimum total sum is $(N/2) \times P$.<br>↵
If $M < (N/2) \times P$, it is impossible.↵
Therefore, if either of these conditions fails, print **NO**.↵
↵
---↵
↵
**When to print YES:**<br>↵
If both conditions are met, print **YES** and construct the array greedily:↵
↵
- **Prefix:** Fill the first $N-2$ positions by alternating $1$ and $P-1$:↵
$1, P-1, 1, P-1, \dots$↵
Every adjacent pair here sums to exactly $P$.↵
↵
- **Second to last element:** Set $A_{N-1} = 1$.↵
Since the prefix always ends in $P-1$, their sum is $P-1+1=P$, which is valid.↵
↵
- **Final element:** Set $A_N$ to whatever value is needed to make the total array sum exactly $M$.↵
↵
Since we already verified that $M \ge (N/2)\times P$, $A_N$ will always be a valid positive integer.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define endl '\n'↵
↵
void solve()↵
{↵
int n, m, p;↵
cin >> n >> m >> p;↵
if ((m % p != 0) || ((m / p) < (n / 2)))↵
{↵
cout << "NO" << endl;↵
}↵
else↵
{↵
cout << "YES" << endl;↵
for (int i = 0; i < n - 2; i += 2)↵
{↵
cout << 1 << " " << p - 1 << " ";↵
m -= p;↵
}↵
cout << 1 << " " << m - 1 << endl;↵
}↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t = 1;↵
cin >> t;↵
while (t--)↵
{↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
**Time Complexity:** $\mathcal{O}(N)$ <br>↵
**Space Complexity:** $\mathcal{O}(1)$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Problem-B: Marvolo Gaunt's Ring">↵
↵
<spoiler summary="Hint-1">↵
↵
Notice that the elements of the transformed array $A$ are powers of $2$ ($A[i] = 2^{b_i}$). <br>↵
Think about the binary representation of numbers. What happens if every element in the array $b$ is completely distinct?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
↵
The sum of any set of strictly distinct powers of $2$ is uniquely determined by its elements. <br>↵
Consider the largest element in any two disjoint subsets. If all $b_i$ are unique, can the subset without the maximum element ever sum up to a value greater than or equal to the maximum element itself?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
↵
Try to determine whether two equal-sum subarrays can exist when every value in $b$ is unique. <br>↵
What changes if two values of $b$ are equal?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
The problem contains a massive bait in the first example's note, leading you to think about complex prefix sums and combining multiple elements to match a single large power of $2$.↵
However, the solution is purely based on a fundamental property of powers of $2$.↵
↵
**Claim:** Two non-overlapping equal-sum subarrays exist if and only if there is at least one duplicate element in the array $b$.↵
↵
The problem fully reduces to checking whether the array $b$ contains any duplicate values.<br>↵
This can be done in two ways:<br>↵
↵
- Sort the array and check adjacent elements.<br>↵
↵
- Use a Hash Set to detect duplicates.↵
↵
<spoiler summary="Proof">↵
↵
**If there is a duplicate:**↵
↵
Suppose $b_i = b_j$ for some $i < j$. We can trivially pick two subarrays of length $1$: $[i,i]$ and $[j,j]$. Since $i < j$, these subarrays are strictly non-overlapping, and their sums are identical: <br>↵
$$A[i] = A[j] = 2^{b_i}$$ <br>↵
Therefore, the answer is **YES**.↵
↵
**If all elements are distinct:** <br>↵
Let's assume all elements in $b$ are strictly unique. Let $S_1$ and $S_2$ be any two disjoint subarrays. Let $M$ be the strictly largest element in $S_1 \cup S_2$. ↵
↵
Without loss of generality, let $M \in S_1$. Because all elements are distinct, the maximum possible sum of $S_2$ would be obtained if it contained every single power of $2$ strictly smaller than $M$. <br>↵
Even in this absolute best-case scenario, the sum of all powers of $2$ up to $2^{k-1}$ is strictly less than $2^k$: <br>↵
$$\sum_{x=0}^{k-1} 2^x = 2^k - 1$$ <br>↵
Therefore, the sum of $S_2$ will always be strictly less than $M$. Hence, <br>↵
$$\text{Sum}(S_2) < \text{Sum}(S_1)$$ <br>↵
and the two subarrays can never have equal sums. Therefore, the answer is **NO**.↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
using namespace std;↵
void solve() {↵
int n;↵
cin >> n;↵
vector<int> b(n);↵
for (int i = 0; i < n; i++) {↵
cin >> b[i];↵
}↵
sort(b.begin(), b.end());↵
bool has_duplicate = false;↵
for (int i = 1; i < n; i++) {↵
if (b[i] == b[i - 1]) {↵
has_duplicate = true;↵
break;↵
}↵
}↵
if (has_duplicate) {↵
cout << "YES\n";↵
} else {↵
cout << "NO\n";↵
}↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
**Using sorting:**<br>↵
Time Complexity: $\mathcal{O}(n \log n)$ <br>↵
Space Complexity: $\mathcal{O}(1)$ if sorting in-place.↵
↵
**Using a Hash Set:** <br>↵
Time Complexity: $\mathcal{O}(n)$ average. <br>↵
Space Complexity: $\mathcal{O}(n)$.↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Problem-C: Salazar Slytherin's Locket">↵
↵
<spoiler summary="Hint-1">↵
↵
Since rearranging the remaining characters is free, the positions of the characters in $s$ do not matter. <br>↵
Think about the problem in terms of the number of $0$ and $1$ available in the string.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
↵
Suppose the final string $t$ has length $k$.<br>↵
For every character of $t$, its value must be different from the character at the same position in $s$.<br>↵
Ask yourself:<br>↵
How many $0$ and $1$ does $t$ need, and how many of each do we have available in $s$?↵
The maximum possible length of $t$ can then be determined from these two frequencies.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
↵
Try matching every character in the original string with an available character of the opposite type.↵
What happens when one of the two types runs out?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
The main observation is that free rearrangement removes the importance of ordering.↵
Let:<br>↵
$cnt_0$ = number of $0$s in $s$ <br>↵
$cnt_1$ = number of $1$s in $s$<br>↵
↵
If $t$ has length $k$, then every $0$ in $t$ must occupy a position where $s$ has a $1$, and every $1$ in $t$ must occupy a position where $s$ has a $0$.<br>↵
Therefore, the number of characters we can keep is limited by the available opposite characters.<br>↵
The important quantity is the maximum number of characters that can remain after matching each character with an opposite character.<br>↵
Since every deleted character costs exactly $1$ coin, once we know the maximum number of characters that can be retained, the answer follows directly.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
string s;↵
cin >> s;↵
int n = s.size();↵
int zeroCount = 0, oneCount = 0;↵
for (char c : s) {↵
if (c == '0') {↵
zeroCount++;↵
} else {↵
oneCount++;↵
}↵
}↵
for (int i = 0; i < n; i++) {↵
if (s[i] == '0') {↵
if (oneCount > 0) {↵
oneCount--;↵
} else {↵
cout << n - i << "\n";↵
return;↵
}↵
} else {↵
if (zeroCount > 0) {↵
zeroCount--;↵
} else {↵
cout << n - i << "\n";↵
return;↵
}↵
}↵
}↵
cout << "0\n";↵
}↵
↵
int main() {↵
int t;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
We only need to count the number of $0$ and $1$.<br>↵
**Time Complexity:** $\mathcal{O}(n)$ per test case<br>↵
**Space Complexity:** $\mathcal{O}(1)$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
Round 2↵
------------------↵
↵
<spoiler summary="Problem-A: Helga Hufflepuff's Cup">↵
↵
<spoiler summary="Hint-1">↵
↵
Don't think of the amplification as changing individual characters.↵
Each character in the original grid is simply replaced by a $K \times K$ block containing the same character.<br>↵
↵
For example, if $K=2$:<br>↵
`X` becomes:<br>↵
`XX` ↵
`XX`↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
↵
For every row of the original grid, we need to:<br>↵
1. Replace every character with $K$ copies of that character horizontally.<br>↵
2. Repeat the resulting row $K$ times vertically.↵
↵
Since the original grid has $M$ rows and $N$ columns, the final grid will have $M \times K$ rows and $N \times K$ columns.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
↵
Think about how the position in the amplified grid maps back to the original grid.↵
For a position $(i,j)$ in the new grid, which original cell does it correspond to?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
The key observation is that every original character is expanded independently into a $K \times K$ block.↵
Suppose the original row is: $$A.X$$↵
For $K=2$, each character is expanded horizontally:<br>↵
$$AA..XX$$<br>↵
and this entire row is printed $K$ times.↵
Therefore, for every input row:<br>↵
↵
- Build an expanded row by repeating each character $K$ times.<br>↵
↵
- Print this expanded row exactly $K$ times.<br>↵
↵
This directly produces the required amplified grid.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
int height, width;↵
int scale;↵
cin >> height >> width >> scale;↵
vector<string> signal(height);↵
for (string &r : signal) {↵
cin >> r;↵
}↵
for (int i = 0; i < scale * height; i++) {↵
for (int j = 0; j < scale * width; j++) {↵
cout << signal[i / scale][j / scale];↵
}↵
cout << '\n';↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
The final grid contains $(M \times K) \times (N \times K)$ characters.↵
Therefore:<br>↵
**Time Complexity:** $\mathcal{O}(MNK^2)$ <br>↵
**Space Complexity:** $\mathcal{O}(NK)$ if we store one expanded row.↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Problem-B: Ravenclaw's Diadem">↵
↵
<spoiler summary="Hint-1">↵
↵
Don't consider $a[i]$ and $b[i]$ independently.↵
If Harry takes a relic, its contribution to the final value $H-D$ is:↵
$+a[i]$↵
<br>↵
If Draco takes it, the contribution is:↵
$-b[i]$↵
<br>↵
Think about what happens when one relic is chosen by Harry and another by Draco.↵
Which property of a relic determines how valuable it is to take before another relic?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
↵
Suppose you have two relics $i$ and $j$, and it is Harry's turn.↵
Compare these two possibilities:<br>↵
↵
↵
- Harry takes $i$, then Draco takes $j$.<br>↵
↵
↵
- Harry takes $j$, then Draco takes $i$.<br>↵
↵
Write the resulting contribution to $H-D$ for both orders and compare them.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
↵
From the pairwise comparison, try to identify a single value for each relic that determines which relic should come first.↵
Once the sorting criterion is known, simulate the alternating turns.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
This is a classic two-player greedy / optimal ordering problem.↵
The important trick is to look at the effect of two consecutive turns together rather than trying to simulate all possible choices.↵
For two relics $i$ and $j$:<br>↵
↵
↵
- If Harry gets $i$ and Draco gets $j$, their combined contribution is:↵
$a[i]-b[j]$<br>↵
↵
↵
- If Harry gets $j$ and Draco gets $i$, their combined contribution is:↵
$a[j]-b[i]$<br>↵
↵
Comparing these expressions reveals that the relevant quantity for each relic is:↵
$a[i]+b[i]$↵
↵
So the game can be transformed into an ordering problem: determine the order in which the relics should be considered based on this combined value.↵
After finding the correct order:<br>↵
↵
- Harry takes the relics at his turns.<br>↵
↵
- Draco takes the relics at his turns.<br>↵
↵
- Add $a[i]$ when Harry takes relic $i$.<br>↵
↵
- Subtract $b[i]$ when Draco takes relic $i$.<br>↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <algorithm>↵
#include <cmath>↵
#include <cstdint>↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long↵
#define pl pair<ll, ll>↵
#define vl vector<ll>↵
#define vpl vector<pl>↵
#define vb vector<bool>↵
#define vvl vector<vl>↵
#define vvpl vector<vpl>↵
#define all(x) (x).begin(), (x).end()↵
#define rall(x) (x).rbegin(), (x).rend()↵
#define f(i, a, b) for (ll i = (a); i < (b); ++i)↵
#define rf(i, a, b) for (ll i = (a); i >= (b); --i)↵
#define each(x, a) for (auto &x : a)↵
#define uniq(x) x.resize(unique(all(x)) - x.begin())↵
#define yes cout << "YES\n"↵
#define no cout << "NO\n";↵
↵
ll M = (1e+9) + 7;↵
↵
using namespace std;↵
↵
bool func(pl &i, pl &j) {↵
if (i.first + i.second != j.first + j.second) {↵
return i.first + i.second > j.first + j.second;↵
} else {↵
return i.first > j.first;↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
ll t;↵
cin >> t;↵
↵
while (t--) {↵
ll n, ans = 0;↵
↵
cin >> n;↵
↵
vl a(n);↵
vl b(n);↵
vvl c(n, vl(3));↵
↵
f(i, 0, n) {↵
cin >> a[i];↵
}↵
↵
f(i, 0, n) {↵
cin >> b[i];↵
↵
c[i][0] = a[i] + b[i];↵
c[i][1] = a[i];↵
c[i][2] = b[i];↵
}↵
↵
sort(all(a));↵
↵
rf(i, n - 1, 0) {↵
if ((n - i) % 2 == 1) {↵
ans += c[i][1];↵
} else {↵
ans -= c[i][2];↵
}↵
}↵
↵
cout << ans << endl;↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
Sorting the relics takes:<br>↵
**Time Complexity:** $\mathcal{O}(n \log n)$<br>↵
↵
The simulation after sorting takes: <br>↵
**Time Complexity:** $\mathcal{O}(n)$<br>↵
↵
Therefore, the overall complexity is:<br>↵
**Time Complexity:** $\mathcal{O}(n \log n)$<br>↵
**Space Complexity:** $\mathcal{O}(n)$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
Round 3↵
------------------↵
↵
<spoiler summary="Problem-A: Good Subarrays">↵
↵
<spoiler summary="Hint-1">↵
↵
The condition says that the sum of the elements in a subarray must be equal to its length.↵
If $\sum_{i=l}^{r} a_i = r-l+1$ <br>↵
what happens if we write the length as a sum of $1$?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
↵
The length of a subarray is exactly the number of elements in it. Therefore:↵
$\sum_{i=l}^{r} a_i = \sum_{i=l}^{r} 1$ <br>↵
Can you move everything to one side?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
↵
After subtracting $1$ from every element, the problem becomes:↵
**Count the number of subarrays whose sum is exactly $0$.** <br>↵
How can prefix sums be used to count zero-sum subarrays efficiently?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
**Key Observation** <br>↵
A subarray $[l,r]$ is good if: $\sum_{i=l}^{r} a_i = r-l+1$ The right-hand side is simply the number of elements in the subarray, so we can write: <br>↵
$$\sum_{i=l}^{r} a_i = \sum_{i=l}^{r} 1$$ <br>↵
Moving everything to the left gives: <br>↵
$$\sum_{i=l}^{r}(a_i-1)=0 = 0$$ <br>↵
This transformation is the key to the problem.↵
↵
**Transformation** <br.>↵
Define a new array $b$ such that: <br>↵
$$b_i=a_i-1$$ <br>↵
Now the original condition becomes: $\sum_{i=l}^{r} b_i=0$ <br>↵
Therefore, instead of directly checking whether the sum of a subarray of $a$ equals its length, we simply need to count the number of **zero-sum subarrays** in $b$.<br>↵
↵
For example, if: $a=[1,2,0,1]$ then:<br>↵
$b=[0,1,-1,0]$ <br>↵
Now we only need to count the subarrays of $b$ whose sum is $0$.↵
↵
**Using Prefix Sums**<br>↵
Let $P_i$ denote the sum of the first $i$ elements of $b$.↵
For a subarray $[l,r]$: $\sum_{i=l}^{r}b_i=P_r-P_{l-1}$ <br>↵
We want this sum to be $0$, so:↵
$P_r-P_{l-1}=0$ <br>↵
which means:↵
$P_r=P_{l-1}$ <br>↵
Therefore, a subarray has sum $0$ exactly when the prefix sum at its two boundaries is the same. <br>↵
So, whenever we encounter a prefix sum that has appeared before, every previous occurrence of that prefix sum gives us one new valid subarray.↵
↵
**Counting the Subarrays**<br>↵
We maintain a frequency map containing how many times each prefix sum has appeared. <br>↵
Initially, the prefix sum is $0$ before processing any elements.↵
Therefore, we initialize: <br>↵
`$\text{freq}[0]=1` <br> = 1$↵
↵
For every element:<br>↵
↵
1. Add the element to the current prefix sum.<br>↵
↵
2. Add`freq[$\text{freq}[\text{prefix]`}]$ to the answer. <br>↵
↵
3. Increment`freq[prefix]`<br>$\text{freq}[\text{prefix}]$↵
↵
Why does this work?<br>↵
Suppose the current prefix sum is $x$ and it has appeared $k$ times before.↵
Each previous occurrence of $x$ gives a different starting position for a zero-sum subarray ending at the current position.↵
Therefore, we can add $k$ directly to the answer.↵
↵
**Correctness**<br>↵
Consider any subarray $[l,r]$.↵
It is good in the original array if and only if: ↵
$\sum_{i=l}^{r}a_i=r-l+1$ <br>↵
This is equivalent to: ↵
$\sum_{i=l}^{r}(a_i-1)=0$ <br>↵
After defining $b_i=a_i-1$, this means: ↵
$\sum_{i=l}^{r}b_i=0$ <br>↵
Using prefix sums: ↵
$P_r=P_{l-1}$<br>↵
↵
Our frequency map counts exactly the number of previous positions having the same prefix sum. ↵
Thus, every good subarray is counted exactly once, and no invalid subarray is counted. <br>↵
Therefore, the algorithm correctly computes the number of good subarrays.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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<int> a(n);↵
for (int i = 0; i < n; i++)↵
cin >> a[i];↵
↵
vector<int> cnt(9 * n + 2, 0);↵
int cur = 0;↵
// Empty prefix↵
cnt[n] = 1;↵
long long ans = 0;↵
for (int i = 0; i < n; i++) {↵
cur += a[i] - 1;↵
ans += cnt[cur + n];↵
cnt[cur + n]++;↵
}↵
cout << ans << '\n';↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
Each element is processed exactly once.<br>↵
↵
Using a hash map:<br>↵
**Time Complexity:** $\mathcal{O}(N)$ average per test case <br>↵
**Space Complexity:** $\mathcal{O}(N)$<br>↵
Since $\sum N \le 2\cdot10^5$, this easily fits within the constraints.<br>↵
↵
Alternatively, using an ordered map gives: <br>↵
**Time Complexity:** $\mathcal{O}(N\log N)$ <br>↵
**Space Complexity:** $\mathcal{O}(N)$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
Round 4↵
------------------↵
↵
<spoiler summary="Problem-A: Harry Potter">↵
↵
<spoiler summary="Hint-1">↵
↵
Think about what happens if you pick a random starting node and walk as far as possible.↵
Where do you end up? Does that destination have a special structural role in the tree?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
↵
Every tree has a **diameter** — the longest path between any two nodes.↵
Let the endpoints of this diameter be $A$ and $B$.<br>↵
If you are standing at an arbitrary node $v$, how does the farthest possible destination relate to $A$ and $B$?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
↵
With up to $10^5$ queries, running a complete BFS or DFS for every query is too slow. <br>↵
Can we precompute distances from a small number of important nodes so that every query can be answered in constant time?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
**Core Idea**<br>↵
The problem asks for the maximum distance from a given node $v$ to any other node in the tree.<br>↵
Running BFS or DFS independently for every query would take $\mathcal{O}(nq)$ time, which is too large.<br>↵
↵
The key observation is based on the **diameter of a tree**. <br>↵
Let the two endpoints of the diameter be $A$ and $B$.↵
For every node $v$, at least one of these two endpoints is a farthest node from $v$.↵
Therefore: <br>↵
$$\text{answer}(v)=\max(\text{dist}(A,v),\text{dist}(B,v))$$<br>↵
**Claim 1 — Finding a Diameter Endpoint**<br>↵
Start from any node, for example node $1$, and find the farthest node from it.↵
This node is guaranteed to be one endpoint of the tree's diameter.↵
Let this node be $A$.<br>↵
↵
**Claim 2 — Finding the Other Endpoint**<br>↵
Now run BFS or DFS starting from $A$.↵
The farthest node from $A$ is the other endpoint of the diameter.↵
Let this node be $B$.↵
During this traversal, also store the distance from $A$ to every node in an array`$\text{dist}_A`$.<br>↵
↵
**Claim 3 — Farthest Node Property**<br>↵
For every node $v$, one of the diameter endpoints $A$ or $B$ is a farthest node from $v$.↵
Therefore:<br>↵
$$\text{answer}(v)=\max(\text{dist}_A[v],\text{dist}_B[v])$$<br>↵
This allows us to answer every query without performing another traversal.<br>↵
↵
**Proof**<br>↵
Let $A$ and $B$ be the endpoints of the tree's diameter.↵
Consider an arbitrary node $v$ and let $u$ be a farthest node from $v$.↵
In a tree, paths are unique. The diameter endpoints capture the maximum extent of the tree, and the eccentricity of any node is determined by its distance to one of these endpoints.↵
Hence: ↵
$$\max_x \text{dist}(v,x)↵
=↵
\max(\text{dist}(v,A),\text{dist}(v,B))$$ <br>↵
Therefore, the maximum distance from $v$ can always be obtained by checking only $A$ and $B$.↵
↵
**Step-by-Step Approach**<br>↵
**↵
↵
1. **Find $A$**↵
Run BFS/DFS from node $1$ and find the farthest node. Call it $A$.<br>↵
**↵
↵
2. **Find $B$ and`$\text{dist}_A`$**↵
Run BFS/DFS from $A$.↵
The farthest node is $B$.↵
Store the distance from $A$ to every node in`$\text{dist}_A`.<br>↵
**$.↵
↵
3. **Calculate`$\text{dist}_B`$**↵
Run BFS/DFS from $B$ and store the distance from $B$ to every node in`$\text{dist}_B`.<br>↵
**$.↵
↵
4. **Answer the queries**↵
For every queried node $v$: ↵
$\text{answer}=\max(\text{dist}_A[v],\text{dist}_B[v])$ <br>, ↵
Each query is now answered in $\mathcal{O}(1)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
<spoiler summary="Brute Force">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int getMaxDistanceBF(int start, int n, const vector<vector<int>> &adj) {↵
vector<int> dist(n + 1, -1);↵
queue<int> q;↵
q.push(start);↵
dist[start] = 0;↵
int maxDist = 0;↵
while (!q.empty()) {↵
int u = q.front();↵
q.pop();↵
maxDist = max(maxDist, dist[u]);↵
for (int nxt : adj[u]) {↵
if (dist[nxt] == -1) {↵
dist[nxt] = dist[u] + 1;↵
q.push(nxt);↵
}↵
}↵
}↵
return maxDist;↵
}↵
↵
void solve() {↵
int n;↵
if (!(cin >> n))↵
return;↵
↵
vector<vector<int>> adj(n + 1);↵
for (int i = 0; i < n - 1; ++i) {↵
int u, v;↵
cin >> u >> v;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
int q;↵
cin >> q;↵
while (q--) {↵
int v;↵
cin >> v;↵
cout << getMaxDistanceBF(v, n, adj) << "\n";↵
}↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t;↵
if (cin >> t) {↵
while (t--) {↵
solve();↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Optimal solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void dfs(int u, int p, int d, const vector<vector<int>> &adj,↵
vector<int> &dist) {↵
↵
dist[u] = d;↵
for (int v : adj[u]) {↵
if (v != p) {↵
dfs(v, u, d + 1, adj, dist);↵
}↵
}↵
}↵
↵
void solve() {↵
int n;↵
if (!(cin >> n))↵
return;↵
↵
vector<vector<int>> adj(n + 1);↵
for (int i = 0; i < n - 1; ++i) {↵
int u, v;↵
cin >> u >> v;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
// Step 1: Find the farthest node from node 1↵
vector<int> dist1(n + 1);↵
dfs(1, 0, 0, adj, dist1);↵
int A = 1;↵
for (int i = 1; i <= n; +↵
+i) {↵
if (dist1[i] > dist1[A]) {↵
A = i;↵
}↵
}↵
↵
// Step 2: Find the farthest node from A↵
vector<int> distA(n + 1);↵
dfs(A, 0, 0, adj, distA);↵
int B = A;↵
for (int i = 1; i <= n; ++i) {↵
if (distA[i] > distA[B]) {↵
B = i;↵
}↵
}↵
↵
// Step 3: Compute distances from B↵
vector<int> distB(n + 1);↵
dfs(B, 0, 0, adj, distB);↵
↵
// Step 4: Answer queries↵
int q;↵
cin >> q;↵
while (q--) {↵
int v;↵
cin >> v;↵
cout << max(distA[v], distB[v]) << "\n";↵
}↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t;↵
if (cin >> t) {↵
while (t--) {↵
solve();↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
We perform three BFS/DFS traversals, each taking $\mathcal{O}(n)$ time.↵
Each query is answered in $\mathcal{O}(1)$ time. <br>↵
↵
**Time Complexity:** $\mathcal{O}(n+q)$ <br>↵
**Space Complexity:** $\mathcal{O}(n)$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
Here is the official editorial for all the problems.↵
↵
Round 1↵
------------------↵
↵
<spoiler summary="Problem-A: Tom Riddle's Diary">↵
↵
<spoiler summary="Hint-1">↵
Since $N$ is always even, try visualizing the array as $N/2$ non-overlapping pairs of adjacent elements.<br>↵
$(A_1,A_2), (A_3,A_4), \dots$↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
If every pair must sum to a multiple of $P$, what must the total sum $M$ be a multiple of?↵
Given that numbers must be positive, what is the absolute minimum possible total sum?↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
To build the array, try repeating a simple pair like $(1,P-1)$ for most of the array, and put all the remaining required sum into the very last element.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
**When to print NO:**↵
↵
- Because $N$ is even, we can split the array into exactly $N/2$ disjoint pairs. The problem requires every adjacent pair to sum to a multiple of $P$. Therefore, the sum of the entire array, $M$, must also be a multiple of $P$ ($M \bmod P = 0$).↵
↵
- Additionally, since the array requires strictly positive integers ($A_i \ge 1$), the smallest valid sum for any pair is $P$. With $N/2$ pairs, the absolute minimum total sum is $(N/2) \times P$.<br>↵
If $M < (N/2) \times P$, it is impossible.↵
Therefore, if either of these conditions fails, print **NO**.↵
↵
---↵
↵
**When to print YES:**<br>↵
If both conditions are met, print **YES** and construct the array greedily:↵
↵
- **Prefix:** Fill the first $N-2$ positions by alternating $1$ and $P-1$:
↵
- **Second to last element:** Set $A_{N-1} = 1$.
↵
- **Final element:** Set $A_N$ to whatever value is needed to make the total array sum exactly $M$.↵
↵
Since we already verified that $M \ge (N/2)\times P$, $A_N$ will always be a valid positive integer.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define endl '\n'↵
↵
void solve()↵
{↵
int n, m, p;↵
cin >> n >> m >> p;↵
if ((m % p != 0) || ((m / p) < (n / 2)))↵
{↵
cout << "NO" << endl;↵
}↵
else↵
{↵
cout << "YES" << endl;↵
for (int i = 0; i < n - 2; i += 2)↵
{↵
cout << 1 << " " << p - 1 << " ";↵
m -= p;↵
}↵
cout << 1 << " " << m - 1 << endl;↵
}↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t = 1;↵
cin >> t;↵
while (t--)↵
{↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
**Time Complexity:** $\mathcal{O}(N)$ <br>↵
**Space Complexity:** $\mathcal{O}(1)$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Problem-B: Marvolo Gaunt's Ring">↵
↵
<spoiler summary="Hint-1">↵
↵
Notice that the elements of the transformed array $A$ are powers of $2$ ($A[i] = 2^{b_i}$). <br>↵
Think about the binary representation of numbers. What happens if every element in the array $b$ is completely distinct?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
↵
The sum of any set of strictly distinct powers of $2$ is uniquely determined by its elements. <br>↵
Consider the largest element in any two disjoint subsets. If all $b_i$ are unique, can the subset without the maximum element ever sum up to a value greater than or equal to the maximum element itself?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
↵
Try to determine whether two equal-sum subarrays can exist when every value in $b$ is unique. <br>↵
What changes if two values of $b$ are equal?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
The problem contains a massive bait in the first example's note, leading you to think about complex prefix sums and combining multiple elements to match a single large power of $2$.↵
However, the solution is purely based on a fundamental property of powers of $2$.↵
↵
**Claim:** Two non-overlapping equal-sum subarrays exist if and only if there is at least one duplicate element in the array $b$.↵
↵
The problem fully reduces to checking whether the array $b$ contains any duplicate values.
This can be done in two ways:
↵
- Sort the array and check adjacent elements.
↵
- Use a Hash Set to detect duplicates.↵
↵
<spoiler summary="Proof">↵
↵
**If there is a duplicate:**↵
↵
Suppose $b_i = b_j$ for some $i < j$. We can trivially pick two subarrays of length $1$: $[i,i]$ and $[j,j]$. Since $i < j$, these subarrays are strictly non-overlapping, and their sums are identical: <br>↵
$$A[i] = A[j] = 2^{b_i}$$ <br>↵
Therefore, the answer is **YES**.↵
↵
**If all elements are distinct:** <br>↵
Let's assume all elements in $b$ are strictly unique. Let $S_1$ and $S_2$ be any two disjoint subarrays. Let $M$ be the strictly largest element in $S_1 \cup S_2$. ↵
↵
Without loss of generality, let $M \in S_1$. Because all elements are distinct, the maximum possible sum of $S_2$ would be obtained if it contained every single power of $2$ strictly smaller than $M$. <br>↵
Even in this absolute best-case scenario, the sum of all powers of $2$ up to $2^{k-1}$ is strictly less than $2^k$: <br>↵
$$\sum_{x=0}^{k-1} 2^x = 2^k - 1$$ <br>↵
Therefore, the sum of $S_2$ will always be strictly less than $M$. Hence, <br>↵
$$\text{Sum}(S_2) < \text{Sum}(S_1)$$ <br>↵
and the two subarrays can never have equal sums. Therefore, the answer is **NO**.↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
using namespace std;↵
void solve() {↵
int n;↵
cin >> n;↵
vector<int> b(n);↵
for (int i = 0; i < n; i++) {↵
cin >> b[i];↵
}↵
sort(b.begin(), b.end());↵
bool has_duplicate = false;↵
for (int i = 1; i < n; i++) {↵
if (b[i] == b[i - 1]) {↵
has_duplicate = true;↵
break;↵
}↵
}↵
if (has_duplicate) {↵
cout << "YES\n";↵
} else {↵
cout << "NO\n";↵
}↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
**Using sorting:**<br>↵
Time Complexity: $\mathcal{O}(n \log n)$ <br>↵
Space Complexity: $\mathcal{O}(1)$ if sorting in-place.↵
↵
**Using a Hash Set:** <br>↵
Time Complexity: $\mathcal{O}(n)$ average. <br>↵
Space Complexity: $\mathcal{O}(n)$.↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Problem-C: Salazar Slytherin's Locket">↵
↵
<spoiler summary="Hint-1">↵
↵
Since rearranging the remaining characters is free, the positions of the characters in $s$ do not matter. <br>↵
Think about the problem in terms of the number of $0$ and $1$ available in the string.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
↵
Suppose the final string $t$ has length $k$.<br>↵
For every character of $t$, its value must be different from the character at the same position in $s$.<br>↵
Ask yourself:<br>↵
How many $0$ and $1$ does $t$ need, and how many of each do we have available in $s$?↵
The maximum possible length of $t$ can then be determined from these two frequencies.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
↵
Try matching every character in the original string with an available character of the opposite type.↵
What happens when one of the two types runs out?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
The main observation is that free rearrangement removes the importance of ordering.↵
Let:<br>↵
$cnt_0$ = number of $0$s in $s$ <br>↵
$cnt_1$ = number of $1$s in $s$
↵
If $t$ has length $k$, then every $0$ in $t$ must occupy a position where $s$ has a $1$, and every $1$ in $t$ must occupy a position where $s$ has a $0$.<br>↵
Therefore, the number of characters we can keep is limited by the available opposite characters.<br>↵
The important quantity is the maximum number of characters that can remain after matching each character with an opposite character.<br>↵
Since every deleted character costs exactly $1$ coin, once we know the maximum number of characters that can be retained, the answer follows directly.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
string s;↵
cin >> s;↵
int n = s.size();↵
int zeroCount = 0, oneCount = 0;↵
for (char c : s) {↵
if (c == '0') {↵
zeroCount++;↵
} else {↵
oneCount++;↵
}↵
}↵
for (int i = 0; i < n; i++) {↵
if (s[i] == '0') {↵
if (oneCount > 0) {↵
oneCount--;↵
} else {↵
cout << n - i << "\n";↵
return;↵
}↵
} else {↵
if (zeroCount > 0) {↵
zeroCount--;↵
} else {↵
cout << n - i << "\n";↵
return;↵
}↵
}↵
}↵
cout << "0\n";↵
}↵
↵
int main() {↵
int t;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
We only need to count the number of $0$ and $1$.<br>↵
**Time Complexity:** $\mathcal{O}(n)$ per test case<br>↵
**Space Complexity:** $\mathcal{O}(1)$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
Round 2↵
------------------↵
↵
<spoiler summary="Problem-A: Helga Hufflepuff's Cup">↵
↵
<spoiler summary="Hint-1">↵
↵
Don't think of the amplification as changing individual characters.↵
Each character in the original grid is simply replaced by a $K \times K$ block containing the same character.
↵
For example, if $K=2$:<br>↵
`X` becomes:<br>↵
`XX` ↵
`XX`↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
↵
For every row of the original grid, we need to:<br>↵
1. Replace every character with $K$ copies of that character horizontally.<br>↵
2. Repeat the resulting row $K$ times vertically.↵
↵
Since the original grid has $M$ rows and $N$ columns, the final grid will have $M \times K$ rows and $N \times K$ columns.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
↵
Think about how the position in the amplified grid maps back to the original grid.↵
For a position $(i,j)$ in the new grid, which original cell does it correspond to?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
The key observation is that every original character is expanded independently into a $K \times K$ block.↵
Suppose the original row is: $$A.X$$↵
For $K=2$, each character is expanded horizontally:<br>↵
$$AA..XX$$<br>↵
and this entire row is printed $K$ times.↵
Therefore, for every input row:
↵
- Build an expanded row by repeating each character $K$ times.
↵
- Print this expanded row exactly $K$ times.
↵
This directly produces the required amplified grid.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
int height, width;↵
int scale;↵
cin >> height >> width >> scale;↵
vector<string> signal(height);↵
for (string &r : signal) {↵
cin >> r;↵
}↵
for (int i = 0; i < scale * height; i++) {↵
for (int j = 0; j < scale * width; j++) {↵
cout << signal[i / scale][j / scale];↵
}↵
cout << '\n';↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
The final grid contains $(M \times K) \times (N \times K)$ characters.↵
Therefore:<br>↵
**Time Complexity:** $\mathcal{O}(MNK^2)$ <br>↵
**Space Complexity:** $\mathcal{O}(NK)$ if we store one expanded row.↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Problem-B: Ravenclaw's Diadem">↵
↵
<spoiler summary="Hint-1">↵
↵
Don't consider $a[i]$ and $b[i]$ independently.↵
If Harry takes a relic, its contribution to the final value $H-D$ is:↵
$+a[i]$↵
<br>↵
If Draco takes it, the contribution is:↵
$-b[i]$↵
Think about what happens when one relic is chosen by Harry and another by Draco.↵
Which property of a relic determines how valuable it is to take before another relic?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
↵
Suppose you have two relics $i$ and $j$, and it is Harry's turn.↵
Compare these two possibilities:
↵
- Harry takes $i$, then Draco takes $j$.
↵
- Harry takes $j$, then Draco takes $i$.
↵
Write the resulting contribution to $H-D$ for both orders and compare them.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
↵
From the pairwise comparison, try to identify a single value for each relic that determines which relic should come first.↵
Once the sorting criterion is known, simulate the alternating turns.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
This is a classic two-player greedy / optimal ordering problem.↵
The important trick is to look at the effect of two consecutive turns together rather than trying to simulate all possible choices.↵
For two relics $i$ and $j$:
↵
- If Harry gets $i$ and Draco gets $j$, their combined contribution is:↵
$a[i]-b[j]$
↵
- If Harry gets $j$ and Draco gets $i$, their combined contribution is:↵
$a[j]-b[i]$
↵
Comparing these expressions reveals that the relevant quantity for each relic is:↵
$a[i]+b[i]$↵
↵
So the game can be transformed into an ordering problem: determine the order in which the relics should be considered based on this combined value.↵
After finding the correct order:
↵
- Harry takes the relics at his turns.
↵
- Draco takes the relics at his turns.
↵
- Add $a[i]$ when Harry takes relic $i$.
↵
- Subtract $b[i]$ when Draco takes relic $i$.
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <algorithm>↵
#include <cmath>↵
#include <cstdint>↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long↵
#define pl pair<ll, ll>↵
#define vl vector<ll>↵
#define vpl vector<pl>↵
#define vb vector<bool>↵
#define vvl vector<vl>↵
#define vvpl vector<vpl>↵
#define all(x) (x).begin(), (x).end()↵
#define rall(x) (x).rbegin(), (x).rend()↵
#define f(i, a, b) for (ll i = (a); i < (b); ++i)↵
#define rf(i, a, b) for (ll i = (a); i >= (b); --i)↵
#define each(x, a) for (auto &x : a)↵
#define uniq(x) x.resize(unique(all(x)) - x.begin())↵
#define yes cout << "YES\n"↵
#define no cout << "NO\n";↵
↵
ll M = (1e+9) + 7;↵
↵
using namespace std;↵
↵
bool func(pl &i, pl &j) {↵
if (i.first + i.second != j.first + j.second) {↵
return i.first + i.second > j.first + j.second;↵
} else {↵
return i.first > j.first;↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
ll t;↵
cin >> t;↵
↵
while (t--) {↵
ll n, ans = 0;↵
↵
cin >> n;↵
↵
vl a(n);↵
vl b(n);↵
vvl c(n, vl(3));↵
↵
f(i, 0, n) {↵
cin >> a[i];↵
}↵
↵
f(i, 0, n) {↵
cin >> b[i];↵
↵
c[i][0] = a[i] + b[i];↵
c[i][1] = a[i];↵
c[i][2] = b[i];↵
}↵
↵
sort(all(a));↵
↵
rf(i, n - 1, 0) {↵
if ((n - i) % 2 == 1) {↵
ans += c[i][1];↵
} else {↵
ans -= c[i][2];↵
}↵
}↵
↵
cout << ans << endl;↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
Sorting the relics takes:<br>↵
**Time Complexity:** $\mathcal{O}(n \log n)$
↵
The simulation after sorting takes: <br>↵
**Time Complexity:** $\mathcal{O}(n)$
↵
Therefore, the overall complexity is:<br>↵
**Time Complexity:** $\mathcal{O}(n \log n)$<br>↵
**Space Complexity:** $\mathcal{O}(n)$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
Round 3↵
------------------↵
↵
<spoiler summary="Problem-A: Good Subarrays">↵
↵
<spoiler summary="Hint-1">↵
↵
The condition says that the sum of the elements in a subarray must be equal to its length.↵
If $\sum_{i=l}^{r} a_i = r-l+1$ <br>↵
what happens if we write the length as a sum of $1$?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
↵
The length of a subarray is exactly the number of elements in it. Therefore:↵
$\sum_{i=l}^{r} a_i = \sum_{i=l}^{r} 1$ <br>↵
Can you move everything to one side?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
↵
After subtracting $1$ from every element, the problem becomes:↵
**Count the number of subarrays whose sum is exactly $0$.** <br>↵
How can prefix sums be used to count zero-sum subarrays efficiently?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
**Key Observation** <br>↵
A subarray $[l,r]$ is good if
$$\sum_{i=l}^{r} a_i = \sum_{i=l}^{r} 1$$ <br>↵
Moving everything to the left gives: <br>↵
$$\sum_{i=l}^{r}(a_i-1)
This transformation is the key to the problem.↵
↵
**Transformation** <br
Define a new array $b$ such that: <br>↵
$$b_i=a_i-1$$ <br>↵
Now the original condition becomes: $\sum_{i=l}^{r} b_i=0$ <br>↵
Therefore, instead of directly checking whether the sum of a subarray of $a$ equals its length, we simply need to count the number of **zero-sum subarrays** in $b$.
↵
For example, if: $a=[1,2,0,1]$ then:<br>↵
$b=[0,1,-1,0]$ <br>↵
Now we only need to count the subarrays of $b$ whose sum is $0$.↵
↵
**Using Prefix Sums**<br>↵
Let $P_i$ denote the sum of the first $i$ elements of $b$.↵
For a subarray $[l,r]$: $\sum_{i=l}^{r}b_i=P_r-P_{l-1}$ <br>↵
We want this sum to be $0$, so:↵
$P_r-P_{l-1}=0$ <br>↵
which means:↵
$P_r=P_{l-1}$ <br>↵
Therefore, a subarray has sum $0$ exactly when the prefix sum at its two boundaries is the same. <br>↵
So, whenever we encounter a prefix sum that has appeared before, every previous occurrence of that prefix sum gives us one new valid subarray.↵
↵
**Counting the Subarrays**<br>↵
We maintain a frequency map containing how many times each prefix sum has appeared. <br>↵
Initially, the prefix sum is $0$ before processing any elements.
`
↵
For every element:
↵
1. Add the element to the current prefix sum.
↵
2. Add
↵
3. Increment
↵
Why does this work?<br>↵
Suppose the current prefix sum is $x$ and it has appeared $k$ times before.↵
Each previous occurrence of $x$ gives a different starting position for a zero-sum subarray ending at the current position.↵
Therefore, we can add $k$ directly to the answer.↵
↵
**Correctness**<br>↵
Consider any subarray $[l,r]$.↵
It is good in the original array if and only if: ↵
$\sum_{i=l}^{r}a_i=r-l+1$ <br>↵
This is equivalent to: ↵
$\sum_{i=l}^{r}(a_i-1)=0$ <br>↵
After defining $b_i=a_i-1$, this means: ↵
$\sum_{i=l}^{r}b_i=0$ <br>↵
Using prefix sums: ↵
$P_r=P_{l-1}$
↵
Our frequency map counts exactly the number of previous positions having the same prefix sum. ↵
Thus, every good subarray is counted exactly once, and no invalid subarray is counted. <br>↵
Therefore, the algorithm correctly computes the number of good subarrays.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#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<int> a(n);↵
for (int i = 0; i < n; i++)↵
cin >> a[i];↵
↵
vector<int> cnt(9 * n + 2, 0);↵
int cur = 0;↵
// Empty prefix↵
cnt[n] = 1;↵
long long ans = 0;↵
for (int i = 0; i < n; i++) {↵
cur += a[i] - 1;↵
ans += cnt[cur + n];↵
cnt[cur + n]++;↵
}↵
cout << ans << '\n';↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
Each element is processed exactly once.
↵
Using a hash map:<br>↵
**Time Complexity:** $\mathcal{O}(N)$ average per test case <br>↵
**Space Complexity:** $\mathcal{O}(N)$<br>↵
Since $\sum N \le 2\cdot10^5$, this easily fits within the constraints.
↵
Alternatively, using an ordered map gives: <br>↵
**Time Complexity:** $\mathcal{O}(N\log N)$ <br>↵
**Space Complexity:** $\mathcal{O}(N)$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
Round 4↵
------------------↵
↵
<spoiler summary="Problem-A: Harry Potter">↵
↵
<spoiler summary="Hint-1">↵
↵
Think about what happens if you pick a random starting node and walk as far as possible.↵
Where do you end up? Does that destination have a special structural role in the tree?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-2">↵
↵
Every tree has a **diameter** — the longest path between any two nodes.↵
Let the endpoints of this diameter be $A$ and $B$.<br>↵
If you are standing at an arbitrary node $v$, how does the farthest possible destination relate to $A$ and $B$?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint-3">↵
↵
With up to $10^5$ queries, running a complete BFS or DFS for every query is too slow. <br>↵
Can we precompute distances from a small number of important nodes so that every query can be answered in constant time?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
**Core Idea**<br>↵
The problem asks for the maximum distance from a given node $v$ to any other node in the tree.<br>↵
Running BFS or DFS independently for every query would take $\mathcal{O}(nq)$ time, which is too large.
↵
The key observation is based on the **diameter of a tree**. <br>↵
Let the two endpoints of the diameter be $A$ and $B$.↵
For every node $v$, at least one of these two endpoints is a farthest node from $v$.↵
Therefore: <br>↵
$$\text{answer}(v)=\max(\text{dist}(A,v),\text{dist}(B,v))$$<br>↵
**Claim 1 — Finding a Diameter Endpoint**<br>↵
Start from any node, for example node $1$, and find the farthest node from it.↵
This node is guaranteed to be one endpoint of the tree's diameter.↵
Let this node be $A$.<br>↵
↵
**Claim 2 — Finding the Other Endpoint**<br>↵
Now run BFS or DFS starting from $A$.↵
The farthest node from $A$ is the other endpoint of the diameter.↵
Let this node be $B$.↵
During this traversal, also store the distance from $A$ to every node in an array
↵
**Claim 3 — Farthest Node Property**<br>↵
For every node $v$, one of the diameter endpoints $A$ or $B$ is a farthest node from $v$.↵
Therefore:<br>↵
$$\text{answer}(v)=\max(\text{dist}_A[v],\text{dist}_B[v])$$<br>↵
This allows us to answer every query without performing another traversal.<br>↵
↵
**Proof**<br>↵
Let $A$ and $B$ be the endpoints of the tree's diameter.↵
Consider an arbitrary node $v$ and let $u$ be a farthest node from $v$.↵
In a tree, paths are unique. The diameter endpoints capture the maximum extent of the tree, and the eccentricity of any node is determined by its distance to one of these endpoints.↵
Hence: ↵
$$\max_x \text{dist}(v,x)↵
=↵
\max(\text{dist}(v,A),\text{dist}(v,B))$$ <br>↵
Therefore, the maximum distance from $v$ can always be obtained by checking only $A$ and $B$.↵
↵
**Step-by-Step Approach**
**
↵
1. **Find $A$**↵
Run BFS/DFS from node $1$ and find the farthest node. Call it $A$.
**
↵
2. **Find $B$ and
Run BFS/DFS from $A$.↵
The farthest node is $B$.↵
Store the distance from $A$ to every node in
**
↵
3. **Calculate
Run BFS/DFS from $B$ and store the distance from $B$ to every node in
**
↵
4. **Answer the queries**↵
For every queried node $v$: ↵
$\text{answer}=\max(\text{dist}_A[v],\text{dist}_B[v])$
Each query is now answered in $\mathcal{O}(1)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
<spoiler summary="Brute Force">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int getMaxDistanceBF(int start, int n, const vector<vector<int>> &adj) {↵
vector<int> dist(n + 1, -1);↵
queue<int> q;↵
q.push(start);↵
dist[start] = 0;↵
int maxDist = 0;↵
while (!q.empty()) {↵
int u = q.front();↵
q.pop();↵
maxDist = max(maxDist, dist[u]);↵
for (int nxt : adj[u]) {↵
if (dist[nxt] == -1) {↵
dist[nxt] = dist[u] + 1;↵
q.push(nxt);↵
}↵
}↵
}↵
return maxDist;↵
}↵
↵
void solve() {↵
int n;↵
if (!(cin >> n))↵
return;↵
↵
vector<vector<int>> adj(n + 1);↵
for (int i = 0; i < n - 1; ++i) {↵
int u, v;↵
cin >> u >> v;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
int q;↵
cin >> q;↵
while (q--) {↵
int v;↵
cin >> v;↵
cout << getMaxDistanceBF(v, n, adj) << "\n";↵
}↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t;↵
if (cin >> t) {↵
while (t--) {↵
solve();↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Optimal solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void dfs(int u, int p, int d, const vector<vector<int>> &adj,↵
vector<int> &dist) {↵
↵
dist[u] = d;↵
for (int v : adj[u]) {↵
if (v != p) {↵
dfs(v, u, d + 1, adj, dist);↵
}↵
}↵
}↵
↵
void solve() {↵
int n;↵
if (!(cin >> n))↵
return;↵
↵
vector<vector<int>> adj(n + 1);↵
for (int i = 0; i < n - 1; ++i) {↵
int u, v;↵
cin >> u >> v;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
// Step 1: Find the farthest node from node 1↵
vector<int> dist1(n + 1);↵
dfs(1, 0, 0, adj, dist1);↵
int A = 1;↵
for (int i = 1; i <= n; +↵
+i) {↵
if (dist1[i] > dist1[A]) {↵
A = i;↵
}↵
}↵
↵
// Step 2: Find the farthest node from A↵
vector<int> distA(n + 1);↵
dfs(A, 0, 0, adj, distA);↵
int B = A;↵
for (int i = 1; i <= n; ++i) {↵
if (distA[i] > distA[B]) {↵
B = i;↵
}↵
}↵
↵
// Step 3: Compute distances from B↵
vector<int> distB(n + 1);↵
dfs(B, 0, 0, adj, distB);↵
↵
// Step 4: Answer queries↵
int q;↵
cin >> q;↵
while (q--) {↵
int v;↵
cin >> v;↵
cout << max(distA[v], distB[v]) << "\n";↵
}↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t;↵
if (cin >> t) {↵
while (t--) {↵
solve();↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
We perform three BFS/DFS traversals, each taking $\mathcal{O}(n)$ time.↵
Each query is answered in $\mathcal{O}(1)$ time.
↵
**Time Complexity:** $\mathcal{O}(n+q)$ <br>↵
**Space Complexity:** $\mathcal{O}(n)$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
