Equal Beauty | SnackDown 1A | easiest observation?

According to the problem

if I just sort the array then if I just consider cases of A having a single element or B having a single element separately, then all that remains is to find

(arr[i] + arr[j]) having closest to (arr[0] + arr[n-1]) where i < j and ( 1 <= i < j <= n-2)

because we will get minimum when like a[j] - a[0] = a[n-1] - a[i] , or a[i] + a[j] = a[n-1] + a[0].

basically problem reduces to find sum closest to a[0] + a[n-1] ,

I am now confused myself, I tried a similar concept 5 times in a row, and got WA,

can anyone tell me the exact observation that I should have done!

it was my solution - Solution: 52868369 | CodeChef


According to your case
A should have 1 elements
B should have rest elements
And this is the case which fails many solution too.
The solution should be
=>Sort the array
=>Give the A the last element, and Give rest to B. Make rest elements equal to a[middle element from 1…n-1]. Operation needed will be-X= sum(|a[i]-a[middle]}) where 1<=i<=n-1

=>Give the A the first element, and Give rest to B. Make rest elements equal to a[middle element from 2…n].Operation needed will be-Y= sum(|a[i]-a[middle]}) where 2<=i<=n

Your answer should be Min(X,Y)

The Magical Case is
1 100 102 103 110

1 Like

What is the answer to the testcase you gave? Can you add some explanation?


I am getting. I can’t figure out the testcase where I am going wrong!
This is my submission. Can you look into it once?

for this input answer should be zero but your code is giving answer answer 1.
1 2 3 4 7 9

Here is how answer can be zero.
Group 1-[1 2 4 7]
Group2- [3 9]

Should be 10?

1 Like

Thanks, I had a gut feeling that sorting the whole thing might cause something bad. My fears turned out to be true. Waiting for the editorial now!!


Why is my code giving WA?
It answers everything correctly, as far as I think.

I was trying similar at first.
This approach inheritedly assumes that [minA,maxA] and [minB,maxB] ranges overlap (and that’s true for most cases if they both don’t overlap we can just swap maxA,minB to make [minA,minB],[maxA,maxB] and they will overlap.)
This fails when there are just 2 distinct elements and the difference in both sets is zero.
A counter test case -
3 3 4 4 4 4 10
Finding closed to 3+10 is 4+4 and will give the answer 5 but you can always change 3s to 4s using total 2 operations.

Apart from doing this run a for loop and find minimum operations required to make 1...i same and i+1....n same where 1<=i<=n-1.
Adding this gave me AC.