REQUEST FOR HINT: USACO Cow Pedigrees

I've been stuck on this problem, 2.3.2 Cow Pedigrees, for a week.

The problem statement goes like this:

Farmer John is considering purchasing a new herd of cows. In this new herd, each mother cow gives birth to two children. The relationships among the cows can easily be represented by one or more binary trees with a total of N (3 <= N < 200) nodes. The trees have these properties:

The degree of each node is 0 or 2. The degree is the count of the node's immediate children.

The height of the tree is equal to K (1 < K <100). The height is the number of nodes on the longest path from the root to any leaf; a leaf is a node with no children.

How many different possible pedigree structures are there? A pedigree is different if its tree structure differs from that of another pedigree. Output the remainder when the total number of different possible pedigrees is divided by 9901.

A solution is here: USACO 2.3.2 – Cow Pedigrees

I modified that solution to print out the whole dp table, but I still do not understand the underlying logic.

Here: Modified Solution

Any hints or explanations of the recurrence solution would be of tremendous help.

Read more…(210 words)

About the author:

BY

Brad Yuan

Loading…

Join the discussion. Add a reply…

Post

About the author

BY

Brad Yuan

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.