# Maximise the value [Player Potential] (Hack with infy 2020 (ended ) )

Given 4 unsorted arrays A , B , C , D of size N , find the value of

MAX( abs( A[ i ] - A[ j ] ) + abs( B[ i ] - B[ j ] ) + abs( C[ i ] - C[ j ] ) + abs( D[ i ] - D[ j ] ) +abs( i - j) )


where 0 < = i < j < N

I think this is the modified version of this : https://www.geeksforgeeks.org/maximum-value-arri-arrj-j/

But unable to solve . Help @galencolin @aryan12 @nishant403 @hetp111 @ssjgz

1 Like

abs(a-b) can be
-a+b
a-b
a+b
-a-b
So for each value ai bi ci di and i there is 2 sign possible either + or -
so consider all combination of these signs
These are total 32 combination
U can easily generate combination by using bits like for 0 -> 00000 denotes + + + + + and
1-> 00001->+ + + + -
now for each combination calculate max and min value of this combination
Eg
For i 0 to n-1
Temp=Max(Ai-Bi+Ci-Di+i )-min(Ai-Bi+Ci-Di+i)
The max value of Temp over all combination is the answer.
Time complexity O(N*32)

4 Likes

https://codeforces.com/blog/entry/78175 Some one asked during contest is live.

Time limit is 5 second so can we apply bruteforce?

No . … . . .

Wont you need 8 bits ? 2 for each…?

i went for brute force since time limit is 5 seconds
i.e n*(n-1)/2
i.e 10^5*(10^5-1)/2
-> 5x10^4x10^5 => 5x10^9
if we consider 10^9 computations per second 5*10^9
i think it atleast give 50% of marks
but there must be better way
lets hope for the best

No brute force will not work in any of the case bro

I think it at least gives 50% of marks for sure

Let 's see…

bro will they hire system specialist role this year

will they hire system specialist role this year

They hire only PP (power pogrammer from Hack with infy) …only top 100 candidates onsite hackathon + interview

they don’t hire system specialist role like last year of (top 3000) people?
how do you know bro ?

On their website , , , , go and read over there