help needed in a DP question.

general
,
1

given two arrays, of which one is increasing (not necessary strictly) and other is decreasing(strictly actually it is the index of that element from back)and we have to answer q queries [x, y] in which we have to find the maximum value of the product of the value at same indices in array excluding the given range [x, y].

for some given query range [x, y] the array a2 is given by :

= n - i + 1 (if i > y)

= (n - i + 1) - (y - x + 1) (if i < x)

Example :

a1 : 1 2 2 3 4 (fixed increasing array)

a2 : 4 - 3 2 1 (for range [2, 2]) : answer is 6 (3* 2 or 2*3)

a2 : 2 - - - 1 (for range [2, 4]) : answer is 4 (4*1)

I thought of applying binary search but as the first array is not strictly increasing it fails!

2

Lets say,
A1= a0 a1… a(n-1)

So A2= n-0 n-1 n-2… 1

Or (n-i)

So lets not consider any query,

Let a3-denote product

So a3 is

a0*(n) a1*(n-1)… an-1*(1)

Now lets say when a query comes ,lets say n=6 ,query is [2,3] ,then when know that a3 will remain same for all indices greater than 3,for indices less than 3

a3 will be

a0*(6-2) a1*(5-2)

Ie value changes to ai*(n-i-x) where x is (r-l+1) of range

So ai*(n-i)->ai*(n-i-x)

Lets say ai * (n-i)=ki

So we get ki-ai * x

Ie we get

a3 -

k0-a0* 2 k1-a1* 2

So now the question is whats the max value of (ki-ai*x) for all i less than l.

We can do this using convex hull trick,-ai*x + ki is of form mx+c

So we now process queries offline,sort the queries by l in (l,r) ,add lines to convex hull accordingly,for each query

We know for (r+1,n-1) the max wouldnt change so we can get it in O(1)

For (0,l-1) find the max using convex hull

Ans for this is max of the two

3

Could u explain abt the second array?it seems unclear to me,and yeah do we have to find max(a1[i]*a2[i]) for i not in range[x,y]?

4

yes! second array is not given it is something which we have to construct(logically as you also can see constructing it will lead to TLE) using query information.

5

And how do we construct the second array?I couldn’t understand this “other is decreasing(strictly actually it is the index of that element from back)”,i mean in a bruteforce manner do we have to first construct the second array and then answer queries?If yes how can we construct it in brute force manner?And also u said its decreasing,however in ur eg a2 it doesnt seem so

6

first we have to construct the 2nd array according to each query(it is the index of that element if taken from back in the new range (i.e. after removing elements in the given range) and then answer query! It can be done easily by brute force but it can have a better solution.

And for the second example please ignore zeroes(as those elements are not considered in this query)

7

i’ve updated the question. please have a look

8

i am thinking of the same but forget offline queries. Thanks a lot! Btw does using offline queries help here? Because we need to remove the lines from the set and it may happen that after adding this line some line may get deleted from set. So, how to overcome that?

9

And i think Li Chao tree helps here but sadly I didn’t get any good resource for it. If you know that please help me in understanding that or if u have some good resources then please share!

10

We are not deleting any lines,we are only adding lines

For a query [l,r] we need all lines mi *x + ci for all i less than l,so so its better to process it in increasing order of l,so that we are sure that we have all lines less than l

And regarding resource , refer this.

https://e-maxx-eng.appspot.com/geometry/convex_hull_trick.html

11

thanks for the help.