USACO analysis
Mark Chen |
14 Nov 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
Problem 1 Balanced Photo
Problem Summary
John want to arrange his $N$ , $1\leq N \leq 100,000$ cows to take a photo. The height of $i$th cow is $h_i$. the heights of all cows are distinct. In a line, a cow is called “unbalanced” if the number of cow that is higher than it on the left is two time (or half of) the number of cow that is lower than it. Given the line of cow, give out the number of unbalanced cows in the photo.
Proposed Solution
First, we can range all the cows from high to low, and fill the array with the cow’s height.
cows = [34, 6, 23, 0, 5, 99, 2]
arr = [_ for _ in range(len(cows))]
arr.sort(key=lambda x: cows[x])
After doing this, we can initialize a new list that used to store whether a cow has been counted. The new list will be filled with 0.
l = [0] * len(cows)
After this, we will apply following steps, suppose we are dealing with the $k$th highest cow, where cows[k] = n
To decrease the time complexity of solution, we will use a data structure called Binary Index Tree (BIT) on $l$. Using BIT, we can calculate $L$, $R$, and update $l$ with time complexity of $O(\log{n})$.
-
Calculate $L = \sum_{i = 0}^n l[i]$. Since we will process all the cows from highest to the shortest, the result of formula will be the number of cow that is higher than current cow and stands on its left.
-
Calculate $R = k - 1 - \sum_{i = 0}^n l[i]$. Since the current cow we are dealing with is the $k$th highest cow, there are $k-1$ cows that are higher than current one. The cow that is higher than current cow and NOT on its left must stand on its right.
- Calculate
- \[\frac{\min{(L, R)}}{\max{(L, R)}}\]
If the result is greater than 2, add the number of unbalanced cow by 1.
- Set the value of $l[n] = 1$.
Time Complexity Analysis
- Time complexity of sorting - $O(n\log{n})$
- Travel through all the cows - $O(n)$
- Calculate L, R, and update $l[n]$ - $O(\log{n})$
Therefore, the total time complexity will be $O(n\log{n})$.
