Question: Google | Complex Subsequence | Subtree XOR

Entering edit mode

Problem 1

Complex Subsequences

You have an array of infinite length with the value of all elements as zero. You are also given the following:

Two integers N and K
In the next N lines, you are given three integers L, R, and X. This means that you have to add X to every element in the array from the index L to R (inclusive).

Your task is to find a subsequence from this array that meets the following conditions:

The subsequence should be of maximum length.
It should also be the smallest lexicographically.
The subsequence should form an increasing sequence of the form [Z, Z + K, Z + 2 * K, ..., Z + (L - 1) * K] for a value Z and length L.

Notes

Remember that the sequence A = [A1, A2, ..., AL] is lexicographically smaller than the sequence [B = [B1, B2, ..., BL] if there exists an index i such that Aj = Bj for all j < i and Ai < Bi.

Output Format

Print the first integer that is the length of the subsequence and then the elements of the subsequence in the same line.

Constraints

1 <= N, K <= 2 * 10^5
1 <= L <= R <= 10^9
1 <= X <= 10^9

Sample Input

4 2
1 3 1
2 4 2
5 6 3
5 5 1

Sample Output

2 1 3

Problem 2

Subtree XOR

You are given the following:

A tree with N nodes
An array A denoting the value of each node
A non-negative integer K

You can do the following operation on the tree at most once:

Pick a node r and make it the root of the tree.
In the new tree, pick a node x and for each of the nodes in the subtree of x, update A[subtree] = A[subtree] ⊕ K.

Task:

Determine the maximum sum of values of all the nodes in the tree that can be obtained.

Notes:

1-Based indexing.
⊕ denotes the Bitwise-XOR operator.
A subtree of a node contains all the nodes that are descendants of that node and the node itself.

Example

Assumptions:

N = 3
edges = {(1, 2), (1, 3)}
A = [1, 1, 3]
K = 3

Approach:

You perform the following operation to get the maximum sum:
- Pick r = 3 as the root of the tree.
- Update the value in the subtree of x = 1.
- The new array becomes A = [2, 2, 3].

The sum obtained is 2 + 2 + 3 = 7 which is maximum. Hence, the answer is 7.

Input Format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first line contains T denoting the number of test cases. T also specifies the number of times you have to run the maximumSum function on a different set of inputs.
For each test case:
- The first line contains an integer N denoting the number of nodes.
- Each of the following (N - 1) lines contains two space-separated integers denoting an edge between the given nodes.
- The next line contains N space-separated integers denoting the value of nodes.
- The next line contains a single integer K.

Question 3

Range function

You are given an array A of N integer elements. You are also given Q queries, where each query is one of the following types:

1 i val: Update value of element at i-th index to val i.e. A[i]=val .
2 L R: Find the value of function ∑i=L,R ∑j=i,R [F(i,j)] , where F(i,j) represents the sum of elements of array A in index range Lto R.

Task

Determine the value of function for queries of Type 2.

Note: Assume 1-based indexing.

Example

Assumptions

N = 5
Q = 2
A = [2,1,4,3,1]
query = [(1, 2, 2), (2, 1, 3)]

Approach

First query is of Type 1. Update A[2]=2 . Now, array A becomes [2, 2, 4, 3, 1] .

Second query of Type 2 with L = 1, R = 3
- Value of function is equal toF(1,1)+F(1,2)+F(1,3)+F(2,2)+F(2,3)+F(3,3) = 2+4+8+2+6+4 = 26

Thus, the answer is 26.

Input Format:

The first line contains a single integer T, which denotes the number of test cases.
For each test case:
- The first line contains an integer N.
- The second line contains an integer Q.
- The third line contains N space-separated integers denoting the array A.
- The next Q lines contain 3 space-separated integers denoting the queries.

Output Format:

For each test case, print the value of the function for queries of type 2 in space-separated format on a new line.

Constraints:

1 ≤ T ≤ 10
1≤ N , Q ≤ 10⁵
1 ≤ A[i] , val ≤ 10³
1 ≤ i ≤ N
1 ≤ L ≤ R ≤ N

Question 4

Min Square Zepto Distance

You are given N integers representing the locations of homes on a straight street (x-axis). The i_thhome is located at A_i . You need to determine the optimal integer location X to build a dark store such that the sum of the squared distances from the dark store to each home is minimized. Specifically, you want to minimize the value of: ∑i=1,N (X−A_i)2 .

Task

Determine the location of X which minimizes the value of function given in the question.

Example

Assumptions

N = 4
A = [1,7,11,9,3]

Approach

For all the values of X only X=6 gives the value of 69 which is minimum among all the integer values of X.

Thus, the answer is 6.

Input Format:

The first line contains a single integer T, which denotes the number of test cases.
For each test case:
- The first line contains an integer N.
- The second line contains N space-separated integers denoting the array A.

Output Format:

For each test case, print the value ofXwhich minimizes the value of the function given in the question.

Constraints:

1 ≤ T ≤ 10
1≤ N ≤ 10⁵
1 ≤ A[i] ≤ 10⁹

Question 5

Min Abs Zepto Distance

You are given N integers representing the locations of homes on a straight street (x-axis). The i_th home is located at A_i. You need to determine the optimal integer location X to build a dark store such that the sum of the absolute distances from the dark store to each home is minimized. Specifically, you want to minimize the value of:

∑i=1,N |X − A_i | .

Task

Determine the location of X which minimizes the value of function given in the question.

Example

Assumptions

N = 4
A = [1,7,11,9,3]

Approach

For all the values ofX only X=7 gives the value of 16 which is minimum among all the integer values of X.

Thus, the answer is 7.

Input Format:

The first line contains a single integer T, which denotes the number of test cases.
For each test case:
- The first line contains an integer N.
- The second line contains N space-separated integers denoting the array A.

Output Format:

For each test case, print the value ofXwhich minimizes the value of the function given in the question.

Constraints:

1 ≤ T ≤ 10
1≤ N ≤ 10⁵
1 ≤ A[i] ≤ 10⁹

ADD COMMENT • link

Entering edit mode

Approach for complex subsequences:

Part 1: Efficient Range Updates

To handle the range updates efficiently, we use a difference array. The steps are as follows:

Initialize a difference array: Create a difference array diff of infinite length initialized to zero. Practically, this array can be managed dynamically using a map.
Apply the operations:
- For each operation (L,R,X), update the difference array as follows:
  - diff[L]+=X
  - diff[R+1]−=X
Convert the difference array to the actual array:
- Calculate the prefix sum to get the final values of the array after all operations are applied.

Part 2: Find the Longest Subsequence

To find the longest subsequence that meets the given conditions:

Next we can form a array corresponding to values which are there in the map.
NOTE: There cann't be more than 2n values in the map.

Next Occurrence Array:
- Create an array next_occurrence where next_occurrence[i] points to the next index j such that array[j]=array[i]+K. This helps in quickly finding the next element of the desired subsequence.
Dynamic Programming:
- Create a DP array dp where dp[i] stores the maximum length of the subsequence starting from index i.
- Iterate over the array from the end to the beginning. For each index iii, update dp[i] based on next_occurrence[i].
Reconstruct the Subsequence:
- Start from the smallest possible value whose dp value is maximum and use the next_occurrence array to reconstruct the longest increasing subsequence of the desired length.
  
  NOTE: Part 1 holds because map is missing only those values which are equal to previous value which is there in the map and consecutive equal values are useless because k is a positive integer.

ADD COMMENT • link 7 weeks ago Keshav Jindal • 50

Entering edit mode

Approach for Problem 2:

Root the tree at node 1, then find sum[v] and sumWithXorApplied[v] for every node v

then subtree of any node v only changes if we make v as new root or any child of v as the new root (no need to consider other nodes in the subtree of v as the new root, because the new subtree of v will be either one of the subtrees that we get after rooting at any child of v)

ADD COMMENT • link 7 weeks ago Abhinav Ratna • 20

Entering edit mode

Approach for problem 3->
(Using Segement Tree)

At a node in the segment tree three values will be stored, suppose the node denotes the range (l,r) in the array, then we will store-->
1) val1= summation of all a[i] : l<=i<=r : i.e. a[l] +a[l+1] +a[l+2]....+ a[r]

2) val2= summation of all i*a[i] : l<=i<=r : i.e. l*a[l] + (l+1)*a[l+1] + (l+2)*a[l+2] +.... + r*a[r]

3) val3= summation of all i*i*a[i] : l<=i<=r : i.e. l*l*a[l] + ((l+1)*(l+1)*a[l+1]) +.......+ r*r*a[r]

now for the update we can do a point update operation on the segment tree and update the val1, val2, and val3 for them as required.

Now for the query part, if we can to use the contribution techinique, i.e. we will calculate the contribution of each of the elements in the given summation equation and then calculate the sum of their individual contribution. Now if we carefully see the expression given it is basically the summation of the sum of all the subarrays that can be formed in the range (l,r). Now if we try to calculate the contribution of each element then it will be -->

let a[i] be the value of that element and cnt be the number of subarrays in (l,r) in which the i'th element is also present. Hence, cnt = [i-l+1] *[r-j+1].
Now the contribution will be-> a[i]*cnt
On simplifying the expression comes out to be-->
a[i]*(r-l+1-lr) + (i*a[i])*(l+r) - (i*i*val)

now if we take the summation of the contribution it will be simply:
our final ans= val1*(r-l+1-lr) + val2*(l+r) - val3 : val1, val2, val3 can be calculated using the segment tree for the range (l,r)

Time-Complexity: Using a segment tree for querying and update hence O((q+n)log(n))

ADD COMMENT • link 4 weeks ago CLOWNTK • 10