The optimal way to hit $$$ n $$$ runs in minimum balls is to hit $$$ 6 $$$ runs on every ball until you reach $$$ n $$$ runs.
The optimal way to hit $$$ n $$$ runs in maximum balls is to hit $$$ 4 $$$ runs on every ball until you reach $$$ n $$$ runs.
Time Complexity: $$$ O(1) $$$.

From the definition of the Good string it clearly seems that string must contain either all 0’s or 1’s.

So all 0’s are converted into 1’s in the following ways:

1. Using Operation 1 by using $$$ a $$$ coins per operation.

2. Using Operation 2 by using $$$ b $$$ coins per operation by using any extra '1' in the string.

All 1’s are converted into 0’s in the following ways:

1. Using Operation 1 by using $$$ a $$$ coins per operation.

2. Using Operation 2 for pair of 1’s using $$$ b $$$ coins per operation. If there is single '1' left this can be converted to '0' by either using $$$ a $$$ coins or $$$ 2b $$$ coins.

The minimum coins will get in one of the above scenarios. Time Complexity: $$$ O(n) $$$.

The lower bound of $$$ F(p) $$$ will be $$$ \log_2(n) + 1 $$$.

Mathematically, Let's consider $$$ \sum \frac{p_i}{i} \geq \log_2(n) + 1 $$$ (ans).

Let $$$ 2^x \leq n \leq 2^{x+1} $$$, $$$ m = 2^{x+1} $$$.

Array $$$ b = p $$$. $$$ \left\lfloor \frac{p_m}{m} \right\rfloor \geq \left\lfloor \frac{2^{x+1}}{m} \right\rfloor = \left\lfloor \frac{(2^x+2^x)}{m} \right\rfloor \geq \left\lfloor \frac{(b_m+m)}{m} \right\rfloor $$$.

So $$$ \sum \frac{p_i}{i} \geq \sum \frac{(b_i+i)}{i} = \sum \frac{(p_i+i)}{i} = \sum \frac{p_i}{i} + 1 \geq \text{ans} + 1 $$$.

Hence showed that lower bound will be limited to $$$ \log_2(n) + 1 $$$.

So construct the permutation accordingly.

Time Complexity: $$$ O(n+\log n) $$$.

From the given queries we only know the information about number of zeroes and ones in the hidden string but how we can get to know the positions of ‘01’ and ‘10’ (Binary Search it!)

Just know the first character by asking queries like 000…n times and 1000…(n-1) times.

Later do the binary search to know the first occurrence of the character other than first character, similarly, do the binary search for another substring position.

Total queries used are $$$ 2\log(n) + 2 < 40 $$$.

Time Complexity: $$$ O(n\log n) $$$.

In this problem we need to find the highest ancestor of the node which is empty.

We can do Binary Lifting, HLD etc., Time limit given to get accept any solution.

Time Complexity: $$$O(nlogn)$$$ (Binary Lifting)

Time Complexity: $$$O(nlog^2 n)$$$ (HLD)

The Naveen’s array elements are the integers which has even number of set bits.

The Pavan Kalyan’s array elements are the integers which has odd number of set bits.

You can get it in OEIS but mentioned in statement for fun activity.

Now you need to find the number of simple of paths whose Bitwise Xor has even set bits and odd set bits. For that, Fix a root of the tree and create an array whose elements indicates ‘1’ if there are odd set bits in the bitwise Xor of the path between the root and that particular node and ‘0’ for vice-versa.

Let u→v path bitwise Xor has even set bits and v→w path bitwise Xor has even set bits the u→w path bitwise Xor has even set bits.

Proof: u→w path bitwise Xor bits= number of bits in u→v + number of bits in v→w – 2*(number of common bits in u→v and v→w).

it is even+even-even which is even.

From the above fact we can find the answer to queries easily.

Time Complexity: $$$O(n+q \cdot log(10^9))$$$.

Observe that the given tree is similar to undirected tree but instead of single edge there are two directed edges with facing opposite directions.

First, let’s get the upper bound of the ans. For each tree edge let cnt be the number of times we pass through this edge. Since there are only two directions for this edge, ans will increase from this edge is at most min(cnt, 2). Thus, the upper bound of the ans is sum of min(cnt, 2) over all edges.

For the constructive part, Take two paths that involve u. Suppose that they are (u,v) and (u,w). Let (u,in) be the intersection of these two paths. Now, we add a restriction: if we choose v → u we must choose u → w, and if we choose u→ v we must choose w → u. With this restriction, we can ensure that the edges between u and in are covered in both directions, and in the future we can ignore those edges. Thus, v→ u and u→w is equivalent to v→w, and u→v and w → u is equivalent to w→ v. Now we can remove two paths (u,v) and (u,w) and add (v,w) instead. Repeat this process for every edge to get the optimal selection.

Time Complexity: $$$O(nm+n^2)$$$.