A Simplified approach to MARRAYS

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

  1. Abs(Max of 1st array - Min of 2nd array)
  2. 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 :smiley: )

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 = 31 = 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… :slight_smile:

Bonus challenge

Design a worst test case for this solution. :slight_smile:

Hints for a worst test case

try maximizing following sum

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

Sum = ab+ bc + cd … mn

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

Enjoy coding…

2 Likes

Wow, I Thought of a similar approach but thought it would not pass the time complexity constraint :frowning: . Can u explain the time complexity of this solution and tell me how it passes.

I am sharing my code hoping that it might help some how to understand what state to use while implementing the dp. I also used a similar approach. My code is slow and it got ACed because of the weak test cases, but it might help someone in understanding the objective function.

In my code, dp[i][j] - is storing the a value till ith block if the ith block is rotated jth time. (last/first)(i,j) - is giving value of the last/first value of the ith block if rotated j times.

i was getting TLE in one test case and believe it was when N=2, m1=m2 = N/2. complexity would be O(T*N^2). So i considered that test case separately.

MY CODE

Tour Inputs are welcome.

For Optimization you can read THIS. Just try to learn what the inner two loops are doing.

Lesson Learnt: Give respect to modulus functions

1 Like

Well, at first sight i thought too that this wouldn’t pass, and definitely without removal part, thia solution will time out.

Talking about time complexity, if we talk about worst case, it’s O(N^2), but im not able to find any test case for this solution. The removal greatly reduces the actual time taken, how much, i don’t know exactly.

It’s a matter of amortized time complexity analysis. Because entry deleted in O(1) time will save O(N) iterations in next iteration of loop 1.

Yes,Now I understood :). Thanks!