LTIME72 Author's notes of last 3 problems

Abdullah And Toll Discounts (The statement is different, but the idea remains the same):

Problem Statement:
Given a tree of N nodes and an integer K, each node has a value Ai written on it. You can perform the following operations any number of times:
-> Choose a node (Let's say it's value was X), change it to a non negative integer Y with cost abs|X-Y|
The total cost is the sum of costs of each operation.
What is the minimum total cost to modify the values in such a way that the sum of values of nodes from root to any node is not greater than K.
1<= N <=10^6
1<= Ai <=10^9
1<= K <= 10^15

Solution:
Since the task is to reduce the sum of values of nodes, we will never increase the value of a node. Let S(i) represent the sum of values of nodes from root to the ith node.
Consider a node i, for every node j in the subtree of i, S(j) will be dependent on Ai. The closer a node is to the root, the more number of nodes it would affect.
Let's do an initial dfs and for every node i find S(i) and also for every node i let's calculate MX(i) which is the max value of S(i) in it's sub tree.
Now we do another dfs from the root for every node, decide the value by which it should be reduced. Let PR(i) denote the sum of amount that we have reduced from root to the parent of ith node. for every node j in subtree of i, S(i) will effectively be S(i)-PR(i). So, the amount by which we should reduce the current node's (i) value will be min(Ai,max(0,MX(i)-K-PR(i))).
Time Complexity: O(N)

Pre-Requisite:
Observation, Dfs.



XOR Magic:

Problem Statement:
You are given an array of N integers, and Q queries.
Each query is of the form L R.
You are required to find (arr[L]^0) + (arr[L+1]^1) + … (arr[R]^(R-L))
More formally, you are required to find sum{i=L to R}arr[i]^(i-L)
Where ^ stands for bitwise xor operator.

1<= N,Q <= 5*10^5
1<= Ai <= 10^6

Solution:

Here is an important observation:-

For the sequence 0 1 2 3 4 5 6 7 8 9 10

Lets see the 0th bit, it is

0 1 0 1 0 1 0 -> (2^0 0’s and then 2^0 1’s and so on)

Lets see the 1st bit, it is

0 0 1 1 0 0 .. -> (2^1 0’s and then 2^1 1’s and so on)

So we can see that for ith bit,we have 2^i 0’s, followed by 2^i 1’s, followed by 2^i 0’s and so on..(it is periodic with period of 2^i+1)

So now our idea is to solve for each bit independently, and then sum it up.

Let dp[pos][j][0] denote the ans for range [pos:N], when we are xoring jth bit of [pos:N] with 0 0 0..{2^j 0’s} 1 1 1..{2^j 1’s} and so on…

Let dp[pos][j][1] denote the ans for range [pos:N], when we are xoring jth bit of [pos:N] with 1 1 1..{2^j 1’s} 0 0 0..{2^j 0’s} and so on…

(1-based indexing)

Lets say the array is:

3 2 4 6 7 1

Lets say j=1, pos=2

So for j=1(considering only 1st bit), the array will be:

1 1 0 1 1 0

So dp[pos=1][j=1][0] will contain 1^0 +0^0 + 1^1 + 1^1 + 0^0

And dp[pos=1][j=1][1] will contain 1^1 +0^1 + 1^0 + 1^0 + 0^1

Now transitions are:

Dp[pos][j][0] = (number of set bits in range [pos,pos+2**j - 1]) + dp[pos+2**j][j][1]

Dp[pos][j][1] = (number of unset bits in range [pos,pos+2**j - 1]) + dp[pos+2**j][j][1]

** -> power operator

So now we can process queries ,

Let’s say we are solving for jth bit, and query is [L:R],

Considering j=2, and [L,R] => [1,6]

Lets say arr -> contains 2nd bit of original array

Dp[1][2][0] will contain arr[1]^0 + arr[2]^0 +arr[3]^0 +arr[4]^0 +arr[5]^1 + arr[6]^1 +arr[7]^1 + arr[8]^1 + arr[9]^0

So, the ans is

Dp[1][2][0]-dp[9][2][0]-number of unset bits in range(7,8)

Generally, the answer for L to R for jth bit will be:

block=floor(R-L)/2**j

rightend = L+(block+1)(2*j)

if (block is even)
{
   ans=dp[L][j][0] - dp[rightend][j][1] - (number of set bits in (R+1,rightend-1))
}
else
{
  ans = dp[L][j][0] - dp[rightend][j][0] - (number of ubset bits in (R+1,rightend-1))
}

Time Complexity: O(N+Q)log(max(Ai))

Pre-Requisite:
DP, Observation (Bit-Patterns)


Intervals And Intersections:

Problem Statement:
Given an array(A) of size N,

And M intervals of the form [L,R],

Choose such a subset of intervals,such that all of them intersect, and which maximises value of Sum((j-st+1)*A[j]) st<=j<=end

Where [st,end] is their intersection range.



#Note Intersection range of K intervals [Li,Ri] (i=1 to K) is given by

[max{i=1 to K}Li, min{i=1 to K}Ri ]

If (max{i=1 to K}Li > min{i=1 to K}Ri) they don’t intersect



1<= N <= 1e5

1<= M <= 1e5

1<= Ai<=1e6



Solution:

First, we can deduce that we can get the desired answer by choosing at most 2 intervals.

Reason:-
Let's say we got an optimal answer using intervals [L1,R1], [L2,R2], [L3,R3]
So their intersection range is [max(L1,L2,L3),min(R1,R2,R3)]
So we can choose an interval which has maximum L value of the 3, and choose an interval which has minimum R value among the 3, and obtain the same intersection range.

Lets see how do we find Sum((j-L+1)*A[j]) L<=j<=R, given a range [L:R]

Lets say construct two prefix arrays,

prefix1[i]=sum{j=1 to i}arr[j]*j

prefix2[i]=sum{j=1 to i}arr[j]

So the answer for the range would be (prefix1[R]-prefix1[L-1])-(L-1)*(prefix2[R]-prefix2[L-1])

= prefix1[R] + (prefix2[L-1]*(L-1)-prefix1[L-1]) - (L-1)*prefix2[R] --------------------------- (1)

Now let’s say that if we fix the right end of our intersection range(lets say R), and have a list of all valid left ends,

Then we just need to find max(prefix1[R] + (prefix2[L-1]*(L-1)-prefix1[L-1]) - (L-1)*prefix2[R]) over all valid L

But prefix1[R] is constant(as we have fixed right end),

= prefix1[R] + max((prefix2[L-1]*(L-1)-prefix1[L-1]) - (L-1)*prefix2[R]) over all valid L

Lets say F(L) = (prefix2[L-1]*(L-1)-prefix1[L-1]) ------------------------------------------------(2)

=prefix1[R] + max(- (L-1)*prefix2[R] + F(L) ) over all valid L ----------------------------------(3)

So we can see that we can apply convex hull trick to find maximum value, we have lines of the form y=mx+c where m=-(L-1), and c=F(L)

We have a segment tree, with node [a:b] containing lines for all valid L,when processing an index i.

ALGORITHM:

query(a,b,val) returns max(F(L) - (L-1)*val) for all valid L(left ends whose right end >= current index i) in range (a,b)

Ans = -inf

For i = n to 1:

     For all intervals(x,y) with y=i:

          Add this line at index x(so will be added in atmost logn nodes in segment tree)

     For all intervals(x,y) with y=i:

          Ans = max(Ans,prefix1[i]+ query(x, y,prefix2[i])) //left end could range from x to y

print(Ans)

Complexity: O(Mlog^2(N) + N)



Pre-Requisite:

convex hull trick, offline processing, segment tree, observation.