Oct 6 2014

b316. 紅圓茵可的消失

內容：

「哇!我終於解出來啦!咦?茵可呢?」剛解完K大數字差的你，在茵可家到處尋找，卻始終不見紅圓茵可的身影。
四處打聽之下，得知茵可前往神秘之山－「板擦山」修練神秘的魔法去了。板擦山本身有天然的結界，只有法力高強的魔法師才有辦法進入山中。「這下子我該怎麼找到茵可呢?」你苦思著，「想找茵可嗎?我可以告訴你怎麼找到茵可!」似乎是剛好路過的長頸鹿這麼說道。
板擦山的山腳下有好幾間便利商店，這些便利商店剛好開在結界外，茵可每天都會到山下的其中一間購買民生用品，而且到哪家便利商店是可以預測的。板擦山上有N個點，每個點有各自的編號，越高的點編號越小，點跟點之間有道路連接，茵可所在的山頂為編號0的點，便利商店也是其中的一個點。茵可每天會由山頂出發，經過一些點後到山下的便利商店買東西。當茵可走到一個點x後，他會先走跟x有連接的點中，編號比x大(當然要往山下走阿)的點中，編號最小的那一個。而下一次又到x時就走第二小的，直到編號比x大的點都走過一次，就會回到最小的點繼續走。(假設 3號點連到 1,4,5，第一次到3時，茵可會走向4。下一次到3時，茵可會走向5。再下一次到3時，茵可會走向4。)若一個點沒有連到編號比它大的點，則該點為便利商店。
你從長頸鹿手中的到了板擦山的地圖，你就可以預測茵可在第K天時會走到哪一家便利商店了!

輸入說明：

第一行有兩個正整數N,M,K，表示有N個點(編號0~N-1)、M條邊(M<=N*(N-1)/2)及詢問第K天茵可會到哪個點。
接下來M行每行有兩個整數a,b表示a跟b間有一條邊(保證同樣兩個點間只會有一條邊)。

測資

N<=10,K<=100
N<=10,K<=100
N<=1000,K<=1000
N<=1000,K<=1000000000，整張圖為一棵樹
N<=1000,K<=1000000000

輸出說明：

輸出第K天時茵可會走到哪個點。

範例輸入：

範例輸出：

提示：

範例測資
第一天 0→1→2→3
第二天 0→2→3
第三天 0→4
第四天 0→1→4

Solution

一開始曲解題目了，不過沒關係。

首先讓我們來了解多久一循環，根據公式 $cycle(u) = \sum cycle(v) | u \rightarrow v$，這個很容易理解的，事實上 cycle(0) 可能很大派不上用場。

如果試圖用週期 M 天，則期望用模擬迭代到 M 天是否與第一天相同，則很容易在 M + 1 天不會與第二天相同，因為路徑相同不代表狀態相同。

藉此我們利用動態規劃的概念，來找尋狀態的基底位置。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int main() {
	int N, M, K;
	int x, y;
	while (scanf("%d %d %d", &N, &M, &K) == 3) {
		for (int i = 0; i < N; i++)
			g[i].clear();
		for (int i = 0; i < M; i++) {
			scanf("%d %d", &x, &y);
			if (x > y)	swap(x, y);
			g[x].push_back(y);
		}
		for (int i = 0; i < N; i++)
			sort(g[i].begin(), g[i].end());
		int pass[1024] = {};
		int now = 0, x, sum = 0;
		pass[0] = --K;
		for (int i = 0; i < N; i++) {
			if (g[i].size() == 0)	continue;
			int u = i, v, div = pass[u] % g[i].size();
			for (int j = 0; j < g[i].size(); j++) {
				v = g[i][j];
				pass[v] += pass[u] / g[i].size();
				if (j < div)
					pass[v]++;
			} 
		}
		for (; g[now].size(); ) {
			x = pass[now]%g[now].size();
			now = g[now][x];
//			printf("-> %d\n", now);
		}
		printf("%d\n", now);
	}
	return 0;
}
/*
5 6 1
0 1
0 2
1 2
2 3
0 4
1 4
5 6 2
0 1
0 2
1 2
2 3
0 4
1 4
5 6 3
0 1
0 2
1 2
2 3
0 4
1 4
5 6 4
0 1
0 2
1 2
2 3
0 4
1 4
*/

Read More +

Oct 6 2014

解題區►解題區 - Zerojudge

b315. 紅圓茵可的考驗

內容：

身為魔法師的你，想讓自己變得更強大，於是前來膜拜紅圓茵可，同時想請教他學習魔法的秘訣。經過日復一日的嘗試，你終於通過了柏油路，並且來到茵可家。「看在你這麼努力的份上，我就稍微指導你一下吧。」茵可說道。「所謂魔法，跟程式設計很像，就是一堆指令的結合。將分子移動、放熱、發光等等基礎的小魔法結合在一起，就會變成強大的魔法(像是防護罩就是控制空氣分子的移動，並使其重新排列成為堅固的結構，達到防禦的效果。)。所以說，腦中運算的能力是很重要的。」語畢，茵可大大丟給你一個題目:

給你N個數字，挑出其中兩個數字可以得到一個數字差(非負)，而N個數字會有N*(N-1)/2個數字差，問第K大數字差是多少?
如範例輸入，數字差有6個，分別為9(10-1)、7(8-1)、5(10-5)、4(5-1)、3(8-5)、2(10-8)，其中第5大的是3。

「等你能在1秒內解完這個問題再來找我吧!」隨後茵可打開比較大的門走掉了。

輸入說明：

第一行有兩個正整數N,K
接下來有N個整數(0<=每個整數<=1,000,000,000)

測資

N<=10，K<=N*(N-1)/2
N<=1,000，K<=N*(N-1)/2
N<=10,000，K<=10,000
N<=100,000，K<=100,000
N<=100,000，K<=1,000,000,000

輸出說明：

輸出第K大數字差

範例輸入：

1 2	4 5 1 5 8 10

範例輸出：

Solution

使用二分搜索答案，通常是查找第 K 小的元素，這題是換成第 K 大元素，那麼就反過來找，中間調校的時候要特別小心。

代碼效率是 O(n log^2 n)，事實上可以壓成 O(n log n)，因為中間的索引值肯定是單調的，不過要考慮組合問題，特別要小心同一個元素自減的結果。由於懶得判斷，複雜度高了點還是過了。

#include <stdio.h>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
int kThDiff(int A[], int n, long long m) {
	int mx = A[0], mn = A[0];
	for (int i = 0; i < n; i++)
		mx = max(mx, A[i]), mn = min(mn, A[i]);
	int l = 0, r = mx - mn, mid, ret;
	m = (long long) n * (n-1)/2 - m + 1;
	long long cnt;
	sort(A, A+n);
	while (l <= r) {
		mid = (l + r)/2;
		cnt = 0;
		for (int i = 0; i < n; i++) {
			int pos = (int)(upper_bound(A+i, A+n, A[i] + mid) - A);
			cnt += pos - i - 1;
		}
		if (cnt >= m)
			r = mid - 1, ret = mid;
		else
			l = mid + 1;
	} 
	return ret;
}
int main() {
	int n, m, A[131072];
	while (scanf("%d %d", &n, &m) == 2) {
		for (int i = 0; i < n; i++)
			scanf("%d", &A[i]);
		printf("%d\n", kThDiff(A, n, m));
	}
	return 0;
}
/*
9 4
4 6 3 7 7 5 0 8 9 
5 1
7 4 2 5 2 
10 3
4 6 9 8 7 1 1 4 2 0 
9 20
3 8 6 2 1 9 6 7 2 
2 1
2 6 
4 4
0 9 0 0 
5 7
4 0 9 1 8 
11 30
1 2 1 6 1 0 7 7 5 2 5 
4 3
4 7 5 8 
2 1
1 6 
10 40
7 5 5 0 2 9 4 9 6 2 
3 2
6 8 7 
10 28
3 5 0 8 1 1 7 9 2 1 
9 3
6 7 1 2 0 8 5 1 0 
8 22
0 3 1 9 1 8 4 7 
11 20
2 3 0 4 7 1 7 6 2 2 1 
3 1
7 3 9 
4 2
9 2 4 5 
10 39
6 5 2 3 6 1 1 8 1 9 
8 7
4 9 7 2 1 6 3 2 
*/

Read More +

Oct 5 2014

解題區►解題區 - Zerojudge

b314. 紅圓茵可的煩惱

內容：

相信大家都知道紅圓茵可是誰，就不多介紹了。最近他有一個煩惱，身為一位大魔法師，每天都有成千上萬的人來膜拜他<( )>。因為人數實在太多了，這麼多人跑到他家膜拜他，害他都無法好好練習魔法了。茵可家門前有一條柏油路，要到他家一定得經過這條柏油路，他決定把這條柏油路(長方形)切成N*M個格子，並且在其中某些格子設下陷阱，踩到陷阱的人會被傳送回柏油路的起點。「恩~這樣子就可以減少膜拜我的人了~」紅圓茵可心想。但是，為了讓jackyXX等人可以到達他家，也不能把柏油路封死，必須確保一定有條路徑可以走到茵可家。而你的任務是要提醒茵可大大<( )>，哪些點能放陷阱，而哪些點不能放陷阱(導致道路封死)。
柏油路的起點在左邊，而茵可家在柏油路的右邊。一個人在柏油路上只能往上下左右四個方向走，不能走斜對角。

一條3*10的柏油路

oooooooooo
oooooooooo
oooooooooo

一條被封死的柏油路

ooooxooooo
oooxoooooo
ooxooooooo

一條沒被封死的柏油路

xxxxxxoooo
oooooxoxxx
ooxxoooxoo

輸入說明：

第一行有3個正整數N、M、T，T為茵可接下來要放的陷阱數量(0<T<=N*M)。
接下來T行每行有2個非負整數x,y表示這個陷阱要放的位址。
縱軸為x軸，橫軸為y軸，左下角那格為(0,0)。
保證一個點只會被放最多一次。

測資

N,M<=10
N,M<=50
N,M<=100
N,M<=1000
N,M<=1000

輸出說明：

對每一個要放的陷阱，若該點可放，請輸出一行”<( )>”(不含雙引號)，並且把陷阱放上去。
若該點不可放(會導致道路封死)，請輸出”>_<”(不含雙引號)，並且不放該陷阱。

範例輸入：

範例輸出：

<(_ _)>
<(_ _)>
>_<
>_<
<(_ _)>

Solution

這一題相當活用并查集的概念，雖然題目問說是否能左右相連，但是反過來則是上下邊界是否會從不相連變成相連。

多設兩個虛點，我們假想所有上界點都與虛上點相連，下界點都與虛下點相連，每次一次加入一個障礙物時，檢查九宮格內是否會造成上下虛點相連，這裡必須先偷看并查集的結果，隨後在考慮是否將其相連。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int parent[1048576], weight[1048576];
int used[1024][1024];
const int dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
const int dy[] = {0, 1, -1, 0, 1, -1, 1, -1};
int findp(int x) {
	return parent[x] == x ? parent[x] : parent[x] = findp(parent[x]);
}
int joint(int p, int q) {
	p = findp(p), q = findp(q);
	if (weight[p] > weight[q])
		weight[p] += weight[q], parent[q] = p;
	else
		weight[q] += weight[p], parent[p] = q;
	return 1;
}
int main() {
	int n, m, Q, cases = 0;
	int x, y, tx, ty;
	while (scanf("%d %d %d", &n, &m, &Q) == 3) {
		cases++;
		int N = n * m + 10, up = n * m + 1, down = n * m + 2;
		int p, q, A[8];
		for (int i = 0; i < N; i++)
			parent[i] = i, weight[i] = 1;
		for (int i = 0; i < Q; i++) {
			scanf("%d %d", &x, &y);
			p = x * m + y;
			up = findp(up), down = findp(down);
			int s = 0;
			for (int j = 0; j < 8; j++)	{
				tx = x + dx[j], ty = y + dy[j];
				if (ty < 0 || ty >= m)	{
					A[j] = p;
					continue;
				}
				if (tx < 0)			q = up;
				else if(tx >= n)	q = down;
				else {
					if (used[tx][ty] != cases) {
						A[j] = p;
						continue;
					}
					q = tx * m + ty;
				}
				if (findp(q) == up)		s |= 1;
				if (findp(q) == down)	s |= 2;
				A[j] = q;
			}
			if (s != 3) {
				puts("<(_ _)>");
				for (int j = 0; j < 8; j++) {
					joint(p, A[j]);
				}
				used[x][y] = cases;
			} else {
				puts(">_<");
			}
		}
	}
	return 0;
}

Read More +

Oct 5 2014

解題區►解題區 - UVa

UVa 225 - Golygons

Problem

每一步轉角九十度，並且第 i 次要走 i 長單位，回到原點且沿途不經過障礙物，同時轉角不可重複。

Sample Input

Sample Output

wsenenws
Found 1 golygon(s).
Found 0 golygon(s).

Solution

沿途經過障礙物，同時轉角不重複。一開始曲解了經過的轉角點，以為他也不能在隨後中經過，但實際上是可以的，因此拿了不少 WA。

#include <stdio.h> 
#include <stdlib.h>
#include <algorithm>
#include <set>
#include <vector>
#include <iostream>
#include <assert.h>
using namespace std;
int n, m, golygons;
set< pair<int, int> > ban;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const char sdir[] = "nsew";
char path[1024];
char g[2048][2048] = {}, g2[2048][2048];
vector<string> ways;
#define BASE 1024
void dfs(int x, int y, int dir, int step) {
	if (abs(x - 0) + abs(y - 0) > (step + n) * (n - step + 1)/2) {
		return;
	}
	if (step == n + 1) {
		if (x == 0 && y == 0) {
			path[step - 1] = '\0';
//			puts(path);
			ways.push_back(path);
			golygons++;
		}
		return ;
	}
	if (dir != 0) {
		for (int i = 0; i < 2; i++) {
			int tx = x, ty = y, ok = 1;
			for (int j = 0; j < step; j++) {
				tx = tx + dx[i], ty = ty + dy[i];
				assert(BASE + tx >= 0 && BASE + ty >= 0);
				assert(BASE + tx < 2048 && BASE + ty < 2048);
				if (g[BASE + tx][BASE + ty]) {
					ok = 0;
					break;
				}
			}
			if (ok && g2[BASE + tx][BASE + ty] == 0) {
				g2[BASE + tx][BASE + ty] = 1;
				path[step - 1] = sdir[i];
				dfs(tx, ty, 0, step + 1);
				g2[BASE + tx][BASE + ty] = 0;
			}
		}
	}
	if (dir != 1) {
		for (int i = 2; i < 4; i++) {
			int tx = x, ty = y, ok = 1;
			for (int j = 0; j < step; j++) {
				tx = tx + dx[i], ty = ty + dy[i];
				assert(BASE + tx >= 0 && BASE + ty >= 0);
				assert(BASE + tx < 2048 && BASE + ty < 2048);
				if (g[BASE + tx][BASE + ty]) {
					ok = 0;
					break;
				}
			}
			if (ok && g2[BASE + tx][BASE + ty] == 0) {
				g2[BASE + tx][BASE + ty] = 1;
				path[step - 1] = sdir[i];
				dfs(tx, ty, 1, step + 1);
				g2[BASE + tx][BASE + ty] = 0;
			}
		}
	}
}
int main() {
	int testcase, x[64], y[64];
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		ban.clear();
		for (int i = 0; i < m; i++) {
			scanf("%d %d", &x[i], &y[i]);
			ban.insert(make_pair(x[i], y[i]));
			g[BASE + x[i]][BASE + y[i]] = 1;
		}
		ways.clear();
		dfs(0, 0, -1, 1);
		sort(ways.begin(), ways.end());
		for (int i = 0; i < ways.size(); i++)
			puts(ways[i].c_str());
		printf("Found %d golygon(s).\n\n", ways.size());
		for (int i = 0; i < m; i++)
			g[BASE + x[i]][BASE + y[i]] = 0;
	}
	return 0;
}
/*
2
8
2
-2 0
6 -2
8
2
2 1
-2 0
1000
16
0
*/

Read More +

Oct 5 2014

解題區►解題區 - UVa

UVa 12785 - Emacs Plugin

Problem

每個 * 位置，可以任意替換成任何字串或者是空字串，是問是否有可能匹配主字串。

Sample Input

4
heyhelloyou
hel*
*o*e
e*o
hello
1
hello
x

Sample Output

yes
no
yes
yes
no

Solution

以 * 劃分，將其切割成好幾個 token，根據貪心原則只要按照順序出現這些 token 即可，因此盡可能靠左。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
using namespace std;
#define MAXN 100005
char P[MAXN], T[MAXN];
int kmpTable[MAXN];
void KMPtable(const char *P, int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPmatching(const char *T, int tlen, const char *P, int plen) {
    for(int i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1)
        	return i;
    }
    return -1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	int n, plen, tlen;
	string token;
	while (scanf("%d", &n) == 1) {
		while (getchar() != '\n');
		gets(P);
		plen = strlen(P);
		for (int i = 0; i < n; i++) {
			gets(T);
			for (int j = 0; T[j]; j++) {
				if (T[j] == '*')
					T[j] = ' ';
			}
			stringstream sin(T);
			int start = 0;
			while (sin >> token) {		
				KMPtable(token.c_str(), token.length());
				int test = KMPmatching(P + start, plen - start, token.c_str(), token.length());
//				printf("%s %d %s\n", token.c_str(), test, P + start);
				if (test == -1)	 {start = -1; break;}
				start += test + 1;
			}
			puts(start == -1 ? "no" : "yes");
		}
	}
	return 0;
}
/*
4
heyhelloyou
hel*
*o*e
e*o
hello
1
hello
x
10
rwoeyhtdvtswftfguuujqxdxdqylkyqaahianzbejckxbgeybq
oexktdvtswftf*w*n*q*rvdloll*qr
kdd*ts*ftv**ur**cdx*qi
*dtlk
**q**g****a**n
*/

Read More +

Oct 5 2014

解題區►解題區 - UVa

UVa 10597 - Right Words

Problem

對一個已經是 Chomsky normal form 的 CFG，問一個 string 是否在 CFG 之中。

Sample Input

S
SABC
ab
S -> AB
S -> BC
A -> BA
A -> a
B -> CC
B -> b
C -> AB
C -> a
# -> #
baaba
ab
abaa
a
aaaaa
bbbbb
#
S
SAB
ab
S -> AB
A -> AA
A -> a
B -> b
# -> #
ab
aaab
aba
baaaaaaaa
abbbbbb
aaaaaba
baaaaaaaab
aaaa
a
ab
#

Sample Output

baaba is in L(G)
ab is in L(G)
abaa is in L(G)
a is not in L(G)
aaaaa is in L(G)
bbbbb is not in L(G)
 
ab is in L(G)
aaab is in L(G)
aba is not in L(G)
baaaaaaaa is not in L(G)
abbbbbb is not in L(G)
aaaaaba is not in L(G)
baaaaaaaab is not in L(G)
aaaa is not in L(G)
a is not in L(G)
ab is in L(G)

Solution

因為 chomsky normal form 恰好劃分成兩個，定義字串 dp[l][r] 中可以解析出那些 nonterminal，藉由矩陣鍊乘積的方式，將其組合。最後檢查整個字串是否可以推回 start symbol。

#include <stdio.h> 
#include <string.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	char s1[1024], s2[1024];
	while (scanf("%s", s1) == 1) {
		char start = s1[0];
		scanf("%*s %*s");
		set<char> re[128];
		set<char> rule[128][128];
		while (scanf("%s -> %s", s1, s2) == 2 && s1[0] != '#') {
			if (s2[1] == '\0')
				re[s2[0]].insert(s1[0]);
			else {
				rule[s2[0]][s2[1]].insert(s1[0]);
			}
		}
		while (scanf("%s", s1) == 1 && s1[0] != '#') {
			int n = strlen(s1);
			set<char> dp[64][64];
			for (int i = 0; i < n; i++) {
				dp[i][i].insert(re[s1[i]].begin(), re[s1[i]].end());
			}
			for (int i = 1; i < n; i++) {
				for (int j = 0; i + j < n; j++) {
					for (int k = j; k < i+j; k++) {
						for (set<char>::iterator a = dp[j][k].begin();
							a != dp[j][k].end(); a++)
						for (set<char>::iterator b = dp[k+1][i+j].begin();
							b != dp[k+1][i+j].end(); b++)
							dp[j][i+j].insert(rule[*a][*b].begin(), rule[*a][*b].end());
					}
				}
			}
			printf("%s is %sin L(G)\n", s1, dp[0][n-1].find(start) == dp[0][n-1].end() 
										? "not " : "");
		}
		puts("");
	}
	return 0;
}

Read More +

Oct 5 2014

學校課程►計算幾何

計算幾何 - HW01

Chapter 1

1.1

The convex hull of a set S is defined to be the intersection of all convex sets that contain S. For the convex hull of a set of points it was indicated that the convex hull is the convex set with smallest perimeter. We want to show that these are equivalent definitions

a. Prove that the intersection of two convex sets is again convex. This implies that the intersection of a finite family of convex sets is convex as well.
b. Prove that the smallest perimeter polygon P containing a set of points P is convex.
c. Prove that any convex set containing the set of points P contains the smallest perimeter polygon P.

a. 證明兩個凸包交集仍然是凸包
假設凸包分別為 $C1, C2$，題目所求 $C = C1 \bigcap C2$
已知：A set $K$ is convex if each $u \neq v$, the line-segment $\bar{uv}$ is contained in $K$, $\bar{uv}\subseteq K$
假設 $C$ 不是凸包，則存在 $\bar{uv} \nsubseteq C$，根據定義 $u, v \in C1, C2$，得到 $\bar{uv} \nsubseteq C1, C2$，矛盾得證 $C$ 一定是凸包。

b. 證明最小周長的多邊形 P 包含所有點集 S 一定是凸包
假設 $P$ 是最小周長的非凸包多邊形，令 $x, y \in P, and \bar{xy} \nsubseteq P$，則 $\bar{xy}$ 會交 $P$ 於至少兩點 $x', y'$，$P'$ 是將 $\bar{x^{'}y^{'}}$ 連起所產生的新多邊形，顯然地 $P'$ 的周長更小。矛盾得證。

c. 證明任何一個凸多邊形 C 包含點集 S 的同時也一定會包含最小周長的多邊形 P。
假設有 vertex $v \in P, but v \notin C$，同時 v 不會在 S 範圍中，因為 C 已經包含了 S。$v1, v2$ 為 $C, P$ 交點，則 $P'$ 是 $v1, v2$ 相連產生的多邊形，則 P’ 藉由 (b) 一定是多邊形，v1 到 v2 的距離更短，找到一個周長更小的多邊形。矛盾得證。

1.3

Let E be an unsorted set of n segments that are the edges of a convex polygon. Describe an O(nlogn) algorithm that computes from E a list containing all vertices of the polygon, sorted in clockwise order.

Algorithm:

得到所有點 ${(x1, y1), (x2, y2), ..., (xn, yn)}$，並且附加是屬於哪兩個邊的端點對點作排序。map< point, vector<seg> > R - O(n log n)

挑最左下的角當作 $(x1, y1)$ 的其中一邊

A[0] = (x0, y0) = R.begin().first;
for (int i = 0; i < E.size(); i++) {
	for (seg s : R[A[0]]) {
		if (s.p0 == A[i] && (i == 0 || s.p1 != A[i-1]))
			A[i+1] = s.p1;
	}
}

檢查是否為順時針，否則反轉序列 - O(n)

1.8

The O(nlogn) algorithm to compute the convex hull of a set of n points in the plane that was described in this chapter is based on the paradigm of incremental construction: add the points one by one, and update the convex hull after each addition. In this exercise we shall develop an algorithm based on another paradigm, namely divide-and-conquer.

a. Let P1 and P2 be two disjoint convex polygons with n vertices in total. Give an O(n) time algorithm that computes the convex hull of P1 ∪P2.
b. Use the algorithm from part a to develop an O(nlogn) time divide-andconquer algorithm to compute the convex hull of a set of n points in the plane.

D&C 的 O(n log n) 凸包算法

a. 將兩個沒有相交的凸包，用 O(n) 時間內合併凸包 $P1 \cup P2$。

假設兩個凸包儲存方式都是逆時針順序，並第一個節點為最左下的節點。
Algorithm:

將最左側的凸包另為 P1，反之 P2。

代碼如下，找到下凸包 - O(n)

vector C
C[m = 0] = P1[0]
for (i = 1, j = 0; i < P1.size(); i++) {
	if (m >= 2 && cross(C[m-1] - C[m-2], P2[j] - C[m-2]) <= 0)
		break;
	C[m++] = P1[i]
}
for (; j < P2.size(); j++)
	while (m >= 2 && cross(C[m-1] - C[m-2], P2[j] - C[m-2]) <= 0)
		m--;
	C[m++] = P2[j];

仿 2. 反過來作，找到上凸包 - O(n)
上下凸包合併 - O(n)

b.
Algorithm:

將所有點按照 x 做升排序 - O(n log n)

convex DC(int l, int r, point p[]) {
	if (l == r)
		return convex(p[l])
	convex leftconvex = DC(l, (l + r)/2, p);
	convex rightconvex = DC((l+r)/2 + 1, r, p);
	return merge(leftconvex, rightconvex);
}

Prove $T(n) = 2 T(n/2) + O(n)$,
by master theorem: $a = 2, b = 2, c = 1, log_{a}b = c, \Rightarrow T(n) = \theta (n^{c} log n) = \theta (n log n)$

Chapter 2

2.1

Let S be a set of n disjoint line segments whose upper endpoints lie on the line y=1 and whose lower endpoints lie on the line y=0. These segments partition the horizontal strip [−∞ : ∞]×[0 : 1] into n+1 regions. Give an O(nlogn) time algorithm to build a binary search tree on the segments in S such that the region containing a query point can be determined in O(logn) time. Also describe the query algorithm in detail.

參閱實作 b321: 河道分界

Algorithm: (build)

sort 線段 (根據上方的 (x, 1) 進行由小排到大 ) - O(n log n)

靜態建造，動態建造請參閱可平衡的 BST。因為任切一條 y = k 的線，保證相交的 x 值得順序不會變 (跟排序結果的順序相比)，因此一開始挑 y = 1 來做排序依據。

root = dfs(0, n - 1, segments) - `O(n)`
node dfs(int l, int r, segment segs[]) {
	if (l == r)
		return new node(segs[l]);
	else if (l < r)
		int mid = (l + r)/2;
		node ret = new node(segs[mid]);
		ret.lson = dfs(l, mid - 1, segs);
		ret.rson = dfs(mid + 1, r, segs);
		return ret;
	else
		return NULL;
}

Algorithm: (query)

令 lbound = null, rbound = null

走訪 BST

void query(node u, point p) {
	if u == NULL
		return;
	if p leftside by u.seg
		rbound = u
		dfs(u.lson, p)
	else
		lbound = u
		dfs(u.rson, p)
}

output (lbound, rbound)

2.5

Which of the following equalities are always true?

$$(1) Twin(Twin(\vec{e})) = \vec{e} \\ (2) Next(Prev(\vec{e})) = \vec{e} \\ (3) Twin(Prev(Twin(\vec{e}))) = Next(\vec{e}) \\ (4) IncidentFace(\vec{e}) = IncidentFace(Next(\vec{e})) \\$$

(1)(2)(4) are always true. (3) may not be true.

2.6

Give an example of a doubly-connected edge list where for an edge e the faces $IncidentFace(\vec{e})$ and $IncidentFace(Twin(\vec{e}))$ are the same.

已知 $IncidentFace(\vec{e}) = IncidentFace(Next(\vec{e}))$ always true，讓 $Next(\vec{e}) = Twin(\vec{e})$ always true。

Half-edge	Orign	Twin	IncidentFace	Next	Prev
$\vec{e_{1, 2}}$	$v_{1}$	$\vec{e_{2, 1}}$	f1	$\vec{e_{2, 1}}$	$\vec{e_{2, 1}}$
$\vec{e_{2, 1}}$	$v_{2}$	$\vec{e_{1, 2}}$	f1	$\vec{e_{1, 2}}$	$\vec{e_{1, 2}}$

2.14

Let S be a set of n disjoint line segments in the plane, and let p be a point not on any of the line segments of S. We wish to determine all line segments of S that p can see, that is, all line segments of S that contain some point q so that the open segment pq doesn’t intersect any p not visible line segment of S. Give an O(nlogn) time algorithm for this problem that uses a rotating half-line with its endpoint at p.

參閱實作 b325: 人格分裂

Algorithm:

對於所有的端點相對 p 做極角排序，並且知道相對應的角度上會存有那些線段的端點。

map<double, vector<int, int> > angle;
for (int i = 0; i < n; i++) {
	double v1 = atan2(D[i].s.y - pos.y, D[i].s.x - pos.x);
	double v2 = atan2(D[i].e.y - pos.y, D[i].e.x - pos.x);
	angle[v1].push_back(make_pair(i, 0));
	angle[v2].push_back(make_pair(i, 1));
}

藉由出現的角度，使用極角掃描，一開始必須將碰的線段加入。

double c;
CMP::base = pos;
double ftheta = angle.begin()->first;
pair<int, int> u = angle.begin()->second[0];
Pt fpt;
if (u.second == 0)
	fpt = D[u.first].s;
else
	fpt = D[u.first].e;
for (int i = 0; i < n; i++) {
	if (cross(pos, fpt, D[i].s) * cross(pos, fpt, D[i].e) < 0)
		S.insert(D[i]);
}
CMP::sin = sin(ftheta);
CMP::cos = cos(ftheta);
for (map<double, vector< pair<int, int> >, CMP2>::iterator it = angle.begin();
	it != angle.end(); it++) {
	CMP::sin = sin(it->first);
	CMP::cos = cos(it->first);
	for (int i = 0; i < it->second.size(); i++) {
		pair<int, int> u = it->second[i];
		if (u.second == 0)
			c = cross(pos, D[u.first].s, D[u.first].e);
		else
			c = cross(pos, D[u.first].e, D[u.first].s);
		if (fabs(c) > eps) {
			if (c > 0)
				S.insert(D[u.first]);
			else
				S.erase(D[u.first]);
		}
	}
	if (S.size()) {
		visual[S.begin()->label] = 1;
	}
}

心得

出題目，出題目，萌萌哒

Read More +

Oct 3 2014

解題區►出題解題

[ACM 題目] 災難再臨

Description

Background

還記得那些年我們已經經歷的災難嗎？PTC201410D！ZJOI 2012 DAY2！如果不記得，接著請聽我捏造個故事。

Problem

危險種這一類的怪物，不斷地在村莊肆虐作亂，並且不斷地靠近帝國首都，艾斯德斯大人受令狩獵帝國周圍的危險種。

根據情報顯示，危險種移動的路徑預估為有向無環圖，牠們的數個巢穴坐落於地圖的末端 (也就是不會在有別的地點抵達這個地方)，而在首都前將有數個要塞，要塞正牠們的目標之地。為了阻止牠們到來，身為艾斯德斯大人的下屬，必須派軍隊前往危險種前往要塞的必經之地，即使抵達的位置無法阻止所有巢穴的危險種，但能對艾斯德斯大人貢獻一份心力便已足夠。

由於必經之地很多，好不容易在地圖上標記起來，卻又不知道哪個地點比較好 (可以阻止最多巢穴前往要塞)。正在困擾的同時，艾斯德斯大人已經將全部危險種給剷除了 …

「還沒一瞬間就將怪物解決，艾斯德斯大人啊！ <(_ _)>」

不過報告書還是得寫 …

Input

輸入有多組測資。

每組測資第一行會有一個整數 N (N < 32767)。

接下來會有 N 行，第 i 行上會有數個整數 x，直到 0 表示結束，表示有一條邊從 i 到 x。

Output

對於每組測資，輸出可以埋伏地點以及埋伏的最佳收穫情況。

Sample Input

Sample Output

1
2

1 1
6 4

Solution

Read More +

Oct 3 2014

解題區►解題區 - UVa

UVa 12747 - Back to Edit Distance

Problem

目標從起始序列經過操作變成目標序列。

操作 1 : 任意替除掉一個元素。
操作 2 : 將元素插入到任意位置。

請問最少次數為何

Sample Input

Sample Output

1 2	Case 1: 2 Case 2: 6

Solution

很明顯地看出，任意插入就可以直接無視，只要找有最長共同子序列即可，剩餘的元素一次替除一次插入即可。

但是最長子序列在這一題無法使用 O(n * n) 的算法，因此將其轉換成 LIS 做法，由於元素恰好不重複，可以在 O(n log n) 完成 (轉換不造成元素增加)。

#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
// LCS to LIS
int A[262144], B[262144];
int LIS(int A[], int n) {
	vector<int> r;
	r.push_back(A[0]);
	for (int i = 1; i < n; i++) {
		int pos = (int)(upper_bound(r.begin(), r.end(), A[i]) - r.begin());
		if (pos == r.size())
			r.push_back(A[i]);
		else
			r[pos] = A[i];
	}
	return r.size();
}
int main() {
	int testcase, cases = 0;
	int n, x;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%d", &x);
			A[x] = i;
		}
		for (int i = 0; i < n; i++) {
			scanf("%d", &x);
			B[i] = A[x];
		}
		printf("Case %d: %d\n", ++cases, (n - LIS(B, n)) * 2);
	}
	return 0;
}
/*
2
5
1 3 5 4 2
1 5 4 3 2
4
1 2 4 3
3 4 2 1
*/

Read More +

Oct 3 2014

解題區►解題區 - UVa

UVa 12166 - Equilibrium Mobile

Problem

給一個天平表達式，請問至少要調整幾個權重才能使之平衡。

Sample Input

3
[[3,7],6]
40
[[2,3],[4,5]]

Sample Output

1
2
3

1
0
3

Solution

恰好是一棵二元樹，那麼可以得知道假使一個權重不改，最後的天平重量為何。
假使 depth 上的權重 w 不改，則最後的天平重量就是 w * pow(2, depth)。

藉此，可以記錄所有最後的天平重量，得知最多有多少不改 = N - 最少改變個樹。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
char exp[1048576];
map<long long, int> R;
void dfs(int l, int r, int dep) {
	if (exp[l] == '[') {
		int p = 0;
		for (int i = l + 1; i <= r - 1; i++) {
			if (exp[i] == '[')	p++;
			if (exp[i] == ']')	p--;
			if (p == 0 && exp[i] == ',') {
				dfs(l+1, i-1, dep+1);
				dfs(i+1, r-1, dep+1);
			}
		}
	} else {
		int w;
		exp[r+1] = '\0';
		sscanf(exp+l, "%d", &w);
		R[(long long)w<<dep]++;
	}
}
int main() {
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%s", exp);
		R.clear();
		dfs(0, strlen(exp) - 1, 0);
		int sum = 0, mx = 0;
		for (map<long long, int>::iterator it = R.begin();
			it != R.end(); it++)
			sum += it->second, mx = max(mx, it->second);
		printf("%d\n", sum - mx);
	}
	return 0;
}
/*
3
[[3,7],6]
40
[[2,3],[4,5]]
*/

Read More +

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

Chapter 1

1.1

1.3

1.8

Chapter 2

2.1

2.5

2.6

2.14

心得

Description

Background

Problem

Input

Output

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

Problem

Sample Input

Sample Output

Solution

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

提示：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：

內容：

輸入說明：

輸出說明：

範例輸入：

範例輸出：