MONOCMN - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Sorting, binary search

PROBLEM:

There are N points on the x-axis and M on the y-axis.
Each point must be colored either red or blue; with the additional constraint that each axis must contain at least one point of both colors.

Minimize the maximum area of a triangle whose vertices all have the same color.

In this version, N, M \le 2\cdot 10^5.

EXPLANATION:

From the solution to the easy version, we know that in an optimal configuration, the points with a single color on any given axis will be contiguous.

Let’s focus on just one configuration: red points form a prefix on both axes, and blue points form a suffix on both axes.

For now, suppose we fix just i, meaning that points x_1, \ldots, x_i are red and the others are blue on the x-axis.
In the easy version, we iterated through all options for j, but that’s of course not possible here.

Instead, we can binary search on the optimal area, given that i is fixed.
More specifically, we’ll binary search on the value A, and check if there exists some choice of j such that the pair (i, j) gives a maximum area that’s \le A.

With A fixed, let’s try to figure out whether an appropriate j exists or not.

Since we want the maximum of the red and blue monochromatic areas to be \le A, we want both of them to be \le A as well.
Observe that:

  • As j increases, the “red area” also increases with it.
    So, there’s some maximum possible j, say j_R, such that going beyond j_R would make the red area \gt A.
  • As j increases, the “blue area” instead decreases with it.
    Since it starts off large and becomes smaller.
    Thus, there’s some minimum possible j, say j_L, such that we need to reach at least j_L for the blue area to be \le A.

Suppose we’re able to find these indices j_L and j_R somehow.
Then, observe that:

  1. If j_L \gt j_R, no valid j can exist, so it’s impossible to obtain an area that’s \le A with this choice of i.
  2. If j_L \le j_R, then a valid j does exist: anything in [j_L, j_R] will work.

Finding j_R is fairly simple: you can for example again use binary search, with the check being if the corresponding red area is \le A.
Alternately, two pointers can be used, noting that the value of j_R decreases as i increases.

To make the implementation even simpler and eliminate some casework, observe that there’s no need to even compute j_L.
This is because, as we noted above, in the situation where some j is valid, certainly j = j_R will work.
Thus, we can simply compute j_R alone, and then perform the area computation with (i, j_R) and see if it’s \le A or not.

This way, we’re able to compute the optimal area of the configuration where both axes have a red prefix quickly: either in \mathcal{O}(N\log{(\text{ans})}) or \mathcal{O}(N\log N\log{(\text{ans})}) time, depending on whether binary search or two pointers were chosen for computing j_R.

The other configuration, of red prefix on the x-axis and blue prefix on the y-axis, can be similarly handled with the same complexity.
We can then take the best of all options.

TIME COMPLEXITY:

\mathcal{O}((N+M)\log{10^{18}}) or \mathcal{O}((N+M)\log{10^{18}}\log N) per testcase.

CODE:

Tester's code (C++) 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case){
    ll n,m; cin >> n >> m;
    vector<ll> a(n+5), b(m+5);
    rep1(i,n) cin >> a[i];
    rep1(i,m) cin >> b[i];

    sort(a.begin()+1,a.begin()+n+1);
    sort(b.begin()+1,b.begin()+m+1);

    auto ok = [&](ll mid){
        // is there a coloring with 2*area <= mid?

        // suffix of Y is red, prefix of Y is blue

        // 1) last point of X and Y have same color
        // ensure: 
        // a) y1*(x2-x1) <= mid --> know max coverable suff range in X
        // b) x1*(y2-y1) <= mid --> know max coverable suff range in Y
        // cover both suffixes to this max range, check if remaining blue prefix is valid (need to check same conditions only)
        ll X1 = a[n], Y1 = b[m];
        
        // find max coverable suff range in X
        ll mx_suff_x = n+1;
        rev(i,n,2){
            if(Y1*(X1-a[i]) <= mid){
                mx_suff_x = i;
            }
            else{
                break;
            }
        }

        // find max coverable suff range in Y
        ll mx_suff_y = m+1;
        rev(i,m,2){
            if(X1*(Y1-b[i]) <= mid){
                mx_suff_y = i;
            }
            else{
                break;
            }
        }
        
        if(mx_suff_x <= n and mx_suff_y <= m){
            // check if blue prefixes are good
            ll X2 = a[mx_suff_x-1], Y2 = b[mx_suff_y-1];
            ll fx = a[1], fy = b[1];
            if(X2*(Y2-fy) <= mid and Y2*(X2-fx) <= mid){
                return true;
            }
        }
    
        // 2) last point of X and Y have diff color
        // fix the red suff on Y, then find max colorable red pref on X (as len of red suff inc, the len of red pref in X dec, so move ptr from back)
        ll ptr = n-1;
        rev(i,m,2){
            while(ptr >= 1){
                bool ok = true;
                if(Y1*(a[ptr]-a[1]) > mid) ok = false;
                if(a[ptr]*(Y1-b[i]) > mid) ok = false;
                if(!ok){
                    ptr--;
                }
                else{
                    break;
                }
            }

            if(!ptr) break;

            // blue pref on Y: [1..i-1]
            // blue suff on X: [ptr+1..n]
            if(b[i-1]*(a[n]-a[ptr+1]) <= mid and a[n]*(b[i-1]-b[1]) <= mid){
                return true;
            }
        }

        return false;
    };

    ll lo = 1, hi = inf2;
    ll ans = -1;

    while(lo <= hi){
        ll mid = (lo+hi)>>1;
        if(ok(mid)){
            ans = mid;
            hi = mid-1;
        }
        else{
            lo = mid+1;
        }
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}
1 Like