Peas

Written by Haithem Djefel

Problem Statement

English
Arabic
Arabic (Algeria)
French

1. Idea

First, for convenience, we will index pods in the order in which their opening brackets appear (0 through n - 1), then, we can make a rooted tree with the given information, the root is pod 0, and for each two nodes and , is a child of if and only if pod is contained inside pod .

Now, letting denote the maximum value that can be obtained after squishing pod number , we can achieve any value after squishing pod number , this is true because all the values are real numbers.

For any leaf node , , and for any red pod , , where is the number of children of .

Now for the blue pods, we will use the following greedy approach, sort the children by their value in ascending order, and we keep processing them in this order one by one, for each child , the maximum optimal value is , and starts with value ( is the number of children), and keeps decreasing by the value we assign to each child.

2. Proof

Note: if you want only the proof of the general case, you can skip this paragraph

For the case of , the proof directly follows from the Arithmetic mean-Geometric mean inequality, more formally, we need the maximum value for such that

By the AM-GM inequality, we have the following:

Dividing both sides by and raising to the power of , we get the maximum value for the product, which holds iff .

The latter case was not necessary to prove, as we will prove the more general case, but I liked to introduce it in the editorial, as it helps build the intuition and make it way more natural.

3. Intuition

From the previous idea we should notice that the numbers assigned to children must be “as close as possible”, now let’s formalize this.

4. General case

For the general case, we will prove it by contradiction, suppose there exists an optimal partition for the numbers with for some (with the number of children > 1), then there exists some number , that satisfies the following and there exists an integer such that , then must hold, expanding and reorganizing, this is equivalent to , contradicting our assumption.

And we're done!

5. Implementation

Below is a code in C++ for this approach

// Peas editorial by Haithem Djefel
#include <bits/stdc++.h>
using namespace std;

typedef double ll;
typedef pair<int, int> pii;

const int MOD = 1000000007;
const ll LOG = 31;

#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);

vector<ll> mx;
vector<vector<ll>> ch;
vector<bool> type;
vector<ll> a;

void dfs(ll u) {
    // leaf node
    if (ch[u].size() == 0) {
        mx[u] = a[1];
        return;
    }
    
    // explore children first, if there are any
    for (ll v : ch[u]) dfs(v);
    
    sort(ch[u].begin(), ch[u].end(), [=](ll a, ll b) -> bool {
        return mx[a] < mx[b];
    });
    
    // if the pod is red
    if (!type[u]) {
        ll max_cap = a[ch[u].size()];
        ll s = 0;
        for (ll v : ch[u]) s += mx[v];
        
        mx[u] = min(s, max_cap);

        return;
    }

    // the pod is blue
    // left corresponds to the sum we're going to distribute, num to the number of unprocessed children
    ll left = a[ch[u].size()], num = ch[u].size(), val = 1;

    for (ll v : ch[u]) {
        // the number to assign to this child
        ll rm = min(mx[v], left / num);
        // adjust the number of children left and the total sum left to distribute
        --num;
        left -= rm;
        val *= rm;
    }

    mx[u] = val;
}

int main() {
    Algerian OI

    ll n;
    cin >> n;
    a.resize(n + 1);

    for (ll i = 1; i <= n; i++) cin >> a[i];

    string s;
    cin >> s;
    ll k = 0;

    for (auto c : s) if (c == '(') ++k; // getting the number of pods

    ch.resize(k);
    mx.resize(k);
    type.resize(k);

    stack<ll> st;
    ll idx = 0;

    // assigning each pod its index, children and type (blue or red)
    for (ll i = 0; i < (ll)s.size(); i++) {
        if (s[i] == '(') st.push(idx++);
        else if (s[i] == ')' && i != s.size() - 1LL) {
            ll cur = st.top();
            st.pop();
            ch[st.top()].push_back(cur);
        }
        else if (s[i] == '*') type[st.top()] = 1;
        else if (s[i] == '+') type[st.top()] = 0;
    }

    dfs(0);

    cout << fixed << setprecision(8);

    cout << mx[0] << "\n";

    return 0;
}