IOI 1989 - Problem 3: Mobile

// 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;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{listings}
\usepackage[margin=2.5cm]{geometry}
\usepackage{xcolor}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{green!50!black},
  stringstyle=\color{red!70!black},
  numbers=left,
  numberstyle=\tiny\color{gray},
  breaklines=true,
  frame=single,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 1989 -- Problem 3: Mobile}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Statement}

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.

\section{Solution}

\subsection{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)}.
\]

\begin{lemma}
These arm lengths are the unique minimal positive integers satisfying
$d_L \cdot W_L = d_R \cdot W_R$.
\end{lemma}
\begin{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$.
\end{proof}

After computing the arm lengths, the total weight at this node is $W_L + W_R$.

\section{Complexity Analysis}

\begin{itemize}
  \item \textbf{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.
  \item \textbf{Space:} $O(n)$ for tree storage plus $O(h)$ recursion stack
    depth where $h$ is the tree height.
\end{itemize}

\section{Implementation}

The input format uses a preorder encoding: a positive integer denotes a leaf
with that weight; a zero denotes an internal node followed by its two subtrees.

\begin{lstlisting}
#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    bool isLeaf;
    long long weight;
    Node* left;
    Node* right;
    long long dL, dR;

    Node() : isLeaf(false), weight(0), left(nullptr),
             right(nullptr), dL(0), dR(0) {}
};

long long gcd(long long a, long long b) {
    while (b) { a %= b; swap(a, b); }
    return a;
}

Node* readMobile() {
    Node* node = new Node();
    long long val;
    cin >> val;
    if (val > 0) {
        node->isLeaf = true;
        node->weight = val;
    } else {
        node->left = readMobile();
        node->right = readMobile();
    }
    return node;
}

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;
}

void printResult(Node* node) {
    if (node->isLeaf) return;
    cout << node->dL << " " << node->dR << "\n";
    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;
}
\end{lstlisting}

\section{Example}

Consider the following mobile:
\begin{verbatim}
       o
      / \
     3   o
        / \
       2   1
\end{verbatim}

Processing bottom-up:
\begin{itemize}
  \item Right subtree: $W_L = 2$, $W_R = 1$, $\gcd = 1$.
    So $d_L = 1$, $d_R = 2$. Total weight $= 3$.
  \item Root: $W_L = 3$, $W_R = 3$, $\gcd = 3$.
    So $d_L = 1$, $d_R = 1$. Total weight $= 6$.
\end{itemize}

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.

\end{document}