Dividing array greedy

#1

in this problem by looking at the sample test cases ,
division for min difference and for max difference will be different ?

because what i can see from the sample test case

for min diff : A=[-3,10] and B=[0,12]
for max diff: A=[-3,0] and B=[10,12]

but in problem the statement is saying that after dividing the array we can rearrange the array A with in A and same for array B .

so my doubt:
for both min diff and max diff the elements of A and B should not be change , but
here
for min diff : A=[-3,10] and B=[0,12]
for max diff: A=[-3,0] and B=[10,12]

array A contain different element in min diff and max diff case and same for B .

please clear my doubt

#2

@sk3657860 you first have to distribute elements into A and B, then for maximum and minimum difference you can rearrange elements within A and B to optimize your answer.

it can be :slight_smile:
for min diff : A=[-3,10] and B=[0,12]
for max diff: A=[-3,10] and B=[12,0]
answer is still same, moreover constraint is also valid!

1 Like
#3

55

as it is given in the editorial ,
let suppose there are 6 elements in my array. and after sorting i got the elements as [ A1,A2,A3,A4,A5,A6]
now min dif: (A1-A0)+(A3-A2)+(A5-A4) so here we have the two parts of the array will be A: {A1,A3,A5}
B: {A0,A2,A4}

now for max diff: (A3-A0)+(A4-A1)+(A5-A2)
here A: {A3,A4,A5}
B: {A0,A1,A2}

so as per editorial we are getting different A and B for min diff and max diff case ,

but problem statement is saying that first divide the array into 2 equal parts then rearrange with in itself halves .

please explain it .
i am not satisfied with the problem statement and the given editorial.
mismatching the flow of both .

#4

this is incorrect
max diff: abs(A5-A0) + abs(A1-A4) + abs(A3-A2)
also
min diff: abs(A1-A0)+abs(A3-A2)+abs(A5-A4)
see that distribution is {A1,A3,A5} and {A0,A4,A2}.

1 Like
#5

sir after sorting here A1<A2<A3<A4<A5<A6 so
here min dif: (A1-A0)+(A3-A2)+(A5-A4) here no meaning of abs
same for max diff case .
i am feeling that there is some glitch with the problem statement

#6

there is no glitch with problem statement, it’s just that it is always possible to divide array such that given answer in editorial is always valid!

I’ve shown this already to you! don’t get confused by abs as putting it (even when not required) doesn’t makes difference

1 Like
#7

can you please show me by an example having 6 or 8 elements in the array ? it will be helpful

#8

take array as {1,2,3,4,5,6}
then max diff = abs(6-1) + abs(2-5) + abs(4-3) = 5 + 3 + 1 = 9
min diff = abs(6-5) + abs(4-3) + abs(2-1) = 1 + 1 + 1 = 3
so arrays are {1,3,5} and {2,4,6}

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.