CF 89B - Widget Library
We are asked to simulate a tiny GUI layout system. There are three kinds of widgets. A plain Widget has a fixed width and height. HBox and VBox are container widgets that can store other widgets. An HBox places children horizontally, while a VBox places them vertically.
Rating: 2300
Tags: dp, expression parsing, graphs, implementation
Solve time: 2m 3s
Verified: yes
Solution
Problem Understanding
We are asked to simulate a tiny GUI layout system.
There are three kinds of widgets. A plain Widget has a fixed width and height. HBox and VBox are container widgets that can store other widgets. An HBox places children horizontally, while a VBox places them vertically.
Each container also has two parameters.
border adds empty padding around all sides of the content.
spacing adds gaps between consecutive children.
The tricky part is that containers store references to widgets, not copies. If a widget later changes size because more children are packed into it, every place where that widget appears immediately reflects the new size.
The input is a sequence of scripting commands. Some commands create widgets, some modify spacing or border, and some pack widgets into containers. At the end we must print the final width and height of every widget in lexicographic order.
The constraints are very small. There are at most 100 instructions, and widget names are short. Even an algorithm that recomputes many sizes repeatedly would fit comfortably inside the limit. The real challenge is modeling the dependency structure correctly and avoiding subtle mistakes in the size formulas.
The packing relation is guaranteed to be acyclic. A widget can never indirectly contain itself. That guarantee matters because the final sizes form a dependency graph. Without cycles, every widget size is well-defined.
Several edge cases are easy to mishandle.
An empty HBox or VBox always has size 0 x 0, regardless of border or spacing.
For example:
3
HBox a
a.set_border(10)
a.set_spacing(20)
Correct output:
a 0 0
A careless implementation might apply the border formula even when there are no children and incorrectly produce 20 x 20.
Spacing only appears between adjacent widgets, not before the first or after the last.
For example:
4
HBox a
Widget x(10,5)
Widget y(20,5)
a.set_spacing(7)
a.pack(x)
a.pack(y)
The width is:
10 + 20 + 7 = 37
not 44. There is only one gap because there are only two widgets.
Another subtle case is shared widgets.
5
Widget x(10,20)
HBox a
VBox b
a.pack(x)
b.pack(x)
The widget x exists once, but contributes to both layouts. Any later change to x must affect both containers automatically. Treating packed widgets as copied objects would silently break this behavior.
Nested containers also require recursive computation.
5
HBox outer
VBox inner
Widget x(10,20)
inner.pack(x)
outer.pack(inner)
The size of outer depends on the computed size of inner, not merely on its direct parameters.
Approaches
The most direct approach is to repeatedly recompute sizes from scratch whenever something changes.
For every container, we can recursively evaluate all descendants. An HBox sums child widths and takes the maximum child height. A VBox sums child heights and takes the maximum child width. Then we add border and spacing contributions.
This brute-force method is actually fast enough here because there are at most 100 instructions. Even if every recomputation traverses all widgets, the total work stays tiny.
The main weakness of a naive recursive implementation is not performance but correctness. If recursion is written carelessly, repeated visits to shared subtrees can produce inconsistent results. Cycles would also cause infinite recursion, though the problem guarantees they never appear.
The key observation is that the widget structure forms a directed acyclic graph. Every container depends only on its children. Since there are no cycles, we can define the size of each widget recursively.
That lets us model the problem cleanly with DFS and memoization.
Plain widgets already know their dimensions.
For containers:
For HBox:
width = sum(child widths) + spacing * (k - 1) + 2 * border
height = max(child heights) + 2 * border
For VBox:
width = max(child widths) + 2 * border
height = sum(child heights) + spacing * (k - 1) + 2 * border
where k is the number of children.
The special empty-container rule overrides everything. If k = 0, the answer is exactly 0 x 0.
Because the graph is acyclic, DFS computes every size correctly. Memoization avoids recomputing the same subtree many times.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force recursive recomputation | O(N²) | O(N) | Accepted |
| Optimal DFS with memoization | O(N + E) | O(N + E) | Accepted |
Here N is the number of widgets and E is the number of packing relations.
Algorithm Walkthrough
- Parse every instruction and build widget objects.
Each widget stores:
type (Widget, HBox, or VBox)
fixed dimensions for plain widgets
border
spacing
list of packed children 2. For creation commands, initialize the corresponding widget.
Plain widgets immediately know their width and height.
3. For pack() commands, append the child widget name to the parent container's child list.
Order matters because spacing depends on adjacency.
4. For set_border() and set_spacing() commands, update the container parameters.
5. Define a DFS function solve(name) that returns the final (width, height) of a widget.
6. If the widget is a plain Widget, return its stored dimensions immediately.
7. If the widget is an empty container, return (0, 0).
This special case must happen before applying border or spacing formulas.
8. Recursively compute the sizes of all children.
9. If the widget is an HBox:
- Sum all child widths.
- Add spacing multiplied by
(children_count - 1). - Add
2 * border. - Take the maximum child height and add
2 * border. - If the widget is a
VBox: - Sum all child heights.
- Add spacing multiplied by
(children_count - 1). - Add
2 * border. - Take the maximum child width and add
2 * border. - Memoize every computed result so repeated references to the same widget are cheap.
- Evaluate every widget and print results sorted lexicographically.
Why it works
The packing structure is a DAG because self-containment is forbidden. Every widget size depends only on descendants lower in this graph.
The DFS computes child sizes before parent sizes, so when a container is evaluated, every required child dimension is already correct.
The formulas exactly match the layout rules:
For HBox, widths accumulate horizontally while height is constrained by the tallest child.
For VBox, heights accumulate vertically while width is constrained by the widest child.
Spacing contributes once between consecutive widgets, which is why the multiplier is (k - 1).
The empty-container special case matches the statement directly and prevents border or spacing from incorrectly affecting empty layouts.
Since every widget is evaluated according to these exact rules, all computed dimensions are correct.
Python Solution
import sys
input = sys.stdin.readline
def solve():
n = int(input())
widgets = {}
for _ in range(n):
s = input().strip()
if s.startswith("Widget "):
rest = s[7:]
name, dims = rest.split("(")
dims = dims[:-1]
w, h = map(int, dims.split(","))
widgets[name] = {
"type": "Widget",
"w": w,
"h": h,
"border": 0,
"spacing": 0,
"children": []
}
elif s.startswith("HBox "):
name = s[5:]
widgets[name] = {
"type": "HBox",
"border": 0,
"spacing": 0,
"children": []
}
elif s.startswith("VBox "):
name = s[5:]
widgets[name] = {
"type": "VBox",
"border": 0,
"spacing": 0,
"children": []
}
elif ".pack(" in s:
left, right = s.split(".pack(")
child = right[:-1]
widgets[left]["children"].append(child)
elif ".set_border(" in s:
left, right = s.split(".set_border(")
val = int(right[:-1])
widgets[left]["border"] = val
elif ".set_spacing(" in s:
left, right = s.split(".set_spacing(")
val = int(right[:-1])
widgets[left]["spacing"] = val
memo = {}
def dfs(name):
if name in memo:
return memo[name]
node = widgets[name]
if node["type"] == "Widget":
ans = (node["w"], node["h"])
memo[name] = ans
return ans
children = node["children"]
if not children:
memo[name] = (0, 0)
return (0, 0)
sizes = [dfs(child) for child in children]
border = node["border"]
spacing = node["spacing"]
k = len(children)
if node["type"] == "HBox":
width = sum(w for w, h in sizes)
width += spacing * (k - 1)
width += 2 * border
height = max(h for w, h in sizes)
height += 2 * border
else:
width = max(w for w, h in sizes)
width += 2 * border
height = sum(h for w, h in sizes)
height += spacing * (k - 1)
height += 2 * border
ans = (width, height)
memo[name] = ans
return ans
for name in sorted(widgets):
w, h = dfs(name)
print(name, w, h)
solve()
The parsing logic mirrors the scripting language directly. Every widget becomes a dictionary containing its type, layout parameters, and child list.
The recursive dfs function implements the mathematical definition of widget size. The memoization dictionary prevents repeated computation when the same widget is packed into multiple containers.
The most important implementation detail is the empty-container check:
if not children:
return (0, 0)
This must happen before applying border or spacing. Otherwise an empty container with border 10 would incorrectly become 20 x 20.
Another subtle point is the spacing formula:
spacing * (k - 1)
There are gaps only between neighboring widgets. With one child there are zero gaps.
The recursion is safe because the input guarantees there are no cycles.
Worked Examples
Sample 1
Input:
12
Widget me(50,40)
VBox grandpa
HBox father
grandpa.pack(father)
father.pack(me)
grandpa.set_border(10)
grandpa.set_spacing(20)
Widget brother(30,60)
father.pack(brother)
Widget friend(20,60)
Widget uncle(100,20)
grandpa.pack(uncle)
Trace
| Step | Widget | Computation | Result |
|---|---|---|---|
| 1 | me | fixed widget | 50 x 40 |
| 2 | brother | fixed widget | 30 x 60 |
| 3 | uncle | fixed widget | 100 x 20 |
| 4 | father | width = 50 + 30, height = max(40,60) | 80 x 60 |
| 5 | grandpa | width = max(80,100) + 20 | 120 |
| 6 | grandpa | height = 60 + 20 + spacing 20 + border 20 | 120 |
Final output:
brother 30 60
father 80 60
friend 20 60
grandpa 120 120
me 50 40
uncle 100 20
This example demonstrates nested containers. grandpa depends on the computed size of father, which itself depends on me and brother.
Custom Example
Input:
6
HBox a
a.set_border(5)
a.set_spacing(7)
Widget x(10,20)
Widget y(30,40)
a.pack(x)
a.pack(y)
Trace
| Step | Widget | Computation | Result |
|---|---|---|---|
| 1 | x | fixed widget | 10 x 20 |
| 2 | y | fixed widget | 30 x 40 |
| 3 | a width | 10 + 30 + 7 + 10 | 57 |
| 4 | a height | max(20,40) + 10 | 50 |
Final output:
a 57 50
x 10 20
y 30 40
This example shows how border and spacing contribute independently.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(N + E) | Each widget and packing edge is processed once |
| Space | O(N + E) | Storage for widgets, child lists, and memoization |
With at most 100 instructions, this solution is comfortably inside the limits. Even repeated recursive traversal would pass, but memoization keeps the implementation clean and avoids redundant work.
Test Cases
# helper: run solution on input string, return output string
import sys
import io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
input = sys.stdin.readline
n = int(input())
widgets = {}
for _ in range(n):
s = input().strip()
if s.startswith("Widget "):
rest = s[7:]
name, dims = rest.split("(")
dims = dims[:-1]
w, h = map(int, dims.split(","))
widgets[name] = {
"type": "Widget",
"w": w,
"h": h,
"border": 0,
"spacing": 0,
"children": []
}
elif s.startswith("HBox "):
name = s[5:]
widgets[name] = {
"type": "HBox",
"border": 0,
"spacing": 0,
"children": []
}
elif s.startswith("VBox "):
name = s[5:]
widgets[name] = {
"type": "VBox",
"border": 0,
"spacing": 0,
"children": []
}
elif ".pack(" in s:
left, right = s.split(".pack(")
child = right[:-1]
widgets[left]["children"].append(child)
elif ".set_border(" in s:
left, right = s.split(".set_border(")
val = int(right[:-1])
widgets[left]["border"] = val
elif ".set_spacing(" in s:
left, right = s.split(".set_spacing(")
val = int(right[:-1])
widgets[left]["spacing"] = val
memo = {}
def dfs(name):
if name in memo:
return memo[name]
node = widgets[name]
if node["type"] == "Widget":
memo[name] = (node["w"], node["h"])
return memo[name]
children = node["children"]
if not children:
memo[name] = (0, 0)
return memo[name]
sizes = [dfs(c) for c in children]
border = node["border"]
spacing = node["spacing"]
k = len(children)
if node["type"] == "HBox":
w = sum(x for x, y in sizes)
w += spacing * (k - 1)
w += 2 * border
h = max(y for x, y in sizes)
h += 2 * border
else:
w = max(x for x, y in sizes)
w += 2 * border
h = sum(y for x, y in sizes)
h += spacing * (k - 1)
h += 2 * border
memo[name] = (w, h)
return memo[name]
out = []
for name in sorted(widgets):
w, h = dfs(name)
out.append(f"{name} {w} {h}")
return "\n".join(out)
# provided sample
assert run(
"""12
Widget me(50,40)
VBox grandpa
HBox father
grandpa.pack(father)
father.pack(me)
grandpa.set_border(10)
grandpa.set_spacing(20)
Widget brother(30,60)
father.pack(brother)
Widget friend(20,60)
Widget uncle(100,20)
grandpa.pack(uncle)
"""
) == (
"""brother 30 60
father 80 60
friend 20 60
grandpa 120 120
me 50 40
uncle 100 20"""
), "sample 1"
# single widget
assert run(
"""1
Widget a(5,7)
"""
) == (
"""a 5 7"""
), "single widget"
# empty container ignores border and spacing
assert run(
"""3
HBox a
a.set_border(10)
a.set_spacing(20)
"""
) == (
"""a 0 0"""
), "empty container"
# spacing counted only between widgets
assert run(
"""6
HBox a
Widget x(10,5)
Widget y(20,5)
a.set_spacing(7)
a.pack(x)
a.pack(y)
"""
) == (
"""a 37 5
x 10 5
y 20 5"""
), "spacing formula"
# nested layouts
assert run(
"""6
VBox root
HBox row
Widget x(10,20)
Widget y(30,40)
row.pack(x)
row.pack(y)
root.pack(row)
"""
) == (
"""root 40 40
row 40 40
x 10 20
y 30 40"""
), "nested containers"
| Test input | Expected output | What it validates |
|---|---|---|
| Single widget | Fixed dimensions preserved | Base case |
| Empty container | 0 x 0 |
Border and spacing ignored for empty layouts |
| Two widgets with spacing | Correct gap counting | Off-by-one in spacing formula |
| Nested layouts | Recursive computation | Parent depends on child size |
Edge Cases
Empty containers
Input:
3
VBox a
a.set_border(5)
a.set_spacing(10)
The algorithm reaches a, sees that its child list is empty, and immediately returns (0, 0).
Output:
a 0 0
This prevents border and spacing from incorrectly affecting empty layouts.
Single child with spacing
Input:
4
HBox a
Widget x(10,20)
a.set_spacing(100)
a.pack(x)
The algorithm computes:
width = 10 + 100 * (1 - 1) = 10
There are zero gaps because there is only one child.
Output:
a 10 20
x 10 20
This catches the classic mistake of adding spacing once per child instead of once per gap.
Shared widgets
Input:
5
Widget x(10,20)
HBox a
VBox b
a.pack(x)
b.pack(x)
The DFS computes x once and memoizes it. Both a and b reuse the same dimensions.
Output:
a 10 20
b 10 20
x 10 20
The algorithm correctly models reference semantics rather than copying widgets.
Deep nesting
Input:
5
VBox a
HBox b
VBox c
Widget x(7,9)
c.pack(x)
b.pack(c)
a.pack(b)
The recursion computes:
x -> c -> b -> a
Every parent uses the already-correct child dimensions.
Output:
a 7 9
b 7 9
c 7 9
x 7 9
This confirms that recursive propagation through multiple container levels works correctly.