Modelize the problem

We modelize the problem as graph, where each fridge is a vertex and each chain is an edge between two vertexes. The problem is now equivalent to: Given a graph with $$$n$$$ vertexes, each vertex has a value $$$a_i \ge 0$$$. We have to add $$$m$$$ edges to the graph such that each vertex is connected to at least two different vertexes and the total cost of edges added is minimum. The cost of an edge is the sum of value of its two end-points.

Observe some basic properties of graph

Now, each edge added will increase the sum of degree of all vertexes by 2. So adding m edges will make the sum of degree equal to $$$2 \times m$$$. Since each vertexes must be connected to at least $$$2$$$ other vertexes, the minimum sum of degree is $$$2 \times n$$$.

• Case 1: $$$2\times m \lt 2\times n \Leftrightarrow m \lt n$$$

In this case, it is obvious that the answer is $$$-1$$$.

• Case 2: $$$2\times m = 2\times n \Leftrightarrow m=n$$$

In this case, it is easy to see that the degree of each vertex will be exactly 2. As a result, no matter what edges we add, the result is still $$$2\times (a_1+a_2+...+a_n)$$$. But please take note that if $$$n=2$$$, then the answer will be $$$-1$$$ since for each vertex we have at most $$$1$$$ different vertex to connect to.

• Case 3(Of the original, pre-modified version of the problem): $$$2\times m \gt 2\times n \Leftrightarrow m \gt n$$$

Please read this excellent answer by Um_nik. All credit goes to him for the excellent proof.

#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define IS_INF(x)   (std::isinf(x))
#define IS_NAN(x)   (std::isnan(x))
#define fi   first
#define se   second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }
template<class T>
    T Abs(const T &x) {
        return (x < 0 ? -x : x);
    }

/* Author: Van Hanh Pham */

/** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/

const string SYMBOLS = "QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm1234567890";

#define MAX  111
char board[MAX][MAX], res[MAX][MAX];
int numRow, numCol, numChicken;

void process(void) {
    memset(board, 0, sizeof board);
    memset(res, 0, sizeof res);

    scanf("%d%d%d", &numRow, &numCol, &numChicken);
    FOR(i, 1, numRow) scanf("%s", board[i] + 1);

    bool leftToRight = true;
    vector<pair<int, int>> cells;
    FOR(i, 1, numRow) {
        if (leftToRight) {
            FOR(j, 1, numCol) cells.push_back(make_pair(i, j));
        } else {
            FORD(j, numCol, 1) cells.push_back(make_pair(i, j));
        }
        leftToRight ^= 1;
    }

    int totRice = 0;
    FOR(i, 1, numRow) FOR(j, 1, numCol) if (board[i][j] == 'R') totRice++;
    int avg = totRice / numChicken;
    int diff = totRice % numChicken == 0 ? 0 : 1;

    REP(i, numChicken) {
        int cntRice = 0;
        while (true) {
            int x = cells.back().fi, y = cells.back().se;
            cells.pop_back();
            res[x][y] = SYMBOLS[i];
            if (board[x][y] == 'R') {
                totRice--;
                cntRice++;
            }
            if (cntRice < avg) continue;
            if (avg * (numChicken - i - 1) <= totRice && totRice <= (avg + diff) * (numChicken - i - 1)) break;
        }
    }
    while (!cells.empty()) {
        int x = cells.back().fi, y = cells.back().se;
        cells.pop_back();
        res[x][y] = SYMBOLS[numChicken - 1];
    }

    FOR(i, 1, numRow) {
        FOR(j, 1, numCol) printf("%c", res[i][j]); printf("\n");
    }
}

int main(void) {
    int t; scanf("%d", &t);
    REP(love, t) process();
    return 0;
}

/*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/

The problem asked you to move chocolate pieces between adjacent boxes so that the number of chocolate pieces in all boxes is divisible by $$$k$$$ ($$$k \gt 1$$$).

How to solve the problem for a specific $$$k$$$

Now, it's clear that we will divide the array into segments, such that the sum of each segment is divisible by $$$k$$$, and move all chocolate pieces in that segment to a common box. Here we take notice of 2 things:

• First, in each segment, let $$$A$$$ be the array of all position with 1, then the position that we move all the 1 to is the median of that array $$$A$$$ (easy to prove).

• Second, the sum of each segment should be all equal to $$$k$$$. It's easy to see that if there exists some segment of sum $$$x*k$$$, then separating them into $$$x$$$ segments of sum $$$k$$$ will improve the result.

With that two observations, we can iterate from 1 to n, push each position with value 1 into a temp array, and whenever the size of array become k, we add to our result the sum of $$$|a_i-median|$$$ and clear the array.

Knowing how to solve for a specific $$$k$$$, how to solve the problem?

It is clear that $$$k$$$ must be a divisor of the total number of chocolate pieces. So we iterate through all possible $$$k$$$ and minimize our answer with the number of steps to make all numbers divisible by k. A number $$$\le 10^5$$$ has at most 128 divisors, and each calculation take $$$O(n)$$$ so the solution should pass easily.

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000006;
int n;
int a[maxn];
vector <int> v;

long long cost(int p) {
    long long ret = 0;
    for (int i = 0; i < v.size(); i += p) {
        int median = v[(i + i + p - 1) / 2];
        for (int j = i; j < i + p; ++j)
            ret += abs(v[j] - median);
    }
    return ret;
}

int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] == 1) v.push_back(i);
    }
    if (v.size() == 1) {
        cout << -1 << endl;
        return 0;
    }
    long long ans = 1e18;
    int tmp = v.size(), p = 2;
    while (p * p <= tmp) {
        if (tmp % p == 0) {
            ans = min(ans, cost(p));
            while (tmp % p == 0)
                tmp /= p;
        }
        ++p;
    }
    if (tmp > 1)
        ans = min(ans, cost(tmp));
    cout << ans << endl;
    return 0;
}

The problem E2 is different from the problem E1 in some ways. Now all $$$A_i$$$ is at most $$$10^6$$$, and so is the number $$$n$$$. That makes our solution on E1 simply not usable in this problem.

A cute observation:

Let $$$S_i$$$ be the sum of $$$a_1 + a_2 + ... + a_i$$$. Now we see that:

• if we move a chocolate piece from box $$$i$$$ to box $$$i+1$$$, it is equivalent to decrease $$$S_i$$$ by 1.

• if we move a chocolate piece from box $$$i+1$$$ to box $$$i$$$, it is equivalent to increase $$$S_i$$$ by 1.

Wow, now each moving steps only affect one number. Next, we can see that if every $$$a_i$$$ is divisible by k, then so is every $$$S_i$$$. Thus, our problem is now transformed to: Given an array $$$S$$$. At each turn, you can choose one $$$S_i$$$ and increase (or decrease) it by one (except for $$$S_n$$$). Find the minimum number of steps to make all $$$S_i$$$ divisible by $$$k$$$.

How to solve the problem for a specific $$$k$$$

An intuitive approach is to try to increase (or decrease) each $$$S_i$$$ to the nearest multiple of $$$k$$$. If such a configuration can be achieved then it will obviously be the best answer. The only concern is that: is there any scenario when there exists some $$$i$$$ such that $$$S_i \gt S_{i+1}$$$, which is indeed a violation? Fortunately, the answer is no. We can enforce the solution to iterate each $$$S_i$$$ from $$$1$$$ to $$$n-1$$$ and always choose to decrease if there is a tie. This way, the sequence $$$S$$$ will remain non-decreasing throughout the process.

So, the solution is as follows. Just iterate from $$$1$$$ to $$$n-1$$$ and for each $$$i$$$, add to our result $$$min(S_i\%k,k-S_i\%k)$$$.

Knowing how to solve for a specific $$$k$$$, how to solve the problem?

Again, like E1, it is clear that $$$k$$$ must be a divisor of the total number of chocolate pieces. But now the total number of chocolate pieces is at most $$$10^{12}$$$, which an iteration through all divisors will not be fast enough to fit in 1 second. (In fact, we did make just one single test case to block this solution. Nevertheless, on random testcases it runs super fast).

But if you have solved the problem to this phase already, you can easily realize that we only need to consider prime $$$k$$$, because if $$$k$$$ is composite then picking any prime divisors of it will lead to either a better result or an equal result.

That's it, there will be at most 12 distinct prime divisors. Each calculation takes $$$O(n)$$$. So the solution will also pass easily.

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000006;
int n;
long long a[maxn];
long long s[maxn];

long long cost(long long mod) {
    long long ret = 0;
    for (int i = 1; i <= n; ++i)
        ret += min(s[i] % mod, mod - s[i] % mod);
    return ret;
}

int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    if (s[n] == 1) {
        cout << -1 << endl;
        return 0;
    }
    long long ans = 1e18;
    long long tmp = s[n], p = 2;
    while (p * p <= tmp) {
        if (tmp % p == 0) {
            ans = min(ans, cost(p));
            while (tmp % p == 0)
                tmp /= p;
        }
        ++p;
    }
    if (tmp > 1)
        ans = min(ans, cost(tmp));
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n;

void check_if_zero(long long x){
    if (x == 0) exit(0);
}

long long get_area(int a,int b,int c){
    long long result;
    cout << 1 << ' ' << a << ' ' << b << ' ' << c << endl;
    cin >> result;
    check_if_zero(result);
    assert(result > 0);
    return result;
}

int get_sign(int o,int a,int b){
    int result;
    cout << 2 << ' ' << o << ' ' << a << ' ' << b << endl;
    cin >> result;
    check_if_zero(result);
    assert(abs(result) == 1);
    return result;
}

vector <int> lef, rig;

void divide(){
    for(int i=3;i<=n;i++){
        int sign = get_sign(1, 2, i);

        if (sign == 1)
            lef.push_back(i);
        else
            rig.push_back(i);
    }
}

long long area12[1005];

void _do(vector<int> &lst){
    if (lst.size() <= 1)
        return;

    long long best = 0;
    for(auto v: lst){
        area12[v] = get_area(1, 2, v);
        if (area12[v] > area12[best])
            best = v;
    }

    vector <int> l, r;
    for(auto v: lst){
        if (v == best)
            continue;

        if (get_sign(1, best, v) == 1)
            l.push_back(v);
        else
            r.push_back(v);
    }

    sort(l.begin(), l.end(), [&](int x,int y){
        return area12[x] > area12[y];
    });
    sort(r.begin(), r.end(), [&](int x,int y){
        return area12[x] < area12[y];
    });

    lst.clear();
    for(auto v: r)  lst.push_back(v);
    lst.push_back(best);
    for(auto v: l)  lst.push_back(v);
}

void answer(){
    cout << 0 << ' ' << 1 << ' ';
    for(auto v: rig)  cout << v << ' ';
    cout << 2 << ' ';
    for(auto v: lef)  cout << v << ' ';
    cout << endl;
}

int main(){
    cin >> n;
    assert(n >= 3);

    divide();   // n-2 queries
    _do(lef);
    _do(rig);   //  2*(n-2) - 1 or 2*(n-2) - 2 queries
    answer();
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 150005;
const int mod = 998244353;
const int heavy = 300;
int n, m, q;
vector <int> adj[maxn];
int dad[maxn];
int sz[maxn];
vector <int> pos[maxn];
int tour[2*maxn];
vector <int> heavy_vector;
int weight[2*maxn];
 
int pw(int x, int y) {
    int r = 1;
    while (y) {
        if (y & 1) r = 1LL * r * x % mod;
        x = 1LL * x * x % mod;
        y >>= 1;
    }
    return r;
}
 
void dfs(int u) {
    tour[++m] = u;
    pos[u].push_back(m);
    sz[u] = 1;
    for (auto v: adj[u]) {
        if (v == dad[u]) continue;
        dad[v] = u;
        dfs(v);
        sz[u] += sz[v];
        tour[++m] = u;
        pos[u].push_back(m);
    }
}
 
int fwt[2*maxn];
void upd(int l, int r, int d) {
    for (int p = l; p <= m; p += p & -p) fwt[p] = (fwt[p] + d) % mod;
    ++r;
    for (int p = r; p <= m; p += p & -p) fwt[p] = (fwt[p] + mod - d) % mod;
}
int get(int p) {
    int ret = 0;
    for (; p; p -= p & -p) ret = (ret + fwt[p]) % mod;
    return ret;
}
 
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> n >> q;
    int inv_n = pw(n, mod - 2);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    dfs(1);
    for (int i = 1; i <= n; ++i) if (adj[i].size() >= heavy)
        heavy_vector.push_back(i);
 
    while (q--) {
        int type, v;
        cin >> type >> v;
        if (type == 1) {
            int d;
            cin >> d;
            weight[v] = (weight[v] + d) % mod;
            if (adj[v].size() < heavy) {
                for (auto u: adj[v]) if (u != dad[v])
                    upd(pos[u][0], pos[u].back(), 1LL * d * (n - sz[u]) % mod * inv_n % mod);
                if (v == 1) continue;
                upd(1, pos[v][0] - 1, 1LL * d * sz[v] % mod * inv_n % mod);
                upd(pos[v].back() + 1, m, 1LL * d * sz[v] % mod * inv_n % mod);
            }
        }
        else {
            int ans = (weight[v] + get(pos[v][0])) % mod;
            for (auto u: heavy_vector) {
                if (u == v) continue;
                auto it = lower_bound(pos[u].begin(), pos[u].end(), pos[v][0]);
                if (it == pos[u].begin() || it == pos[u].end())
                    ans = (ans + 1LL * weight[u] * sz[u] % mod * inv_n) % mod;
                else {
                    int p = tour[*(--it) + 1];
                    ans = (ans + 1LL * weight[u] * (n - sz[p]) % mod * inv_n) % mod;
                }
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int maxn = 500005;

int n;
vector <int> adj[maxn];
int a[maxn];
int dad[maxn];
int h[maxn];
vector <pair <int, int> > conditions[maxn];
int nxt[maxn], prv[maxn], seen[maxn];

void no(int ncase) {
    cerr << ncase << endl;
    cout << 0 << endl;
    exit(0);
}

void dfs(int u) {
    for (auto v: adj[u]) if (v != dad[u]) {
        dad[v] = u;
        h[v] = h[u] + 1;
        dfs(v);
    }
}

int cnt; ///total distance, must not be more than 2n-2

void go(int u, int v) {
    if (u == v) no(0);
    vector <int> from_u, to_v;
    ///naive LCA works here as long as we exit upon finding a conflict
    from_u.push_back(n + 1); ///first edge (fake)
    to_v.push_back(n + 2); ///last edge (fake)
    while (h[u] > h[v]) {
        from_u.push_back(u);
        u = dad[u];
    }
    while (h[v] > h[u]) {
        to_v.push_back(v);
        v = dad[v];
    }
    while (u != v) {
        from_u.push_back(u);
        u = dad[u];
        to_v.push_back(v);
        v = dad[v];
    }
    from_u.push_back(u);
    from_u.insert(from_u.end(), to_v.rbegin(), to_v.rend());
    for (int i = 1; i + 1 < from_u.size(); ++i)
        conditions[from_u[i]].push_back({from_u[i-1], from_u[i+1]});
    cnt += from_u.size() - 3;
    if (cnt > 2 * n - 2) no(0); ///important break
}

int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        adj[i].push_back(n + 1); ///first edge (fake)
        adj[i].push_back(n + 2); ///last edge (fake)
    }
    for (int i = 1; i <= n; ++i) cin >> a[i];

    if (n == 1) {
        cout << 1 << endl;
        exit(0);
    }

    dfs(1);
    for (int i = 1; i <= n; ++i) if (a[i] != 0) go(i, a[i]);

    ///answer 0 if:
    ///1. there are 2 or more incoming/outgoing
    ///conditions to/from an edge, or
    ///2. there is a cycle, or
    ///3. first (n+1) is connected to last (n+2),
    ///but does not contain all other edges.
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        ///check case 1
        for (auto edge: conditions[i]) {
            int u = edge.first, v = edge.second;
            if (nxt[u] && nxt[u] != v) no(1);
            if (prv[v] && prv[v] != u) no(1);
            nxt[u] = v;
            prv[v] = u;
        }
        ///check case 2
        for (auto u: adj[i]) if (!seen[u]) {
            seen[u] = 1;
            int cur = nxt[u];
            while (cur) {
                if (cur == u) no(2);
                if (seen[cur]) break;
                seen[cur] = 1;
                cur = nxt[cur];
            }
        }
        ///check case 3
        if (nxt[n+1]) {
            int cur = n + 1, all = 1;
            while (cur) {
                if (cur == n + 2) break;
                ++all;
                cur = nxt[cur];
            }
            if (cur == n + 2 && all < adj[i].size()) no(3);
        }
        ///all good - for now
        int free = 0;
        for (auto u: adj[i]) if (u <= n && !prv[u]) ///fake edges doesn't count
            ++free;
        if (prv[n+2]) --free; ///connected to last edge => not free
        for (int j = 1; j <= free; ++j) ans = 1ll * ans * j % mod;
        ///reset
        for (auto u: adj[i]) nxt[u] = prv[u] = seen[u] = 0;
    }

    ///no conflicts
    cout << ans << endl;
    return 0;
}