作者DJWS (...)
看板Prob_Solve
標題Re: [問題] Google Interview Question (4)
時間Fri Mar 15 07:44:02 2013
※ 引述《stimim (qqaa)》之銘言：
: 於是，我們就可以得到一個小一點的問題，
: lists = {list_1, list_2, ..., list_K}
: where list_1 = {p_1j},
: list_i = {a_i, b_i}
: 這個問題的大小是 O(K) ，如果可以在 O(K) 的時間得到答案的話，
: 我們就可以用 O(N) 的時間得到原問題的答案：
以下嘗試說明這個小一點的問題
目標是每個list_i當中，ai和bi兩個選一個，
讓 max{abs(ai)} + max{bi} 越小越好。
http://postimage.org/image/xfpn6lbe3/
首先把 [ai,bi] 畫在數線上，按照 ai 由小到大排序
http://postimage.org/image/t4icz76cx/
如果已經排序好，
就可以 ai 由小到大掃描一次所有區間，O(K) 算出答案。
我們要找的答案，是最短的紅線。
(這個好難解釋，總之各位應該看得懂吧...一開始假設通通都選ai這樣...)
http://postimage.org/image/5c91no4c1/
可以發現這些區間可以分成一堆一堆的盤子，
就好像疊盤子一樣，每一堆最下面的是大盤子，上面有一些小盤子。
所有的小盤子的邊緣，都不會超過最下面的大盤子。
如果還沒有排序好，
這個問題比找出所有的 dominating intervals 還要難一點。
dominating intevals 就是每一堆盤子裡面，最下面的大盤子。
define [ai,bi] dominates [aj,bj] iff ai<=aj and bi>=bj
dominatring intervals 又可以等價變成二維平面上的 dominating points。
(CLRS 叫做 maximal layer)
只要把區間 [ai,bi] 改成二維座標 (-ai, bi) 即可。
也就是說這個問題至少比 maximal layer 來的複雜。
至於 maximal layer 的嚴格下限是 omega(NlogM)，
其中 N 是給定的座標數量，M 是 maximal layer 的數量，證明在這篇：
Lower bounds for maximal and convex layers problems
Algorithmica, June 1989, Volume 4, Issue 1-4, pp 447-459
不是很懂那個 algebraic dicision tree model 是指什麼意思，
不過我的理解是：除非用 counting sort 之類的技巧，不然這題應該很難做到 O(K) 吧!
報告完畢
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
補充一下原題的 worst case lower bound。
stimim 的方法是：
在 K 個 inverted list 當中，找到長度最短的那個 inverted list，
然後窮舉長度最短的 inverted list 當中的每一個 occurrence，
針對每個 occurrence，從其他 inverted list 找到 [ai,bi]，
進而得到一個小一點的問題。
運氣不好時，最短的 inverted list 長度是 omega(N/K)。
【這裡的 N 是指全部的、也就是那K個 inverted list 的總長度。】
所以窮舉的次數就是 omega(N/K)。
運氣不好時，每個小問題之間的 [ai,bi] 通通都不一樣。
所以每個小問題之間沒有關聯，可以分開計算。
解決一個小問題的下限，如前文所述，就是 omega(KlogK)。
所以原本問題的下限就是 omega(N/K * KlogK) = omega(NlogK)。
所以這一題不會有 O(N) 的方法。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.132.202
※ 編輯: DJWS 來自: 36.225.132.202 (03/15 10:25)