AI Translated from Chinese

Problem: Luogu UVa 12166

Problem Statement

Given a binary tree with depth not exceeding 16, representing a balance scale. Each rod is hung in the center, and the weight of each counterweight is known. What is the minimum number of counterweight weights that need to be modified to balance the scale? — Liu Rujia “Algorithm Competition Introduction Basics”

Analysis

At first glance, it seems difficult to start with. We can first study what properties a balanced scale has.

Treat each sub-scale as a counterweight. If the scale is balanced, its total weight equals the weight of one counterweight multiplied by 2.

Let the depth of the scale be $ depth $. Through the diagram below, we discover:

Total weight of scale = weight of any counterweight (including treating sub-scale as counterweight) × $ 2^{depth} $

So, just read the scale, record the number of times $ num \times 2^{depth} $ (num is the counterweight weight) repeats. The result is:

Minimum modifications = total nodes - max(times $ num \times 2^{depth} $ repeats)

Using STL’s map makes this problem easy to solve.

Code

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define LL long long
#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
#include <map>
using namespace std;

map<LL, int> cnt;  // map: records times num*2**depth repeats

int solve(string s) {
    int depth = 0, sum = 0, maxn = 0;  // Binary tree depth, total nodes, nodes that don't need modification
    int len = s.length();
    for (int i = 0; i < len; i++) {
        if (s[i] == '[') depth++;
        if (s[i] == ']') depth--;
        if (isdigit(s[i])) {
            LL num = 0;
            for (; isdigit(s[i]); i++) { num *= 10; num += s[i] - '0'; }  // Convert character to integer
            i--;  // Prevent off-by-one error from for loop
            sum++;
            cnt[num << depth]++;  // cnt[num*2**depth]++
            maxn = max(maxn, cnt[num << depth]);
        }
    }
    return sum - maxn;
}

int main() {
#ifdef LOCAL
    freopen("uva12166.in", "r", stdin);
    freopen("uva12166.out", "w", stdout);
#endif
    IOS
    int t;
    string s;
    cin >> t;
    while (t--) {
        cnt.clear();
        cin >> s;
        cout << solve(s) << endl;
    }
    return 0;
}

C++ STL’s map is similar to Python’s dictionary, but with differences: map can reference key-value pairs that haven’t been assigned yet, and their values default to 0; Python cannot reference undefined key-value pairs.

Appendix

References

[1]https://www.luogu.com.cn/blog/Einstein-study/solution-uva12166

[2]Liu Rujia “Algorithm Competition Introduction Basics”