COFO::1637D Yet Another Minimization Problem

• Link : COFO::1637D

Problem

• level : 1800
• tag : dp, greedy, math
• TIME
  • to understand :
  • to algorithm : fail
  • to code :
  • to debug :
  • understanding edit and solve with edit: 240
  • Tried to solve the problem before read edit : 120

Point

• Array a and b are given,
• Find the minimum sum of (a[i] + a[j]) ^2 + (a[i] + a[j]) ^ 2 for all i < j
• You can use as many operations, which is
  • Swap a[i] and b[i]

Design

• It took so long to understand how to solve it perfectly.
• This problem has a lot to learn!
• First of all,
  • Let’s say
    • cost = (a[i] + a[j]) ^ 2 + (b[i] + b[j]) ^ 2
    • = a[i]^2 + a[j]^2 + b[i]^2 + b[j]^2 + 2a[i]a[j] + 2b[i]b[j]
• a[i]^2 + a[j]^2 => (n-1) * a[i]^2 for all i
• b[i]^2 + b[j]^2 => (n-1) * b[i]^2 for all i
• Then the cost will be
  • cost = (n-1) * (a[i]^2 + b[i]^2) + 2a[i]a[j] + 2b[i]b[j]
• Let’s say
  • sq_sum = sum(a[i]^2) + sum(b[i]^2)
• Then the cost will be
  • cost = (n-1) * sq_sum + 2a[i]a[j] + 2b[i]b[j]
• Since sq_sum is constant, we need to focust on ohter values
• For ‘sum (2a[i]a[j]) for all i < j’, it can be substituted by sum (a[i]a[j]) for all i (i != j)
• Then, a(1)(a[2] + a[3] + … + a[n]) + a(2)(a[1] + a[3] + … + a[n]) + … + a(n)(a[1] + a[2] + a[3] + … + a[n-1])
  • Let’s say s1 = sum of all a[i] for all i
  • Let’s say s2 = sum of all b[i] for all i
• a(1)(s1 - a[1]) + a(2)(s1 - a[2]) + … + a(n)(s1 - a[n])
• s1(a[1] + a[2] + … + a[n]) - (a[1]^2 + a[2]^2 + … + a[n]^2)
• s1^2 - (a[1]^2 + a[2]^2 + … + a[n]^2)
• It can be applied on b as well
• s2^2 - (b[1]^2 + b[2]^2 + … + b[n]^2)
• Now let’s sum them
  • s1^2 + s2^2 - (a[1]^2 + a[2]^2 + … + a[n]^2 + b[1]^2 + b[2]^2 + … + b[n]^2)
  • s1^2 + s2^2 - sq_sum
• Now, cost is
  • cost = (n-1) * sq_sum + (s1^2 + s2^2 - sq_sum)
  • = (n-2) * sq_sum + (s1^2 + s2^2)
• Since sq_sum is constant, we need to minimiza (s1^2 + s2^2)
• Let’s focus on one of the arrays
• The sum of one array can be up to 10000 as maximum, so we can figure out if we can get this sum or not with the array
• Since n is 100, and the sum is 10000 we can approach with dp with knapsack style
• dp[i][j] : if we can make ‘j’ as summing first i values of the array
  • Since it can be swapped, we need to consider both side
• Then this is it
• We find the minimum value of dp and add with (n-2) * sq_sum

Thought process

vector oriA, oriB;
map<string, ll> dp;

ll dynamic (string s, int i, bool f, ll sa, ll sb, vector a, vector b) {
	if (i == n) {
		return (sa + sb);
	}
	ll ns = s +  (f == false ? "0" : "1") ;
	if (dp.find(ns) != dp.end()) return dp[ns];
	
	// current = no swap
	ll ta = 0, tb = 0;
	ll x = (f == false ? oriA[i] : oriB[i] ), y = (f == false ? oriB[i] : oriA[i]);
	
	rep(j, 0, i-1) {
		ta += (a[j] + x)^2;
		tb += (b[j] + y)^2;
	}
	a.push_back(x), b.push_back(x);
	ll ret = dynamic(ns , i + 1, f, sa + ta, sb + tb, a, b );
	ret = min(ret, dynamic(ns, i + 1, !f, sa + ta, sb + tb, a, b);
	a.pop_back(), b.pop_back();
	
	return dp[ns ] = ret;
}

int main() {
	int n; cin >> n;
	oriA.resize(n), oriB.resize(n);
	rep(i, 0, n) cin >> oriA[i];
	rep(i, 0, n) cin >> oriB[i];
	
	vector a, b;
	
	ll ret = dynamic( "", 0, false, 0, 0, a, b);
	ret = min(ret, dynamic( "", 0, true, 0, 0, a, b);
	
	cout << ret << '\n';
}
</pre>

</details>

### Complexity
- O(100 * 10000)

### Code

```cpp
#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;

bool dp[109][10009];
void solve() {
    int n; cin >> n;
    vector a(n + 1), b(n + 1);
    ll allsum = 0;
    rep(i, 1, n + 1) {
        cin >> a[i];
        allsum += a[i];
    }
    rep(i, 1, n + 1) {
        cin >> b[i];
        allsum += b[i];
    }
    ll square_sum = 0;
    rep(i, 1, n + 1) square_sum += (a[i] * a[i]) + (b[i] * b[i]);
    
    memset(dp, false, sizeof(dp[0]) * (n + 2));
    
    dp[0][0] = true;
    rep(i, 1, n + 1) {
        rep(j, 0, 10000 + 1) {
            if (j - a[i] >= 0 && dp[i-1][j - a[i]]) dp[i][j] = true;
            if (j - b[i] >= 0 && dp[i-1][j - b[i]]) dp[i][j] = true;
        }
    }
    ll mn = 1e12;
    rep(j, 0, 10000 + 1) if (dp[n][j]) {
        ll s1 = j;
        ll s2 = allsum - s1;
        ll s = s1 * s1 + s2 * s2;
        mn = min(mn, s);
    }
    
    ll ans = (n-2) * square_sum + mn;
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int tc; cin >> tc; while(tc--)
        solve();
    return 0;
}
```