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.

oh i don’t know about that …I m asking here :slight_smile:

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 :slight_smile:

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

Let 's see… :slight_smile:

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 :slight_smile:

bro if you don’t mind please give the link
thanks in advance!

Don’t worry they hired for SES role . And now about your bruteforce solution . Definately it will fetch some of points like you will get at least more than half i think. As N constraints is 100000 so in worst case we need comparison is (10^5 + 10^5-1 + 10^5-2…+1) = (10^5 * (10^5+1))/2 which is nearly equal to 510^9 and our system gives time limit is 5 second so we can assume that we can iterate nearly 510^9 . So I think brute force will give definitely some points . It may fail on strictly bounded data on 10^5.
@ssrivastava990
@ssjgz

@galencolin Please correct me if i’m wrong

Well, naively, each of the 5 \cdot 10^9 “operations” cause four function calls, which is not exactly ideal in terms of speed

NO this will not call any function . We can just calculate in O(1) in each iteration by using abs