Aafat_Wapas's blog

By Aafat_Wapas, history, 10 months ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Sword_Of_The_Morning (previous revision, new revision, compare).

»
10 months ago, # |
  Vote: I like it +19 Vote: I do not like it

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.

»
10 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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).

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain how you arrived at this approach.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Thanks :)

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hello , can you please provide the code based on whatever you understood? It would be helpful.

»
10 months ago, # |
  Vote: I like it +11 Vote: I do not like it

what does K do

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Sword_Of_The_Morning (previous revision, new revision, compare).

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

first find minimum and maximum element of the array and find the mid = (min + max)/2

decrease 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.

»
2 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

include<bits/stdc++.h>

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;

}