2014-12-02

UVa 1169 - Robotruck

Problem

在一個二維平面中，灑落 N 個垃圾，機器人從原點 (0, 0) 依序要蒐集垃圾，機器人一次承載 W 重量的垃圾，隨時可以返回原點將垃圾放下。

請問依序收集垃圾的最少花費為何？

Sample Input

Sample Output

Solution

一開始得到方程式 dp[i] = min(dp[j-1] + cost[j, i] + dist[j] + dist[i]) 必須滿足 w[j, i] <= C，其中 j <= i。

其中 dp[i] 表示依序收集前 i 個垃圾的最小花費，cost[j, i] 表示走訪編號 j 到 i 垃圾位置的花費，補上原點到編號 j，並且收集完從 i 回到原點。

這樣的方程式轉換需要 N^2 時間，化簡一下式子

1
2
3

dp[i] = dp[j-1] + cost[j, i] + dist[j] + dist[i]
dp[i] = dp[j-1] + cost[i] - cost[j] + dist[j] + dist[i]
dp[i] = (dp[j-1] - cost[j] + dist[j]) + cost[i] + dist[i]

會發現 i, j 獨立，也滿足垃圾重量累計遞增，因此盡可能保留 dp[j-1] - cost[j] + dist[j] 小的結果，並且重量不超過限制，當重量超過限制時，該組答案在隨後保證再也不會用到，直接捨棄之。

核心就是單調隊列的思路。

#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 131072
int x[MAXN], y[MAXN], w[MAXN];
int cost[MAXN], dist[MAXN];
int dp[MAXN];
int f(int j) {
    return dp[j-1] - cost[j] + dist[j];
}
int main() {
    int testcase, C, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &C, &N);
        w[0] = 0, cost[0] = 0;
        for (int i = 1; i <= N; i++) {
            scanf("%d %d %d", &x[i], &y[i], &w[i]);
            cost[i] = cost[i-1] + abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]);
            dist[i] = abs(x[i]) + abs(y[i]);
            w[i] += w[i-1];
        }
        // dp[i] = dp[j-1] + cost[j, i] + dist[j] + dist[i]
        // dp[i] = dp[j-1] + cost[i] - cost[j] + dist[j] + dist[i]
        // dp[i] = (dp[j-1] - cost[j] + dist[j]) + cost[i] + dist[i]
        deque<int> Q;
        Q.push_back(0);
        for (int i = 1; i <= N; i++) {
            while (!Q.empty() && w[i] - w[Q.front()] > C)
                Q.pop_front();
            dp[i] = f(Q.front() + 1) + cost[i] + dist[i];
            while (!Q.empty() && f(Q.back() + 1) >= f(i + 1))
                Q.pop_back();
            Q.push_back(i);
        }
        printf("%d\n", dp[N]);
        if (testcase)	puts("");
    }
    return 0;
}

Read More +

2014-11-28

學校課程/計算幾何

計算幾何 - HW04

Chapter 7

7.1

Prove that for any n > 3 there is a set of n point sites in the plane such that one of the cells of Vor(P) has n−1 vertices

證明一個點個數 n > 3 的 Voronoi diagram，存在一個 cell 具有 n - 1 個頂點。

7.1

如圖所示，一個點放置在圓心，剩餘的 n - 1 個放置在圓周上。則中間的 cell 必然有 n - 1 個頂點。

7.3

Show that$\Omega (nlogn)$ is a lower bound for computing Voronoi diagrams by reducing the sorting problem to the problem of computing Voronoi diagrams. You can assume that the Voronoi diagram algorithm should be able to compute for every vertex of the Voronoi diagram its incident edges in cyclic order around the vertex.

7.3

證明 Voronoi diagram 的 lower bound$\Omega (nlogn)$，藉由 reduce 到 sorting problem。

關於 reduce 證明，將一個簡單、約束較少的問題 A，藉由一個合適的轉換，變成一個困難問題 B 的 subset，已知 A 的 lower bound，則 B 的 lower bound 至少與 A 相同。

假設排序 n 個整數$x_{1}, x_{2}, ..., x_{n}$
轉換成$(x_{1}, 0), (x_{2}, 0), ..., (x_{n}, 0)$ 將所有點放置在 x 軸上，並且額外增加一點$(\infty, 0)$。將 n + 1 個點找到 Voronoi diagram，對於$(\infty, 0)$ 的 cell 而言，恰好邊都是由另外 n 個點對應的 cell 構成 cell edge (相鄰)。假設儲存邊的順序為順或逆時針，則邊的順序等價排序結果。

最後如上圖所示，又已知轉換需要$O(n)$，sorting$\Omega (nlogn)$，則 Voronoi diagram 的 lower bound$\Omega (nlogn)$。

7.5

Give an example where the parabola defined by some site$p_{i}$ contributes more than one arc to the beach line. Can you give an example where it contributes a linear number of arcs?

7.5

如上圖所示$p_{i}$ 拉出的拋物線 (parabola) 有可能提供多個弧 (arc)。(最左側的點提供 2 個弧)

一個點$p_{i}$ 存有的 arc 數量與 cell$p_{i}$) 的頂點數量線性相關。由 exercose 7.1 得到最多$O(n)$ 的頂點。同理 arc 數量最多$O(n)$。

beach line 上的 arc 數最多為 Voronoi diagram 的 edge 數，又 Voronoi diagram 的 edge 最大數為$3n - 6$，也因此最多為$O(n)$

7.10

Let P be a set of n points in the plane. Give an$O(nlogn)$ time algorithm to find two points in P that are closest together. Show that your algorithm is correct.

Algorithm:

建造 Voronoi Diagram by fortune’s algorithm$O(nlogn)$
對於每一個 cell$p_{i}$) 檢查鄰居 cell$p_{neighbor}$)，計算$distance(p_{i}, p_{neighbor})$ 的結果。Voronoi diagram 的 edge 數$3n - 6$，每一條 edge 檢查只需要$O(1)$。$O(n)$

證明：每一個點所張開的 cell 只會與相鄰的 cell 最近，否則不符合 Voronoi diagram 的定義。

7.14

Show that the farthest point Voronoi diagram on n points in the plane has at most 2n−3 (bounded or unbounded) edges. Also give an exact bound on the maximum number of vertices in the farthest point Voronoi diagram.

歐拉公式$v - e + f = 2$
一個頂點至少三條邊。
farthest point Voronoi diagram 的最多有 n - 2 個頂點。
- 對於每一個頂點而言，通過其相鄰 cell 對應的點的外接圓，其圓包含所有平面點。
- 這種圓最多 n - 2 個。
從隨機增量算法中得知，插入一個點時，最多增加一個 vertex (繞行時，會刪除對於 cell 相交兩個線段之間的所有 vertex，這種 vertex 至少一個，並且增加與線段的交點 1 個)。$v(3) = 1, v(n) = v(n-1) + 1 \text{ for } n > 3$
考慮增加一個虛點，連接所有 unbounded edge $v - e + f = 2 \Rightarrow (n-2+1) - e + n = 2 \Rightarrow e = 2n - 3$。

Chpater 9

9.2

The degree of a point in a triangulation is the number of edges incident to it. Give an example of a set of n points in the plane such that, no matter how the set is triangulated, there is always a point whose degree is n−1.

對於任意三角化的結果，總會有一個點的 degree = n - 1。

9.2

此點一定能用一條線區隔所有剩餘點。
剩餘 n - 1 個點，一定能滿足任兩點的連線不遮蔽其他的點。

example：n - 1 個點落在$y = e^{x}$ 上，且$x < p$，另外一點在$(p, q)$

9.4

Prove that the smallest angle of any triangulation of a convex polygon whose vertices lie on a circle is the same. This implies that any completion of the Delaunay triangulation of a set of points maximizes the minimum angle.

對於所有頂點共圓的凸多邊形，任何的三角化的最小角度都會相同。

任何三角形必然是圓上三點。
任何凸邊形的邊都會是一個三角形上的邊
三角形的邊都是圓的弦，並且對應角度正比弦長大小。
凸多邊形的最小弦長是多邊上的邊，又因一定會在三角形上，任何三角化一定包含這個最小角。

9.7

Prove that all edges of DG(Pr) that are not in DG(Pr−1) are incident to pr. In other words, the new edges of DG(Pr) form a star as in Figure 9.8. Give a direct proof, without referring to algorithm DELAUNAYTRIANGULATION.

對於新增加的邊$e$，只會與新加入的點$p_{r}$ 相連。

從 Voronoi diagram 等價 Delaunay triangulation，加入點的 cell，不會使其他兩個 cell 從沒相鄰變成相鄰。
對於$\Delta(p_{i}, p_{j}, p_{k})$ 之間加入$p_{r}$，由於$C(p_{i}, p_{j}, p_{k})$ 內部不存在任何點$C'(p_{i}, p_{r})$ (兩點當直徑)，得到$C' \subseteq C$，且$C'$ 內部不存在任何點，確定$\bar{p_{i} p_{r}}$ 屬於 Delaunay 上。同理$\bar{p_{j} p_{r}}$$\bar{p_{k} p_{r}}$。
由於$\Delta(p_{l}, p_{i}, p_{j})$ 原本是 Delaunay 上，如果 flip$\bar{p_{i} p_{j}}$，得到$C(p_{i}, p_{r}, p_{l}) \subseteq C(p_{l}, p_{i}, p_{j})$$C(p_{j}, p_{r}, p_{l}) \subseteq C(p_{l}, p_{i}, p_{j})$，確定$\bar{p_{r} p_{l}}$ 屬於 Delaunay 上。
也因此，對於增加的三角形進行檢查時，每次已經保證該三角形其中兩邊一定屬於 Delaunay 上，同時必然有$p_{r}$，flip 的邊一定會接到$p_{r}$ 上。遞迴得證。

9.11

A Euclidean minimum spanning tree (EMST) of a set P of points in the plane is a tree of minimum total edge length connecting all the points. EMST’s are interesting in applications where we want to connect sites in a planar environment by communication lines (local area networks), roads, railroads, or the like.

Prove that the set of edges of a Delaunay triangulation of P contains an EMST for P.
Use this result to give an O(nlogn) algorithm to compute an EMST for P.

對於歐幾里得距離的平面最小生成樹。

證明 EMST 的 edge set 被 Delaunay triangulation 的 edge set 包含。(參考 wiki)
目標： every edge not in a Delaunay triangulation is also not in any EMST
- 最小生成樹的性質：任何一個 cycle 上的最重邊將不會在最小生成樹中。
- Delaunay triangulation： If there is a circle with two of the input points on its boundary which contains no other input points, the line between those two points is an edge of every Delaunay triangulation.
  
  對於鈍角三角形，最大邊必然不在 EMST 中，然而對於 Delaunay triangulation 性質，必須考慮他們兩點的 boundary (shared Voronoi edge) 是否存在。
  
  假設 p, q 之間沒有邊於 Delaunay，則對於任意通過 p, q 的圓都存在點 r 在圓內，從性質中發現 r 到 p, q 的距離一定小於 p q 之間的距離。同時在 EMST 中，p q r 三點會構成鈍角三角形，其中 p q 是最大邊，p q 之間必然沒有邊。
找到 EMST 的$O(nlogn)$ 算法
Algorithm:
1. 利用 Delaunay triangulation 找到所有邊$O(nlogn)$
2. 最多有 3n - 6 條邊，利用 MST 中的 kruskal’s algorithm$O(ElogE)$
  3.$E = O(3n-6) = O(n)$，得到$O(nlogn)$ 的做法。

9.13

The Gabriel graph of a set P of points in the plane is defined as follows:
p q Two points p and q are connected by an edge of the Gabriel graph if and only if the disc with diameter pq does not contain any other point of P.

Prove that DG(P) contains the Gabriel graph of P.
Prove that p and q are adjacent in the Gabriel graph of P if and only if the Delaunay edge between p and q intersects its dual Voronoi edge.
Give an O(nlogn) time algorithm to compute the Gabriel graph of a set of n points

Gabriel graph：任兩點之間為直徑的圓內若沒有其他點，則兩點之間有邊。

證明 subgraph 關係。

根據 Theorem 9.6 (1) 任三點圓內$C(p_{i}, p_{j}, p_{k})$沒有其他點，但是$C(p_{i}, p_{j})$ 內部可能存有其他點 (如單純的 n = 3 的鈍角三角形)。找到$e_{p_{i}, p_{j}} \notin Gabriel \text{ but } e_{p_{i}, p_{j}} \in Delaunay$
*$C(p_{i}, p_{j})$ 內部沒有其他點，則兩點之間必然有 shared Voronoi edge，符合 Theorem 9.6 (2)。得到 $\text{ if }e_{p_{i}, p_{j}} \in Gabriel \text{ , then } e_{p_{i}, p_{j}} \in Delaunay$，得證$g(P) \subseteq DG(P)$。

如果$\bar{pq}$ 經過多個 Voronoi edge，則$\bar{pq}$ 上一點 x 滿足 $$\bar{xr} < \bar{xp}, \bar{xr} < \bar{xq} \\ \Rightarrow \angle rpx < \angle prx, \angle rqx < \angle xrq \text{(triangle)} \\ \text{let } \angle rpx = a, \angle prx = c, \angle rqx = b, \angle xrq = d \\ \Rightarrow a + b + c + d = 180^{\circ} \\ \Rightarrow c + d > 90^{\circ}$$

符合圓內角性質，點 r 一定在圓內，得證$e_{p_{i}, p_{j}} \notin Gabriel$。

在 O(n logn) 時間內完成。
Algorithm：
1. 利用 Delaunay triangulation 找到所有邊$O(nlogn)$
2. 將$e_{p{i}, p{j}} \in DG(P)$ 進行測試是否有點落在$C(p{i}, p{j})$$O(n)$
  
  只需要拿鄰居進行檢測，鄰居最多 2 個 (共邊的三角形)。

9.14

The relative neighborhood graph of a set P of points in the plane is defined as follows: Two points p and q are connected by an edge of the relative neighborhood graph if and only if

$d(p, q) \leq \underset{r \in P, r \neq p, q }{min} max(d(p, r), d(q, r)).$

Given two points p and q, let lune(p,q) be the moon-shaped region p q lune(p,q) formed as the intersection of the two circles around p and q whose radius is d(p,q). Prove that p and q are connected in the relative neighborhood graph if and only if lune(p,q) does not contain any point of P in its interior.
Prove that DG(P) contains the relative neighborhood graph of P.
Design an algorithm to compute the relative neighborhood graph of a given point set.

整體而言類似 9.13。

若 p, q 之間沒有邊，則 $$\exists r : d(p, q) > \underset{r \in P, r \neq p, q }{min} max(d(p, r), d(q, r)) \\ \exists r : d(p, q) > d(p, r) \text{ and } d(p, q) > d(q, r)$$ AND 就是做交集操作，不知道該怎麼寫才好。
與 9.14 依樣畫葫蘆，只是$lune(p, q) \subseteq C(p, q)$，則更暗示$\text{ if }e_{p_{i}, p_{j}} \in G \text{ , then } e_{p_{i}, p_{j}} \in Gabriel$
速度是$O(n^{2})$，沒辦法單純看鄰居進行檢查。拿每一條邊進行 O(n) 窮舉。不過在分散式計算，整體是 O(n)。

Read More +

2014-11-26

學校課程/通識課程

[通識] 文明的進程 Week 10

重大體悟

羞恥重要的性質是在行為舉止後對於 自我優越感下降 的恐懼，個人害怕喪失他人的尊重，思考這些帶來的可能性，也就是羞恥情感！其實活得身分低下、與那些自認不同的人處於相同地位。

學了半學期羞恥，這時才發現那吞噬信心的巨獸－羞恥，不知道何時開始，它就像常駐技能似的，不管睡著還醒著都沒有關閉的跡象，這樣活著像遊戲 BUG 似的存在，那麼地與眾不同。

也許，早在那年發現自我弱點時，就烙上那 奴隸的印記 ，不斷地想要遮掩身分的不同，隨時隨地都要小心祕密被發現，想到個人價值有可能在一夕崩落，羞恥感壟罩整個心頭。其實我就是那身分低下的奴，不斷地遮掩印記，卻試圖想要往那更高層爬去。

既然都爬到這，還不想崩落、還不想被發現，至少還要在某些人中存有價值，帶著罪惡感不斷輪迴，也因此走了自己最不想走的路，但是不這麼做，自我價值就在瞬眼之間消散。

如今，崩落假想也隨之成長，直到那再也無法遮掩自己的脆弱前，假想帶來的恐懼不斷地侵蝕我。

回過頭來

段考檢討

寫點與印象答案比較不同的，總之能想到自己很多是零分面向的作答，無知就是我的本體。

為何淡定、 hold 住 的情感為何在中世紀比較沒有呢？
中世紀的人必須野蠻，對人的關係不是 朋友就是敵人 ，任何一點猶豫將把自己處於不利地位，為了生存，這些克制自我的情感將成為阻礙。
解釋 內心世界 為何而生？
隨著文明化，人與人之間的關係相當重要，在 人際互動 的親密下，考慮遠程利益，不斷地盤算要做出甚麼樣的決策，才能最適應未來、現在的人際網路，也因此要表現出那衝突、矛盾的思緒都會在內心世界中。
對於中古世紀以及現代教育對於 兒童教育 的方針有何基礎的不同？
中世紀的兒童教育，兒童就是小大人，什麼都必須知道、什麼都能做，因為它們要趕快成為大人。相對於近代，防止被帶壞、很多不能學、不能知道，不斷地隔離成人的內容。
為什麼機場配置的「紅外線水龍頭」高科技廁所是一個文明化的象徵？
隔離人與人之間的接觸，同時也是在衛生觀念的防病、防疫措施。隔絕彼此已經作為一個文明化的指標。

本周課程

本周圍繞的主題為社會結構與人際關係，不過說是禮儀與社會結構之間交互關係也可，作為階級區隔，人與人之間所需的禮儀也會有所不同。

曾經說到階級流動與禮儀之間的關係，在不同階級下，人的生活型態不同，面對不同的環境就需要不同的禮儀，即使是在相同時空下，對人制宜也是相當重要的！

階級競逐

作為看待一個社會階級流動，正因為流動的存在，也會形成激烈的競逐，而作為競逐的項目也會隨著年代、國情不同而有所變化，從文憑、車款、養生、 … 都能見得。在傳統社會的世襲中，階級也許不太變化，權貴般的生活到了現代，如果把自己家境多有錢拿出來凸顯階級，也許還比不上一個有品味、氣質、風度的平民百姓。

你的強大若無法帶給別人恩惠，充其量就是個異類。

不過從印度婆羅門教、種姓制度看來，用了一個宗教藉口使得人們相信此生所為將決定下個人生的階級，某些手段利益看來，相當高明呢！社會看起來肯定相當安定，各盡其職。如果沒有太離譜的表現，制度當初為了血統純正的說法，就能達到目標。

結構改變

當社會結構改變時，帶動的是許多職業的消失。當然在科技的發展下，也不少職業消失，而這些人去了哪裡？又有甚麼樣的心理狀態改變？

曾想過自己一身技能，在一個事件動盪下一文不值嗎？接著又要何去何從，找到自我價值？

細看武士階級的年代，其實那段日子在早些時間都消失，他們練就一身武藝，卻沒有在年代中獲得需要、找到工作，不管是在西方騎士、東方武士都有相同的處境，即使後來在重要人士旁進行護衛工作，但身分地位上也有所轉變，至少在禮儀上也必須相對於在戰場上那樣的狂野，轉為平靜的心態。

在中國歷史角度看來，從諸侯分權到王權獨大，武力霸權帶來的壟斷、和平，卻也造成武士們再也沒有表現的機會，何處才有戰場讓咱們逞逞威風？每天面對帝王鞠躬盡瘁，哪適合咱們？也因此不少人從國民崇拜的英勇武士落魄到連下一餐都找不到，即便現在沒了戰場，也要秉持著武士精神度日！絕不能讓別人看到自己軟弱的地方！

講到這，講到動物也有此特性，再凶猛的動物即使自己受傷處於弱勢，若展現脆弱的一面，也會受到反撲。

在西方歷史中，最有印象的是具有領土的貴族們，當商人興起，開始擁有大把大把鈔票時，農地生產不及鈔票來得有價值，金錢觀念勝過於階級，貴族們也無法守住自己的農民，最後要倚靠皇宮的保護，最後遺失自己的自由。「 雖然窮，但我們自由。 」這一詞也在某些勵志的文章中見到，金錢的重要性還是看個人操守吧。

投票是什麼？「有錢有勢的人動員沒錢沒勢的人進行大規模支持活動」－老師一語，全堂竊笑。

到了現代，仍然有許多國家存有兩極化，例如墨西哥貧民窟，上網搜尋的結果，還真是一線之隔，可謂「 住得近、習相遠 」老師的意思可能不是這樣，在分工體系下，人們從自給自足轉變到相互依賴，開始有了密切交易，同時也帶來緊張氣氛。

達爾文獎：「讓自己愚蠢的基因不再自由地傳播出去」，對人類的演化做出了貢獻。亦有人認為，達爾文獎是用來記錄「那些在演化過程中走得最慢的人們」。

達爾文獎（Darwin Awards）zh.wikipedia.org/wiki/%E9%81%94%E7%88%BE%E6%96%87%E7%8D%8E

內心世界

在現在的人情交易所中，深思熟慮、自我克制、精確調整情緒成為交易所的基礎籌碼，只要拿著這些籌碼去，多少能搏得人情網路，同時了解人情網路的拓樸關係，有助於思考站於哪個地位進行支持，可謂拓樸學的二分圖、三分圖之類的關係呢！一個人改變關係，可能標染都要更動！

我們將會變成一個縝密分析的生物，就為了站在有利的位置上，不斷地將訊息解析，否則無法立於社會中。必須知道情感用事也無法撼動這個世界，世界道理不依個人意志運作。

作為這一點，如果一個人思考的太多，針對、多角式、深入剖分的思考會不會造成反應速度的延遲？意即聰明到跟笨蛋似的。

國人特有現象，在一般常理下，自己做出脫格行為將會為自己帶來羞恥，對於別人做的，則會身感難堪，但是我們似乎更進化了？會感到憎恨。

Read More +

2014-11-24

網頁設計/About This Blog

部落格架構更新與狀態

當前使用主題為 hexo-theme-landscape，早期使用 pacman，自己修改成 moman 一個黑色系主題，但是隨著文章數量的增加，pacman 樣板的生成速度越來越慢，更新 hexo 後，發現 landscape 的速度異常地快，於是將整個樣板配色轉移到 landscape。

想打包我嗎？直接至 morris821028/morris821028.github.io 下載即可。還是即時的版本呢，可惜地是無法再用 hexo 繼續產生文章，也就是要新增一篇文章是困難的。這裡有純草稿 morris821028/HexoBlog 提供，偶爾會更新，這偶爾想必是挺久的日子。往後要在其他主題下部屬也不是問題！

反應速度

由於 hexo 本身就是 靜態網頁 的框架，所以不會有資料庫調用問題，反應速度理所當然會快很多。為了增加網頁的反應速度，要把不少重複的框捨去，siderbar 訊息最小化！

原理就當作編寫 markdown，利用 hexo 編譯成 html 後上傳。跟一般寫 cpp 程式很像呢！

將 Tags 搬移到額外的分頁，由於每一個頁面下都會出現在 sidebar，無用訊息量太多導致載入速度拉慢，不要忽視使用者經驗 (UX)！

額外分頁的建立

/blog/source/tags/index.md

1
2
3

title: Tags
layout: tags
---

hexo 配置是採用每一個 markdown 上的參數 layout。接著只需要在主題下寫一個 /themes/landscape/layout/tags.ejs，到時候會直接經過 layout.ejs 呼叫 tags.ejs。

接著就可以在 http://localhost:4000/tags/ 下看到自己想要頁面，一般而言不會有這一頁，會呈現 NOT FOUND 404 狀態。

主題設定檔

既然有用 font awesome ，覺得在默認主題下 Home 顯得不太夠力且明瞭，直接點擊 logo 也是能返回主頁。於是把設定檔案改成以下內容，搭配圖示和文字描述，希望這種方式會更脫離死板的配置。

/themes/landscape/_config.yml

menu:
  - {name: Home, path: /, class: icon-home, layout: 1}
  - {name: About, path: /about, class: icon-user, layout: 2}
  - {name: Archives, path: /archives, class: icon-archive, layout: 2}
  - {name: Tags, path: /tags, class: icon-tags, layout: 2}
  - {name: Pictures, path: /picture, class: icon-camera, layout: 2}
  - {name: Works, path: /works, class: icon-trophy, layout: 2}

接著在 header.ejs 下修改一下內容，畢竟參數上有點調整。

/themes/landscape/layout/_partial/header.ejs

<a id="main-nav-toggle" class="nav-icon"></a>
<% for (var i in theme.menu){ %>
  <% if (theme.menu[i].layout && theme.menu[i].layout == 1) { %>
    <a class="main-nav-link" href="<%- url_for(theme.menu[i].path) %>"><i class=<%= theme.menu[i].class %> title='<%= theme.menu[i].name %>'></i></a>
  <% } else if (theme.menu[i].layout && theme.menu[i].layout == 2) { %>
    <a class="main-nav-link" href="<%- url_for(theme.menu[i].path) %>"><i class=<%= theme.menu[i].class %> title='<%= theme.menu[i].name %>'></i> <%= theme.menu[i].name %></a>
  <% } else { %>
    <a class="main-nav-link" href="<%- url_for(theme.menu[i].path) %>"><%= theme.menu[i].name %></a>
  <% } %>
<% } %>

Ukagaka

由於 史蒂芙 任務結束，現在由 派拉斯 接管，她們的個人照片都可以在 Pictures 中見到哦！

關於 Ukagaka 的製作，目前把音樂坑解決，將可以在功能列表中看到音樂撥放功能！實作採用 HTML5 + js 的方式，並且把圖片部分全部用 font awesome 解決，功能還不夠齊全，希望已經能符合最低需求。

其實很早就用 HTML5 + js 弄過音樂撥放，但遲遲沒有嫁入到 Ukagaka 中。

音樂部份的免空是個問題，目前用容量較小的音樂檔案放置 hexo 中一起部屬。

至於 AIML 的 AI 智能對話部分，之前停留在 JAVA 那邊，暫且還不會去完成她，其一原因是必須轉成比較好跑在 server 上面的版本，並且能應付多人單一的狀態保留。如果不寫 web socket，必然要透過 ip 進行辨識，至少能記住當前使用者的名稱 (如果有教導 Ukagaka 的話)。

根據之前用 nodejs 寫 web socket 完成 chat room 的感想，有一部分是相當難理解的 js，同時存在瀏覽器要解析的 js 中，模組部分很好奇實際運作原理，詳細還沒有理解。

Read More +

2014-11-22

學校課程/自然語言

自然語言處理論文研讀 1

Introduction

語意分析涉及正反意見在文字語句中判定，因此必須使用多方視角看待問題與答案，這一點在之前，有人做過意見導向的資訊萃取、資訊摘要 (於文件、語句、片語)。語意分析通常分為三個階段，校準、辨識、分類所有已經讀取的文句。這篇論文探討文件分級 (document-level) 的分析，將會著重分析 特定類型的評論文件 。

第一個問題－極性分類 (polarity classification)，對於目標決策正極性 (贊同) 或者是負極性 (反對)，最近也在擴大到中性文件的分類上，雖然研究成果相當多且廣，極性分類仍然是自然語言處理系統中重大的挑戰。

接著將會著重於語言學上的極性分類。在語言學中，建立一個高校的極性分類透過：

high order n-grams
複合形容詞，例如 happy 被視為正，而 terrible 視為負面。
詞彙的相依關係
來自於中立文件中所描述的詞組

… 本文略

主要是極性分類，反映正反兩方兩種評論，為了增加精準度，其一種方法把單純闡述事實的評論去除、以及在中性評論用的用詞特別處理，接著對於形容詞與關聯名詞做統計，確保面向的評論對象是所需。

至於 n-gram 部分，有說明到 n 越大，將會造成模糊範圍增加，這樣一來其極性價值就會被削減，對於精準度是會掉的，只用 n = 2 好不好？他說他複合使用 n = 2 和 n = 3 將精準度提升，看到所謂顯著 2% 上升，似乎跟誤差無仿。

Read More +

2014-11-22

解題區/解題區 - UVa

UVa 10907 - Art Gallery

Problem

給一個簡單多邊形，內部放置一點求可視範圍的區域面積。

Sample Input

Sample Output

1
2
3

Gallery #1
6250.00
7500.00

Solution

一開始以為可視範圍可能保證是凸多邊形，後來發現其實不一定，有可能是簡單多邊形。

錯誤的思路－一開始想用半平面交計算，所以一直掛在特殊 case 下。

首先，對詢問點將每一個點拿來作極角排序，然後掃描相鄰的極角，對於每一個相鄰極角會與詢問點拉出一個小角度，兩邊的射線無限延伸，接著保證簡單多邊形的每一條邊要不橫跨這個張角、要不完全沒有，不會存在一小段於張角中。

因此會發現會有很多三角形，取交集拿到最靠近詢問點的三角形，兩條射線上取最靠近詢問點的座標，但是這樣的三角形不保證一定在三角形內部，把最後得到的三角形每條邊上的中點拿來做測試，使用射線法檢查是否在簡單多邊形內部。

抓思路 BUG 就花一個早上 Orz。

#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
#define MAXN 131072
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    bool operator==(const Pt &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    } 
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
        angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
};
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if (onSeg(as, at, bs) || onSeg(as, at, bt) ||
        onSeg(bs, bt, as) || onSeg(bs, bt, at))
        return 1;
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
        cross(at, as, bs) * cross(at, as, bt) < 0 &&
        cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
        cross(bt, bs, as) * cross(bt, bs, at) < 0)
    return 1;
    return 0;
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(onSeg(p[i], p[j], q))
            return 1;
        if(p[i].y > q.y != p[j].y > q.y &&
            q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
            cnt++;
    }
    return cnt&1;
}
const double pi = acos(-1);
double artGallery(Pt p[], int n, Pt q) { // polygon: anti-clockwise order
    vector< pair<double, Pt> > A;
    for (int i = 0; i < n; i++) {
        if (!(p[i] == q))
            A.push_back(make_pair(atan2(p[i].y - q.y, p[i].x - q.x), p[i]));
    }
    sort(A.begin(), A.end());
    double ret = 0;
    int m = A.size();
    for (int i = 0, j = m-1; i < m; j = i++) {
        if (fabs(A[i].first - A[j].first) > eps) {
            vector<Seg> segs;
            Pt a, b, ta, tb;
            a = q + (A[j].second - q) * 10000;
            b = q + (A[i].second - q) * 10000;
            for (int k = 0, l = n-1; k < n; l = k++) {
                if ((cross(q, A[j].second, p[k]) * cross(q, A[j].second, p[l]) < eps 
                    && cross(q, A[i].second, p[k]) * cross(q, A[i].second, p[l]) < eps)) {
                    if (p[l] == q || p[k] == q)	continue;
                    if (intersection(a, q, p[l], p[k]) && intersection(b, q, p[l], p[k]) && !onSeg(p[l], p[k], q))
                        segs.push_back(Seg(p[l], p[k]));
                }
            }
//			printf("base %lf %lf %lf %lf\n", A[i].second.x, A[i].second.y, A[j].second.x, A[j].second.y);
            for (int i = 0; i < segs.size(); i++) {
//				printf("%lf %lf %lf %lf\n", segs[i].s.x, segs[i].s.y, segs[i].e.x, segs[i].e.y);
                if (intersection(a, q, segs[i].s, segs[i].e)) {
                    ta = getIntersect(Seg(a, q), segs[i]);
                    tb = getIntersect(Seg(b, q), segs[i]);
                    if (dist(ta, q) < dist(a, q) && !(a == q))
                        a = ta;
                    if (dist(tb, q) < dist(b, q) && !(b == q))
                        b = tb;
                }
            }
            if (inPolygon(p, n, Pt((a.x + b.x)/2, (a.y + b.y)/2)) &&
                inPolygon(p, n, Pt((a.x + q.x)/2, (a.y + q.y)/2)) &&
                inPolygon(p, n, Pt((q.x + b.x)/2, (q.y + b.y)/2))) {
                ret += fabs(cross(q, a, b))/2;
//				puts("Y");
            }
//			printf("---- %lf %lf %lf %lf\n", a.x, a.y, b.x, b.y);
//			puts("--");
        }
    }
    return ret;
}
int main() {
    int testcase, cases = 0;
    int n, m;
    double x, y;
    Pt D[105];
    while(scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &D[i].x, &D[i].y);
        scanf("%d", &m);
        printf("Gallery #%d\n", ++cases);
        for (int i = 0; i < m; i++) {
            scanf("%lf %lf", &x, &y);
            double area = artGallery(D, n, Pt(x, y));
            printf("%.2lf\n", area);
        }
    } 
    return 0;
}
/*
5
0 0
50 50
100 0
100 100
0 100
2
49 50
50 51
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
*/

Read More +

2014-11-22

解題區/解題區 - UVa

UVa 12865 - Volume Control

Problem

1, 2, 4, 7, 10, 15, 19, 26, 31, 37, 43, 54, 60, 73

A027384 Number of distinct products ij with 0 <= i, j <= n.

詢問 0 到 N 的連續整數，任兩個挑出來相乘，有多少不同的整數。

Sample Input

1
2
3

2
3
4

Sample Output

1
2

7
10

Solution

聽說當下比賽很多人直接本地建表，不過這一題還真的不知道該怎麼解比較好。

用了窮舉的方式，加入第 i 個整數，將與 0 ~ i 相乘，這時候增加多少不同整數？

找到 i * j == p * q 其中滿足 p, q < i，要忽略所有可能的 j，剩餘的結果就是增加的數量。
假設 i = a * b, p = a * ?1, q = b * ?2。
得到 j = ?1 * ?2、?2 < a, ?1 < b。

用嚴格增加的趨勢，依序窮舉 i 的因數 a (小到大)，?2 可以帶入的數字會遞增，而 ?1 會遞減，而中間會有一段重複的窮舉，只考慮 ?2 進行遞增即可。將不好的 j 給篩掉。

#include <stdio.h> 
#include <set>
#include <math.h>
#include <vector>
using namespace std;
int main() {
    int ret[65536] = {1}, sum = 1;
    int nop[32767] = {}, cases = 0;
    for (int i = 1; i <= 30000; i++) {
        vector<int> f;
        int first_prime;
        for (int j = 2; j * j <= i; j++) {
            if (i%j == 0) {
                f.push_back(j);
            }
        }
        // i * j == p * q (p, q < i)
        // i = a * b, p = a * ?1, q = b * ?2
        // j = ?1 * ?2
        cases++;
        first_prime = f.size() ? f[0] : i;
        for (int j = 0, q1, q2 = 2; j < f.size(); j++) { // f[j] x (i / f[j])
            for (; q2 < f[j]; q2++) { // ?2 < a, ?1 < b
                for (q1 = i/ f[j] - 1; q1 >= 1; q1--)
                    nop[q1 * q2] = cases;
            }
        }
        for (int j = i / first_prime; j <= i; j++)
            sum += nop[j] != cases;
        ret[i] = sum;
    }
    int testcase, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        printf("%d\n", ret[n]);
    }
    return 0;
}

Read More +

2014-11-22

解題區/解題區 - UVa

UVa 12863 - Journey through the kingdom

Problem

對於每一個點 (i, j) 可以護送人的範圍為中間張開矩形 [i-r: i+r] x [j - c: j+c]，可以傳送到矩形任何一點花費為 V(i, j)。每個點的花費和矩形大小都可以不同。

Sample Input

Sample Output

3 -1 1 0

Solution

什麼，居然有 range tree 配上 dijkstra？

很明顯是一題最短路徑。所有點都分配在 N x M 上，最慘為 25 萬個點，同時邊最慘邊數量也就是 25 萬 x 25 萬，因此在 O(E log V) 肯定是過不去的。

但是後來發現到，花費是在點上，因此可以換個角度想，每次更新離開該點花費最小的，也就是說每 pop 一個點，就能知道有一個矩形內保證是最短路，不會再進行任何更新。因此只要不斷地找到區域內尚未走訪的點，將其移除即可。

為了能夠快速找到矩形內尚未走訪的點，最好的方式是使用 range tree，但是找到區域內所有點的成本是 O(log^2 n + k)，用一堆 set<int> 串 list 起來也要 O(r log n + k)，這種作法會 TLE。而標程中使用 BIT 完成 range tree 的概念，BIT 查找速度是挺快的，但是看起來比較接近 O(k log^2 n)，只能說點移除的速度很快，所以 k 小很多。

用 2D BIT 作為 range tree 的基底，也要確保每一個點很緊密地在 R x C 的每一格，range tree 找到區域內所有尚未走訪的點，進行 dijkstra 更新。

自己寫一個樹套樹的作法嘗試輾輾看，但是在建表上就已經快崩，記憶體飛漲得相當快，導致速度被拉下。之後改用一個 list 串出一堆一條一條的 set，這樣的速度，隨後用二分處理，比用 2D BIT 建造的 range tree 還要快，至少在隨機測資中速度是兩三倍以上，上傳 TLE。

看來只能乖乖地標程給的 … WTF，居然就這樣屈服了，都寫了好幾個版本。就不能讓我混過嗎。QAQ

當前使用優化策略：建立於 dijkstra

方案 1：
(1) 啟發式搜索，相同花費下鄰近目標地的優先擴充，沒有好的估價。
(2) 對於矩形，每個 row 當作一條，建立 list，把不可能需要更新的點移除，實作由 set row[MAXN] 完成。

方案 2：
(1) 啟發式搜索，相同花費下鄰近目標地的優先擴充，沒有好的估價。
(2) 對於矩形，random 矩形內部 K 個點。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <set>
#include <algorithm> 
using namespace std;
#define MAXN 512
int V[MAXN][MAXN], R[MAXN][MAXN], C[MAXN][MAXN];
int TX, TY;
struct Node {
    int r, c, v, h;
    Node(int a=0, int b=0, int d=0, int e=0):
    r(a), c(b), v(d), h(e) {}
    bool operator<(const Node &x) const {
        if (v != x.v)
            return v > x.v;
        return h > x.h;
    }
};
priority_queue<Node> pQ; // dijkstra
struct RangeTree { // 2D binary indexed tree
    int A[MAXN][MAXN];
    int R, C;
    void init(int R, int C) {
        this->R = R, this->C = C;
        memset(A, 0, sizeof(A));
        for (int i = 1; i <= R; i++)
            for (int j = 1; j <= C; j++)
                modify(i, j, 1);
    }
    
    void modify(int x, int y, int val) {
        for (; x <= R; x += x&(-x)) {
            for (int i = y; i <= C; i += i&(-i)) 
                A[x][i] += val;
        }
    }
    int query(int x, int y) {
        int ret = 0;
        for (; x > 0; x -= x&-x)
            for (int i = y; i > 0; i -= i&(-i))
                ret += A[x][i];
        return ret;
    }
    int rectSum(int lx, int rx, int ly, int ry) {
        return query(rx, ry) - query(lx-1, ry) - query(rx, ly-1) + query(lx-1, ly-1);
    }
    void update(int lx, int rx, int ly, int ry, int val, int tot) { // {val: update cost, tot: #unvisited point in area.}
        if (tot == -1) 	
            tot = rectSum(lx, rx, ly, ry);
        if (tot == 0) 	return;
        if (lx == rx) {
            if (ly == ry) {
                pQ.push(Node(lx, ly, val + V[lx][ly], abs(lx-TX) + abs(ly-TY)));
                modify(lx, ly, -1);
                return;
            }
            int cnt = rectSum(lx, rx, ly, (ly + ry)/2);
            if (cnt) 
                update(lx, rx, ly, (ly + ry)/2, val, cnt);
            if (cnt < tot) 
                update(lx, rx, (ly + ry)/2 + 1, ry, val, tot - cnt);
        }
        else {
            int cnt = rectSum(lx, (lx + rx)/2, ly, ry);
            if (cnt) 
                update(lx, (lx + rx)/2, ly, ry, val, cnt);
            if (cnt < tot)
                update((lx + rx)/2 + 1, rx, ly, ry, val, tot - cnt);
        }
    }
} rangeTree;
int findPath(int n, int m, int sx, int sy, int ex, int ey) {
    if (sx == ex && sy == ey)	return 0;
    TX = ex, TY = ey;
    rangeTree.init(n, m);
    rangeTree.modify(sx, sy, -1);
        
    while (!pQ.empty())	pQ.pop();
    pQ.push(Node(sx, sy, V[sx][sy], abs(sx-ex) + abs(sy-ey)));
    
    Node u;
    int lr, rr, lc, rc;
    while (!pQ.empty()) {
        u = pQ.top(), pQ.pop();
        
        if (abs(u.r - ex) <= R[u.r][u.c] && abs(u.c - ey) <= C[u.r][u.c])
            return u.v;
            
        lr = max(1, u.r - R[u.r][u.c]), rr = min(n, u.r + R[u.r][u.c]);
        lc = max(1, u.c - C[u.r][u.c]), rc = min(m, u.c + C[u.r][u.c]);
        rangeTree.update(lr, rr, lc, rc, u.v, -1);
    }
    return -1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
    int n, m, q, X[16], Y[16];
    while (scanf("%d %d %d", &n, &m, &q) == 3) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &V[i][j]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &R[i][j]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &C[i][j]);
        for (int i = 0; i < q; i++)
            scanf("%d %d", &X[i], &Y[i]);
            
        for (int i = 1; i < q; i++) {
            int r = findPath(n, m, X[i-1], Y[i-1], X[i], Y[i]);
            printf("%d%c", r, i == q - 1 ? '\n' : ' ');
        }
    }
    return 0;
}
/*
 3 4 5
 1 2 1 1
 1 5 3 4
 1 1 6 3
 1 2 3 3
 3 3 1 2
 0 0 0 1
 1 4 0 1
 2 3 0 1
 4 1 3 1
 1 1
 3 4
 1 1
 2 2
 2 2
 */

Read More +

2014-11-21

解題區/解題區 - UVa

UVa 10154 - Weights and Measures

曾經紅及一時的的烏龜塔問題，討論相當多。最近學弟因為 2014 年資訊奧林匹亞研習營初選中的一題，跑來問我怎麼解比較好。但是想一想之前都是用 dp 過去的。速度 O(n^2)，優化也只會是 O(k n)，k 是答案，還是還用了貪心去解決，但是後來才挖到這個化石，想法是挺簡單的，人生白活了。

l大所寫的演算法是有來源的。
寄信詢問l大之後，得到的回覆，整理於下。

最早出現的文獻

Moore, J.M.(1968) An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science. 15(1):102-109.

現在的演算法名稱 Moore-Hodgson Algorithm 時間複雜度 O(N * log(N)) 演算法證明

先證至少有一最佳解工作順序是依完工期限由小到大排

證明拿掉最大執行時間的工作不會比最佳解差問題轉換方式

Instance:

有n個工作要完成 <—> 有n個箱子要疊

每個工作有不同的處理時間 <—> 不同的重量

每個工作有不同的完工期限 <—> 不同的載重量(要包含自己重量)

Question: 讓無法如期完工的工作越少越好 <—> 箱子疊越多越好 C++實作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Job {int time, due;} job[10]; 
bool cmp(const Job& j1, const Job& j2) { 
    return j1.due < j2.due;
} 
void Moore_Hodgson() {
    sort(job, job+10, cmp); 
    int t = 0;
    priority_queue<int> pq; 
    for (int i=0; i<10; ++i) {
        pq.push(job[i].time); 
        t += job[i].time; 
        if (t > job[i].due) t -= pq.top(), pq.pop();
    } 
    cout << "如期完成的工作(箱子)數目，最多為" << pq.size();
}
DJWSwww.ptt.cc/bbs/Prob_Solve/M.1271995568.A.15C.html

Read More +

2014-11-18

解題區/解題區 - UVa

UVa 12862 - Intrepid climber

Problem

從山頂往下爬不需要花費，往上爬則要根據給定的邊上的花費計算。現在有朋友在特定的點上，找到一條花費最少的路徑。(花費計算到抵達最後一個朋友的所在地，不用特地返回山頂。)

給定的圖為一棵樹。

Sample Input

Sample Output

1
2
3

2
2
0

Solution

如果把最後停留的點再走回去山頂，則會構成一個尤拉環道，而在這一題可以觀察出這個尤拉環道的花費是固定的。

那麼要找停留的地方，必然是扣除返回山頂的最大花費，這樣就能找到拜訪所有朋友的最小花費。對於某些朋友可能不是在葉節點，如果其子樹內沒有朋友，就可以不用走訪。概念上，需要將這個樹稍微壓縮一下。

#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
vector< pair<int, int> > g[131072];
int f[131072], w = 0, ret = 0;
void dfs(int u, int &friends, int dep) {
    int v, ff = 0, cost;
    friends = f[u];
    if (f[u])	ret = max(ret, dep);
    for (int i = 0; i < g[u].size(); i++) {
        v = g[u][i].first;
        dfs(v, ff, dep + g[u][i].second);
        if (ff > 0) {
            w += g[u][i].second;
            friends += ff;
        }
    }
}
int main() {
    int n, m, x, y, v;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 1; i <= n; i++)
            g[i].clear(), f[i] = 0;
        for (int i = 1; i < n; i++) {
            scanf("%d %d %d", &x, &y, &v);
            g[x].push_back(make_pair(y, v));
        }
        for (int i = 0; i < m; i++) {
            scanf("%d", &x);
            f[x] = 1;
        }
        w = 0, ret = 0;
        dfs(1, x, 0);
        printf("%d\n", w - ret);
    }
    return 0;
}
/*
6 2
1 2 2
2 4 2
1 3 3
3 6 3
3 5 1
5 2
4 2
1 2 2
1 3 1
3 4 2
2 4
4 2
1 4 1
1 3 1
4 2 2
2 4
*/

Read More +