Aafat_Wapas's blog

By Aafat_Wapas, history, 23 months ago,

Given an array of integers H representing heights of towers and a positive integer B. It is allowed to either increase or decrease the height of every tower by B (only once).

How to calculate the minimum possible difference between the heights of the longest and the shortest tower after modifications.

Note: It is mandatory to either increase or decrease the height of every tower.

• +8

 » 23 months ago, # |   0 Auto comment: topic has been updated by Aafat_Wapas (previous revision, new revision, compare).
 » 23 months ago, # |   +19 Decrease all towers height by B. Then you need to increase some subset of them by 2*B. If you sort them it will be some prefix.
 » 23 months ago, # |   +16 Sort the heights and try every possible split into two halves [0, i-1] and [i, n-1], where you add B to the left half and subtract B from the right half. Then the difference for that split is max(a[n-1] - B, a[i-1] + B) - min(a[0] + B, a[i] - B).
•  » » 23 months ago, # ^ |   0 Can you please explain how you arrived at this approach.
•  » » » 23 months ago, # ^ |   +6 I'm not sure, mostly intuition. But maybe this can help:So we have to add B to some elements $a_{i_1}...a_{i_k}$ and subtract B from the rest $a_{j_1}...a_{j_l}$. Let's say these sets are sorted, so the minimum of the first is $a_{i_1} + B$. The minimum of the other set is $a_{j_1} - B$. The overall minimum will then be $min(a_{i_1} + B, a_{j_1} - B)$. But if $a_{j_1} < a_{i_k}$ (i.e. they are not a split into halves of the sorted array), then we could exchange $a_{i_k}$ and $a_{j_1}$ and achieve a larger minimum.Same can be argued for maximum.
•  » » » » 23 months ago, # ^ |   +8 Thanks :)
•  » » » » » 22 months ago, # ^ |   0 Hello , can you please provide the code based on whatever you understood? It would be helpful.
•  » » 7 months ago, # ^ |   0 With this,there is chance that we are making height of tower negative, which is not ideal
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 I think I have got a working solution which is logical as well and handles non-negative condition also. The concept is the same but only one change, we start checking for min and max elemnts only when arr[i] >= k. The reason for that is if arr[i] < k then, all elements before it are also less than k, so we can't decrease them, so we will have to increase them, also since arr[i] < k, we can't decrease arr[i] to arr[n-1] by k, because then arr[i] will be negative.In short we will have to increase all elements of the array, and that will not help us as the difference remains same.So we have to skip all elements less than k, and only when we reach an element >= k, we can perform the operation which is: 1. Increase all elements before, and decrease all elements after arr[i] (including it) by k. class Solution{ public: int getMinDiff(int arr[], int n, int k) { sort(arr, arr+n); int min_elem, max_elem; int ans = arr[n-1] - arr[0]; for (int i=1 ; i<=n-1; i++){ if (arr[i] >= k){ max_elem = max(arr[i-1] + k, arr[n-1] - k ); min_elem = min(arr[0] + k, arr[i] - k ); //cout << max_elem << " "<< min_elem<< endl; ans = min(ans, max_elem - min_elem); } else continue; } return ans; } }; 
•  » » » 6 months ago, # ^ |   0 class Solution { public: int smallestRangeII(vector& A, int K) { int N = A.size(); sort(A.begin(),A.end()); int ans = A[N-1] — A[0]; for (int i = 0; i < N - 1; ++i) { int a = A[i], b = A[i+1]; int high = max(A[N-1] - K, a + K); int low = min(A[0] + K, b - K); ans = min(ans, high - low); } return ans; }}; the correct and accepted code
•  » » » 5 months ago, # ^ |   0 Thanks for this. It really helped. Working perfectly fine. :)
•  » » » 6 weeks ago, # ^ |   0 what if the heights are negative??
 » 23 months ago, # |   +11 what does K do
 » 23 months ago, # |   0 Auto comment: topic has been updated by Aafat_Wapas (previous revision, new revision, compare).
 » 22 months ago, # |   +3 first find minimum and maximum element of the array and find the mid = (min + max)/2decrease all height more than mid by B and increase all height more than mid by B.sort the array.the diff between min and max of new array will be the answer. we also have to check for answer in the original array.
•  » » 22 months ago, # ^ |   0 How did you came up with the logic? and what to do if element is equal to mid?
•  » » » 21 month(s) ago, # ^ |   0
•  » » 12 months ago, # ^ |   0 That would fail for the testcase k = 6, n = 4, arr = [35, 43, 43, 23]. The average would be 36. If you decrease all elements less than 36 by 6 and decrease the other ones then you'll get [41, 37, 37, 29]. Answer would be 12 this way.Where as if you decrease the first element (35) by 6. Decrease second and third by 6 and increment the last element by 6, you would get [29, 37, 37, 29]. The answer would be 8 is the most optimal solution.
•  » » » 10 months ago, # ^ |   0 Not failing. It's average of min and max.. not an average of all elements.
•  » » 8 months ago, # ^ | ← Rev. 6 →   0 fails for testcase, I guess 7 2 [[38, 43]]
»
15 months ago, # |
Rev. 2   -8

define ll long long

using namespace std;

int main() {

ll k, n;
cin >> k >> n;

vector<ll> v(n);

for(ll i = 0; i<n; i++)
cin >> v[i];

sort(v.begin(), v.end());

ll minn = v[0], maxx = v[n-1];

ll direct = maxx - minn;

ll low = minn + k;
ll high = maxx - k;

if(low > high)
swap(low, high);

ll a, b;

for(ll i = 1; i<n-1; i++)
{

a = v[i] - k;
b = v[i] + k;

if(a >= low || b<=high )
continue;

if(high - a <= b - low)
low = a;

else
high = b;
}

cout << min(direct, high-low) << endl;

}

 » 8 months ago, # |   0 https://stackoverflow.com/a/63220955/10015362This link has explained it very well. Also the gfg practice question and gfg solution is not optimal and hence wrong. Example testcase: 5 57 6 2 1 10
 » 3 months ago, # | ← Rev. 6 →   +4 What is wrong in my approachevery state of dp will store a pairdp(i,0) will store that using arr[i]-k and what will be the (min,max) from index 0 to idp(i,1) will store that using arr[i]+k and what will be the (min,max) from index 0 to ians=min(dp(n-1)(0).second-dp(n-1)(0).first,dp(n-1)(1).second-dp(n-1)(1).first)Transition in statetemp1=min(dp[i-1][1].first,arr[i]-k) //dp[i-1][1].first will store the minimum vale till i-1 index considering arr[i]-k temp2=max(dp[i-1][1].second,arr[i]-k)temp3=min(dp[i-1][0].first,arr[i]-k)temp4=max(dp[i-1][0].second,arr[i]-k)if(abs(temp1-temp2)>abs(temp3-temp4)) dp[i][0]={temp3,temp4}else dp[i][0]={temp1,temp2}//same way we can find dp[i][1]