USACO analysis
Mark Chen |
10 Dec 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
Problem 1. A Pie For A Pie
Problem Description
Bessie and Elsie have each baked $N$ pies and each pie has two tasty value - one from Bessie and one from Elsie. In the begining, Bessie gave a pie to Elsie.
If Elsie receive a pie that she think has a tasty value of $n$, she will try to give back Bessie one of her pie that has a tasty value that is in range $n \leq n’ \leq n + D$. If such a pie does not exist, she will ‘exile’ herself.
If Bessie receive a pie from Elsie, the same thing will happen.
Such a cycle will continue, until one of the cow exile herself or they receive a pie that has a tasty value of 0 for them. For each input case, we will solve the minimum number of pies that could be gifted in a happy gift exchange started with Bessie’s pie $i$. If no gift exchange with pie $i$ is happy, then we should print out a single integer $-1$ instead.
:warning: Notice that a pie can only be sent once and the cow can’t send back the pie the other cow sent.
Proposed Solution
In this question, we can use the bottom-to-up method. Instead of checking how many pies will be exchanged for a given beginning pie, we can search reversely from the end point to the start point. In this way, we can only apply one search on all the pie and get the result with time complexity of $O(1)$ for each query.
The actual program will work like this
- Sort all the pies
- Search from pies that have a taste value of 0 both for Bessie and Elsie.
- While searching, store the number of pies exchanged from 0 of Bessie and Elsie.
- For each query, find the number stored in the corresponding index.
Time Complexity Analysis
The time complexity for steps above will be -
- $O(n\log{n})$
- $O(n)$
- $O(1)$ for each query and total time complexity will be $O(n)$.
