NiNi's Den

2018/01/15 Share

##### 1. For two points $p$ and $q$ in the plane, we say that $p$ dominates $q$ if both $x$ and $y$ coordinates of $p$ are no less than that of $q$ respectively. Given a set $S$ of $n$ points, the rank of a point $p$ in $S$ is the number of points in $S$ dominated by $p$. We want to find the rank of every point in $S$. A naïve algorithm needs $O(n2)$ time. Design a faster algorithm for this problem.

• 一個點支配另外一個點，表示他的$x,y$都要比另外一個點大，因此將所有的點照$x$軸升冪排序後，我們可以確定$x$是遞增的，因此若右半面某點$P_r$的$y$比左半面某點$P_l$的y還大，則我們知道$P_r$支配$P_l$，同時$P_r$也支配$P_l$所支配的所有點。
• 複雜度：$T(n)=2T(n/2)+c_1nlogn+c_2nlogn \Rightarrow O(nlog^2n)$
sim i$產生衝突（因為我們是照結束時間排序，不可能目前活動的開始時間跟$i$沒有交集但是跟$i-1$有交集)。 • 對於每個活動作類似背包為題的做法，對活動j有兩種情況：有j在解當中，沒有j在解當中，遞迴下去可得解。 解法 ##### 9. Solve Problem 10003 “Cutting Sticks” in the ACM web site. 給定一個長度$l$的木棒，必須將其切斷$n$次，切斷的位置分別為$c_1$~$c_n$，($0 < c_i < l$)。 每切一刀的成本為「切斷前」該木棒的長度，求達成目標所需的最小成本。 ##### 10. Given a list of n positive integers d1, d2, …, dn, we want to efficiently determine whether there exists a simple undirected graph whose nodes have degrees precisely d1, d2, …, dn. Design an algorithm to solve this problem. 貪婪法(有數學解) 老師：放這裡應該是貪婪 ##### 11. Given a weighted graph, find a spanning tree such that the maximal edge weight of the tree is minimized over all spanning trees. •$O(|E|log|V|)$: by Kruskal’s algorithm： • A MST is necessarily a MBST, but a MBST is not necessarily a MST. 所以我們可以直接用 Kruskal’s algorithm 來找MST，同時他也會是MBST。 •$O(|E|)$: by Camerini’s algorithm ##### 12. Solve Problem 11264 “Coin Collector” in the ACM web site. • 英文題目 • 中文題目 •$Sum(i-1) < c[i]$是多餘的條件，因為會被上一步的$Sum(i) = Sum(i-1)+c[i] < c[i+1]\$所覆蓋

reference

Original Author: Terrynini