Equal Beauty | SnackDown 1A | easiest observation?

general
1

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 - CodeChef: Practical coding for everyone

2 Likes
2

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
5
1 100 102 103 110

1 Like
3

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

4

11

5

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

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

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

7

Should be 10?

1 Like
8

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

9

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

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

10

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.

3 Likes