Mobile
Recursive Computation The solution proceeds bottom-up. For each internal node with left subtree weight W_L and right subtree weight W_R, the balance condition d_L W_L = d_R W_R must hold. The minimal positive integer...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
A mobile is a binary tree where each leaf has a positive integer weight. At each internal node, a horizontal bar is hung from a string. The bar has a left arm of length $d_L$ and a right arm of length $d_R$, with sub-mobiles hanging from each end. The mobile is balanced when, at every internal node: \[ W_L \cdot d_L = W_R \cdot d_R \] where $W_L$ and $W_R$ are the total weights of the left and right subtrees, respectively.
Given the structure and leaf weights, compute the minimal positive integer arm lengths needed to balance the mobile at every internal node.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Recursive Computation
The solution proceeds bottom-up. For each internal node with left subtree weight $W_L$ and right subtree weight $W_R$, the balance condition $d_L \cdot W_L = d_R \cdot W_R$ must hold. The minimal positive integer solution is: \[ d_L = \frac{W_R}{\gcd(W_L, W_R)}, \qquad d_R = \frac{W_L}{\gcd(W_L, W_R)}. \]
Lemma.
These arm lengths are the unique minimal positive integers satisfying $d_L \cdot W_L = d_R \cdot W_R$.
Proof.
Let $g = \gcd(W_L, W_R)$, and write $W_L = g \cdot a$, $W_R = g \cdot b$ with $\gcd(a, b) = 1$. The equation $d_L \cdot W_L = d_R \cdot W_R$ becomes $d_L \cdot a = d_R \cdot b$. Since $\gcd(a,b) = 1$, we must have $a \mid d_R$ and $b \mid d_L$. The minimal solution is $d_L = b = W_R / g$ and $d_R = a = W_L / g$.
After computing the arm lengths, the total weight at this node is $W_L + W_R$.
Complexity Analysis
Time: $O(n \log W_{\max})$ where $n$ is the number of nodes and $W_{\max}$ is the maximum subtree weight. Each node is visited once, and each GCD computation takes $O(\log W_{\max})$ time.
Space: $O(n)$ for tree storage plus $O(h)$ recursion stack depth where $h$ is the tree height.
Example
Consider the following mobile:
o
/ \
3 o
/ \
2 1Processing bottom-up:
Right subtree: $W_L = 2$, $W_R = 1$, $\gcd = 1$. So $d_L = 1$, $d_R = 2$. Total weight $= 3$.
Root: $W_L = 3$, $W_R = 3$, $\gcd = 3$. So $d_L = 1$, $d_R = 1$. Total weight $= 6$.
Verification: at the root, $3 \times 1 = 3 \times 1$. At the right internal node, $2 \times 1 = 1 \times 2$. Both balance conditions hold.
Code
C++ solution used for this page.
// IOI 1989 - Problem 3: Mobile
// Balance a binary mobile by computing minimal integer arm lengths.
// For each internal node: d_L * W_L = d_R * W_R => d_L = W_R/g, d_R = W_L/g
#include <bits/stdc++.h>
using namespace std;
struct Node {
bool isLeaf;
long long weight;
Node *left, *right;
long long dL, dR;
Node() : isLeaf(false), weight(0), left(nullptr), right(nullptr), dL(0), dR(0) {}
};
// Read mobile: positive int = leaf weight, 0 = internal node followed by two subtrees
Node* readMobile() {
Node* node = new Node();
long long val;
scanf("%lld", &val);
if (val > 0) {
node->isLeaf = true;
node->weight = val;
} else {
node->left = readMobile();
node->right = readMobile();
}
return node;
}
// Compute total weight and arm lengths bottom-up
long long solve(Node* node) {
if (node->isLeaf) return node->weight;
long long wL = solve(node->left);
long long wR = solve(node->right);
long long g = __gcd(wL, wR);
node->dL = wR / g;
node->dR = wL / g;
node->weight = wL + wR;
return node->weight;
}
// Print arm lengths for all internal nodes (pre-order)
void printResult(Node* node) {
if (node->isLeaf) return;
printf("%lld %lld\n", node->dL, node->dR);
printResult(node->left);
printResult(node->right);
}
void freeMobile(Node* node) {
if (!node) return;
freeMobile(node->left);
freeMobile(node->right);
delete node;
}
int main() {
Node* root = readMobile();
solve(root);
printResult(root);
freeMobile(root);
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.