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.

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