Three-Coloring of Binary Trees

Interview

Time limit3sMemory limit128 MB

Summary

Given a binary tree as a digit specification, color each node red, green, or blue so adjacent nodes differ and siblings differ, then report the maximum and minimum number of green nodes.

Level: Medium6 of 10
Topics: Tree, DFS, Dynamic programming, Greedy
Solved: No attempts yet

Problem

A tree consists of one node and some (zero, one, or two) subtrees connected to it. These subtrees are called its children.

A specification of a tree is a sequence of digits. If the number of children of the tree is:

zero, the specification is a sequence with the single element 0;
one, the specification begins with 1, followed by the specification of the child;
two, the specification begins with 2, followed by the specification of the first child and then the specification of the second child.

Every vertex of the tree must be painted red, green, or blue, subject to the following rules:

a vertex and its child cannot have the same color;
if a vertex has two children, the two children must have different colors.

At most and at least how many vertices can be painted green?

Write a program that:

reads the specification of the tree from standard input,
computes the maximum and the minimum number of vertices that can be painted green,
writes the results to standard output.

Input

The first and only line of standard input contains one word (no longer than 10000 characters), which is a specification of a tree.

Output

Print on the first and only line of standard output exactly two integers separated by a single space: the maximum and the minimum number of vertices that can be painted green, in that order.

Examples3

Example 1
Input
```
1122002010
```
Expected output
```
5 2
```
Example 2
Input
```
0
```
Expected output
```
1 0
```
Example 3
Input
```
10
```
Expected output
```
1 0
```