In request of repeated queries regarding my approach to MARRAYS in my solution and editorial, i am explaining my approach to MARRAYS in this post. (I hope moderators don’t mind this)

So here it goes.

First think of only first subtask in which N = 2

So, the simplest solution to this approach would be the minimum of

- Abs(Max of 1st array - Min of 2nd array)
- Abs(Min of 1st array - Max of 2nd array)

This works because only the minimum of one array and maximum of other can give the maximum absolute value. You may see this solution for 20 points (just to check this fact )

Now, coming to the main problem, i have basically run a brute force algorithm, discarded useless entries before processing them at next step, in short.

Coming to details, i will be making continuous reference to solution, so I’ll recommend u open this solution in next tab for better understanding.

I am solving the problem from right to left, processing (n-1) th … 2nd 1st. Left to right order is also possible and makes no difference except minor implementation changes.

Firstly i use a LinkedHashMap array, ith map storing the best results for fixed first value of ith array.

That is

Consider following example test case

3

3 1 2 3

3 1 3 2

2 4 5

In this case map at index 1 (using 0-indexing) will have two key 1,2 and 3

In map{1} //map at index 1

Value mapped to value 1 = Max(abs(4-2), abs(5-2)) *1 = 3*1 = 3

// if 1 is first element, 2 is the last element

Value mapped to value 3 = Max(abs(4-1), abs(5-1)) * 1 = 4 * 1 = 4

// if 3 is first element, 1 would be last element

Value mapped to value 2 = Max(abs(4-3), abs(5-3)) = 2 * 1 = 2

// if 2 is first element, then 3 would be last element

In case map already has a mapping with same key, take maximum of two.

This was the basic working of map in my solution.

Now, when you solve any recursive problem, you often run something like solve(0 , 0) something like that, ryt??

Similarly, i took maximum and minimum of last array, mapped them to 0 in map{N-1}

These values start the recursive progress below.

// because best solution till now is 0

Now, the main loop // ar{i}{j} denote jth element in ith array given

For i = N-2 to 0 // loop 1 start

Int min = 1e7, max = 0 // ill use this later

For j = 0 to ar{i}.length // loop 2 start

Int current = ar{i}{j}, nextValue = ar{i}{j+1} //( ar{i}{0} if j == ar{i}.length-1 )

// observe, if cuurent value is last element in array, nextValue will be first element

min = min(min, nextValue) // min value fixed at first position

max = max(max, nextValue) // max value fixed at first position

Int temp = map{i}.get(nextValue) // if map already has some result stored, else 0.

For entry e:map{i+1} // loop 3 // looping through (i+1)th results

Int key = e.key; // key means first element in (i+1)th array

Long previousResult = e.value //best answer for key

temp = max(temp, abs(current-key)*(i+1) + previousResult) // according to formula given in problem

//end loop 3

map{i}.put(nextValue, temp) // best answer fixing nextValue at first position in ith array.

// end loop 2

Now comes the discarding part. The solution is completely a brute force solutuon without this

Array removal = new int{1e6+1}

Int removed = 0

Long maxResult = map{i}.get(max), minResult = map{i}.get(min) // best results fixing minimum and maximum value of ith array at first position.

For entry e : map{i} // loop 4

If( e.key != min &; e.key != max && e.value <= minResult && e.value <= maxResult) removal{removed++} = e.key //explained below

// end loop 4

// following loop just removes the useless entries which for sure do not give us best results, we just selected them in above loop

For int j = 0 to removed // loop 5

map{i}.remove(removal{j});

// end loop 5

// end loop 1

Now the answer of this problem is the maximum value mapped to any key in map{0}

The observation to remove values is that if any value other than min and max has a result smaller than both max and min, then the entries will never give optimal solution.

Consider three mapping in ith map as below

3 => 5

4 => 4

5 => 6

In i+1 th map

Entry 5 will always give better result than entry 4 for any value x < 4

And

Entry 3 will always give better result than entry 4 for any value x > 4

So, we can safely discard entry 4 without further ado, getting 100 points. Hurray!!!

Feel free to ask anything…

**Bonus challenge**

Design a worst test case for this solution.

**Hints for a worst test case**

try maximizing following sum

Let a,b,c … n be the size of inner arrays

Sum = a*b+ b*c + c*d … m*n

And select elements in array in such a manner that entries deleted are minimum

Enjoy coding…