Video Editorial with Scoring Distribution: https://youtu.be/8tEXXSc351c

Problem 1:

Observation 1: Notice that the left arrows will form a prefix of any row. L U L can be made L U U without affecting anything. Observation 2: The number of left arrows will decrease as we go from the bottom row to the top row.

These 2 solutions lead to a $$$O(N\cdot M)$$$ DP where N, M are the dimensions of the rectangle.

Problem 2:

Observation 1: If any bit is set in >= 2 numbers in the range, answer is 0. So we can compute prefix frequencies for each bit. Observation 2: Answer will atmost be 2 because we can make the last bit 1 (having two odd integers in the range is sufficient).

So, with the prefix computation, if answer is not 0, it is 2 — (number of odd integers in the range). Solution complexity: $$$O(N + Q)$$$

Problem 3: Simple implementation problem — just store the frequency of every number. Answer = Sum of initial array. Then, ans = min(ans, sum — freq(val) * val) for all values. Solution complexity: $$$O(N)$$$

Problem 4:

We can have a $$$O(N \cdot M)$$$ DP, where DP(i, j) stores the number of ways of spending i days, where at the last day, we did an activity of type j, adhering to all the constraints. Using prefix summations, we can get the transitions in O(1) time.

Problem 5:

Observation 1: The order of the elements does not matter — we can swap any two elements doing the mentioned operations, and also get the xor of any subset of elements.

Observation 2: The above leads to Gaussian elimination based solution — we only care about the basis (linearly independent set) of elements in the array, since we can get all other XORs from it. Thus, the problem is reduced to finding the basis with the smallest sum. We can do this by finding any basis, and reduce the larger basis elements using the smaller ones.

Solution code: http://p.ip.fi/-1b1

Problem 6:

Observation 1: The required node is basically the LCA of all the leaf nodes in the range [L, R]. Observation 2: If we do a DFS order traversal of the tree and store the discovery time of every node, then we only care about finding LCA(first discovered leaf node, last discovered leaf node) in the query range, because all the other nodes lie in between.

Using this, we can solve the problem in $$$O(N \log N)$$$ using various techniques.

In problem 6, was Farach Colton LCA the intended solution to find LCA without MLE? or was segment tree solution for LCA sufficient?

can anyone please explain problem statement of problem 1 , i could'nt even understand problem clearly , i tried hard to understand but couldnt ..plz explain anyone..

This is problem 4 — Problem

How do you guys come to know about these contests? Can anyone participate?

I solved P2, P3 and P6 is there any probability I may get a call?

Will I get the internship interview opportunity ? I solved first 3 Questions. Ashishgup

can anyone post the solutions of problem 4?

Can someone explain 5th question solution in a more detailed way? It will be better if you can mention the required mathematical concepts properly.

Ashishgup, could you please tell whether the testcases on which the solutions were tested at the time of the contest were only pretests or full testcases.

After being asked to do it by multiple people, I finally made a video explanation of all of these problems on my youtube channel.

provide more problems please