Minimum Number of moves for n piles of stones

help
1

Problem Statement
There are n piles of stones. Each pile of stone has a height Ai. Mickey and Minnie are
bored, so they decide to play a game. The game is as follows -
Minnie will give Mickey an integer k. Now Mickey has to make the difference between
the height of the highest pile and the lowest equal to k.
In a move, Mickey can either increase the height of any pile by one or decrease by one.
Find the minimum number of moves Mickey will need.
Note: Answers can be large use long long.
Input Format
The first line of input consists of a single integer t , the number of test cases.
The first line of each test case contains two integers n and k number of piles and value of k respectively.
The second line of each test case contains n space separated integers, the height of the ith pile.
It is guaranteed that the sum of n over all test cases does not exceed 2*10^5.
Output Format
For each test case, print the minimum number of moves required to do the task.

Sample Testcase #0
Testcase Input
1
5 2
1 2 3 4 5
Testcase Output
2
Explanation
In the first sample, we can increase A1 by 1 and decrease A5 by 1. The final
configuration will become [2,2,3,4,4]. The answer will be 2.
Sample Testcase #1
Testcase Input
3
5 10
5 5 5 5 5
10 0
1 2 3 4 5 6 7 8 9 10
72
1 1 1 4 7 7 7
Testcase Output
0
25
12

2

Brute force:
Sort the whole array-(use functions)
now increase a[0] by 1 and decrease a[n-1] by one using while loop with condition (a[n-1]-a[0]!=k) and between them put conditions to break just in case a[n-1]-a[0]==k;
keep check on count after each +1 and -1 using count++;

Print count at the end.

Now code it since the approach is already in front of you :smile:

1 Like
3

I’ll suppose you have no idea how to even tackle this problem.

Let the piles be sorted in the increasing order. Let’s say that in the final arrangement heights of piles are greater or equal to L and lower or equal to R. Formally, for every pile P[i], 1 \leq i \leq N, P[i] \subseteq [L, R] . Notice that either L or R belongs to the original array.

Let’s prove the statement by contradiction. Suppose that height of every pile belongs to the range [L, R] such that it’s optimal and neither R nor L was part of the starting sequence. Let number of piles whose height we’ve decreased to R be r and number of those whose height we’ve increased to L be l. If l < r, we could have bound the heights by L + 1 and R + 1 and the answer wouldn’t increase (it could only decrease). Similar is true for other case when l > r.

Now that we’ve got this on our minds, it’s easy to notice that you can compute number of elements less than X and those greater than X in O(N) time after sorting the original array. All that is left is for each A[i] in the original array calculate the number of elements to be increased to A[i] and those to be decreased to A[i] + K. Similarly do the same with every A[i] being the right bound, instead of left.

I hope this helps. I could provide the code, but that’s left as an exercise for you. :slight_smile:

2 Likes
4

This looks so professionally written T_T.

Mine was my first ever reply on the forums

1 Like
5

I don’t think your approach is going to work on the given constraints. Yes, you can greedily brute force, but not on the array, rather on a multiset. This is because you can’t remove elements and insert them at needed positions dynamically efficiently. You need to keep track of the number of occurrences of the greatest and lowest number in the multiset and thus make a decision whether to decrease one occurrence of the greatest or the smallest element. A simple approach that works, but needs a bit refining. :slight_smile:

BTW good job considering it’s your first post here, there aren’t many people around, so any type of help is appreciated. BTW, I’d recommend learning TeX to insert math equations, it’s going to help the readability of your code and your ability to convey ideas.

In case somebody gets confused about this solution, here’s how it looks:

int ans = 0;

multiset<int> ms;

for (int i = 0; i < n; i++) {
    ms.insert(ar[i]);
}

while (*(ms.rbegin()) - *(ms.begin()) > k) {
    if (ms.count(*(ms.rbegin())) < ms.count(*(ms.begin()))) {
        int tmp = *(ms.rbegin());
        ms.erase(ms.find(tmp));
        ms.insert(tmp - 1);
    } else {
        int tmp = *(ms.begin());
        ms.erase(ms.find(tmp));
        ms.insert(tmp + 1);
    }
    ans++;
}

This will however fail as the complexity can be up to O(N^2 \cdot \log N), because in the worst case you have to perform \frac{N}{2} increments on \frac{N}{2} elements and the same goes for decrementing. So for optimal solution you will need a map to keep the count of values and a set to keep the values.

1 Like
6

Okie,
I’ve started off recently so that was my basic intuition :stuck_out_tongue:

7

I’m very glad for your input. Thank you so much for your time. I try my best to solve the exercise. If I couldn’t I’ll ping you back. Again thanks a lot. :blush:

1 Like
8

Same here, this is my first question to post in forums. I’m really thankful who are trying to help me. :blush:

9

No problem, glad I could help. Feel free to ask about anything you didn’t get here. Try both approaches out, as these provide a lot for a beginner to learn (the first approach is much more advanced, and requires experience to come up with the crucial observation, but it’s provable so I went for it :laughing:).

1 Like