S11E00 - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Kanhaiya Mohan
Tester: Nishant Shah, Divyansh Tyagi, Syed Ali Aatif
Editorialist: Akshit Dhoundiyal

DIFFICULTY

Medium

PREREQUISITES

Binary search

EXPLANATION

Observation 1

Finding the optimal X

For a given sequence of N integers the minimum value of Σ|A(i) - X| is achieved when X is equal to the median of the elements of the array.

Why?

Suppose X is smaller than the median, then the sum becomes smaller by increasing X, and if X is larger than the median, the sum becomes smaller by decreasing X. If N is even and there are two medians, both medians give the optimal solution.

For example, if we have 5 elements 1 3 5 6 8.

X = 1 3 5 6 8

Σ( A_i-X) = 18 12 10 11 17

General Observation:

Suppose you have two sorted sequences of N elements A and B, such that B satisfies B(i) - B(i-1) >= A(i) - A(i-1).

We can say that the value Σ|B(i) - X(a)| >= Σ|A(i) - X(b)|. This is because the elements of B are relatively more scattered as compared to the elements of A. And thus the overall sum of deviation of elements from the median will be more in case of B.

Observation 2

Finding for the optimal positioning for the rectangle

Suppose we take two rectangles of the same dimensions starting from different positions:

Rectangle 1:

Elements : 5, 8, 9, 12, 13, 18

Median = 9

Ans=|5 - 9| + |8 - 9| + |9 - 9| + |12 - 9| + |13 - 9| + |18 - 9|

= 21

Rectangle 2:

Elements : 2, 4, 5, 7, 8, 12

Median = 5

Ans=|2 - 5| + |4 - 5| + |5 - 5| + |7 - 5| + |8 - 5| + |12 - 5|

= 16

We can clearly see that in the second rectangle, the answer is minimized.

This observation, in fact, can be generalized by saying that as we move the rectangle upwards, the answer that we need gets minimized. This can be proven easily by the fact that the differences between the elements in the upper rows are less than the differences between the elements in the lower rows. Thus choosing an upper row leads to the reduction in deviation of elements from the median and thus the overall answer. We can extend this observation for columns as well. The columns in the left have lesser differences between the elements, thus choosing a column from left leads to the reduction in deviation of elements from the median and thus the overall answer.

In conclusion, the most optimal way of choosing the rectangle will be to start from the top-most and the leftmost point of the given matrix. In other words, our rectangle will always start from the position where 1 is located.

Observation 3

Finding the optimal dimensions for the rectangle

Look at the elements that are present at the diagonals running top-right to bottom-left.

We can see that the elements present in the same diagonal have less deviation among themselves compared to the elements present in different diagonals, for instance 4 and 6 will be closer to each other than 4 and 7. So, we can say that it would be optimal for us to choose elements for our rectangle such that the number of elements sharing common diagonals is maximized. This can be re-framed as the number of diagonals in the rectangle should be minimum”.

Thus, the most optimal way to choose the dimensions for our rectangle would be to make them equal(resulting in a square) or nearly equal(|columns-rows| is minimum).

For example, if N = 24, it would be better for us to take dimensions as 4 * 6(or 6 * 4) than 2 * 12 (or 12 * 2) as |6 - 4|<|12 - 2|.

Observation 4:

Final dimensions of the rectangle

If N is a perfect square the dimensions of the rectangle will be √N * √N.

Otherwise, we first select the largest square possible for given$ N$ and extend that square either through columns or through rows.

If we extend the columns, the values in the next column we add, will be less than the elements of its row-counterpart. This selection will result in the minimum relative deviation from the median.

Elements of first rectangle: 2 4 5 7 8 12

Ans = |2 - 5| + |4 - 5| + |5 - 5| + |7 - 5| + |8 - 5| + |12 - 5|

= 16

Elements of first rectangle: 2 4 5 8 9 13

Ans = |2 - 5| + |4 - 5| + |5 - 5| + |8 - 5| + |9 - 5| + |13 - 5|

= 19

Conclusion:

  1. X will be equal to the median of the elements of the rectangle.

  2. Choose 1 as the starting point of the rectangle.

  3. Number of rows <= Number of columns.

  4. Number of rows is the greatest factor of n smaller than √N.

So, it would be optimal for us to always make the number of rows <= number of columns.

Implementation

  1. Finding the median
  • First, we find the minimum and maximum elements in the matrix. The minimum element can be easily found by comparing the first element of each row, and similarly, the maximum element can be found by comparing the last element of each row.

  • Then we use binary search on our range of numbers from minimum to maximum, we find the mid of the min and max and get a count of numbers less than our mid. And accordingly change the min or max.

  • For a number to be median, there should be (r * c) / 2 numbers smaller than that number. So for every number, we get the count of numbers less than that by using upper_bound() in each row of the matrix, if it is less than the required count, the median must be greater than the selected number, else the median must be less than or equal to the selected number.

  1. Calculating Σ|A_i - X|
  • For each row we can calculate the prefix sum.

  • Using binary search we can find the sum of elements which are less than equal to x. Let us assume that the upper bound of x in a given row with n elements is at position$ j$, then for that particular row, j elements are ≤ X and the rest are greater. Thus, the contribution to |Ai -X| from that particular row would be ( j* X - presum[j]) + ((presum[N] - presum[j]) - (N - j) * X).

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

const int MAXN = 4e5+5;
const int rows = 640;
vector<int> matrix[rows];
vector<int> rowsum[rows];   
int factor[MAXN];   //largest divisor less than root(n)

void factorsieve() 
{
    int n = MAXN;  
    for (int p=1; p*p<=n; p++) 
    { 
        for (int i=p*p; i<=n; i+=p) 
        {
            factor[i] = p;
        } 
    } 
} 

void fill()
{  
    for(int i = 0;i<rows;i++)
    {
        int cols = ceil(MAXN/(i+1));    //maximum columns required in each row
        matrix[i].push_back((i+1) * (i+2)/2);
        if(!rowsum[i].empty())
            rowsum[i].push_back(rowsum[i].back()+matrix[i].back());
        else
        {
            rowsum[i].push_back(matrix[i].back());
        }
        
        for(int j = 1;j<=cols;j++)
        {
            matrix[i].push_back(matrix[i][j-1] + (j) + (i));
            rowsum[i].push_back(rowsum[i].back()+matrix[i].back());
        }
    }
}

int findMedian(int r, int c)
{
    int min = 1e18;
    int max = -1e18;
    for (int i=0; i<r; i++)
    {
        // Finding the minimum element
        if (matrix[i][0] < min)
            min = matrix[i][0];

        // Finding the maximum element  
        if (matrix[i][c-1] > max)
            max = matrix[i][c-1];
    }
  
    int desired = (r * c + 1) / 2;
    while (min < max)
    {
        int mid = min + (max - min) / 2;
        int place = 0;
  
        // Find count of elements smaller than mid
        for (int i = 0; i < r; ++i)
            place += upper_bound(matrix[i].begin(), matrix[i].begin()+c, mid) - matrix[i].begin();
        if (place < desired)
            min = mid + 1;
        else
            max = mid;
    }
    return min;
}

pair<int,int> sum(int median, int r, int c)
{
    int lowsum = 0, highsum = 0;
    for(int j = 0;j<r;j++)
    {
        int posn = upper_bound(matrix[j].begin(),matrix[j].begin()+c,median)-matrix[j].begin()-1;
        if(posn>=0)
            lowsum += rowsum[j][posn];
        highsum += rowsum[j][c-1];
    }
    return {lowsum,highsum};
}

int n;

void solve()
{
    cin>>n;

    int ans;

    int i = factor[n];  //rows
    int j = n/i;    //columns
    //cout<<i<<' '<<j<<endl;
    int x = (n+1)/2;
    int median = findMedian(i,j);
    pair<int,int> total = sum(median,i,j);
    int firsthalf = total.first; //sum less than median
    int secondhalf = total.second - total.first;    //sum greater than median
    ans = (x*median - firsthalf + secondhalf - (n-x)*median);
    cout<<ans%mod;
    
}

int32_t main()
{

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    sync;
    
    factorsieve();
    fill();

    int t = 1;
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }

    return 0;
}
1 Like

Fast editorial