Official

F - Minimize Bounding Square Editorial by en_translator

We give you some hints for this problem. Click each item to reveal it.

Hint 1 In this problem, $x$ and $y$ coordinates can be considered independently.
Hint 2 There is a greedy solution.
Editorial Let $X'$ be the sequence of the $x$ coordinates of the given points, and $Y'$ be that of $y$.
When no more move can be made, the minimum side of a drawable square is $\max(\max(X')-\min(X'), \max(Y')-\min(Y'))$.
We divide into two cases depending on the ordering between the two terms $\chi=\max(X')-\min(X')$ and $\gamma=\max(Y')-\min(Y')$ in $\max$.
  • If $\chi < \gamma$
    • Modifying an $x$ coordinate does not change the value to minimize, so we leave it for now. For the $y$ coordinates, we should shift (in the proper direction) either those with $\max(Y')$ or those with $\min(Y')$, whichever fewer, to reduce $\gamma$ by one; otherwise, there is no room of improvement.
  • Same applies if $\chi > \gamma$.
  • If $\chi = \gamma$
    • In this case, we can either regard $\chi < \gamma$ to reduce $\gamma$ by one first, or reduce both $\chi$ and $\gamma$ by one.
An important caveat is that the constraints $10^9$ of the coordinates do not allow you to naively update them one by one within the execution time limit.
Instead, notice that the values $\min(X'), \max(X'), \min(Y'), \max(Y')$ are updated at most $2N$ times, and perform operations in bulk until they change.
Brief Proof First, it is obviously no use making $\min(X')$ smaller or $\max(X')$ larger; we always try to bring them closer.
The more you move $\min(X')$ or $\max(X')$, the more points you need to do so. In other words, the cost to shift them by $1$ increases (weakly) monotonically.
By this property, for a fixed $\chi$, one can modify a sequence of operations not conforming to the greedy algorithm above to one that does, without increasing the number of times to move points.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;
using pl=pair<long long,long long>;

int main(){
  long long n,k;
  cin >> n >> k;

  vector<long long> x(n),y(n);
  map<long long,long long> mx,my;
  for(long long i=0;i<n;i++){
    cin >> x[i] >> y[i];
    mx[x[i]]++;
    my[y[i]]++;
  }

  vector<pl> xv,yv;
  for(auto &nx : mx){
    xv.push_back(nx);
  }
  for(auto &nx : my){
    yv.push_back(nx);
  }

  long long xl=0,xr=xv.size()-1;
  long long yl=0,yr=yv.size()-1;

  while(k>0){
    long long gx=xv[xr].first-xv[xl].first;
    long long gy=yv[yr].first-yv[yl].first;

    long long fx,fy;
    long long hx,hy;
    long long cx,cy;
    if(gx!=0){
      if(xv[xl].second<xv[xr].second){
        hx=xv[xl+1].first-xv[xl].first;
        cx=xv[xl].second;
        fx=-1;
      }
      else{
        hx=xv[xr].first-xv[xr-1].first;
        cx=xv[xr].second;
        fx=1;
      }
    }
    if(gy!=0){
      if(yv[yl].second<yv[yr].second){
        hy=yv[yl+1].first-yv[yl].first;
        cy=yv[yl].second;
        fy=-1;
      }
      else{
        hy=yv[yr].first-yv[yr-1].first;
        cy=yv[yr].second;
        fy=1;
      }
    }

    if(gx==0 && gy==0){break;}
    else if(gx<gy){
      // shorten y
      long long opt=min({k/cy,hy,gy-gx});
      if(opt==0){break;}
      k-=cy*opt;
      if(fy==-1){yv[yl].first+=opt;}
      else{yv[yr].first-=opt;}
    }
    else if(gx>gy){
      // shorten x
      long long opt=min({k/cx,hx,gx-gy});
      if(opt==0){break;}
      k-=cx*opt;
      if(fx==-1){xv[xl].first+=opt;}
      else{xv[xr].first-=opt;}
    }
    else{
      // once x==y, let's keep it
      // shorten x&y
      long long opt=min({k/(cx+cy),hx,hy});
      if(opt==0){break;}
      k-=(cx+cy)*opt;

      if(fy==-1){yv[yl].first+=opt;}
      else{yv[yr].first-=opt;}
      
      if(fx==-1){xv[xl].first+=opt;}
      else{xv[xr].first-=opt;}
    }

    if(xl!=xr){
      if(xv[xl].first==xv[xl+1].first){
        xv[xl+1].second+=xv[xl].second;
        xl++;
      }
      else if(xv[xr].first==xv[xr-1].first){
        xv[xr-1].second+=xv[xr].second;
        xr--;
      }
    }
    if(yl!=yr){
      if(yv[yl].first==yv[yl+1].first){
        yv[yl+1].second+=yv[yl].second;
        yl++;
      }
      else if(yv[yr].first==yv[yr-1].first){
        yv[yr-1].second+=yv[yr].second;
        yr--;
      }
    }
  }

  {
    long long gx=xv[xr].first-xv[xl].first;
    long long gy=yv[yr].first-yv[yl].first;
    cout << max(gx,gy) << "\n";
  }
  return 0;
}

posted:
last update: