Problem Setters — modi_aashu2, fLUKEmASTER
Was a Cakewalk Problem. Just sum up the values $$$(A[i]*B[i])$$$ in the range $$$[L,R]$$$.

Problem Setters — modi_aashu2, fLUKEmASTER
The track of top,bottom, left and right nodes can be kept in the start.
No of edges = $$$2^{(n + 1)} - 2$$$, Top = $$$1$$$, bottom = $$$2^n$$$, left = right = $$$n + 1$$$, Where $$$n$$$ is the depth.
In every query of “1 x” type, the variables can be updated as follows.
If it is a top query, then the no of edges = 2*no of edges + top. And newtop = bottom, newleft = 2*left, newright = 2*right.
If it is a bottom query, then the no of edges = 2*no of edges + bottom. And newbottom = top, newleft = 2*left, newright = 2*right.
If it is a left query, then the no of edges = 2*no of edges + left. And newleft = right, newtop = 2*top, newbottom = 2*bottom.
And if it is a right query, then the no of edges = 2*no of edges + right. And newright = left, newtop = 2*top, newbottom = 2*bottom.

Finally at every query of type “2”, display the no of edges stored.

Problem Setter — shivamg_isc
Through DFS(Single Source Shortest Path), compute the minimum distance required to reach all the N nodes using specific number of edges.
$$$dis [ i ] [ j ]$$$ = distance to reach from node 1 to node $$$i$$$ using $$$j$$$ number of edges.
Now for each node $$$i$$$, we can form linear equations of form $$$y=mx+c$$$ for each edge.
Where, $$$c=dis[i][j]$$$, and $$$m=j$$$.
Whenever in queries, the weight of all edges gets changed to a value $$$VAL$$$,
then for each equation $$$y = j*VAL+dis[i][j]$$$.
Now, we need minimum value among all equations corresponding to a node, which can be done using Convex hull trick.

Problem Setter — modi_aashu2
Can be solved by 3D $$$DP(i, j, k)$$$, Where $$$dp[i][j][k]$$$ is the number of stars collected while going from $$$(i, j)$$$ to $$$(i, j + k)$$$. Note that $$$i$$$ and $$$j$$$ range from $$$1$$$ to $$$1000$$$ and $$$k$$$ ranges from $$$1$$$ to $$$X$$$.
All the ways to go from $$$(i,j)$$$ to $$$(i,j+k)$$$ are of the following form:-
Going rightways to some point, then going down till $$$(m, n)$$$ and coming back up to some point in $$$(i+1)^{th}$$$ row, and then entering $$$i^{th}$$$ row and moving left till we reach $$$j+k$$$.
Assume the point at which you start going down as $$$(i, a)$$$ and the point when you come back to $$$i^{th}$$$ row as $$$(i, b)$$$.
Now, we can go from $$$(i,j)$$$ to $$$(i,a)$$$ then go one row down to $$$(i+1, a)$$$, now complete the journey and reach $$$(i+1, b)$$$ which is equal to $$$dp[i+1][a][b]$$$, then move back to $$$i^{th}$$$ row and return to $$$(i,k)$$$
This can be computed in the following way:-
$$$dp[i][j][k]$$$ = Max($$$dp[i + 1][a][b]$$$ + no.of stars from $$$(i,j)$$$ to $$$(i,a)$$$ and $$$(i,k)$$$ to $$$(i,b)$$$) for all $$$a$$$ in $$$j$$$ to $$$(j + x)$$$ and $$$b$$$ from $$$max(k, a)$$$ to $$$(j + x)$$$.
The final solution is stored in $$$dp[0][0][0]$$$.

Problem Setter — priyanshupkm
Precompute the number of divisors of all $$$B[i]$$$’s and store it in $$$C$$$.
Now we calculate XOR of all $$$C[i]$$$ such that $$$L \leq i \leq R$$$ and $$$A[i] \leq K$$$. This can be done using Merge sort tree where we sort each node according to the value of $$$A[i]$$$ and $$$C[i]$$$ are automatically arranged along with it.
On each node we store prefix XOR of all numbers appearing before the given index and calculate the answer using merge sort tree query.
Once we have $$$X$$$ = the XOR of all $$$C[i]$$$'s corresponding to the query.
We need to find how many elements in that range have values = $$$X$$$, as removing this value will make the resultant XOR = 0 .
This can be done by storing for each node in Merge Sort Tree the index ranges that need to be answered for a value.
As total number of elements in the Merge Sort Tree is just $$$N \, log (N)$$$, we can answer all queries by traversing all nodes of the Merge Sort Tree exactly once, and finding the contribution made by each node for any query.

Problem Setter — fLUKEmASTER
This problem can be approached as a normal vertex cover problem on a binary tree with an extra restriction that nodes from all classes ($$$1$$$ to $$$k$$$) should be considered.
This extra constraint can be handled by introducing an extra state in the naive solution for vertex cover of a binary tree.
This state could be a mask for all the classes which are to be found in the subtree of a node.
Hence, the final states could be $$$dp(node)(mask)(parent)$$$.
To compute the value of a particular state, we need to divide the mask between the two children for the node.
The net complexity of the code would be lesser than $$$O(n*2^{2k})$$$.(Think why?)

Problem Setter — blake_786
Consider a DS which supports following function:
Insert a pair $$$(x, y)$$$.
Given a pair $$$(x, y)$$$ , find number of pairs $$$(x_i, y_i)$$$ such that $$$x_i \leq x$$$ && $$$y_i \leq y$$$.
Given a pair $$$(x, y)$$$, find sum of all $$$y_i$$$ ’s of pair $$$(x_i, y_i)$$$ such that $$$x_i \leq x$$$ && $$$y_i \leq y$$$.
Given a pair $$$(x, y)$$$, find sum of all $$$x_i$$$ ’s of pair $$$(x_i, y_i)$$$ such that $$$x_i \leq x$$$ && $$$y_i \leq y$$$.
For every node $$$q$$$, we have to consider only the ancestor of node $$$q$$$.
While traversing using DFS, if we update the points of all ancestor in the DS then we can calculate the sum by making $$$v$$$ fixed and breaking the equation $$$min(max(A_u, A_v), max(B_u, B_v))$$$ into different cases on the basis of value of $$$A_v$$$ and $$$B_v$$$.

To maintain such DS we can compress the $$$A_i$$$ ’s and $$$B_i$$$ ’s.
Consider a BIT tree such that each index of BIT tree is itself a segment tree part.
Now to update a pair $$$(A_i, B_i)$$$, update with starting index $$$A_i$$$ of BIT and for every update index in BIT update the segment tree with $$$B_i$$$.

Problem Setter — shivamg_isc
This representation of bases and numbers can be changed to a simple grid of dimensions $$$(X+1)*Y$$$.
We can form a matrix $$$M$$$ of dimension $$$Y*Y$$$, such that $$$M[i][j]$$$ denotes the number of ways to go from $$$(x,i)$$$ to $$$(x+1,j)$$$, if entire row $$$(x+1)$$$ doesn’t contain any obstacle.

Let’s say we have the answer till row number $$$x$$$, then if $$$(x+1, x+2,.......x+a)$$$ are empty, we can apply Matrix Exponentiation of $$$M^a$$$ to compute the answer for row $$$(x+a)$$$ directly.

Now, for those cases where some row $$$x$$$ has certain obstacles, take the matrix obtained above from matrix exponentiation, compute DP in $$$O(Y^2)$$$ to frame new transitions for such row to obtain the new DP array for row number $$$x$$$.

Once you obtain this DP array for a non empty row x, apply matrix expo again upon this temporarily obtained matrix with a factor $$$a$$$, such that $$$(x+1…..x+a)$$$ are empty. Matrix precomputation will take $$$O(Y^3 log X)$$$.
Also, for these 200 rows, the computation has to be at max this complexity via optimisations — $$$O(200*Y^2*log(X))$$$. (observe $$$Y^2$$$ in the complexity- this has to be toned down from $$$Y^3$$$ of matrix expo. How?).

Problem Setter — satylogin
The problem consist of 2 parts, $$$1^{st}$$$ is selecting the nations that have influence greater than dream influence.
For that we can use rotating calliper as the farthest points will lie on the convex hull formed by the set of points (can be proved by method of contradiction. Will add the proof in details editorial).

Ones hull is made, one can use the rotating calliper technique to calculate the max distance.
After that The convex hulls that have max distance greater than dream value, they can be transformed into lines by projecting their shadows on $$$x$$$ axis.
After that one can use sweep line and maintain the frequency of the symbols. That can be used to check whether the name can be formed or not. Among all the events, one has to choose the one with minimum set.
The sweep line will work slightly different, as we not only have to check on line edges, but between them, as even touching the line means that we have to take that, and we have to find the smallest subset.

Problem Setter — shivamg_isc
Build a suffix array over the concatenation of the all strings and use binary search to find the answer.

Let us build a string , $$$K$$$ = $$$s[1] + '#' + s[2] +.... + '#' + s[n]$$$, where $$$s[i]$$$ is the $$$i^{th}$$$ input string.
Let the length of string $$$K$$$ be $$$Len$$$.

Build the Suffix array over this string , let us call it SA.
Now, for a query, one is provided with $$$X$$$ and $$$Y$$$. We can easily find starting position of $$$X^{th}$$$ string in SA by using mapping.

Let’s denote this position by $$$A$$$.
Now , $$$LCP( A, i )$$$ is a decreasing function as $$$i$$$ varies from $$$A$$$ to $$$0$$$.
Similarly, $$$LCP (A,i)$$$ is a decreasing function as $$$i$$$ varies from $$$A$$$ to $$$Len-1$$$.

So we will use binary search to find two indexes :
First index is leftmost which is the minimum index between $$$0$$$ and $$$A$$$ , such that $$$LCP(leftmost,A)>=Y$$$.
Second index is rightmost which is the maximum index between $$$A$$$ and $$$(Len-1)$$$, such that $$$LCP(rightmost,A)>=Y$$$.

Now, in the range $$$[Leftmost, Rightmost]$$$ , we need to find number of unique substrings.
This can be easily precomputed upto a particular index in SA using LCP of adjacent suffixes in the SA.

For finding answers corresponding to 2) and 3) parts of each query, build a Segment Tree on top of the Suffix Array.
For each suffix in the Suffix Array, find the string it was derived from.
Segment Tree will be built on top of the lexicographical ranks of these strings from which these suffixes were derived.

For each query, one can find through the Segment tree the minimum and maximum rank strings in the range $$$[Leftmost, Rightmost]$$$.