SIMARRAY - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Sundar
Tester: Riley Borgard
Editorialist: Aman Dwivedi

DIFFICULTY

Medium

PREREQUISITES

Maths, Observation

PROBLEM:

You are given two arrays of positive integers, A and B, both of length N. You must choose a sequence of N non-increasing real numbers R_1, R_2, \ldots R_N to multiply with B_1, B_2, \ldots B_N respectively, such that the sum of the squares of their differences with corresponding terms A_1, A_2, \ldots A_N is minimized.

Formally, find the minimum possible value of \displaystyle \sum_{i=1}^{N} (A_i - R_i B_i)^2, over all possible N-tuples of real numbers R = (R_1, R_2, \ldots R_N) satisfying R_1 \ge R_2 \ge \cdots \ge R_N.

EXPLANATION:

N=2

Since our goal is to minimize the possible value by taking R_1 and R_2 such that R_1 \ge R_2. Let us just take the first expression i.e (A_1 - R_1 * B_1)^2 if we want to minimize this expression then what is the optimal choice for R_1 ?

R_1 = A_1/B_1 is the optimal choice since keeping this value makes the value of expression 0 which is the minimum possible value we can achieve. Similarly, we can put the value of R_2 as R_2 = A_2/B_2 if R_2 \le R_1 and hence we achieve the final minimum value as 0.

But what happens when R_1 comes out to be less than R_2 then they would have the same values of r i.e. R_1 = R_2 = r, you can prove this bu contradiction that they need to have same values.

Hence now the expression will become:

(A_1-B_1*R_1)^2 + (A_2-B_2*R_2)^2

Since the expression is quadratic we can easily find the minimum value for the expression.

N>2

We can make a vector of length N of pairs a,b and iterate on this vector N times each time checking that whether b/a is in descending order or not. If we find two adjacent elements out of order we can merge them by adding their a's and b's.

If two adjacent elements in the vector have their points of minima in the wrong order we can prove that by contradiction that they will have the same r values in their final answer because we can move one closer to another to decrease the final answer.

After this merging is allowed as they have the same r values. Hence the array will be divided into consecutive blocks of equal value of r. The contribution for each block having same value of r is quadratic in r. Then the value of r for the block must be the one that gives the lowest possible value for this quadratic, else we can shift to the left or right to improve the objective, while maintaining the non-increasing property.

TIME COMPLEXITY:

O(N*log(N))

SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
 
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#endif
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			if(!(l<=x && x<=r))cerr<<l<<"<="<<x<<"<="<<r<<endl;
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd, char minc = 'a', char maxc = 'z'){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		assert(g >= minc && g <= maxc);
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r, char minc = 'a', char maxc = 'z'){
	return readString(l,r,'\n', minc, maxc);
}
string readStringSp(int l,int r, char minc = 'a', char maxc = 'z'){
	return readString(l,r,' ', minc, maxc);
}
template<class T>
vector<T> readVector(int n, long long l, long long r){
    vector<T> ret(n);
    for(int i = 0; i < n; i++){
        ret[i] = i == n - 1 ? readIntLn(l, r) : readIntSp(l, r);
    }
    return ret;
}
 
struct Rational
{
    ll num, den;
    int cnt;
    Rational(ll n, ll d, int cnt) : num(n), den(d), cnt(cnt){}
    bool operator<(const Rational &r) const{
        return num * __int128_t(r.den) < den * __int128_t(r.num);
    };
    Rational operator + (const Rational & r) const{
        return Rational(num + r.num, den + r.den, cnt + r.cnt);
    }
};
 
const int MAXN = 500000;
int main(){
    int t = readIntLn(1, MAXN);
    int sn = 0;
    while(t--){
        int n = readIntLn(2, MAXN); 
        sn += n;
        assert(sn <= MAXN);
        vector<ll> a = readVector<ll>(n, 1, 1000), b = readVector<ll>(n, 1, 1000);
        double ans = 0;
 
        for(ll & x : a){
            ans += x * x;
        }
 
        vector<Rational> stk;
 
        for(int i = 0; i < n; i++){
            a[i] *= b[i];
            b[i] *= b[i];
            // b * x^2 - 2 * a * x
            stk.push_back(Rational(a[i], b[i], 1));
            while(stk.size() >= 2){
                Rational x = stk.back(); stk.pop_back();
                Rational y = stk.back(); stk.pop_back();
                if(y < x){
                    stk.push_back(x + y);
                } else{
                    stk.push_back(y);
                    stk.push_back(x);
                    break;
                }
            }
        }
        int j = 0;
        for(int i = 0; i < stk.size(); i++){
            double x = stk[i].num / (double) stk[i].den;
            for(int k = 0; k < stk[i].cnt; k++, j++){
                ans += x * (b[j] * x - 2 * a[j]);
            }
        }
        trace(stk.size());
        cout << setprecision(20) << fixed << ans << endl;
    }
}
Tester
#include <bits/stdc++.h>
 
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
 
using ftype = long double;
 
struct node {
    ftype ab, bb;
    int n;
    node(ftype a, ftype b) {
        n = 1;
        ab = a * b;
        bb = b * b;
    }
    node(ftype ab, ftype bb, int n) : ab(ab), bb(bb), n(n) {}
    node operator+(const node &o) const {
        return node(ab + o.ab, bb + o.bb, n + o.n);
    }
    ftype getx() const {
        return ab / bb;
    }
};
 
void solve() {
    int n;
    cin >> n;
    vector<ftype> a(n), b(n);
    rep(i, 0, n) cin >> a[i];
    rep(i, 0, n) cin >> b[i];
    vector<node> st;
    rep(i, 0, n) {
        node x(a[i], b[i]);
        while(!st.empty() && st.back().getx() < x.getx()) {
            x = x + st.back();
            st.pop_back();
        }
        st.push_back(x);
    }
    vector<ftype> r;
    for(node &x : st) {
        ftype val = x.getx();
        rep(i, 0, x.n) r.push_back(val);
    }
    ftype ans = 0;
    rep(i, 0, n) ans += (a[i] - r[i] * b[i]) * (a[i] - r[i] * b[i]);
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    int te;
    cin >> te;
    while(te--) solve();
}