Since $$$N$$$ is always even, try visualizing the array as $$$N/2$$$ independent, non-overlapping pairs: $$$(A_1,A_2), (A_3,A_4), \dots$$$

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?

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.

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 \lt (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.

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

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?

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?

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.

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

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)$$$.

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.

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.

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.

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

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 becomes:

XX XX

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.

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.

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.

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

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?

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.

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.

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)

PASTE YOUR C++ CODE HERE

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?

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$$$?

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?

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)$$$