USACO analysis
Mark Chen |
15 Dec 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
Problem 2. Barn Painting
Problem Description
Farmer John has $N$ barns connected together. (It is guaranteed that the connected graph does NOT contain a cycle) and three different paints. He has already painted $K$ of $N$ barns. Find out the number of valid ways he can paint the remaining barns.
Proposed Solution
We can solve this problem recursively. Let $f(n, c)$ represent the number of possible valid solutions of painting on a subtree with root $n$ and color $c$ on root, we can represent this function recursively.
\[\begin{aligned} &U = \left\{n' \mid n' \text{ is child of }n\right\}\\ &f(n, c) = \prod_{u\in U}\left({\sum_{c'\in C}{f(u, c')}}\right) \end{aligned}\]When we meet a node that is already been painted, we let $f(node, c) = 0$ if $c$ is not the color that is painted.
Time Complexity Analysis
For each node, we will calculate $f(n, c)$ for at most three times (with three different $c$). Therefore, the time complexity will be $O(3N)$.
