The answer is $$$YES$$$ if and only if the number of red balls and the number of blue balls are both divisible by $$$2$$$.

The solution will not exist if $$$n < k$$$ because each letter must be used at least once. Further, if $$$k = 1$$$ and $$$n > 1$$$, the solution will not exist because each pair of adjacent characters must be different.

In all other cases, we can greedily construct the solution from left to right by maintaining number of characters not yet used, $$$r$$$; and the previous character, $$$prev$$$.To decide for the $$$i$$$-th position we do the following:

• If $$$r < n+1-i$$$, we can place the lexicographically smallest letter which is not equal to $$$prev$$$. (This will always be either "a" or "b".)
• Otherwise, we can place the smallest unused letter and decrease $$$r$$$ by $$$1$$$.

Time Complexity: $$$O(|A|*n)$$$ where $$$|A| = 26$$$ denotes the alphabet size.

It can also be done in $$$O(n)$$$ independent of $$$|A|$$$ but that is not required in this problem.

For any bit, how many numbers among the three can have it on?

Write N as sum of contributions of each bit.

For $$$a$$$ $$$XOR$$$ $$$b$$$ $$$XOR$$$ $$$c = 0$$$, it must be the case that each bit is either set in $$$0$$$ or $$$2$$$ among the three integers. Let us consider the set $$$S$$$ of the bit positions (starting with $$$0$$$ for least significant bit) which are set in exactly $$$2$$$ of these. We can now write: $$$N = 2*(\sum_{x \in S} 2^{x})$$$.

Clearly, if $$$N$$$ is odd no solution may exist. If $$$N$$$ is even, the above equation gives a representation of $$$\frac{N}{2}$$$ as a sum of distinct powers of $$$2$$$. This representation must be equivalent to the binary representation of $$$\frac{N}{2}$$$.

Therefore, we have uniquely recovered the set of bits which must be set in exactly two of the outputs. Now, we only need to distribute them among the three numbers. First of all, if $$$|S| = 1$$$, there can be no answer (all three outputs are required to be positive). Otherwise, let $$$i$$$ be the smallest member of $$$S$$$, then the following triple $$$(a, b, c) = (2^{i}, \frac{N}{2} - 2^{i}, \frac{N}{2})$$$ is the required answer. (This is obtained by greedily minimising $$$a$$$, followed by greedily minimising $$$b$$$.)

Time Complexity: $$$O(logN)$$$ per test case.

Can you solve for a fixed center vertex?

How many distinct center vertices are possible?

We can note the following:

• The center vertex must have degree $$$\geq K$$$.
• Two distinct $$$K$$$-stars can not share more than $$$1$$$ edge.

First of all, for simplicity, root the tree at $$$C$$$. Now, for every child $$$x$$$ of $$$C$$$, we can store an array $$$cnt_{x}$$$, where $$$cnt_{x}[d]$$$ will store the number of nodes in the subtree of $$$x$$$ at a depth $$$d$$$. After processing all children, we iterate over all possible depths $$$d$$$, and construct a temporary array $$$arr_{d}$$$ which contains the non-zero values of $$$cnt_{x}[d]$$$ over all $$$x$$$. The number of $$$K$$$-stars centred at $$$C$$$ with $$$dist(C, v_{corner}) = d$$$ is equal to the sum of products of all subsets of size $$$K$$$ of $$$arr_{d}$$$.

This can be easily computed using a dynamic programming with state:

$$$dp[i][j]$$$: the sum of products of all subsets of $$$j$$$ elements from the first $$$i$$$ elements

The dp takes $$$O(|arr_{d}|*K)$$$ time. Overall, $$$\sum_{d}|arr_{d}| \leq N$$$, therefore, the overall complexity is bounded by $$$O(NK)$$$. Combined with $$$O(\frac{N}{K})$$$ distinct possible centers, we get the final time complexity of $$$O(N^2)$$$ for each tree.

Did you try Mo's algorithm?

What is the optimal order of removal in a given range?

How many distinct frequencies can exist? Is there a way of maintaining them in constant time while adding and deleting elements?

For a given range $$$[L, R]$$$, let $$$freq_{x}$$$ be the frequency of element $$$x$$$. It is obvious we need to remove elements in increasing order of frequency, because removing the one with the smallest frequency will lead to the quickest isolation of a single element. The number of different values of $$$freq_{x}$$$ possible is $$$O(\sqrt{R-L+1})$$$. See proof if you are not sure why this holds.

To maintain the set of all frequencies while adding and deleting elements, we maintain three arrays $$$cnt$$$, $$$next$$$ and $$$prev$$$. $$$cnt[i]$$$ denotes the number of elements in current range with frequency = $$$i$$$. $$$next[i]$$$ denotes the next available frequency after $$$i$$$ , or $$$-1$$$ if frequency $$$i$$$ does not exist. $$$prev$$$ is defined analogously. It is not difficult to see that these three arrays can be updated in $$$O(1)$$$ upon addition or deletion of elements with some careful implementation. For each query now, we can start at the smallest available frequency and follow $$$next$$$ until we remove $$$k_{i}$$$ items.

Time Complexity: $$$O(QlogQ + Q\sqrt{N})$$$

Let us first look at an $$$O(n^2m^2)$$$ solution.

If we fix vectors for $$$2$$$ of the $$$3$$$ sides of the triangle, the third vector is uniquely determined. It only remains to be checked whether all $$$3$$$ of them are "valid" vectors or not, and whether a triangle with those $$$3$$$ vectors would completely fit in the $$$n*m$$$ grid given. We define a "valid" vector as a vector which does not contain any lattice point on it if we place its ends on lattice points. A vector $$$(x, y)$$$ is valid if and only if $$$gcd(|x|, |y|) = 1$$$.

The number of distinct vectors, $$$(x, y)$$$, in an $$$n*m$$$ grid is $$$\approx 4nm$$$. Simply brute forcing over every pair gives us the required $$$O(n^2m^2)$$$ solution with a pretty horrible constant factor. This approach can be optimised by a factor of around 2 by precomputation of all "valid" vectors. This approach counts each type of triangle $$$6$$$ times. Can we improve?

Let us consider any triangle on the grid. We can orient its sides in such a way that the side vector with the largest value of $$$|x|$$$ is oriented towards negative-$$$X$$$ axis while the other two sides are oriented towards positive-$$$X$$$ axis. This orientation is unique for all triangles that do not have a vertical side!! For triangles with a vertical side, there are $$$2$$$ representations.
This allows us to improve the constant by a further factor of $$$4$$$ since we can safely ignore vectors with negative value of $$$x$$$, while fixing $$$2$$$ sides. We can handle the case when one of the two fixed vectors have $$$x = 0$$$ by adding their answers to a different variable and dividing it by $$$2$$$ in the end.

For the final trick, we can use FFT!!
Let us fix only the $$$x$$$ values of the two fixed vectors, say $$$x_{1}$$$ and $$$x_{2}$$$. Further, we must have $$$x_{1}+x_{2} < n$$$. Let us compute a vector of size $$$2m-1$$$ where the $$$i$$$-th element is $$$1$$$ if $$$(x_{1}, i-m+1)$$$ is a valid vector. Compute a similar vector for $$$x_{2}$$$. We can now use FFT to multiply these vectors, and for each index $$$i$$$ such that $$$m-1 \leq i \leq 3*(m-1)$$$, if the coefficient of the index is non-zero, check whether the vector $$$(x_{1}+x_{2}, i-(2*m-2))$$$ is valid or not. If valid, we add the coefficient to our answer. We must make sure to separately handle for vertical sides whenever $$$x_{1} = 0$$$ or $$$x_{2} = 0$$$.

Note that the range on $$$i$$$ is to ensure that the triangle fits into the grid along the side of length $$$m$$$.

Time Complexity: $$$O(n^2mlog(m))$$$