You can simply brute force for the solution. one by call friend for each level and then compute the answer for that call. Out of all possible solution select the maximum one.

http://paste.ubuntu.com/25305339/

http://paste.ubuntu.com/25305411/

the problem was simple brute force. There were two cases to handle, when the second index is odd, and when second is even for both type of queries. Just make a big enough picture, and it will help you in understanding the solution.

http://paste.ubuntu.com/25305429/

We will solve the problem using binary representation of the number.Since we have to find the number of solutions of the equation a+b+c = N , we have to make sure that ith bit of a , b and c add up to ith bit of N i.e. (ai + bi + ci)%2 = (Ni). A carry might also get generated which will be equal to (ai + bi + ci)/2. For the condition (a & b & c) > 0 to be true we have to make sure that some jth bit have to be set for all three variables(for this purpose we will take a variable flag which is set to 1 when all the 3 numbers have same bit set). Thus after assigning values for MSB , the value of carry and flag should be equal to 0(in case of carry being equal to 1 implies overflow) and 1(in case of value of flag being 0 implies (a&b&c)=0) respectively. Trying all possible combinations for all bit for a,b,c will cost 8^len where ,
len = number of bits required to denote the number n. But since we are making same same kind of recursive calls many times we can memorize it using 64*2*2 array(Since the number can be of max 64 bits , carry and flag can take value 0,1 ).

http://paste.ubuntu.com/25305466/

AN EXCURSION WITH MATHEMATICS

Time Complexity:-O(T*3000)

In this question the most important part was finding x,y,z for given a,b,c.

we are given,
x^2 + y^2 + z^2 = a
x^4 + y^4 + z^4 = b
x^5 + y^5 + z^5 = c

suppose, we know the value of x then,

y^2 + z^2 = a' __(1)
y^4 + z^4 = b' __(2)
y^5 + z^5 = c' __(3)

now solving equations (1) and (2) is doable. So now we got the values of y^2 and z^2 (i.e. y and z). Now check if y and z are integers and they satisfy eq(3). We can do above checking for every x. Once you get the values of x,y and z you can find sum using modular exponentiation and properties of Geometric progression.

C++ Code — https://paste.ubuntu.com/25306084/

http://paste.ubuntu.com/25305520/

Note that the ways of tossing and of H and T have a bijection with each other.

Let X(n),Y(n),Z(n) represent the allowable sequences ending with 2,1 and 0 consecutive tails respectively.

We have:

X(n)=Y(n-1)...(i) Y(n)=Z(n-1)...(ii) The above two results can be shown by considering that we can append a tails to the end of the n-1 length chain to create an n length chain with one more consecutive tail at the end.

Now let F(n) denote the total number of acceptable sequences.

Now, we have:

Z(n)=F(n-1)...(iii) (By appending an heads to the end of any acceptable sequence and removing heads from end of any (acceptable) sequence ending with tails ... bijection can be proved)

Also (obviously):

F(n)=X(n)+Y(n)+Z(n)

Thus, we can show:

F(n)=F(n-1)+F(n-2)+F(n-3) ...by (i), (ii), (iii)

We can easily compute this in log(n) complexity using Matrix Exponentiation.

solution link : https://paste.ubuntu.com/25305080/

Time complexity : O(T*log(n))

java solution : http://paste.ubuntu.com/25305535/

prerequisite : Lowest Common ancestor , DFS

For each 1 ≤ i ≤ n and 0 ≤ j ≤ log(n), store the minimum 20 values in the path from U(vertex) i to its 2^j-th parent in an array. Now everything is needed is: how to merge the array of two paths? You can keep the these 20 values in the array in increasing order and for merging, use standard merge function which will work in . And then delete the extra values (more than 20). Do the same for a query (just like the preprocess part) and you will get the list.

solution link : http://paste.ubuntu.com/25305169/

Time complexity: O((n+q)*20*log(n))

PLAY WITH NUMBERS.

Time Complexity:-O(max(N,Q))

In this question you had to find out the expected value of value of the subarray from l to r.

The expected value of the subarray is the mean of the subarray i.e. the sum of all the terms in the subarray divide by the number of terms in the subarray. So to solve this we make an array A where A[i] stores the cumulative sum of all elements before index i+1. Then for every query given l and r the answer will be (A[r]-A[l-1])/(r-l+1). To ensure that we get the floor of the expected value we need to do integer divison.

C++ Code — https://paste.ubuntu.com/25305261/

Just make 26 maps for each character. make 2, such map arrays. one stores the frequency of sum that ends in current character and other for sums till previous index (sums means prefix sum); Then just iterate over the values then decrease in both array for current character and then add count of such numbers that end in same prefix sum (as then their difference will be zero)

http://paste.ubuntu.com/25305989/

A direct implementation of dsu. http://paste.ubuntu.com/25305377/ http://paste.ubuntu.com/25305621/

CLOCK

Time Complexity:-O(R*R)

In this question you had to find out number of integral points that lie between the minute hand and the hour hand (taking the clockwise angle from the minute to the hour hand) within the clock.

For this we first needed to find out the angle of the minute and hour hand. ->minute hand angle:-m*6; ->hour hand angle:-h*30+m*(0.5); After this for every integral point in the range (-R,-R) we need to check if it lies within the circle and whether it lies between the minute and hour hand.

C++ Code — https://paste.ubuntu.com/25305475/