Equal Beauty | EQBEAUTY | Snackdown 1A

Hello everyone!

I just wanted to know the solution to this problem which appeared in yesterday’s contest.

Problem link: CodeChef: Practical coding for everyone

No editorial has been added yet and I’m really eager to know how to solve it. I looked up on youtube and some solutions were posted during the contest itself. I was not interested in participating in yesterday’s contest but this question caught my interest.

Let’s take a solution for reference.

Solution link: CodeChef: Practical coding for everyone

I’m not able to understand the reasoning behind these two for-loops below. Please help me with it.

for (ll i = 0; i < n - 1; i++) 
{
res1 += abs(a[i] - a[(n - 1) / 2]);
}
for (ll i = 1; i < n; i++)
    res2 += abs(a[i] - a[1 + (n - 1) / 2]);
m = min(res1, res2);

Also if possible, please provide other ways to solve this problem too.

1 Like

I tried a totally different process,
I just checked some solutions, I have the same doubt.

Take these two examples
First:
1 2 3 15
In this question the answer is 2. Now the how part is if you look carefully if we take sub array 1 to n-1, we see it is taking less steps to make 1 to 2 and 3 to 2 rather taking any other subarray and increasing or decreasing.
Second:
1 15 16 17
Same goes here. Taking 1 to n subarray and making 15 to 16 and 17 to 16. It takes less steps.
So the conclusion is if in the array after sorting the first and last element are pretty huge then we handle that cases by running those two loops.
Hope I was clear.
Thanks.

6 Likes

These two loops are calculating the cost of making all elements equal of subarray (0,n-1) & (1,n).
The first observation for solving is to know that maximum and minimum element would always be present in different arrays for optimal partitioning.

3 Likes

“Taking 1 to n subarray and making 15 to 16 and 17 to 16”

This helped me realize my mistake. I forgot that increasing or decreasing any number can change the order of the array. Such a silly mistake :sweat_smile:.

Thank you!

lol , I also just realized now! how silly of me! thanks btw for this little explanation

1 Like

Thanks, brother :slightly_smiling_face:

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

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