P1:
Many alternate solutions exist to this problem. We will list one of them.
One can simply observe that if we divide a number repetitively by a number > 1, it will reduce to 0 in O(LogN) steps. Thus, we can simply store at each index the index of the next element that has value > 1 in the array. We jump over these from L to R and divide k, thus answering queries in LogK time after an O(N) Precomputation step.
P2:
The problem is simply a 3D extension of the classic Prefix Sum problem.
We can determine the sum for any cube with Top-Left-Out corner as
[x1, x2) x [y1, y2) x [z1, z2)
Px2, y2, z2 - Px1, y2, z2 - Px2, y1, z2 - Px2, y2, z1 + Px1, y1, z2 + Px2, y1, z1 + Px1, y2, z1 - Px1, y1, z1
P3:
A careful interpretation of the problem statement reduces it to a Longest Common Subsequence problem. Suppose a set of moves on any tree forms a string, we want to maximize the LCS for the 2 strings obtained. Now, since the trees are directed and rooted, we can obtain a fixed value for the subtree of any pairs of nodes (a, b) if a is in tree 1 and b in tree 2 starting at node a, b. If we take all children of a and b and make pairs out of them (ca, cb), the maximum starting at (a,b) will be the max of these (ca, cb) pairs and +1 if the value at a is equal to the value of b. We can do this with simultaneous DFS of the 2 trees with memoization…
P4:
The problem can be reduced to the following:
Since there are M employees and each have to be given some equal amount, with X < M remaining, we just need to find the number of integers y such that y mod M = X. This can be done using the following algorithm:
Denote the answer to the problem f(A, B). Note that f(A, B) = f(0, B) - f(0, A - 1) or what is the same f(A, B) = f(0, B) - f(0, A) + g(A), where g(A) equals to one if A is a possible value, otherwise g(A) equals to zero. Let’s solve the problem for the segment [0, n].
Here is described the standard technique for this kind of problems, sometimes it is called ‘dynamic programming by digits’. It can be realized in a two ways. The first way is to iterate over the length of the common prefix with number n. Next digit should be less than corresponding digit in n and other digits can be arbitrary. Below is the description of the second approach.
Let Zijk be the number of magic prefixes of length i with remainder j modulo m. If k = 0 then the prefix should be less than the corresponding prefix in n and if k = 1 than the prefix should be equal to the prefix of n (it can not be greater). Let’s do ‘dynamic programming’. Let’s iterate over digit in position i. Also we should check for k = 1 p should be not greater than corresponding digit in n. Now let’s see what will be the next state. Of course i’ = i + 1. j’ = (10j + p) mod m. Easy to see that . To update the next state we should increase it: Zi’j’k’ + = Zijk. Of course all calculations should be done modulo 10^9 + 7. Finally we need the value with i = number of digits in the number, j = X and k = 0 or 1
P5:
The problem statement reduces to the following:
We have a directed rooted tree and at each node we have an array. Each node has an effective range Li to Ri and its value is defined as the maximum element value in the Range Li to Ri. We can do this easily using a Segment Tree at each node for Range Max Query. We can perform Update 1 on the arrays using Lazy Propagation on a segment tree and each time we perform this update, we have to reset the value for a node. If we can do this, all we need to do is find the subtree sum at node X, this can be done with Tree Flattening using a Segment Tree. We can do the whole problem with 2 segment trees, lets call one subtreesum[] and one nodesegtree[i] (segment tree at ith node for range max query). After each addition update or change in effective range update on nodesegtree[i], we make a point update on the subtreesum array to reset the nodes value to the new value after the update. A simple range query for subtreesum on the flattened tree can get us the answer.
You can find algorithms for RMQ, Lazy Propagation, Tree Flattening etc. easily on the internet. The problem required just interpret the statement and implement 2 segment trees efficiently. The complexity per query is logN. An alternate solution with Log^2N would have given TLE if one used a direct 2D segment tree implementation.
