You have an array of infinite length with the value of all elements as zero. You are also given the following:
Your task is to find a subsequence from this array that meets the following conditions:
Print the first integer that is the length of the subsequence and then the elements of the subsequence in the same line.
4 2
1 3 1
2 4 2
5 6 3
5 5 1
2 1 3
N
nodesA
denoting the value of each nodeK
r
and make it the root of the tree.x
and for each of the nodes in the subtree of x
, update A[subtree] = A[subtree] ⊕ K
.Determine the maximum sum of values of all the nodes in the tree that can be obtained.
⊕
denotes the Bitwise-XOR operator.Assumptions:
N = 3
edges = {(1, 2), (1, 3)}
A = [1, 1, 3]
K = 3
Approach:
r = 3
as the root of the tree.x = 1
.A = [2, 2, 3]
.The sum obtained is 2 + 2 + 3 = 7
which is maximum. Hence, the answer is 7
.
Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).
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.N
denoting the number of nodes.(N - 1)
lines contains two space-separated integers denoting an edge between the given nodes.N
space-separated integers denoting the value of nodes.K
.
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:
Determine the value of function for queries of Type 2.
Note: Assume 1-based indexing.
Thus, the answer is 26.
For each test case, print the value of the function for queries of type 2 in space-separated format on a new line.
You are given N integers representing the locations of homes on a straight street (x-axis). The ithhome is located at Ai . 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−Ai)2 .
Determine the location of X which minimizes the value of function given in the question.
Thus, the answer is 6.
For each test case, print the value ofXwhich minimizes the value of the function given in the question.
You are given N integers representing the locations of homes on a straight street (x-axis). The ith home is located at Ai. 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 − Ai | .
Determine the location of X which minimizes the value of function given in the question.
Thus, the answer is 7.
For each test case, print the value ofXwhich minimizes the value of the function given in the question.
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:
Convert the difference array to the actual array:
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:
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:
dp
where dp[i]
stores the maximum length of the subsequence starting from index i.dp[i]
based on next_occurrence[i]
.Reconstruct the Subsequence:
next_occurrence
array to reconstruct the longest increasing subsequence of the desired length.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)
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))