解題區/解題區 - UVa

UVa 12878 - Flowery Trails

Problem

在國家公園的步行路道上要在兩側放置花卉，而主辦單位認為只要在其中兩個重要景點的最短路徑上的道路放置即可。通常大部分人只會走最短路徑。

請問總花費為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160
4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1

Sample Output

1
2
3860
18

Solution

最短路徑可能有數條，因此要窮舉每一條邊是否在最短路徑上，已知景點分別為 st 和 ed ，那麼找到 st -> u 和 ed -> v 的單源最短路徑，接下來窮舉 u -> v ，加上 st -> u 和 v -> ed ，得到 st -> u -> v -> ed 的最少花費，檢查是否等於最短路徑長即可。

這一題是雙向圖，如果是單向圖則要反轉邊，才能對 ed 進行單源最短路徑 (SSSP)。在這一題寫 SSSP 使用 SPFA 算法，也許 dijkstra 也是挺不錯的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm> 
using namespace std;
#define MAXN 32767
vector< pair<int, int> > g[MAXN];
int dist1[MAXN], dist2[MAXN];
void spfa(int st, int ed, int dist[]) {
    static int inq[MAXN];
    queue<int> Q;
    int u, v, w;
    dist[st] = 0, Q.push(st);
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].first, w = g[u][i].second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v])
                    inq[v] = 1, Q.push(v);
            }
        }
    }
}
int main() {
    int n, m;
    int x, y, w;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(make_pair(y, w));
            g[y].push_back(make_pair(x, w));
        }
        
        for (int i = 0; i < n; i++)
            dist1[i] = dist2[i] = 0x3f3f3f3f;
        spfa(0, n-1, dist1);
        spfa(n-1, 0, dist2);
    
        int sp = dist1[n - 1], ret = 0;
        for (int i = 0; i < n; i++) {
            x = i;
            for (int j = 0; j < g[i].size(); j++) {
                y = g[i][j].first, w = g[i][j].second;
                if (dist1[x] + w + dist2[y] == sp)
                    ret += w;
            }
        }
        printf("%d\n", ret * 2);
    }
    return 0;
}
/*
10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160
4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1
*/
Read More +
解題區/解題區 - UVa

UVa 12876 - City

Problem

現在給定格子狀的街區，每一個街區只會與垂直、水平的相鄰街區有通行的人行道。現在已知每個街區有多少人行道，求未知的街區人行道數量情況。

Sample Input

1
2
3
4
5
1
3 3
2 2 3
1 -1 3
1 1 0

Sample Output

1
1

Solution

二分圖黑白染色，知道每一個只會與相鄰上下左右的街區相鄰，那麼就像國際象棋一樣的黑白染色，相鄰的人行道一定只會連接於黑跟白之間。

分別計算黑和白的 degree 總數，差的絕對值就是未知街區的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h> 
#include <stdlib.h>
#include <algorithm>
using namespace std;
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int testcase, n, m, x;
//	scanf("%d", &testcase);
    ReadInt(&testcase);
    while (testcase--) {
//		scanf("%d %d", &n, &m);
        ReadInt(&n);
        ReadInt(&m);
        int odd = 0, even = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
//				scanf("%d", &x);
                ReadInt(&x);
                if (x == -1)	continue;
                if ((i+j)&1)
                    odd += x;
                else
                    even += x;
            }
        } 
        printf("%d\n", abs(odd - even));
    }
    return 0;
}
/*
1
3 3
2 2 3
1 -1 3
1 1 0
*/
Read More +
學校課程/資料庫系統

資料庫正規化 Database BCNF

Problem

stackoverflow : Decomposing a relation into BCNF.

資料庫講到正規化，針對 1NF, 2NF, 3NF 的做法。正規化的目的
－要避免資料重複或相互矛盾的情形，並使資料庫在使用時能更有效率、更容易維護。

關於 1NF, 2NF, 3NF 的細節操作就上網查吧。也就是在還沒正規化前，可能會遭遇到

  • 修改一個 f(x) = y 值時，可能修改非常大量的 row，因為有可能 f(x, z) = y，無用相依關係的 z 很多。
  • 刪除某個元素時，造成 y 值沒有被任何相依，導致 y 的資訊無法存入資料庫。 … 如此類推。

現在給定 relation 和 functional dependencies，正規化它們！

舉個例子：(直接從 stackoverflow 的例子來說)

  • Relation : R(A, C, B, D, E)
  • Functional dependencies (FD): A -> B, C -> D

Functional dependencies 簡單來說就是一個決定性的一對多、或者是一對一的相依關係，可以根據 LHS (left hand side) 決策 RHS (right hand side)，當然 function dependencies 的訊息只有部分，也暗示著具有遞移關係。因此例如 A->B, B->C 則可以推論出 A->C 。

定義 X+ 為 X 的遞移閉包，因此假設知道 A->B, B->C 則 {A}+ = {A, B, C} ，假設知道 AB->C 則 {A, B}+ = {A, B, C}

回到例子，每一步要找到違反 BCNF 規則 (violates BCNF) 的 R’ 進行拆分。怎麼樣才算違反 BCNF 規則？可以找到一個 X != X+ != [R’ all attributes] ，就可以對 R’ 進行拆分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Step 1:
S = {ABCDE}       
    R' = ABCDE, 
    find {A} != {A, B} != {A, B, C, D, E}, 
    R1 = (X+) = {A, B}
    R2 = R' - ((X+) - X) = {A, C, D, E}
Step 2:
S = {ACDE, AB}
    R' = ACDE,
    find {C} != {C, D} != {A, C, D, E}, 
    R1 = (X+) = {C, D}
    R2 = R' - ((X+) - X) = {A, C, E}
Step 3:
S = {ACE, AB, CD}
    // NOT FOUND END.

在程式實作 (非人工) 的時候，如何找到 X 滿足上述的條件很重要，由於 X 是所有變數的 subset 情況，相當於 O(2n) ，很多項目是無用的。假如 R’ = ABE ，針對 X = AC 是無效的操作，基本上只要拿所有 function dependencies 的 X = LHS 進行測試即可？這貪心的做法應該是對的。

1
2
3
4
5
6
7
BCNF_Decompose(R)
    find X s.t.: X != (X+) != [all attributes]
    if (not found) then “R is in BCNF”
    let Y = (X+) - X
    let Z = [all attributes] - (X+)
    decompose R into R1(X union Y) and R2(X union Z) 
    continue to decompose recursively R1 and R2

說真的，老師上課講的練習答案還有錯，講算法時也不夠確切，真不知道教授怎麼教的，還是我沒認真上課。當教授發現全班答題有極端的相似錯誤時，到底是我們學不好？還是他沒教好？教授一點都不會反思。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
5 2
A->B
C->D
6 3
AC->B
C->D
A->EF
6 6
AB->C
BC->AD
D->E
CF->B
BC->A
BC->D 
5 3
AB->C
DE->C
B->E

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
A->B
S = {AB, ACDE}
C->D
S = {AB, CD, ACE}
  
C->D
S = {CD, ABCEF}
A->EF
S = {ABC, CD, AEF}
  
AB->C
S = {ABCDE, ABF}
D->E
S = {ABCD, DE, ABF}
  
AB->C
S = {ABD, ABCE}
B->E
S = {ABC, ABD, BE}

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <assert.h>
using namespace std;
#define INF 0x3f3f3f3f
// stackoverflow Database: Decomposing a relation into BCNF
void parsingStmt(string s, string &l, string &r) {
    size_t pos = s.find("->");
    l = s.substr(0, pos);
    r = s.substr(pos + 2);
}
int toBitmask(string s) {
    int ret = 0;
    for (int i = 0; i < s.length(); i++) {
        assert(s[i] >= 'A' && s[i] <= 'Z');
        ret |= 1<<(s[i] - 'A');
    }
    return ret;
}
void printBitmask(int state) {
    for (int i = 0; (1<<i) <= state; i++) {
        if ((state>>i)&1)
            putchar(i + 'A');
    }
}
vector<int> LHS, RHS;
int findFD(int i) {
    int ss = i;
    for (int j = 0; j < LHS.size(); j++) {
        if ((LHS[j]&i) == LHS[j])
            ss |= RHS[j];
    }
    if (ss != i)
    	return findFD(ss);
    return ss;
}
vector<int> decomposing(vector<int> state, int fdlhs, int fdrhs) {
    vector<int> ret;
    for (int i = 0; i < state.size(); i++) { // X->Y
        int X = fdlhs, Y = fdrhs&state[i];
        if (Y != state[i] && (X&state[i]) == X && Y && X && X != Y) {
            ret.push_back(state[i]^X^Y);
            ret.push_back(Y);
        } else {
            ret.push_back(state[i]);
        }
    }
    sort(ret.begin(), ret.end());
    ret.resize(unique(ret.begin(), ret.end()) - ret.begin());
    return ret;
}
void printResult(vector<int> &ret) {
    printf("S = {");
    for (int i = 0; i < ret.size(); i++) {
        printBitmask(ret[i]);
        if (i != ret.size() - 1) {
            printf(", ");
        }
    }
    puts("}");
}
int main() {
    int n, m;
    string s;
    while (cin >> n >> m) {
        LHS.clear(), RHS.clear();
        for (int i = 0; i < m; i++) {
            cin >> s;
            string lhs, rhs;
            parsingStmt(s, lhs, rhs);
            LHS.push_back(toBitmask(lhs));
            RHS.push_back(toBitmask(rhs));
        }
        vector<int> ret;
        int update = 0;
        ret.push_back((1<<n) - 1);
        do {
            update = (int) ret.size();
            for (int i = 0; i < m; i++) {
                ret = decomposing(ret, LHS[i], findFD(LHS[i]));
                if (ret.size() > update) {	
                    printBitmask(LHS[i]);
                	printf("->");
                	printBitmask(RHS[i]);
                	puts("");
                    printResult(ret);
                	break;
                }            
            }
            update = ret.size() > update;
        } while (update);
    }
    return 0;
}
Read More +
學校課程/計算幾何

計算幾何 - HW05

Chapter 10

10.1

In Section 10.1 we solved the problem of finding all horizontal line segments in a set that intersect a vertical segment. For this we used an interval tree with priority search trees as associated structures. There is also an alternative approach. We can use a 1-dimensional range tree on the y-coordinate of the segments to determine those segments whose y-coordinate lies in the y-range of the query segment. The resulting segments cannot lie above or below the query segment, but they may lie completely to the left or to the right of it. We get those segments in O(logn) canonical subsets. For each of these subsets we use as an associated structure an interval tree on the x-coordinates to find the segments that actually intersect the query segment.

a. Give the algorithm in pseudocode.
b. Prove that the data structure correctly solves the queries.
c. What are the bounds for preprocessing time, storage, and query time of this structure? Prove your answers.

給 n 個水平線段，詢問垂直的線段與那些水平線段有相交，輸出所有有相交的線段。

a. Algorithm:

  1. 對 n 個線段建造 interval tree，使用課本上 CONSTRUCTINTERVALTREE(l) 的做法。
  2. 對 interval tree 上每一個 node 建造 Priority Search Tree，node 依照 x 劃分，分別對 node.x 的左右兩側建造 PST，距離 node.x 越遠的端點，其優先權越高，左右子樹依照 y-value 分兩堆。
  3. 詢問調用 QUERYINTERVALTREE(v, qx)，得到相對應的 ndoe 後，查找每個 node 下的 Priority Search tree 與線段相交，調用 QUERYPRIOSEARCHTREE()。

b. Prove that the data structure correctly solves the queries.
上述的作法與 axis-parallel rectangular query window 相同。而此問題的詢問是 axis-parallel rectangular query window 的 subset，一個線段的詢問是 qx = qx’ 的情況，故得證。

c. What are the bounds for preprocessing time, storage, and query time of this structure? Prove your answers.

preprocessing time : O(n log n)
store space : O(n)
query time : O(log n + k)

前處理因 interval tree 最慘 T(n) = 2 T(n/2) + O(n) ，建造 PST 只需要 O(n) ，每個線段最多在兩個 PST 中，得到記憶體空間最多為 O(n) 。詢問最多為 interval tree 的深度 O(log n)

10.2

Let P be a set of n points in the plane, sorted on y-coordinate. Show that, because P is sorted, a priority search tree of the points in P can be constructed in O(n) time.

類似 bottom0up heap construction，已知 bottom-up heap 可在 O(n) 時間內完成。

假設最後的樹高 H，第 i 次的 bottom-up 會調整 2H-i 個元素，每個元素最多下降 i 層。則

$$O(\sum_{i = 1}^{H} i \times 2^{H-i}) = O(1 \times 2^{H-1} + 2 \times 2^{H-2} + ... ) \\ = O((2^{H-1} + 2^{H-2} + ... + 1) + (2^{H-2} + 2^{H-3} + ... + 1) + ...) \\ = O(2^{H} + 2^{H-1} + ... + 1) = O(2^{H+1}) = O(n)$$

雖然要求左右子樹的 y 值要符合左小、右大，但由於已經根據 y 排好，bottom-up 時，保證調整的 shiftdown 操作會符合其性質。

10.6

Let I be a set of intervals on the real line. We want to be able to count the number of intervals containing a query point in O(logn) time. Thus, the query time must be independent of the number of segments containing the query point.

a. Describe a data structure for this problem based on segment trees, which uses only O(n) storage. Analyze the preprocessing time, and the query time of the data structure.
b. Describe a data structure for this problem based on interval trees. You should replace the lists associated with the nodes of the interval tree with other structures. Analyze the amount of storage, preprocessing time, and the query time of the data structure.
c. Describe a data structure for this problem based on a simple binary search tree. Your structure should have O(n) storage and O(logn) query time. (Hence, segment trees are actually not needed to solve this problem efficiently.)

有 n 個 [li, ri]，詢問一個點 x 被多少個區間包含，輸出為一個整數。

a. 使用 segment tree 儲存所有的 interval。

對於其 node(u) 會 cover(l, r) 的區間，紀錄有多少區間 cover(l, r)，最多有 2n 個葉節點，樹節點最多 4n 個，每個 node 只有一個額外的整樹紀錄區間個數。然而一個區間最多被拆分 O(log n) 個，依序插入需消耗共計 O(n log n) 時間。

preprocessing time : O(n log n)
query time : O(log n)
store space : O(n)

b. 使用 inteerval tree 處理 interval。

對於每個 node 分別對左右兩側建造平衡樹，這個平衡樹要支持某數字是第 k 大或第 k 小的操作。對於一個 node 而言，會有數個區間交 node.x，假設詢問點 qx 在 node.x 左側，則根據左側的平衡樹，查找 qx 是第 k 小，用以回報個數。每一個區間對多在 2 個平衡樹中，故空間複雜度為 O(n) 。

preprocessing time : O(n log n)
query time : O(log2 n)
store space : O(n)

c. 使用 simple binary search tree。

  1. 將 n 個線段的端點，共計 2n 個丟入 binary search tree。
  2. 每一個 node 紀錄有多少個區間包含它，如果 node 是某個線段的右端點，則無視此區間的包含情況。
  3. 對於每個詢問 qx，輸出 node = lower_bound(qx) 的包含結果。

將所有端點排序後，會得到 [a0, a1, a2, …, a2n]，每一個 node 的資訊是 [ai, ai+1) 的區間包含訊息。簡單地說，切成最小塊的相鄰資訊，與 segment tree 反過來的概念。

前處理使用 line sweep algorithm 掃描線算法，來找到每一個端點被多少個線段包含。掃描線算法需要 O(n log n) ，binary search tree 只需要 O(n) ，查找 lower_bound 只需要 O(log n) ，保證最多 2n 個端點，樹最多使用 O(n) 個空間。

preprocessing time : O(n log n + n) = O(n log n)
query time : O(log n)
store space : O(n)

10.7

a. We want to solve the following query problem: Given a set S of n disjoint line segments in the plane, determine those segments that intersect a vertical ray running from a point (qx,qy) vertically upwards to infinity. Describe a data structure for this problem that uses O(nlogn) storage and has a query time of O(logn+k), where k is the number of reported answers.
b. Now suppose we only want to report the first segment hit by the query ray. Describe a data structure for this problem with O(n) expected storage and O(logn) expected query time. Hint: Apply the locus approach

給定 n 個不相交的線段，詢問一點開始的射線，射線方向向 y 軸正向，輸出所有交到的線段。

a. 使用 segment tree，依照所有的端點的 x 值，接著對於每個 node 建造以 y 值得 binary search tree，儲存數個線段，因為不相交，保證 binary search tree 在 [xl, xr] 區間的所有線段都是單調的。每個線段最多切成 O(log n) ，故使用空間 O(n log n) ，詢問 O(log n + k) ，只須訪問 O(log n) 個節點，從 binary tree tree 最遠的開始往下輸出即可。

b. 只找第一個碰到的線段，使用 trapezoidal map 找到 point location，走訪 DG 其最後一個 segment below 的情況就是輸出結果。已知 trapezoidal map 在隨機增量算法中，expected size of search structure O(n) ，expected query time O(log n) 。

Chapter 11

11.1

In Chapter 1 we defined the convex hull of a set P of points as the intersection of all convex sets containing the points. In the current chapter we saw another definition: the convex hull of P is the set of all convex combinations of the points in P. Prove that these two definitions are equivalent, that is, prove that a point q is a convex combination of points in P if and only if q lies in every convex set containing P.

首先 convex combinations 指得是$q = \sum_{i = 1}^{n} \lambda_{i} p_{i}, \lambda_{i} \geq 0, \sum_{i = 1}^{n} \lambda_{i} = 1$，證明 q 會在所有的凸包集中，也就是 q 點相當於任抓幾點出來，會在這幾點形成的凸包中，公式計算類似物理上的質心計算。

(=>)$q = \sum_{i = 1}^{n} \lambda_{i} p_{i}, \lambda_{i} \geq 0, \sum_{i = 1}^{n} \lambda_{i} = 1$. Prove q lies in every convex set containing P.

  • Base : $n = 2, q = \lambda_{1} p_{1} + \lambda_{2} p_{2}$, q lies on segment p1p2, which must be a subset of every convex set containing p1, p2.
  • Suppose: $n \le k$ 均成立，當 n = k + 1 時$\lambda_{k+1} = 0$ 必定成立。
$$\begin{align} & q = \lambda_{1} p_{1} + \lambda_{2} p_{2} + ... + \lambda_{k} p_{k} + \lambda_{k+1} p_{k+1} \\ & = (1 - \lambda_{k+1}) \left [ \frac{\lambda_{1}}{1 - \lambda_{k+1}} p_{1} + \frac{\lambda_{2}}{1 - \lambda_{k+1}} p_{2} + ... + \frac{\lambda_{k}}{1 - \lambda_{k+1}} p_{k} \right ] + \lambda_{k+1} p_{k+1} \\ & = (1 - \lambda_{k+1}) ({\lambda_{1}}' p_{1} + {\lambda_{2}}' p_{2} + ... + {\lambda_{k}}' p_{k}) + \lambda_{k+1} p_{k+1} \\ & \text{where } {\lambda_{i}}' = \frac{\lambda_{i}}{1 - \lambda_{k+1}}, \lambda_{1} + \lambda_{2} + ... + \lambda_{k} = 1 - \lambda_{k+1} \\ & \sum_{i = 1}^{k} {\lambda_{i}}' = \sum_{i = 1}^{k} \frac{\lambda_{i}}{1 - \lambda_{k+1}} = \frac{1}{1 - \lambda_{k+1}} \sum_{i = 1}^{k} \lambda{i} = 1 \end{align}$$

Hence, the point${q}' = \sum_{i=1}^{k} {\lambda_{i}}' p_{i}$ is convex combination of p1, p2, …, pk, q’ lies every convex set containing the them.

$q = (1 - \lambda_{k+1}) {q}' + \lambda_{k+1} p_{k+1}$

every convex set containing p1, p2, …, pk, q’. Since it also contains pk+1 the set must contain q as a convex combination of two points.
(<=) Prove q lies in every convex set containing P =>$q = \sum_{i = 1}^{n} \lambda_{i} p_{i}, \lambda_{i} \geq 0, \sum_{i = 1}^{n} \lambda_{i} = 1$
In particular, q lies in the smallest convex set, the convex hull of P. Triangulate the convex hull, q must lie in one of the triangles$\triangle p_{1} p_{2} p_{3}$. Connect q to p1, p2, p3. This partitions the triangle into tree smaller ones.

$$\left\{\begin{matrix} \triangle p_{1} p_{2} p_{3} = A \\ \triangle q p_{2} p_{3} = A_{1} \\ \triangle q p_{1} p_{3} = A_{2} \\ \triangle q p_{1} p_{2} = A_{3} \\ A = A_{1} + A_{2} + A_{3} \end{matrix}\right. \Rightarrow q = \frac{A_{1}}{A} p_{1} + \frac{A_{2}}{A} p_{2} + \frac{A_{3}}{A} p_{3}$$

得證。

11.2

Prove that the worst case running time of algorithm CONVEXHULL is O(n3), and that there are sets of points where a bad choice of the random permutation makes the algorithm actually need Θ(n3) time.

CONVEXHULL 共有三層 for loop.

  • LINE 7 如果每次的新加入的 pi 都在 convex hull 外面，即 Fconflict(pi) 非空。
  • LINE 10$e \in \pounds$，而最多有 i - 1 個，投影的情況下，最多 i 個點都在凸包上，因此最多產生 i - 1 個 facets。
  • LINE 18 對每個新加入的 facets 最多增加 n - i 個 conflict 點。

故最慘 O(n3)。

11.6

Describe a data structure that allows you to test whether a query point q lies inside a convex polytope with n vertices in R3. (Hint: Use the results from Chapter 6.)

快速判斷一個點是否在 3D convex hull 中。

  • 方案一：3D point location by 3D trapezoidal map. 感覺非常難做，弄出很多柱狀體。
  • 方案二：convex hull 最多會有 3n - 6 個面，最多有 3n - 6 個面不等式，判斷是否全在同一側 O(n) 。
  • 方案三：將做好的 3D convex hull，將所有點投影到 x-y 平面，每一個梯形區域會由 2 個 convex hull 的面覆蓋，要不沒有面。對於投影的 2D 建造 trapezoidal map。query 一個點 q 時，先投影到 x-y 平面，找到所在的梯形區域，針對兩面的不等式進行判斷。預處理 O(n log n) ，詢問 O(log n) 。

11.8

Describe a randomized incremental algorithm to compute the intersection of half-planes, and analyze its expected running time. Your algorithm should maintain the intersection of the current set of half-planes. To figure out where to insert a new half-plane, maintain a conflict graph between the vertices of the current intersection and the half-planes that are still to be inserted.

  • 維護半平面 hi 與 Sj 的相交資訊。

  • add half-place
    繞外部 (半平面的另一側的凸包邊) 的 edge e，將 hconflict(e) 移除掉 intersection(e, hconflict(e)) in$\bar{h_{i}}$。
    期望值的複雜度依賴中間過程中產生的交集點個數。

  • 假設 c(H, h) 表示 inter(H) 和 h 的 conflict vertice 個數。
    則$\sum_{i = 1}^{n} \left [ \frac{2}{i} \sum_{h \in S \setminus S_{i} }{c(H, h)} \right ]$－所有的花費。

$$E[c(S_{i}, h_{i})] = \frac{1}{n-i} \sum_{h \in S \setminus S_{i} } c(S_{i}, h) \\ \Rightarrow \sum_{i = 1}^{n} \left ( \frac{2}{i} \sum_{h \in S \setminus S_{i} }{c(H, h)} \right ) = \sum_{i = 1}^{n} \left ( \frac{2}{i} \sum_{h \in S \setminus S_{i} }{E(S_{i}, h_{i-1})} \right ) \\ = \sum_{i = 1}^{n} \left ( \frac{2}{i} (n - i) E(S_{i}, h_{i-1}) \right ) = \sum_{i = 1}^{n} \left ( \frac{2(n-i)}{i} E[\text{the number of of vertices destroy ed at i+1}] \right )$$

對於每一個 vertice v 被創建的時間為 tc(v), 被移除的時間 td(v)。

$$\sum_{i = 1}^{n} \left ( \frac{2(n-i)}{i} E[\text{the number of vertices destroy ed at i+1}] \right ) \\ = \sum_{v} \frac{2(n - td(v) + 1)}{td(v) - 1} \le \sum_{v} \frac{2(n - tc(v)) + 2}{tc(v)} \\ \le \sum_{n}^{i=1} \frac{2(n - i) + 2}{i} E[\left |v \mid tc(v) = i \right |] \\ = \sum_{n}^{i=1} \frac{2(n - i) + 2}{i} \times 2 = O(\sum_{n}^{i=1} \frac{n}{i} - 1) = O(n ln n)$$

得證。

Read More +
解題區/解題區 - UVa

UVa 10266 - Surveying

Problem

從隨機幾點進行觀察，可以知道其相對高度。

現在給定數組觀察的部分紀錄，求在某一點的觀察的數據，如果可以得到完整的則輸出整個地圖的相對高度，如果不齊全、或者發生矛盾，則參考範例輸出。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3
2 2
1 2
1 1 10 1 2 10
1 2 20 2 2 30 2 1 30
2 2
1 1
1 1 10 1 2 10
2 2
1 2
1 1 10 1 2 10
1 1 20 1 2 30

Sample Output

1
2
3
4
5
6
0 0
10 10
the lack of measurements
conflicting measurements

Solution

不斷地部分記錄進行更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
#define MAXN 128
vector<int> g[MAXN][MAXN];
struct Survey {
    int x, y, h;
    Survey(int a = 0, int b = 0, int c = 0):
    x(a), y(b), h(c) {}
};
vector< vector<Survey> > D;
int n, m;
int spfa(int sx, int sy) {
    int ret[MAXN][MAXN], used[MAXN][MAXN] = {};
    vector<int> sid;
    sid.resize(D.size(), 0);
    int x, y, h, id, tx, ty;
    queue<int> X, Y, ID;
    used[sx][sy] = 1, ret[sx][sy] = 0;
    for (int i = 0; i < g[sx][sy].size(); i++) {
        int u = g[sx][sy][i];
        X.push(sx), Y.push(sy), ID.push(u);
        sid[u] = 1;
    }
    while (!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        id = ID.front(), ID.pop();
        int shift = 0;
        for (int i = 0; i < D[id].size(); i++) {
            if (D[id][i].x == x && D[id][i].y == y) {
                shift = ret[x][y] - D[id][i].h;
                break;
            }
        }
        for (int i = 0; i < D[id].size(); i++) {
            tx = D[id][i].x, ty = D[id][i].y;
            h = D[id][i].h + shift;
            if (used[tx][ty] && h != ret[tx][ty])
                return 0;
            ret[tx][ty] = h;
            if (used[tx][ty] == 0) {
                used[tx][ty] = 1;
                for (int j = 0; j < g[tx][ty].size(); j++) {
                    int u = g[tx][ty][j];
                    if (sid[u]) continue;
                    X.push(tx), Y.push(ty), ID.push(u);
                    sid[u] = 1;
                }
            }
        }
    }
    
    int ok = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ok &= used[i][j];
        }
    }
    if (ok) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                printf("%d%c", ret[i][j], j == m ? '\n' : ' ');
            }
        }
    } else {
        puts("the lack of measurements");
    }
    return 1;
}
char line[1048576 * 8];
int main() {
    int testcase, bx, by;
    int x, y, h;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        scanf("%d %d", &bx, &by);
        while (getchar() != '\n');
        
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                g[i][j].clear();
        D.clear();
        while (gets(line)) {
            if (line[0] == '\0')   break;
            stringstream sin(line);
            int id = (int) D.size();
            vector<Survey> item;
            while (sin >> x >> y >> h) {
                item.push_back(Survey(x, y, h));
                g[x][y].push_back(id);
            }
            D.push_back(item);
        }
        int f = spfa(bx, by);
        if (!f) {
            puts("conflicting measurements");
        }
        if (testcase)
            puts("");
    }
    return 0;
}
/*
 3
 
 2 2
 1 2
 1 1 10 1 2 10
 1 1 20 2 2 30 2 1 30
 
 2 2
 1 1
 1 1 10 1 2 10
 
 2 2
 1 2
 1 1 10 1 2 10
 1 1 20 1 2 30
 */
Read More +
解題區/解題區 - UVa

UVa 10253 - Series-Parallel Networks

Problem

給定 N 條邊，去除掉同構的情況，請問有多少個不同的串并連網路。

Sample Input

1
2
3
4
1
4
15
0

Sample Output

1
2
3
1
10
1399068

Solution

首先，拆分結果可以依序按照串－并－串－并 … 或者并－串－并－串 …

這樣會形成樹圖，其中奇數層是串/并，而偶數層是并/串，如此一來，要找到 N 個葉節點的樹有多少不同種的。根據兩種不同的分層方式，隨後乘上 2 就是答案。

定義 dp[i][j] 表示總共有 j 個葉節點的樹，並且每個子樹的葉節點最多 i 個 (至少)。這麼定義有它的好處，而不去直接定義 恰好 。

接著組合其具有 k 個樹－其子樹最多 i 個葉節點，剩下不足的葉節點，弄成一個樹，使用重複排列防止重複的計算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h> 
#include <algorithm>
using namespace std;
long long dp[32][32] = {};
/*
parallel/series
consider parallel/series operation -> node, 
n-edge == counting number of tree with n-leaf node.
dp[i][j]: at most i-leaves in subtree, total j-leaves.
dp[i][j] = \sum C(ret[i] + k - 1, k) \times dp[i-1][j - i*k]
				^^^^^^^^^^^^^^^^^^^^[1]		^^^^^^^^^^^^^^^[2]
[1]: pick k subtree with at most (i-1)-leaves, total i-leaves
[2]: a subtree with at most (i-1)-leaves, total (j-i*k)-leaves
*/
long long C(long long n, long long m) {
    long long ret = 1;
    m = min(m, n-m);
    for (long long i = 1; i <= m; i++)
        ret = ret * (n + 1 - i) / i;
    return ret;
}
int main() {
    
    long long ret[32] = {};
    ret[1] = 1;
    for (int i = 1; i <= 30; i++)
        dp[0][i] = 0, dp[i][1] = 1;
    for (int i = 0; i <= 30; i++)
        dp[i][0] = 1;
    for (int i = 1; i <= 30; i++) {
        for (int j = 2; j <= 30; j++) {
            for (int k = 0; i * k <= j; k++) {
                dp[i][j] += C(ret[i] + k - 1, k) * dp[i-1][j - i*k];
            }
        }
        ret[i+1] = dp[i][i+1];
    }
    
    int n;
    while (scanf("%d", &n) == 1 && n)
        printf("%lld\n", n == 1 ? 1 : ret[n] * 2);
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1482 - Playing With Stones

Problem

有 N 堆石頭，每次選一堆，只能不能拿大於一半的石頭總數。

求兩個人都採用最佳策略，請問誰輸誰贏。

Sample Input

1
2
3
4
5
6
7
8
9
4 
2 
4 4 
3 
1 2 3
3 
2 4 6
3 
1 2 1

Sample Output

1
2
3
4
NO 
YES 
NO 
YES

Solution

建造 SG 函數進行觀察，接著直接套用 SG 函數的 nim 規則。

關於 SG

让我们再来考虑一下顶点的SG值的意义。当g(x)=k时，表明对于任意一个0<=i<k，都存在x的一个后继y满足g(y)=i。也 就是说，当某枚棋子的SG值是k时，我们可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。不知道你能不能根据这个联想到Nim游戏， Nim游戏的规则就是：每次选择一堆数量为k的石子，可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。这表明，如果将n枚棋子所在的顶 点的SG值看作n堆相应数量的石子，那么这个Nim游戏的每个必胜策略都对应于原来这n枚棋子的必胜策略！

http://baike.baidu.com/view/2855458.htm

Sprague-Grundy 圖示演說參考

對於博弈，一直以來盡可能靠記憶化搜索 dp 完成，寫題基本上也還算過得去，在大數據的題目上，除了幾個噁心的數學分析外，利用記憶化搜索進行小數據觀察，真的沒搞頭的題目，大多解法是所謂的 SG 函數 (Sprague-Grundy)。

再不學點新的，就要沒有看得懂的題目可以刷了 … 如果因為看不懂題目，而增加對英文的仇恨值，都不知道溢位幾個世紀去了。

SG 函數簡單而言是對於針對某一類型的博弈遊戲，可以轉換成 Nim 遊戲，每一個 SG 函數的 value 對應 Nim 遊戲中一堆石頭的個數。新世界！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <string.h>
void buildSG() { // observe rule
    int mex[1024] = {}, SG[50];
    SG[0] = 0;
    for (int i = 1; i < 50; i++) {
        memset(mex, 0, sizeof(mex));
        for (int j = 1; j <= i/2; j++)
            mex[SG[i - j]] = 1;
        int sg = 0;
        for (sg = 0; mex[sg]; sg++);
        SG[i] = sg;
        printf("%d : %d\n", i, SG[i]);
    }
}
long long SG(long long x) {
    return x%2 == 1 ? SG(x/2) : x/2; 
}
int main() {
//	buildSG();
    int testcase, n;
    long long x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            ret ^= SG(x);
        }
        puts(ret ? "YES" : "NO");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1404 - Prime k-tuple

Problem

查找區間內，相鄰 k 個質數中，滿足最大減最小恰好為 s 的情況有多少個。

Sample Input

1
2
1
100 200 4 8

Sample Output

1
2

Solution

a, b 大小簡直不可思議，就算能做到全搜索，建表時間是線性，也必須跑上 20 億乘上 20。

先做一次 sieve，接著對 [a, b] 進行 local sieve，題目雖然沒說明 b - a 的大小，實際看來是非常小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
#define maxL (50000>>5)+1
#define MAXN (2000000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
#define GET2(x) (mark2[x>>5]>>(x&31)&1)
#define SET2(x) (mark2[x>>5] |= 1<<(x&31))
int mark[maxL], mark2[MAXN];
int P[5500], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 50000;
    for(i = 2; i <= n; i++) {
            if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
int local_sieve(int a, int b, int k, int s) {	
    int sqr = sqrt(b), gap = b - a;
    memset(mark2, 0, ((gap>>5) + 1) * 4);
    
    for (int i = 0; i < Pt && P[i] <= sqr; i++) {
        int p = P[i], base = a / p * p;
        while (base <= p)	base += p;
        for (int j = base; j <= b; j += p)
            SET2(j - a);
    }
    if (a == 1)	SET2(0);
    queue<int> Q;
    int ret = 0;
    for (int i = 0; i <= gap; i++) {
        if (!GET2(i)) {
            if (Q.size() == k - 1) {
                if (k == 0)
                    ret += s == 0;
                else if ((a + i) - Q.front() == s)
                    ret++;
            }
            Q.push(a + i);
            while (Q.size() >= k)	Q.pop();
        }
    }
    return ret;
}
int main() {
    sieve();
    
    int testcase;
    int a, b, k, s;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d %d", &a, &b, &k, &s);
        printf("%d\n", local_sieve(a, b, k, s));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1291 - Dance Dance Revolution

Problem

跳舞機共有四個方向，兩隻腳必須在某一個時刻按到該按鈕。

1
2
3
#1#
204
#3#

一開始雙腳站立於 0 的位置，每一個時刻只能移動一隻腳。

每一次移動的花費，0 到任何位置都是消耗體力 2、其餘數字移動到相鄰格子消耗體力 3、其餘數字移動到相面格子消耗體力 4，腳不動消耗體力 1。

過程中雙腳不能站立於同一個格子。

Sample Input

1
2
3
1 2 2 4 0 
1 2 3 4 1 2 3 3 4 2 0 
0

Sample Output

1
2
8 
22

Solution

dp[i][j][k] 分別記錄時刻 i，左腳所在位置 j，右腳所在位置 k。分別進行轉移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int A[32767];
int cg[5][5] = {
    {0, 2, 2, 2, 2},
    {INF, 1, 3, 4, 3},
    {INF, 3, 1, 3, 4},
    {INF, 4, 3, 1, 3},
    {INF, 3, 4, 3, 1}
};
int main() {
    while (scanf("%d", &A[0]) == 1 && A[0]) {
        int n = 1;
        for (; scanf("%d", &A[n]) && A[n]; n++);
        int dp[2][5][5]; // [][left][right]
        memset(dp, 0x3f, sizeof(dp));
        int p = 0, q = 1;
        dp[p][0][0] = 0;
        for (int i = 0; i < n; i++) {
            p = !p, q = !q;
            memset(dp[p], 0x3f, sizeof(dp[p]));
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    int l = A[i];
                    if (j != l) {
                        dp[p][j][l] = min(dp[p][j][l], dp[q][j][k] + cg[k][l]);
                    }
                    if (k != l) {
                        dp[p][l][k] = min(dp[p][l][k], dp[q][j][k] + cg[j][l]);
                    }
                    if (j == l || k == l) {
                        dp[p][j][k] = min(dp[p][j][k], dp[q][j][k] + 1);
                    }
                }
            }
        }
        
        int ret = INF;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                ret = min(ret, dp[p][i][j]);
            }
        }
        
        printf("%d\n", ret);
    }
    return 0;
}
/*
 1 2 2 4 0
 1 2 3 4 1 2 3 3 4 2 0
 0
 */
Read More +
解題區/解題區 - UVa

UVa 1267 - Network

Problem

有一個 N 節點的樹，要架設服務的 server，必須滿足所有葉節點到最近的 server 距離小於等於 M。一開始會給定一個架好的 server。

求最少的放置個數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2 14 
12 2 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11 
14 
3 4 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11

Sample Output

1
2
1 
0

Solution

針對加好的 server，將這個 server 當作 root，將 tree 轉換成 rooted tree，接著使用貪心。

盡可能放置越遠越好，根據 dfs 搜索的順序，查看內部節點 u，其子樹最遠的葉節點深度為何，以及子樹內部距離最近的 server 所在。

共計三種可能

  • 節點 u 逼不得已情況下放置 server
  • 節點 u 無須 server，其子樹的葉節點都已經符合標準
  • 節點 u 無須 server，其子樹的葉節點必須靠另外一個子樹的最近 server 服務。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int n, m, s, x, y;
int ret = 0;
int dfs(int u, int p, int dep, int &place) {
    int leaf = 0, pp = 0x3f3f3f3f;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == p)
            continue;
        int p;
        int tmp = dfs(v, u, dep + 1, p);
        pp = min(p, pp);
        leaf = max(leaf, tmp);
    }
    place = pp;
    if (leaf - dep + pp - dep <= m)
        leaf = 0;
    if (leaf == dep + m) {
        place = dep;
        ret += (u != s), leaf = 0/*, printf("place %d, %d\n", u, place)*/;
    }
    if (g[u].size() == 1)
        return dep;
    else
        return leaf;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &n, &s, &m);
        for (int i = 0; i <= n; i++)
            g[i].clear();
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        
        ret = 0;
        int foo;
        dfs(s, -1, 0, foo);
        printf("%d\n", ret);
    }
    return 0;
}
/*
2 
14 12 2 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11 
14 3 4 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11
*/
Read More +