解題區/解題區 - UVa

UVa 12809 - Binary Search Tree

Problem

類似 UVa 10304 - Optimal Binary Search Tree，給每個節點的拜訪頻率，建造一個二元樹，使得詢問次數最小化。

Sample Input

1
2
3
4
5
6
3
0.33 0.34 0.33
3
0.8 0.15 0.05
4
0.23 0.4 0.17 0.2

Sample Output

1
2
3
1.6600
1.2500
1.7700

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
#include <stdio.h> 
#include <string.h> 
double f[128];
double sum[128], w[128][128];
double dp[128][128];
int arg[128][128];
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++)
            scanf("%lf", &f[i]);
        sum[0] = 0;
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i-1] + f[i];
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
                w[i][j] = sum[j] - sum[i - 1];
        for (int i = 0; i <= n; i++)
            dp[i][i] = 0, arg[i][i] = i;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; i + j <= n; j++) {
                double mn = 1e+30;
                int idx = -1;
                for (int k = arg[j][i+j-1]; k <= arg[j+1][i+j]; k++) {
                    double t = dp[j][k-1] + dp[k+1][i+j] + w[j][k-1] + w[k+1][i+j];
                    if (t < mn)
                        mn = t, idx = k;
                }
                dp[j][i+j] = mn, arg[j][i+j] = idx;
            }
        }
        printf("%lf\n", dp[1][n] + 1);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12786 - Friendship Networks

Problem

類似 UVa 10720 - Graph Construction，給一個無向圖的每一個節點 degree，請問是否能構成圖。

Sample Input

1
2
3
4 3 2 2 3
4 1 3 2 3
8 2 5 4 5 4 3 5 2

Sample Output

1
2
3
1
0
1

Solution

使用公式加二分。

Erdős–Gallai theorem

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
#include <stdio.h>
#include <algorithm>
#include <functional>
using namespace std;
int n, i, k;
long long sum[1005], d[1005];
int main() {
    while(scanf("%d", &n) == 1 && n) {
        sum[0] = 0;
        for(i = 0; i < n; i++)
            scanf("%lld", &d[i]);
        sort(d, d+n, greater<int>());
        for(i = 0; i < n; i++)
            sum[i+1] = sum[i] + d[i];
        long long left = 0, right;
        int ret = 1;
        if(sum[n]&1)    ret = 0;
        for(k = 0; k < n; k++) {
            left += d[k];
            right = (long long)k * (k+1);
            int l =  lower_bound(d , d + n, k+1, greater<int>()) - d;
            if(l < k+1)
                right += sum[n] - sum[k+1];
            else
                right += sum[n] - sum[l] + (long long)(k+1)*(l - k - 1);
            if(left > right)	ret = 0;
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12776 - Query for Divisor-free Numbers

Problem

給一個序列 A，請問在 A[l:r] 中 A[i] 不被 A[j] 整除的個數為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2
10 5
4 6 2 7 5 11 14 21 13 2
2 6
4 8
2 8
3 7
4 9
5 3
4 6 8 1 5
1 5
2 3
3 3

Sample Output

1
2
3
4
5
6
7
8
9
10
Case 1:
4
3
4
4
4
Case 2:
1
2
1

Solution

首先先貪心 A[i]，找到左側最鄰近的因數、右側最鄰近的因數的位置找出 L[i], R[i]。

以下使用 binary indexed tree 進行區域操作。

然後對於詢問 [l, r] 事先讀進來，加入掃描線算法，確保能夠詢問 [l, r] 時，找尋 BIT[r] 的值為何。

掃描時，當我們遇到某個因數所展開的區間 [L[i], R[i]] 的左端點

  • 對於 BIT[i, R[i]] 範圍元素都加上 1，而在遇到區間對應的 A[i] 位置進行移除區間 (不用等到右端點，必須在中間就移除掉，確保查詢的時 A[i] 還在裡面)，BIT[i, R[i]] 範圍元素都減去 1。
  • 對於遇到詢問 [l, r] 的左端點時，詢問 BIT[r] 的值為何。

因此資料結構要維護

  • 將一個區間內的元素都加上 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
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define maxL (50000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[32767], 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;
        }
    }
}
vector< pair<int, int> > factor(int n) {
    int on = n;
    vector< pair<int, int> > R;
    
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {		
            for(j = 0; n%P[i] == 0; n /= P[i], j++);
            R.push_back(make_pair(P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
void make(int idx, int n, int m, vector< pair<int, int> > &v, vector<int> &ret) {
    if(idx == v.size()) {
        ret.push_back(m);
        return;
    }
    int a = m, b = v[idx].first;
    for(int i = v[idx].second; i >= 0; i--)
        make(idx + 1, n, a, v, ret), a *= b;
}
int A[131072], L[131072], R[131072];
vector<int> Af[131072], RM[131072];
vector< pair<int, int> > Q[131072], QL[131072];
int OUT[131072];
int BIT[131072];
void modify(int x, int val, int L) {
    while (x <= L) {
        BIT[x] += val;
        x += (x)&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += BIT[x];
        x -= (x)&(-x);
    }
    return ret;
}
int main() {
//		freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    sieve();
    int testcase, cases = 0;
    int n, m, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &A[i]);
            vector< pair<int, int> > f = factor(A[i]);
            Af[i].clear();
            make(0, A[i], 1, f, Af[i]);
        }
        for (int i = 0; i < n + 20; i++)
            Q[i].clear(), QL[i].clear(), RM[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            Q[x].push_back(make_pair(y, i));
        }
        map<int, int> mp;
        map<int, int>::iterator mpit;
        for (int i = 1; i <= n; i++) {
            x = 0;
            for (int j = 0; j < Af[i].size(); j++)
                x = max(x, mp[Af[i][j]]);
            mp[A[i]] = i;
            L[i] = x + 1;
        }
        mp.clear();
        for (int i = n; i >= 1; i--) {
            x = n + 1;
            for (int j = 0; j < Af[i].size(); j++) {
                mpit = mp.find(Af[i][j]);
                if (mpit != mp.end())
                    x = min(x, mpit->second);
            }
            mp[A[i]] = i;
            R[i] = x - 1;
        }
        for (int i = 1; i <= n; i++) {
            QL[L[i]].push_back(make_pair(R[i], i));
            RM[i].push_back(R[i]);
        }
        for (int i = 1; i <= n + 20; i++)
            BIT[i] = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < QL[i].size(); j++) {
                modify(QL[i][j].second, 1, n + 20);
                modify(QL[i][j].first + 1, -1, n + 20);
//				printf("add [%d %d]\n", QL[i][j].second, QL[i][j].first);
            }
            if (i)
            for (int j = 0; j < RM[i-1].size(); j++) {
                modify(i-1, -1, n + 20);
                modify(RM[i-1][j] + 1, 1, n + 20);
//				printf("rm [%d %d]\n", i-1, RM[i][j]);
            }
            for (int j = 0; j < Q[i].size(); j++) {
                int v = query(Q[i][j].first);
                OUT[Q[i][j].second] = v;
//				printf("%d %d - %d\n", Q[i][j].first, Q[i][j].second, v);
            }
//			puts("--");
        }
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < m; i++)
            printf("%d\n", OUT[i]);
    }
    return 0;
}
/*
2
10 5
4 6 2 7 5 11 14 21 13 2
2 6
4 8
2 8
3 7
4 9
5 3
4 6 8 1 5
1 5
2 3
3 3
*/
Read More +
解題區/解題區 - UVa

UVa 12775 - Gift Dilemma

Problem

找到 Ax + By + Cz = P, 給定 A, B, C, P，要求 (x, y, z) 有幾組解，並且 x >= 0, y >= 0, z >= 0。

Sample Input

1
2
1
202 203 200 606

Sample Output

1
Case 1: 2

Solution

看一下數據範圍 0 < A, B, C, P <= 100000000，C / gcd(A, B, C) >= 200，後者是強而有力的條件，肯定 z 情況最多 100000000/200 = 500000 個可能，窮舉 z 的情況，用擴充歐基里德找到 Ax + By = (P - Cz) 的解個數。

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
#include <stdio.h> 
long long exgcd(long long x, long long y, long long &a, long long &b) {
    // ax + by = gcd(x,y)
    int flag = 0;
    long long t, la = 1, lb = 0, ra = 0, rb = 1;
    while(x%y) {
        if(flag == 0)
            la -= x/y*ra, lb -= x/y*rb;
        else
            ra -= x/y*la, rb -= x/y*lb;
        t = x, x = y, y = t%y;
        flag = 1 - flag;
    }
    if(flag == 0)
        a = ra, b = rb;
    else
        a = la, b = lb;
    return y;
}
long long countSolution(long long n1, long long n2, long long n) {
    long long a, b, g;
    g = exgcd(n1, n2, a, b); // a*n1 + b*n2 = gcd(n1,2)
    if(n%g) return 0;
    long long k = n/g, k1, k2;
    a *= k, b *= k;// a*n1 + b*n2 = n
    // (a+F)*n1 + (b+G)*n2 = n =>  Fn1 + Gn2 = 0,
    //F = lcm(n1, n2)/n1 * i, G = lcm(n1, n2)/n2 * i
    k1 = n1*n2/g/n1, k2 = n1*n2/g/n2;
    if(a < 0) { // adjust a >= 0
        k = -(a/k1) + (a%k1 != 0);
        a += k*k1, b -= k*k2;
    }
    if(b < 0) { // adjust b >= 0
        k = -(b/k2) + (b%k2 != 0);
        a -= k*k1, b += k*k2;
    }
    if(a < 0 || b < 0) return 0;
    long long x1, x2, y1, y2;
    // minimize a, maximize b
    k = a/k1;
    a -= k*k1;
    b += k*k2;
    x1 = a, y1 = b;
    // maximize a, minimize b
    k = b/k2;
    a += k*k1;
    b -= k*k2;
    x2 = a, y2 = b;
    return (x2 - x1) / k1 + 1;
}
int main() {
    int testcase, cases = 0;
    long long A, B, C, P, ret, ta, tb;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld %lld %lld %lld", &A, &B, &C, &P);
        long long g = exgcd(exgcd(A, B, ta, tb), C, ta, tb);
        P /= g, A /= g, B /= g, C /= g;
        ret = 0;
        for (long long i = 0; P - C * i >= 0; i++)
            ret += countSolution(A, B, P - C * i);
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
1
202 203 200 606
*/
Read More +
解題區/解題區 - UVa

UVa 12607 - Amazing Maze

Problem

在一個迷宮中有 M x N 個房間，每個房間有四個門，並且以逆時針的順序依次出現，每一個時間每個房間只會有一個門通往另一個地方。

必須從左上角開始，花最少時間收集到 K 個寶物後抵達右下角。

Sample Input

1
2
3
4
5
6
2 2
EE
NN
1
1 2
0 0

Sample Output

1
2

Solution

分析狀態，由於 K 不大，直接 2^K 狀態下去，而只會有四個門，因此時間論替只需要考慮 mod 4 的結果，最後 dist[x][y][4][1<<8] 抵達 (x, y) 時的門狀態、同時身上帶了多少寶物 (用 bitmask 去壓縮)。

BFS 一下就過去，記得要注意可以在同一個房間內等待下一個時刻。

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 <algorithm>
#include <queue>
#include <assert.h>
using namespace std;
const int dx[] = {-1, 0, 1, 0}; // N E S W 
const int dy[] = {0, 1, 0, -1};
int used[100][100][4][1<<8] = {}, testcase = 0;
int dist[100][100][4][1<<8] = {};
int main() {
    int N, M, K, x, y;
    char g[128][128];
    while (scanf("%d %d", &N, &M) == 2 && N+M) {
        int treasure[128][128] = {}, dirg[128][128] = {};
        for (int i = 0; i < N; i++) {
            scanf("%s", g[i]);
            for (int j = 0; j < M; j++) {
                if (g[i][j] == 'N')
                    dirg[i][j] = 0;			
                if (g[i][j] == 'E')
                    dirg[i][j] = 1;	
                if (g[i][j] == 'S')
                    dirg[i][j] = 2;	
                if (g[i][j] == 'W')
                    dirg[i][j] = 3;
            }
        }
        scanf("%d", &K);
        for (int i = 0; i < K; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            assert(treasure[x][y] == 0);
            treasure[x][y] = i + 1;
        }
        queue<int> X, Y, D, T;
        int x = 0, y = 0, d = 0, t = 0;
        int tx, ty, td, tt;
        if (treasure[x][y])
            t |= 1<<(treasure[x][y] - 1);
        X.push(x), Y.push(y), D.push(d), T.push(t);
        testcase++;
        used[x][y][d][t] = testcase;
        dist[x][y][d][t] = 0;
        while (!X.empty()) {
            x = X.front(), X.pop();
            y = Y.front(), Y.pop();
            d = D.front(), D.pop();
            t = T.front(), T.pop();	
                    
            tx = x, ty = y, td = (d + 1)%4, tt = t;
            if (used[tx][ty][td][tt] != testcase) {
                used[tx][ty][td][tt] = testcase;
                dist[tx][ty][td][tt] = dist[x][y][d][t] + 1;
                X.push(tx), Y.push(ty), D.push(td), T.push(tt);
                if (tx == N - 1 && ty == M - 1 && tt == (1<<K) - 1)
                    break;
            }
            
            int dir = (dirg[x][y] + d)%4;
            tx = x + dx[dir], ty = y + dy[dir], td = (d + 1)%4, tt = t;
            if (tx < 0 || ty < 0 || tx >= N || ty >= M)
                continue;
            if (treasure[tx][ty])
                tt |= 1<<(treasure[tx][ty] - 1);
            if (used[tx][ty][td][tt] != testcase) {
                used[tx][ty][td][tt] = testcase;
                dist[tx][ty][td][tt] = dist[x][y][d][t] + 1;
                X.push(tx), Y.push(ty), D.push(td), T.push(tt);
                if (tx == N - 1 && ty == M - 1 && tt == (1<<K) - 1)
                    break;
            }
        }
        int ret = 0x3f3f3f3f;
        for (int i = 0; i < 4; i++) {
            if (used[N-1][M-1][i][(1<<K)-1] == testcase)
                ret = min(ret, dist[N-1][M-1][i][(1<<K)-1]);
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
2 2
EE
NN
1
1 2
1 1
E
1
1 1
1 2
NE
1
1 2
0 0
*/
Read More +
學校課程/計算幾何

計算幾何 - 期中考練習

  1. (15 points total)
    a. (10 points) Given a set of points that are presorted by their x-coordinate value, provide an algorithm that computes the convex hull of these points in O(n).
    b. (5 points) If more than 2 points are possibly on an edge of convex hull, explain briefly how your algorithm handles this case.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) 
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    for(i = n-1, t = m+1; i >= 0; i--) 
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    return m - 1;
}

會將三點一線段的中間那一點替除掉，直到一個線段上只經過兩個點。

  1. (20 points total)
    a. (5 points) What are the types of event points in the plane sweep algorithm for line segment intersection problem?
    b. (10 points) Explain briefly when each type of event points is inserted to the event queue. Create a simple example (with 2 line segments) to demonstrate how it works.
    c. (5 points) When will the plane sweep algorithm for line segment intersection problem not suitable? Give a quantitative answer (i.e., describe your answer by using the Big-O notations). In addition, why is applying plane sweep algorithm on subdivision overlay in general a good idea?
  • 掃描時遇到的三種情況
    1. 碰到開始的左端點 (加入此線段)
    2. 碰到結束的右端點 (移除此線段)
    3. 碰到線段之間的交點 (預測下個最近的相交點後，將其包含這個交點線段移除後，重新加入)
  • 很簡單的，請參考上述三種情況繪製。
  • 當交集的數量在$\Theta(n^{2})$ 的時候，複雜度是$\Theta(n^{2}log n)$，還不如直接窮舉任兩個線段計算交點$\Theta(n^{2})$，就算要去重複，常數也比掃描線算法來得低。
  1. (20 points total)
    a. (10 points) Draw a simple polygon with 4 different types of vertices. Mark each vertex with its type. In addition, which two out of these 4 types are NOT allowed in a y-monotone piece?
    b. (5 points) Mark the “helper” for each of the vertices in your part (a) simple polygon that are not allowed in a y-monotone piece.
    c. (5 points) The triangulation of a y-monotone piece (with n vertices) can be done in linear time. Explain briefly why.
  • start, split, end, merge, regular vertex 明明有五種！
  • split, merge vertex 不符合 y-monotone piece
  • 加入 helper，對於 split 而言要往下找 split 或者是 regular vertex 相連，對 merge 而言要往上找 merge 或者是 regular 相連。
  • 因為往左可以根據維護凹性在 O(n) 時間內完成三角化，同理往右走訪。
  1. (20 points total)
    a. (5 points) What is the worst-case time complexity for the algorithm that solves the 2-dimensional linear programming problem?
    b. (5 points) Simplex algorithm is known to solve the linear programming problem in Operational Research. Why don’t we simple apply Simplex algorithm for the 2-dimensional linear programming problem?
    c. (10 points) Let (H, c) be a linear program. We number the half-planes h1, h2,…, hn. Let Hi be the set of the first i constraints, together with the special constraints m1 and m2 (i.e., the bound so that the solution space is limited). Let vi be the optimal point in Hi that satisfies the constraints. Explain why vi = vi-1 if vi-1 is contained in hi.

*$O(n^{2})$ incremental LP problem，每加入一個半平面，都必須重新計算最佳交集。

  • Simplex algorithm O(n log n)，在 2D 限制下，可以做到 O(n)。
  • 其實這是一個廢話，因為 hi 加上去，只會讓最佳解更糟，如果最佳解沒變，那麼最佳解仍然維持。
  1. (15 points total)
    a. (10 points) Briefly explain what a “split node” is. Create a balanced one-dimensional search tree with 8 leave nodes to be “1”, “2”, “3”, “4”, “5”, “6”, “7”, and “8”, and a range query [2, 6] to show where the split node is and how it helps to find all numbers in the range.
    b. (5 points) Both kd-trees and range trees are designed to do range query. Give one scenario that the kd-trees should be used and another scenario that the range trees should be adopted.
1
2
3
4
5
6
7
8
9
           [4]
          /   \
         /     \
        /       \
     [2]        [6]
    /   \       / \
  [1]  [3]    [5]  \
  /\    /\     /\   \
[1][2][3][4] [5][6] [7]

找到其中一邊的 split node 的寫法如下：

1
2
3
4
5
6
v = root
while v is not leaf && (r <= xv || xv' > l)
    if l <= xv'
        v = lc(v)
    else
        v = rc(v)

最後我們找到兩個 split node [1], [7]，在兩個 split node 之間的葉節點都是答案，對於葉節點可以利用建造時，使用一個 linked list 去完成。

  • 對於多維度範圍查找用 range tree 最好，可以保證在$O(log^{d} n)$ 以內找到解，kd-tree 在這種情況很容易退化。
  • 對於最鄰近點搜索則是使用 kd-tree 最好，range tree 反而沒辦法支持這種操作。
  1. (20 points)
    a. (5 points) Draw the trapezoidal map of the following given figure. Note that the bounding box is provided already. (Give each trapezoid a number, which will be used in part (b).)
    b. (10 points) Follow the algorithm to construct the search structure D for the trapezoidal map in part a). The segments are inserted in the order of s4, s3, s2, and s1.
    c. (5 points) In the trapezoidal algorithm, the endpoints of line segments are assumed to have different x-coordinate value (i.e., so-called general position). While a method was provided to relax this constraint, explain briefly why the composite-number method (i.e., transform (x, y) to (x|y, y|x)) which has been used in kd-trees and range trees to deal with the similar constraint was not adopted?
  • 因為它們是 range query，對於相同的 x 值仍然要算相同，利用偏斜的效果不利於操作。
Read More +
學校課程/計算幾何

計算幾何 - HW03

Master Theorem

$$T(n) = \begin{cases} aT(n/b) + n^{c} & \text{ if } n > 1 \\ d & \text{ if } n = 1 \end{cases}$$

1.$\text{if } log_{b}a < c, T(n) = \theta(n^{c})$
2.$\text{if } log_{b}a = c, T(n) = \theta(n^{c} log n)$
3.$\text{if } log_{b}a > c, T(n) = \theta(n^{log_{b}a})$

Extend Master Theorem

$$T(n) = \begin{cases} aT(n/b) + f(n) & \text{ if } n > 1 \\ d & \text{ if } n = 1 \end{cases} \\ E = log_{b}(a)$$

1.$\text{if } f(n) = O(n^{E} (log_{b}n)^{\alpha} ) \text{ and } \alpha < -1, T(n) = \theta(n^{E})$
2.$\text{if } f(n) = O(n^{E} (log_{b}n)^{\alpha} ) \text{ and } \alpha = -1, T(n) = \theta(n^{E} log_{b} log_{b}(n))$
3.$\text{if } f(n) = O(n^{E} (log_{b}n)^{\alpha} ) \text{ and } \alpha > -1, T(n) = \theta(n^{E}(log_{b}n)^{\alpha + 1})$

Chapter 5

5.1

In the proof of the query time of the kd-tree we found the following
recurrence:
$$Q(n) = \begin{cases} O(1) & \text{ if } n = 1 \\ 2 + 2Q(n/4)& \text{ if } n > 1 \end{cases}$$
Prove that this recurrence solves to Q(n) = O(√n). Also show that Ω(√n) is a lower bound for querying in a kd-tree by defining a set of n points and a query rectangle appropriately.

  1. by master theorem,$a = 2, b = 4, c = 0 \Rightarrow Q(n) = \Theta(\sqrt{n})$
    2.$\Omega(\sqrt{n})$ 是 kd-tree 的 lower_bound。如果 + 號存在的行都一直被執行，另外 - 號行都不會被執行，那麼複雜度就會達到$\Omega(\sqrt{n})$，要明白如何加上 report 則會更慢，必須將包含的點依序回報。找一個不包含所有點的細長矩形於正中央即可，每次循環切割到 x 時，保證會留下 n/4 個節點。
1
2
3
4
5
6
7
8
9
10
11
12
13
Algorithm: SEARCHKDTREE(v, R) 
if v is leaf
    report the points stored at v if it lies in R.
else
-	if region(lc(v)) contains R
        report subtree lc(v)
+	else if lc(v) intersects R
        SEARCHKDTREE(lc(v), R)
  
-	if region(rc(v)) contains R
        report subtree rc(v)
+ 	else if rc(v) intersects R
        SEARCHKDTREE(rc(v), R)

5.3

In Section 5.2 it was indicated that kd-trees can also be used to store sets of points in higher-dimensional space. Let P be a set of n points in d-dimensional space. In parts a. and b. you may consider d to be a constant.

  1. Describe an algorithm to construct a d-dimensional kd-tree for the points in P. Prove that the tree uses linear storage and that your algorithm takes$O(n log n)$ time.
  2. Describe the query algorithm for performing a d-dimensional range query. Prove that the query time is bounded by$O(n^{1−1/d} +k)$.
  3. Show that the dependence on d in the amount of storage is linear, that is, show that the amount of storage is$O(dn)$ if we do not consider d to be a constant. Give the dependence on d of the construction time and the query time as well.
1
2
3
4
5
6
7
8
9
Algorithm : build(int k, int l, int r, int dep)
    if l > r
        return NULL
    m = (l + r)/2
    Node ret = median axis[k%K] of point[l, r] ----- O(n)
    split points[l, r] by median               ----- O(n), C++ std::nth_element()
    ret.lson = build((k+1)%K, l, m-1);
    ret.rson = build((k+1)%K, m+1, r);
    return ret;
  1. 利用 median of medians 算法找到中位數，數據儲存用指針來完成搜索，不用移動資料。
    以上代碼根據遞迴公式$T(n) = 2T(n/2) + O(n) \Rightarrow T(n) = \Theta(n log n)$，而 kd-tree 是一個 full binary tree，每一個節點都代表一個實際資料，因此空間複雜度$O(n)$
  2. 假設在 d 為空間，Q(n) 表示 n 個點的詢問，依序按照維度切割 (ex. x, y, z, x …)，現在只關注 x 軸上的切割，假設詢問範圍包含所有的 y, z，那麼在 2ed x 節點中，每一個節點具有$n/2^{d}$ 資料，而同一層會有$2^{d-1}$ 個 x 維度的子節點。然後遞迴詢問$2^{d-1}$ 所包含的範圍查找。
    藉由 master theorem,$a = 2^{d-1}, b = 2^{d}, c = 0 \Rightarrow Q(n) = \Theta(n^{1 - 1/d})$ $$Q(n) = \begin{cases} O(1) & \text{ if } n < 2^{d} \\ 2^{d-1} + 2^{d-1} Q(n/2^{d}) & \text{ if } n \geq 2^{d} \end{cases}$$
  3. 如果 d 不是常數，每一個內部節點空間 O(d)，有 n 個節點則需 O(dn) 的儲存空間。詢問上，需要在 intersected 花 O(d) 時間決定是否存在交集、包含，再來判斷是否走訪子樹，因此詢問是$2dQ(n) = O(dn^{1-1/d})$，加上回報的效率為$2dQ(n) = O(dn^{1-1/d} + k)$。

5.5

Algorithm SEARCHKDTREE can also be used when querying with other ranges than rectangles. For example, a query is answered correctly if the range is a triangle.

a. Show that the query time for range queries with triangles is linear in the worst case, even if no answers are reported at all. Hint: Choose all points to be stored in the kd-tree on the line y = x.
b. Suppose that a data structure is needed that can answer triangular range queries, but only for triangles whose edges are horizontal, vertical, or have slope +1 or −1. Develop a linear size data structure that answers such range queries in O(n3/4+k) time, where k is the number of points reported. Hint: Choose 4 coordinate axes in the plane and use a 4-dimensional kd-tree.
c. Improve the query time to O(n2/3+k). Hint: Solve Exercise 5.4 first.

  1. 最慘情況是 O(n)－詢問範圍為三角形。
    詢問的範圍如圖，所有點落在 y = x 上，三角形範圍是一個很貼近 y = x 的三角形，三角形並沒有包含任何一個點，卻與所有劃分的區域有交集，因此必須走訪所有節點。
  2. 如果要支持三角形範圍查找 (三角形的邊要不垂直、平行、斜率 +1、斜率 -1)。找到一個詢問$O(n^{3/4} + k)$ 的資料結構。
    類似 kd-tree，但是輪替的標準為 x 軸 、 y 軸 、 斜率 1 、 斜率 -1 ，根據 5.3(b) 的公式，相當於 d = 4 的情況，得到$O(n^{1 - 1/4} + k) = O(n^{3/4} + k)$。
  3. 加快到$O(n^{2/3} + k)$ 的詢問時間。
    在這裡想到是建立兩個 kd-tree，其中一個順序為 x 軸 、 斜率 1 、 斜率 -1 ，另一個順序為 y 軸 、 斜率 1 、 斜率 -1 。前者可以回答向上、向下三角形，後者回答向左、向右三角形。相當於 d = 3 的切割，最多拆成 4 個範圍查找$O(4n^{1 - 1/3} + k) = O(n^{2/3} + k)$。
    1. 在詢問矩形時，拆成四個三角形查找 (向上、向下、向左、向右三角形)
    2. 在詢問三角形時，拆成兩個三角形查找

5.9

One can use the data structures described in this chapter to determine whether a particular point (a,b) is in a given set by performing a range query with range [a : a]×[b : b].

  1. Prove that performing such a range query on a kd-tree takes time O(logn).
  2. What is the time bound for such a query on a range tree? Prove your answer.
  1. 對於 kd-tree 所消耗的時間 O(log n) 說明。 $[a:a] \times [b:b]$ 並不會跨區間。在 SEARCHKDTREE(v, R) 函數中，Line SEARCHKDTREE(lc(v), R) 和 SEARCHKDTREE(rc(v), R) 只會有一個符合。$$Q(n) = \begin{cases} O(1) & \text{ if } n = 1 \\ 1 + Q(n/2) & \text{ if } n > 1 \end{cases}$$
  2. 對於 kd-tree 所消耗的時間 O(d log n) 說明。
    首先能知道會先在第一維度探訪$[a:a]$ 的葉節點，中間經過 log n 個節點最後到葉節點，然後在其相對應的 y 軸 tree 中查找$[b:b]$ 也是 log n。因此是$O(\sum{i = 1}^{d} log n) = O(d log n)$

5.11

Let S1 be a set of n disjoint horizontal line segments and let S2 be a set
of m disjoint vertical line segments. Give a plane-sweep algorithm that
counts in O((n+m) log(n+m)) time how many intersections there are
in S1 ∪ S2.

給 n 個不相交的水平線段、m 個不相交的垂直線段，在 O((n+m) log (n+m)) 的時間內找到焦點個數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Algorithm:
    1. sort all x-coordinate ----- O((n+m) log (n+m))
    2. sweep x from small to large, maintain a segment tree or range tree.
    for x = -oo to oo
        for each horizontal line (sx, y)-(ex, y) in x
            if sx = x
                1Drangetree.add(y) 				----- O(log (n+m))
        for each vertical line (x, sy)-(x, ey) in x
            ret += 1Drangetree.query(sy, ey) 	----- O(log (n+m))
        for each horizontal line (sx, y)-(ex, y) in x
            if ex = x
                1Drangetree.remove(y) 			----- O(log (n+m))
    return ret

Chapter 6

6.1

Draw the graph of the search structure D for the set of segments depicted
in the margin, for some insertion order of the segments.

雖然沒有加入順序的考量，但是手爆一個 17 個線段、平面空間 29 個的建造 … 也許有點瘋狂，用最簡單的由上而下掃描，造成一個傾斜的樹也是各種不容易。

6.2

Give an example of a set of n line segments with an order on them that
makes the algorithm create a search structure of size Θ(n2) and worst-case
query time Θ(n).

找到一個最慘空間$\Theta(n^{2})$，最慘詢問時間$\Theta(n)$。

n 個線段，將其中 n/2 放置在同一個水平線上，對於剩餘 n/2 個：

每次加入的順序 s1, s2, …, si，每次的線段的 x 值會包含前一個線段$s_{i}.lx < s_{i-1}.lx, s_{i}.rx > s_{i-1}.rx$，美加入一個線段，會增加 n/2 個內部節點，並且最大深度增加 1。總計加入 n/2 次，增加的節點數量 O(n/2 x n/2) = O(n^2)，深度 O(n/2) = O(n)。

6.5

Given a convex polygon P as an array of its n vertices in sorted order along the boundary. Show that, given a query point q, it can be tested in time O(logn) whether q lies inside P.

由於詢問次數相當多，必須將複雜度降到 O(log n)，採用的方式將凸包其中一個點當作基準，則如果在凸包的點而言，一定會落在某個以基點拉出的三角形內部中，為了方便計算，則可以拿外積的正負邊界上。得到可能的三角形後，從邊界中可以藉由外積計算是否同側。

採用射線法 O(n) 肯定是吃大虧的。

part of UVa 12048 - Inhabitants
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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);
}
int inside_convex(const Pt &p, Pt ch[], int n) {
    if(n < 3)
        return false;
    if(cross(ch[0], p, ch[1]) > eps)
        return false;
    if(cross(ch[0], p, ch[n-1]) < -eps)
        return false;
    
    int l = 2, r = n-1;
    int line = -1;
    while(l <= r) {
        int mid = (l + r)>>1;
        if(cross(ch[0],p, ch[mid]) > -eps) {
            line = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return cross(ch[line-1], p, ch[line]) < eps;
}
Read More +
學校課程/自然語言

自然語言處理 - HW01

編譯環境

Dev-C++ 5.6.3

Language model implementation

實作語言處理模型，要求讀入一連串的英文語句做為基底，接著詢問一句的正確性為多少，也就是這句話是正確拼讀的機率為何，算是一個可用的句子嗎？

$$P(w_{i}) = \frac{Count(w_{i})}{\sum_{j} Count(w_{j})} \\ P(w_{i}, w_{i+1}) = \frac{Count(w_{i}, w_{i+1})}{\sum_{j} Count(w_{j}, w_{j+1})} \\ P(w_{i+1}|w_{i}) = \frac{P(w_{i}, w_{i+1})}{P(w_{i})}$$

上述分別是一個單詞的機率，以及計算相鄰兩個單詞的機率，最後推估在這個單詞下，它們相鄰的機率。請查閱 貝氏定理 。

  • P(A)是A的先驗機率或邊緣機率。之所以稱為”先驗”是因為它不考慮任何B方面的因素。
  • P(A|B)是已知B發生後A的條件機率，也由於得自B的取值而被稱作A的後驗機率。
  • P(B|A)是已知A發生後B的條件機率，也由於得自A的取值而被稱作B的後驗機率。
  • P(B)是B的先驗機率或邊緣機率，也作標准化常量（normalizing constant）.
$P(s) = P(w_{0}) \times P(w_{1}|w_{0}) \times ... \times P(w_{n-1}|w_{n-2})$

上述為一個句子的機率，一個句子可以表示成一個序列單詞，利用連乘積將機率算出。當句子越常時，很容易發現機率陡降的速度相當快，就算是數個字詞，機率大約也是在$10^{-3}$ 左右。因此這麼算下去，長句子的正確性就會大幅減少，但是在邏輯上，如果句子都是短短幾個單詞也是相當奇怪的，口語上也許是，文章判讀上就難說。至於要不要取$\sqrt[n]{x}$ 值得思考。

$$\begin{cases} Count^{*}(w_{i}) = (Count(w_{i})+1) \times \frac{N_{Count(w_{i})+1}}{N_{Count(w_{i})}} & \text{ if } Count(w_{i}) < k \\ Count^{*}(w_{i}) = Count(w_{i}) & \text{ if } Count(w_{i}) \geq k \end{cases} \\ \text{unigram } N_{0} = 80000$$

當我們去計算一個單詞的機率時，必須相對於其他單詞的出現機率，然而像介係詞、助詞等，出現次數是相對高出取多，必須取一個閥值，來忽略過高無用的機率，以免將其他的單詞的機率過低不均。

$$\begin{cases} Count^{*}(w_{i}, w_{i+1}) = (Count(w_{i}, w_{i+1})+1) \times \frac{N_{Count(w_{i}, w_{i+1})+1}}{N_{Count(w_{i}, w_{i+1})}} & \text{ if } Count(w_{i}, w_{i+1}) < k \\ Count^{*}(w_{i}, w_{i+1}) = Count(w_{i}, w_{i+1}) & \text{ if } Count(w_{i}, w_{i+1}) \geq k \end{cases} \\ \text{bigram } N_{0} = 80000 \times 80000$$

在計算相鄰兩個單詞的出現次數時，一樣會遇到這種情況。既然在計算次數上需要做 smoothing 的調整，在機率處理上也是一樣動作。

$$\begin{cases} P(w_{i}) = \frac{N_{1}}{N} & \text{ if } Count(w_{i}) = 0 \\ P(w_{i}) = \frac{Count^{*}(w_{i})}{N} & \text{ if } Count(w_{i}) < K \\ P(w_{i}) = \frac{Count(w_{i})}{N} & \text{ if } Count(w_{i}) \geq K \end{cases}$$ $$\begin{cases} P(w_{i}, w_{i+1}) = \frac{Count^{*}(w_{i}, w_{i+1})}{N} & \text{ if } Count(w_{i}, w_{i+1}) < K \\ P(w_{i}, w_{i+1}) = \frac{Count(w_{i}, w_{i+1})}{N} & \text{ if } Count(w_{i}, w_{i+1}) \geq K \end{cases}$$

在單詞出現次數很少時，就必須使用 smoothing，因為出現 1 次、2 次、3 次 … 的單詞次數，之間大小關係不保證嚴格遞增或遞減，

實作細節

  • 公式都已經給定，基本上麻煩就是在於資料紀錄而已，其他就照著流程跑。
  • 雖然沒有規定語言，以下代碼在 Dev-C++ 下編過，別問 VS 到底行不行。

原則上，讀檔案，建立模型可以在 1.4 秒內完成

1
2
3
4
5
6
processing dataset.txt ...
read file end. Start prepare language model ...
input a sentence in a line :
  
--------------------------------
Process exited after 1.493 seconds with return value 0

測試輸入

1
2
3
4
5
6
7
8
causes AIDS and is associated with AIDS cases primarily in West Africa
AIDS cases primarily in West Africa
AIDS cases primarily at West Africa
AIDS cases primarily AIDS West Africa
morris
West Africa
East Africa
Taiwan Africa

測式輸出

考量長句子的機率，採用 log 平均結果，輸出應該為負值。

1
2
3
4
5
6
7
8
-4.597715
-4.796396
-5.992288
-7.245960
-1.857392
-4.639120
-8.003706
-8.003706

原始版本，直接輸出 P(s)，這裡採用科學記號表示法。

1
2
3
4
5
6
7
8
1.101764e-026
2.622182e-015
6.068425e-019
9.372080e-023
2.436068e-002
9.031667e-007
3.733396e-011
3.733396e-011

結語

有 STL library，代碼不用太長，跑得時間也不會太久。想到插手別學校的自然語言處理，玩了一下他們作業，把同學的代碼效率修得好一點，其實也不錯玩得，只是在公式計算上比較沒有，但是要求高效率的搜索結構，讀檔案進來後，依據什麼建表、該用什麼順序完成是很重要的。

切記，在寫這種程式時，發現跑的速度太久，一部分是因為使用太多的標準輸出，也就是用太多 printf()、cout << 或 System.out.println() 之類的在進行流程監控。輸出的效率必須將檔案寫到螢幕顯示的 memory buffer，因此 context-switch 什麼，消耗時間太大，盡可能不要輸出，要不然就是按比例輸出，速度可以快個數百倍。

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <stdio.h>
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <assert.h>
#include <sstream>
#include <math.h>
#include <ctype.h>
using namespace std;
#define DEBUG
class Model {
    public:
    map<string, int> Count;
    map<pair<string, string>, int> Count2;
    map<int, int> Ni;
    map<int, int> Ni2;
    int totalCountWord, totalCount2Word;
    static const int K;
    static const int V;
    string str2lower(string s) {
        for (int i = 0; i < s.length(); i++)
            s[i] = tolower(s[i]);
        return s;
    }
    void prepare() {
        totalCountWord = totalCount2Word = 0;
        for (map<string, int>::iterator it = Count.begin();
            it != Count.end(); it++) {
            Ni[it->second]++;
            totalCountWord += it->second;
//#ifdef DEBUG
//			if (it->second > 1000)
//			printf("Count(%s) = %d\n", it->first.c_str(), it->second);
//#endif
        }	
        for (map<pair<string, string>, int>::iterator it = Count2.begin();
            it != Count2.end(); it++) {
            Ni2[it->second]++;
            totalCount2Word += it->second;
        }		
        int smooth = 0x3f3f3f3f;
        for (map<int, int>::iterator it = Ni.begin();
            it != Ni.end(); it++) {
//			smooth = min(smooth, it->second);
//			it->second = smooth;
//#ifdef DEBUG
//			printf("N(%d) = %d\n", it->first, it->second);
//			getchar();
//#endif
        }
    }
    double getN(int i) { // N_{Count(w)}
        if (i == 0)	return 80000;
        map<int, int>::iterator it = Ni.lower_bound(i), jt;
        if (it == Ni.begin())	return it == Ni.end() ? 1 : it->second;
        jt = it, jt--;
        double sx = jt->first, sy = jt->second, ex = it->first, ey = it->second;
        return sy + (ey - sy) / (ex - sx) * (i - sx);
    }
    double getN2(int i) { // N_{Count(w_{i}, w_{i+1})}
        if (i == 0)	return 80000.0 * 80000.0;
        map<int, int>::iterator it = Ni2.lower_bound(i), jt;
        if (it == Ni2.begin())	return it == Ni2.end() ? 1 : it->second;
        jt = it, jt--;
        double sx = jt->first, sy = jt->second, ex = it->first, ey = it->second;
        return sy + (ey - sy) / (ex - sx) * (i - sx);
    }
    double getCountStar(const string &w) { // Count^{*}(w_{i})
        int n = Count[w];
        if (n < K) {
            return (double) (n + 1) * (getN(n + 1) / getN(n));
        } else {
            return n;
        }
    }
    double getCountStar2(const string &w1, const string &w2) { // Count^{*}(w_{i}, w_{i+1})
        int n = Count2[make_pair(w1, w2)];
        if (n < K) {
            return (double) (n + 1) * (getN2(n + 1) / getN2(n));
        } else {
            return n;
        }
    }
    double getPofW1(const string &w) { // P(w_{i}) = \frac{Count(w_{i})}{\sum_{j} Count(w_{j})}
        map<string, int>::iterator it = Count.find(w);
        if (it == Count.end() || it->second == 0) { // Count(w_{i}) = 0
            double Nu0 = V - Count.size();
            return (double) getN(1) / Nu0 / totalCountWord; // \frac{N_{1}}{N}
        } else if (it->second < K) { // 0 < Count(w_{i}) < K
            return (double) getCountStar(w) / totalCountWord; // \frac{Count^{*}(w_{i})}{N}
        } else { // Count(w_{i}) \geq K
            return (double) it->second / totalCountWord; // \frac{Count(w_{i})}{N}
        }
    }
    double getPofW2(const string &w1, const string &w2) { // P(w_{i}, w_{i+1})
        map< pair<string, string>, int>::iterator it = Count2.find(make_pair(w1, w2));
        if (it == Count2.end() || it->second == 0) {
            double Nb0 = (double) V * V - Count2.size();
            return (double) getN2(1) / Nb0 / totalCount2Word;
        } else if (it->second < K) { // Count(w_{i}, w_{i+1}) < K
            return (double) getCountStar2(w1, w2) / totalCount2Word; // \frac{Count^{*}(w_{i}, w_{i+1})}{N}
        } else { // Count(w_{i}, w_{i+1}) \geq K
            return (double) it->second / totalCount2Word; // \frac{Count(w_{i}, w_{i+1})}{N}
        }
    }
    void parseStmt(vector<string> &stmt) {
        for (int i = 0; i < stmt.size(); i++) {
            stmt[i] = str2lower(stmt[i]);
            Count[stmt[i]]++;
            if (i)
                Count2[make_pair(stmt[i-1], stmt[i])]++;
        }
    }
    double getPs(string in) {
        stringstream sin(in);
        vector<string> stmt;
        string token;
        while (sin >> token)
            stmt.push_back(str2lower(token));
        // P(s) = P(w_{0}) \times P(w_{1}|w_{0}) \times ... \times P(w_{n-1}|w_{n-2})
        double p = 1;
        if (stmt.size() > 0)
            p = getPofW1(stmt[0]);
        for (int i = 1; i < stmt.size(); i++ ) {
            p *= getPofW2(stmt[i-1], stmt[i]) / getPofW1(stmt[i-1]);
//			printf("%lf\n", getPofW2(stmt[i-1], stmt[i]) / getPofW1(stmt[i-1]));
//			cout << stmt[i-1] << " "  << stmt[i]  << endl; 
//			printf("%lf\n", getPofW2(stmt[i-1], stmt[i]));
        }
        return p;
    }
} tool;
const int Model::K = 10, Model::V = 80000;
int main() {
    ifstream fin("dataset.txt");
//	freopen("tmp.txt", "w+t", stdout); 
    string token, line;
    vector<string> stmt;
    puts("processing dataset.txt ...");
    while (getline(fin, line)) {
        stringstream sin(line);
        stmt.clear();
        while (sin >> token) {
            stmt.push_back(token);
        }
        tool.parseStmt(stmt);
    }
    puts("read file end. Start prepare language model ...");
    tool.prepare();
    puts("input a sentence in a line :");
    while (getline(cin, line)) {
        printf("P*('%s') : %.10e\n", line.c_str(), tool.getPs(line));
    }
    return 0;
}
/*
causes AIDS and is associated with AIDS cases primarily in West Africa
AIDS cases primarily in West Africa
AIDS cases primarily at West Africa
AIDS cases primarily AIDS West Africa
morris
IL-2 is a gene .
IL-2 is an gene .
*/
Read More +
學校課程/通識課程

[通識] 文明的進程 Week 5

文明化的過程，有可能整個記憶封鎖在過去的盒子中。

前言

本周上課講述的內容為 痰盂 ，在 18 世紀時，這盆子可說是相當受到歡迎，當我們發現吐痰這事衛生上有所疑慮，找了一個盆子還裝，就跟尿壺類似。但是問別人痰盂是何物時，大概也沒幾個人見過。

為什麼經過了 2 個世紀，痰盂就不見了，應該說是不被需要， 吐痰 這件事從正常行為，到不需要吐痰，當然還是有人或在某個狀態下會吐痰 (生病)，由於環境的改善，尤其是空氣汙染的關係，痰並沒有必要性。

談吐痰行為

早期到處可見吐痰，可說是隨地大小便的程度，吐痰在地上踏踏輾輾即可，中間開始注意到衛生，不管東方西方都曾出現過 痰盂 ，甚至在大大小小的照片中還一起入鏡呢，外觀上與一般花盆無異，只是裡面裝的東西不同罷了。

後來開始用法規、法款來制止人們隨地吐痰，從不吐在室內開始，也許允許往外吐是件很可笑的事情，但是在過度時期也算個進步，至少人們還知道吐痰這個行為需要被約束。到了二十世紀仍然會有使用罰款的方式來告誡人們，那為什麼現在根本沒有看過這些警告標語呢？「 請不要隨地吐痰 」

他制到自制：外部或他人而遵守戒律 → 內化到自我強制

談約束禮儀

任何一個爛事，找一個 powerful 的理由，也能昇華！

在一個民主平等的社會中，才能用衛生健康的理由來約束人們。如果在那種貧富不均，又有階級高低之分的社會，物質分配不均，光是活著就有困擾，遵守禮儀這件事情何止奢侈可說。

如果看看在傳統菜市場買賣的人，用呼喊的方式叫賣，那樣的行為舉止，在有限的資源下，你還說什麼禮儀嗎，能賣出去就好，下次還要搶攤位賣呢。

社會組織的方式將會影響心理生活的可塑性，根據國情不同、情操與行為的主旨不同，心理上要適應新的規則模式，反應上也會有所不同。基於什麼樣的條件，接受某些事情的難易度不同。 (文理組織差，相互學習對方領域的可塑性也會有差別)

談我們

美當我們成長，越來越會覺得小孩子很吵，那我們還能這麼吵嗎？兇不起來的人類？越來越退化了嗎？接受禮儀的約束，在何種環境下，才能拿回被約束的習慣。

「當我們不只遵守禮儀，也會開始要求別人遵守禮儀」這必須看看台灣最強的人肉搜索，不外乎一個人做錯事情，馬上就會被人肉出來，必且大眾強力苛責這個人的行為，可見我們多麼要求別人遵守禮儀。在某些條件下，例如家裡、年紀之差，容忍不禮貌的程度也會不同。

幾件趣事

結合民族自尊心推動宣傳，當我們厭惡、崇尚其他民族時，它們活生生的例子就會是很好的宣傳，例如：西方人多麼高雅、韓國人常在體育賽事作弊 … 等，約束力相當好。

在早期哪有什麼裸體抗議，大家都是赤裸裸地睡覺、洗澡，不赤裸睡覺必有身體上的缺陷，不想引人猜疑，那時都是安妥妥地赤裸。而現在卻不同，赤裸居然可以拿來做為抗議手段，用一個羞恥力來擊倒敵人！

在人來人往的地方生活，就會不由自主地意識到他人的存在，任何行為不管是否被他人看見，都會論及自己是否會 貶值 的行為，做了某件事情，我是否就貶值了呢？因此焦慮心情在城市中也常在人們身上發現。

成人與小孩的衝突有時只是世代的價值衝突，而非禮儀上的學習多寡，當沒有過去世代的記憶，沒有那些曾經被拋下的某些行為經驗，不知道不做的原因，為何不做？

為什麼常有人不碰別人用過的東西？人際關係的 獨立 與 疏離 ，總覺得人越來越不是人了，說是昆蟲也不為過，之後就各自獨立生存，最終進化呢。

沒有一個時代的狀態可以做為 絕對化標準

少在那邊自己為是，可以說自己不夠好，但是絕不能批評別人太差，看到別人用你不曾使用的行為模式活著，才是訝異敬佩的地方－「 原來還可以這麼活著！ 」

用範例教育成人該做、不該做的事情，也就是說什麼都能說，何必忌諱任何一個汙穢的事情。

越要說明一個真理，請拋開羞恥心去描述它吧。

Read More +
解題區/出題解題

[ACM 題目] 最近餐館

Problem

每到吃飼料時間，某 M 正思考要去哪裡解決，雖然有很多很多地方可以去吃，由於某 M 對於美食沒有特別需求，所以只會到最近的幾個地點即可，然後再以循環輪食的方式日復一日。

某 M 現在的位置與每個餐館的位置都用一個笛卡爾坐標系中的點表示，每個點與每個點的距離為歐幾里得距離。

x = (x1,…,xn) 和 y = (y1,…,yn) 之間的距離為

test

現給出在 K 維空間中某 M 所處的位置座標，以及 N 個餐館位置，請觀察某 M 會到哪裡吃飼料。.

Input

輸入有多組測資，

每一組第一行會有兩個整數 N, K，

接下來會有 N 行，每行包含 K 個整數，表示第 i 個餐館座標。

接下來一行，包含一個整數 Q，表示某 M 的可能座標 。

接下來會有 Q 行，每一組詢問會有兩行，第一行會有 K 個整數，表示某 M 所在的座標，第二行會有一個整數 P。

(N < 8192, K < 6, Q < 10,000, P < 11, 座標值 0 < x, y < 10,000)

Output

對於每一組詢問，輸出一行 Case #:，第一個整數為 P，接下來 P 個整數按照距離由小到大輸出餐館編號，如果相同則輸出編號小的。

Sample Input

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

Sample Output

1
2
3
Case 1: 1 1
Case 2: 2 2 3
Case 3: 1 2

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 8192
#define MAXD 8
#define INF 0x3f3f3f3f
class kdTree {
    public:	
    struct PointD {
        int d[MAXD];
        int label;
    };
    struct Node {
    	Node *lson, *rson;
    	int label;
    };
    struct cmp {
        bool operator()(const PointD* x, const PointD* y) const {
    		return x->d[sortDidx] < y->d[sortDidx];
        }
    };
    struct pQcmp {
        bool operator() (pair<int, int> &a, pair<int, int> &b) const {
        	if (a.first != b.first)	return a.first < b.first;
        	return a.second < b.second;
        }
    };
    static int sortDidx;
    priority_queue<pair<int, int>, vector< pair<int, int> >, pQcmp> pQ; // <dist, label>
    Node buf[MAXN], *root;
    PointD pt[MAXN], *A[MAXN];
    int bufsize, K;
    int Q[MAXD], max_dist, qM;
    void prepare(int n) {
        bufsize = 0;
        for (int i = 0; i < n; i++)
        	A[i] = &pt[i];
        root = build(0, 0, n - 1);
    }
    Node* build(int k, int l, int r) {
        if(l > r)	return NULL;
        int m = (l + r)/2;
        Node *ret = &buf[bufsize++];
        sortDidx = k;
        nth_element(A + l, A + m, A + r + 1, cmp());
        ret->label = A[m]->label, ret->lson = ret->rson = NULL;
        if(l != r) {
            ret->lson = build((k+1)%K, l, m-1);
            ret->rson = build((k+1)%K, m+1, r);
        }
        return ret;
    }
    int dist(int idx) {
        int ret = 0;
        for(int i = 0; i < K; i++)
            ret += (pt[idx].d[i] - Q[i]) * (pt[idx].d[i] - Q[i]);
        return ret;
    }
    int h_func(int h[]) {
        int ret = 0;
        for(int i = 0; i < K; i++)	ret += h[i];
        return ret;
    }
    void findNearest(Node *u, int k, int h[]) {
        if(u == NULL || h_func(h) >= max_dist)
            return;
        int d = dist(u->label);
        if (d < max_dist) {
            pQ.push(make_pair(d, u->label));
            if (pQ.size() == qM + 1) {
                max_dist = pQ.top().first, pQ.pop();
            }
        }
        int old_hk = h[k];
        if (Q[k] <= pt[u->label].d[k]) {
            if (u->lson != NULL)
                findNearest(u->lson, (k+1)%K, h);
            if (u->rson != NULL) {
                h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
                findNearest(u->rson, (k+1)%K, h);
                h[k] = old_hk;
            }
        } else {
            if (u->lson != NULL) {
                h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
                findNearest(u->lson, (k+1)%K, h);
                h[k] = old_hk;
            }
            if(u->rson != NULL)
                findNearest(u->rson, (k+1)%K, h);
        }
    }
    void query(int p[], int M) {
        for (int i = 0; i < K; i++)
            Q[i] = p[i];
        max_dist = INF, qM = M;
        int h[MAXD] = {};
        findNearest(root, 0, h);
        printf("%d", M);
        vector<int> ret;
        while (!pQ.empty())
            ret.push_back(pQ.top().second), pQ.pop();
        for (int i = ret.size() - 1; i >= 0; i--)
        	printf(" %d", ret[i] + 1);
        puts("");
    }
};	
int kdTree::sortDidx;
kdTree tree;
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, m, q, p[MAXD], x;
    int cases = 0;
    while (scanf("%d %d", &n, &m) == 2) {
    	tree.K = m;
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++)
    			scanf("%d", &tree.pt[i].d[j]);
    		tree.pt[i].label = i;
    	}
    	tree.prepare(n);
        scanf("%d", &q);
        while (q--) {
        	for (int i = 0; i < m; i++)
        		scanf("%d", &p[i]);
        	scanf("%d", &x);
        	printf("Case %d: ", ++cases);
        	tree.query(p, x);
        }
    }
    return 0;
}
/*
2 2
1 1
3 3
1
2 2
1
3 2
1 1
1 3
3 4
2
2 3
2
2 3
1
*/
Read More +