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$independent, non-overlapping pairs: of adjacent elements.↵
$(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="ExplanaSolution">↵
↵
**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$.↵
↵
If $M < (N/2) \times P$, it is impossible.↵
↵
Therefore, if either of these conditions fails, print **NO**.↵
↵
---↵
↵
**When to print YES:**↵
↵
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>↵
↵
<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}$).↵
↵
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.↵
↵
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="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:↵
↵
$$A[i] = A[j] = 2^{b_i}$$↵
↵
Therefore, the answer is **YES**.↵
↵
---↵
↵
**If all elements are distinct:**↵
↵
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$.↵
↵
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$:↵
↵
$$\sum_{x=0}^{k-1} 2^x = 2^k - 1$$↵
↵
Therefore, the sum of $S_2$ will always be strictly less than $M$.↵
↵
Hence,↵
↵
$$\text{Sum}(S_2) < \text{Sum}(S_1)$$↵
↵
and the two subarrays can never have equal sums.↵
↵
Therefore, the answer is **NO**.↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Conlcusion">↵
↵
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>↵
↵
<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 the array to easily find duplicates↵
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() {↵
// Optimize standard I/O operations for performance↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
**Using sorting:**↵
↵
Time Complexity: $\mathcal{O}(n \log n)$↵
<br>↵
Space Complexity: $\mathcal{O}(1)$ if sorting in-place.↵
↵
**Using a Hash Set:**↵
↵
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.↵
↵
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$.↵
↵
For every character of $t$, its value must be different from the character at the same position in $s$.↵
↵
Ask yourself:↵
↵
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="Solution">↵
↵
The main observation is that free rearrangement removes the importance of ordering.↵
↵
Let:↵
↵
$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$.↵
↵
Therefore, the number of characters we can keep is limited by the available opposite characters.↵
↵
The important quantity is the maximum number of characters that can remain after matching each character with an opposite character.↵
↵
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$.↵
↵
**Time Complexity:** $\mathcal{O}(n)$ per test case↵
<br>↵
**Space Complexity:** $\mathcal{O}(1)$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
Round 2↵
------------------↵
↵
<spoiler summary="Problem A —-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$:↵
↵
X`X` becomes:↵
↵
`XX`<br>↵
`XX`↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
↵
For every row of the original grid, we need to:↵
↵
1. Replace every character with $K$ copies of that character horizontally.↵
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="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:↵
↵
$AA..XX$↵
↵
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="Complexity">↵
↵
The final grid contains $(M \times K) \times (N \times K)$ characters.↵
↵
Therefore:↵
↵
**Time Complexity:** $\mathcal{O}(MNK^2)$↵
↵
**Space Complexity:** $\mathcal{O}(NK)$ if we store one expanded row.↵
↵
</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:↵
↵
**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]↵
↵
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.↵
↵
This pairwise comparison should reveal the sorting criterion for the relics.↵
↵
</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="Complexity">↵
↵
Sorting the relics takes:↵
↵
Time Complexity: O(n log n)↵
↵
The simulation after sorting takes:↵
↵
Time Complexity: O(n)↵
↵
Therefore, the overall complexity is:↵
↵
Time Complexity: O(n log n)↵
↵
Space Complexity: O(n)↵
↵
</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>↵
↵
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$↵
↵
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$↵
↵
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$.**↵
↵
How can prefix sums be used to count zero-sum subarrays efficiently?↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
<spoiler summary="Key Observation">↵
↵
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:↵
↵
$\sum_{i=l}^{r} a_i = \sum_{i=l}^{r} 1$↵
↵
Moving everything to the left gives:↵
↵
$\sum_{i=l}^{r}(a_i-1)=0$↵
↵
This transformation is the key to the problem.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Transformation">↵
↵
Define a new array $b$ such that:↵
↵
$b_i=a_i-1$↵
↵
Now the original condition becomes:↵
↵
$\sum_{i=l}^{r} b_i=0$↵
↵
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:↵
↵
$b=[0,1,-1,0]$↵
↵
Now we only need to count the subarrays of $b$ whose sum is $0$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Using Prefix Sums">↵
↵
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}$↵
↵
We want this sum to be $0$, so:↵
↵
$P_r-P_{l-1}=0$↵
↵
which means:↵
↵
$P_r=P_{l-1}$↵
↵
Therefore, a subarray has sum $0$ exactly when the prefix sum at its two boundaries is the same.↵
↵
So, whenever we encounter a prefix sum that has appeared before, every previous occurrence of that prefix sum gives us one new valid subarray.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Counting the Subarrays">↵
↵
We maintain a frequency map containing how many times each prefix sum has appeared.↵
↵
Initially, the prefix sum is $0$ before processing any elements.↵
↵
Therefore, we initialize:↵
↵
$freq[0]=1$↵
↵
For every element:↵
↵
1. Add the element to the current prefix sum.↵
2. Add `freq[prefix]` to the answer.↵
3. Increment `freq[prefix]`.↵
↵
Why does this work?↵
↵
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.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Correctness">↵
↵
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$↵
↵
This is equivalent to:↵
↵
$\sum_{i=l}^{r}(a_i-1)=0$↵
↵
After defining $b_i=a_i-1$, this means:↵
↵
$\sum_{i=l}^{r}b_i=0$↵
↵
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.↵
↵
Therefore, the algorithm correctly computes the number of good subarrays.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Complexity Analysis">↵
↵
Each element is processed exactly once.↵
↵
Using a hash map:↵
↵
**Time Complexity:** $\mathcal{O}(N)$ average per test case↵
↵
**Space Complexity:** $\mathcal{O}(N)$↵
↵
Since $\sum N \le 2\cdot10^5$, this easily fits within the constraints.↵
↵
Alternatively, using an ordered map gives:↵
↵
**Time Complexity:** $\mathcal{O}(N\log N)$↵
↵
**Space Complexity:** $\mathcal{O}(N)$↵
↵
</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>↵
↵
</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$.↵
↵
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.↵
↵
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">↵
↵
<spoiler summary="Core Idea">↵
↵
The problem asks for the maximum distance from a given node $v$ to any other node in the tree.↵
↵
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**.↵
↵
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:↵
↵
$\text{answer}(v)=\max(\text{dist}(A,v),\text{dist}(B,v))$↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Claim 1 — Finding a Diameter Endpoint">↵
↵
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$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Claim 2 — Finding the Other Endpoint">↵
↵
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 `dist_A`.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Claim 3 — Farthest Node Property">↵
↵
For every node $v$, one of the diameter endpoints $A$ or $B$ is a farthest node from $v$.↵
↵
Therefore:↵
↵
$\text{answer}(v)=\max(\text{dist}_A[v],\text{dist}_B[v])$↵
↵
This allows us to answer every query without performing another traversal.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Proof">↵
↵
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))$↵
↵
Therefore, the maximum distance from $v$ can always be obtained by checking only $A$ and $B$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="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 `dist_A`**↵
↵
Run BFS/DFS from $A$.↵
↵
The farthest node is $B$.↵
↵
Store the distance from $A$ to every node in `dist_A`.↵
↵
**3. Calculate `dist_B`**↵
↵
Run BFS/DFS from $B$ and store the distance from $B$ to every node in `dist_B`.↵
↵
**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>↵
↵
↵
<spoiler summary="Complexity Analysis">↵
↵
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)$↵
↵
**Space Complexity:** $\mathcal{O}(n)$↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
<spoiler summary="Brute Force">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
// Function to perform a BFS from a given query node 'v' and find the maximum↵
// distance↵
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;↵
// For each query, run a full BFS from node 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 (let's call it A)↵
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 (let's call it B) and distances 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 the other diameter endpoint B↵
vector<int> distB(n + 1);↵
dfs(B, 0, 0, adj, distB);↵
↵
// Step 4: Answer the q queries in O(1) time each↵
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>↵
↵
</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$
$(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="
↵
**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$.↵
↵
If $M < (N/2) \times P$, it is impossible.↵
↵
Therefore, if either of these conditions fails, print **NO**.↵
↵
---↵
↵
**When to print YES:**↵
↵
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>↵
↵
<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}$).↵
↵
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.↵
↵
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="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$.
↵
↵
↵
$$A[i] = A[j] = 2^{b_i}$$↵
↵
Therefore, the answer is **YES**.↵
↵
↵
↵
Let's assume all elements in $b$ are strictly unique.
↵
↵
Without loss of generality, let $M \in S_1$.
↵
↵
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$:↵
↵
$$\sum_{x=0}^{k-1} 2^x = 2^k - 1$$↵
↵
Therefore, the sum of $S_2$ will always be strictly less than $M$
↵
↵
$$\text{Sum}(S_2) < \text{Sum}(S_1)$$↵
↵
and the two subarrays can never have equal sums.
↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
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>↵
↵
↵
~~~~~↵
#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];↵
}↵
↵
↵
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() {↵
cin.tie(NULL);↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
solve();↵
}↵
↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Complexity">↵
↵
**Using sorting:**↵
↵
Time Complexity: $\mathcal{O}(n \log n)$
Space Complexity: $\mathcal{O}(1)$ if sorting in-place.↵
↵
**Using a Hash Set:**↵
↵
Time Complexity: $\mathcal{O}(n)$ average.
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.↵
↵
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$.↵
↵
For every character of $t$, its value must be different from the character at the same position in $s$.↵
↵
Ask yourself:↵
↵
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="Solution">↵
↵
The main observation is that free rearrangement removes the importance of ordering.↵
↵
Let:↵
↵
$cnt_0$ = number of $0$s in $s$
$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$.↵
↵
Therefore, the number of characters we can keep is limited by the available opposite characters.↵
↵
The important quantity is the maximum number of characters that can remain after matching each character with an opposite character.↵
↵
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$.↵
↵
**Time Complexity:** $\mathcal{O}(n)$ per test case
**Space Complexity:** $\mathcal{O}(1)$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
------------------↵
↵
<spoiler summary="Problem
↵
<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$:↵
↵
↵
`XX`<br>↵
`XX`↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
↵
For every row of the original grid, we need to:↵
↵
1. Replace every character with $K$ copies of that character horizontally.↵
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="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:↵
↵
$AA..XX$↵
↵
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>↵
↵
↵
↵
The final grid contains $(M \times K) \times (N \times K)$ characters.↵
↵
Therefore:↵
↵
**Time Complexity:** $\mathcal{O}(MNK^2)$↵
↵
**Space Complexity:** $\mathcal{O}(NK)$ if we store one expanded row.↵
↵
</spoiler>↵
↵
↵
↵
↵
~~~~~↵
#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:↵
↵
**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]↵
↵
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.↵
↵
This pairwise comparison should reveal the sorting criterion for the relics.↵
↵
</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="Complexity">↵
↵
Sorting the relics takes:↵
↵
Time Complexity: O(n log n)↵
↵
The simulation after sorting takes:↵
↵
Time Complexity: O(n)↵
↵
Therefore, the overall complexity is:↵
↵
Time Complexity: O(n log n)↵
↵
Space Complexity: O(n)↵
↵
</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>↵
↵
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$↵
↵
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$↵
↵
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$.**↵
↵
How can prefix sums be used to count zero-sum subarrays efficiently?↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
<spoiler summary="Key Observation">↵
↵
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:↵
↵
$\sum_{i=l}^{r} a_i = \sum_{i=l}^{r} 1$↵
↵
Moving everything to the left gives:↵
↵
$\sum_{i=l}^{r}(a_i-1)=0$↵
↵
This transformation is the key to the problem.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Transformation">↵
↵
Define a new array $b$ such that:↵
↵
$b_i=a_i-1$↵
↵
Now the original condition becomes:↵
↵
$\sum_{i=l}^{r} b_i=0$↵
↵
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:↵
↵
$b=[0,1,-1,0]$↵
↵
Now we only need to count the subarrays of $b$ whose sum is $0$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Using Prefix Sums">↵
↵
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}$↵
↵
We want this sum to be $0$, so:↵
↵
$P_r-P_{l-1}=0$↵
↵
which means:↵
↵
$P_r=P_{l-1}$↵
↵
Therefore, a subarray has sum $0$ exactly when the prefix sum at its two boundaries is the same.↵
↵
So, whenever we encounter a prefix sum that has appeared before, every previous occurrence of that prefix sum gives us one new valid subarray.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Counting the Subarrays">↵
↵
We maintain a frequency map containing how many times each prefix sum has appeared.↵
↵
Initially, the prefix sum is $0$ before processing any elements.↵
↵
Therefore, we initialize:↵
↵
$freq[0]=1$↵
↵
For every element:↵
↵
1. Add the element to the current prefix sum.↵
2. Add `freq[prefix]` to the answer.↵
3. Increment `freq[prefix]`.↵
↵
Why does this work?↵
↵
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.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Correctness">↵
↵
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$↵
↵
This is equivalent to:↵
↵
$\sum_{i=l}^{r}(a_i-1)=0$↵
↵
After defining $b_i=a_i-1$, this means:↵
↵
$\sum_{i=l}^{r}b_i=0$↵
↵
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.↵
↵
Therefore, the algorithm correctly computes the number of good subarrays.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Complexity Analysis">↵
↵
Each element is processed exactly once.↵
↵
Using a hash map:↵
↵
**Time Complexity:** $\mathcal{O}(N)$ average per test case↵
↵
**Space Complexity:** $\mathcal{O}(N)$↵
↵
Since $\sum N \le 2\cdot10^5$, this easily fits within the constraints.↵
↵
Alternatively, using an ordered map gives:↵
↵
**Time Complexity:** $\mathcal{O}(N\log N)$↵
↵
**Space Complexity:** $\mathcal{O}(N)$↵
↵
</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>↵
↵
</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$.↵
↵
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.↵
↵
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">↵
↵
<spoiler summary="Core Idea">↵
↵
The problem asks for the maximum distance from a given node $v$ to any other node in the tree.↵
↵
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**.↵
↵
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:↵
↵
$\text{answer}(v)=\max(\text{dist}(A,v),\text{dist}(B,v))$↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Claim 1 — Finding a Diameter Endpoint">↵
↵
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$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Claim 2 — Finding the Other Endpoint">↵
↵
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 `dist_A`.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Claim 3 — Farthest Node Property">↵
↵
For every node $v$, one of the diameter endpoints $A$ or $B$ is a farthest node from $v$.↵
↵
Therefore:↵
↵
$\text{answer}(v)=\max(\text{dist}_A[v],\text{dist}_B[v])$↵
↵
This allows us to answer every query without performing another traversal.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Proof">↵
↵
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))$↵
↵
Therefore, the maximum distance from $v$ can always be obtained by checking only $A$ and $B$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="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 `dist_A`**↵
↵
Run BFS/DFS from $A$.↵
↵
The farthest node is $B$.↵
↵
Store the distance from $A$ to every node in `dist_A`.↵
↵
**3. Calculate `dist_B`**↵
↵
Run BFS/DFS from $B$ and store the distance from $B$ to every node in `dist_B`.↵
↵
**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>↵
↵
↵
<spoiler summary="Complexity Analysis">↵
↵
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)$↵
↵
**Space Complexity:** $\mathcal{O}(n)$↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
<spoiler summary="Brute Force">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
// Function to perform a BFS from a given query node 'v' and find the maximum↵
// distance↵
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;↵
// For each query, run a full BFS from node 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 (let's call it A)↵
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 (let's call it B) and distances 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 the other diameter endpoint B↵
vector<int> distB(n + 1);↵
dfs(B, 0, 0, adj, distB);↵
↵
// Step 4: Answer the q queries in O(1) time each↵
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>↵
↵
</spoiler>↵
