 # 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 + arr[n-1]) where i < j and ( 1 <= i < j <= n-2)

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

basically problem reduces to find sum closest to a + 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

2 Likes

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

The Magical Case is
5
1 100 102 103 110

1 Like

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

11

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?

6
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!!

https://www.codechef.com/viewsolution/52989530

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 `3`s to `4`s 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`.