May 17 2015

認知風格找你所好

前言

曾想過明明有資源，卻怎麼樣都學不好嗎？在一個群體中學習，偏偏是落單的那一個人嗎？最近上課講到認知風格的相關內容，又對學習上有所障礙，到底是哪裡出了問題？

本文

如果一名學生的認知風格與教師類似，這個學生就會有更積極的學習經歷，學習將會改善。
隊員如果擁有 類似認知風格 ，將會使他們對於參與有更積極的感受。而認知風格的匹配將使參與者與人共事時感覺更為舒適，雖然它並不能獨自保證取得勝利的結果。

wikien.wikipedia.org/wiki/…

明明身處同一個環境下，成長幅度卻來得比別人低，沒錯！學習上完全沒有共鳴，導致學起來相當痛苦，建造、聚集知識的方式不同，兩路不相逢，要如何引領另一個走向相同目標？

在思考知識、經驗傳播問題前，先來認識自己，當然以前人所提供的分類方法，既不是唯一也不能二值劃分，必然有人有於兩邊優缺點，呈現自然分布，很少人是相當極端的特例！

接下來要胡言亂語囉！不用擔心！只是學習的過程不同，不代表能力的侷限。

認知風格

Wholist-Analytic

看待一個事物時，採用策略的認知方法 (從舊有事物著手，了解處理事物之間的關聯)。來看看是怎麼吸收、管理新訊息。

Field Dependence & Independence

美國心理學家威特金 (Witkin) 在 1940 年代研究垂直知覺時首先發現的。強調認知的過程而非內容。

Field Dependence 場依賴
偏向利用環境訊息來了解事物。
Field Independence 場獨立
不依賴外界資訊，由個體的方式去理解。

場獨立自主、改造能力高，對於社會技能低。相反地，場依賴則在社會技能高，對於自主、改造能力低。當然從成長過程、性別差異，會逐漸地特化、轉變成另一類，並非完全由天生決定。

一種宅宅的既視感，不外乎差別就是願不願意聽外界，當個固執的聰明人還是頑固的蠢蛋，靠著外界成長就能成為現充，當個活在社會的人。場獨立則相當危險似的，若不是聰明的那一群，很容易被誤解、淘汰於社會中。 社會究竟是何物呢？

Leveller & Sharpener

赫爾茲曼 (K.Holzman) 和克萊因 (Klein, 1954) 使用 水平 - 尖銳 認知型來描述認知風格的另一維度。

Leveller 水平
利用舊有資料產生關聯，並且加入新資料進去，但這樣做容易發生混淆，關聯的下場不保證能夠邏輯地去理解，相當於把多個物品放在同一處，「 他們應該是相似的 」的感覺，甚至有時還會因為擺滿物品而捨棄。一種以增加代替修改的 持久化算法 呢！
Sharpener 尖銳
相對於水平，會想盡辦法取代掉舊有資料，把相似之處抓出來後，放大物品差異再放回去架子上，減少混淆的情況。但對於相似之處會被移除，聯想某個物品時，只會看到最後擺放的位置，回答問題只會去描述極端的差異？操作起來一定相當耗時，放大差異去分析處理，想必會很慢。

接下來分析行為上，有一種傾向。Leveller 運行 self-inwardness 模式，避免主動參與活動，對於指導、相助有迫切的需要，傾向於 自我貶抑 的性格。Sharpener 運行 self-outwardness 模式，相較於 Leveller 更喜歡競爭、 自我展現 ，對於成就有高度的需求，常常會逼迫自己推進。

看起來，Leveller 只是因為有 Sharpener 的人存在，才會偏向自我貶抑吧！而 Sharpener 擺明就是一個抖 M 推進器。

Impulsivity & Reflectivity

由卡根 (J.Kagan, 1964) 及同事提出來的，指在不確定條件下個體作出決定速度上的差異。

Impulsivity 衝動
快速地成形自己的看法，對於問題可以很快速地回答，有迫切做出決定的慾望。
Reflectivity 反思
相反地，不斷地反思自己看法，考量所有可能性才能回答問題，並且設想所有評估所有答案的優缺。

這兩種在整體性的工作上沒有任何差異，但反思型學習速度比較慢。

Diverging & Converging

由吉爾福特 (Guilford, 1967) 在介紹智力模型時提出的。

Diverging 發散
回答問題時，答案允許多個，接受多種解決方案，強調多樣性、創造性。
Converging 收斂
強調找到一種明確的正確答案。

只有一種答案不是很無趣嗎？對於我而言，越是要求那麼唯一，就越不是答案，也許是因為找不到唯一的答案吧，才去接受多種選項的可能性。

Holist & Serialist

由帕斯克 (G.Pask, 1972) 和司科特 (Scott) 提出的。

Holist 整體
大規模搜索資料，進行較大的特徵假設，嘗試去找到一個模式、關係來理解。
Serialist 序列
單一方向、單一步驟來完成理解，對於細節較為著重，不在意整體的連接關係。

序列導向的人肯定對於讀書這類的序列資料很感興趣，也比較能一頁一頁的讀完，對於整體導向的人而言，常常會跳躍章節去讀，才會逐漸深入理解。

序列導向通常面臨的是細節著重，而無法看到整體概念，整體導向則由整體概念來理解，而缺少細節的驗證。從具有遠見的程度來看，整體導向會比序列導向來得高，正因為不清楚，才有廣闊的視野吧！

Verbaliser-Imager

心理學家 Paivio (1974) 提出了長時記憶信息如何被加工存儲的理論。影像儲存還是文字儲存？有一種原始影像資料和壓縮過後的大綱儲存差別，語言系統一改，壓縮而成的文字內容會造成理解錯誤吧？

Verbaliser & Imager

Riding 和 Taylor 最初提出的。

Imager 形象
傾向於以視覺表象的形式思維的人被稱為形象型的人。
Verbaliser 言語
傾向於以詞的形式思維的人被稱為言語型的人。

根據許多研究，當學習材料不匹配時，得到的成績往往不理想。而在人格性質上，往往言語型偏向外向、形象型偏向內向。等等，好像明白為什麼語言類型的科目會比較難學，因為很難形象化，導致只有言語型的人可以在這一方面學習得不錯。

Reference

认知风格模型的研究

Read More +

May 16 2015

學校課程►虛擬實境

虛擬實境論文研讀 Part 2

接續上一篇，接下來會有很多數學，自己也是一知無解狀態。

QEM

QEM 方程如下，當找到許多在等值曲面上的 $p_k$ 時，接著要找到一個最小 $v$ 參數為滿足目標方程

$$v^{M} \leftarrow \text{arg } \underset{v}{min} \sum_{k} (n^t_{k} (v - p_{k}))^2$$

為了找到這個 $v$

$$v^M \leftarrow v^M + Q^+ (q - Q v^M)$$

其中矩陣 $Q = \sum_{k} n_{k} n^{t}_{k}$，

使用 SVD ( singular value decomposition )，奇異值分解去找解，這個計算好像在巨量資料中也存在 SVD，這世界太可怕了！ )。在找到 $v^M$ 之後，進行簡化模型的縮點 (減少節點數)。經由這一步，可以更貼近物體的輪廓線，來強化邊緣的存在。

為了減少退化三角形跟三角網格的品質，可以藉由 Delaunay Tetrahedralization 再刷新一次。修改、刪除的點其實並不多於全局 (大多都是邊緣？)，那麼可以利用鬆弛的方式進行更新會比全局刷新還來得快速。

實戰

接下來這篇論文的作者，要進行實戰比較 (一起來吸收別人怎麼去驗證、統計、比較！實驗方法也是相當重要的。)，查看每一次迭代的是否可以的過程、速度。

誤差評定

利用模擬的模型 (幾何模型構成，拿真物要找到物體表面的方向量有點麻煩)，來看梯度方向的準確性，簡單來說就是拿實際結果與實驗結果中的一個點，於表面上的法向量夾角作為誤差大小。

$$\varepsilon_{n}(p) = \text{arccos } (n(p)^t m(p))$$

梯度估計

即使是誤差，平滑也是好事。梯度越小越平滑。

接著它拿兩個物體 sphere 和 fandisk mesh (球體和一個 ???) 進行測試，看來在那些特殊的地方的誤差。算法可能會在某些特殊邊緣、平面的運行效果不好 (算法擅長於那些特徵計算、不善長什麼，來釐清這一點)。

視覺化時，利用下列二種方式凸顯梯度 central differences、Sobel operator (索貝爾運算就是在影像處理運用中，檢測邊緣、圖像梯度用的)。論文作者接下來提供一的新穎 CT value 的計算公式，與一般傳統的不同，讓這個誤差梯度下降。經由上面兩種方式的梯度表示，發現論文作者提供的這種會再更好一點點。

討論

提供一個更準確的 CT value 的計算方式
動態運作 ODT, QEM 的方式

比較 Grid-Based

拿其他的建造方案，如 Grid-Based Polygonization，進行邊緣銳利比較。使用 Hausdorff distance 比較好壞，當然地 Grid-Based 沒對齊好，基本上贏不過三角化的版本！Grid-Based 取樣點夠密集才能勝過 vary triangle 的建模吧！在大多共平面的狀況下，三角形建模的方式需要頂點數非常少。

時間消耗

由於精準度上的調校，提出的方法比起常規的建模是消耗更多時間，但 CT 掃描數據的時間通常需要 10min 到 1hr，但是提出的方法比掃描時間還快。

也就是說讀取資料很慢，處理速度不用這麼快也沒關係，算起來有種 $O(n)$ 的效能。

空間消耗

由於過程中需要大量的矩陣、附加值於記憶體中，會消耗上 GB 的使用空間來維護操作。但現代電腦的記憶體可以超過 10GB 以上，因此這個缺點可以忽略不計。

實作細節

為了加速運行，特別將物體表面周圍的取樣多、密集一點，對於其他地方的取樣少點，如此一來計算量會少很多。

插值

在 $Tiso= (f(gi)+f(gj))/2$ 中提到插值法，但插值法有很多種，如 tricubic interpolation、bicubic interpolation … 等，如果選擇別種的插植法，效果會不會比較好呢？經過它們的梯度估算方法，他們所提到的插值法會稍微好一些。

結論

提出一個可以用 CT 圖去建模的方法，仰賴的不是三維空間 volumetric data，並且可以提供一個更高精度的建模方法，用少許的三角形就能構造出相當銳利的結果。

以上都是建立在單一素材上，如果由複合的素材構成，可能是一個無法解決的問題。
對於光束敏感的物體，CT 的建造方法可以支持更好。
如果一開始的四面體不夠完善，有可能無法捕抓到邊緣。自適應的 meshing 也許能解決這問題。

提出一個速度慢、空間多的算法，但是現代電腦記憶體夠，速度慢沒關係，比輸入還快就行了

Read More +

May 16 2015

學校課程►資訊安全

近代加密快速冪次計算

先來上競賽中最常見到的快速冪次寫法

long long mul(long long a, long long b, long long mod) { 
	long long ret = 0; 
	for( ; b != 0; b>>=1, (a<<=1)%=mod) 
		if(b&1) (ret += a) %= mod; 
	return ret; 
}
long long mpow(long long x, long long y, long long mod) {
	long long ret = 1;
	while (y) {
		if (y&1)
			ret = mul(ret, x, mod);
		y >>= 1, x = mul(x, x, mod);
	}
	return ret;
}

這樣的寫法，只運算 64-bits 內的結果相當不錯，與接下來講的算法速度差異並不大。但對於近代加密所需要的離散對數過程，則會有放大速度差異，因為 x, y, mod 三個參數的 bit-length 都相當長。

Right-To-Left

做法就是最普遍見到的。

void pow(x, a) {
	R = 1, g = x
	for i = 0 to n, step 1
		if (a[i] == 1) // a[i] mean i-bit in a
			R = R * g
		g = g * g
	return R
}

example: a = 26 = (11010)
---
#iterator  0   1    2    3     4 
#g         x, x^2, x^4, x^8, x^16, ...
binary     0   1    0    1     1
x^a =         x^2       x^8 x^16 = x^26

Left-To-Right

void pow(x, a) {
	R = 1
	for i = n-1 to 0, step -1
		R = R ^ 2
		if (a[i] == 1)
			R = R * x
	return R;
}

example: a = 26 = (11010)
---
#iterator  0   1    2      3     4 
binary     1   1    0      1     0
R         x^1 x^11 x^110 x^1101 x^11010

也就是說，每一次迭代，將會將指數左移 (R = R ^ 2 就是要移動 R^xxxx 變成 R^xxxx0，切著看是否要乘上 x 來變成 R^xxxx1)，這方法雖然不錯，但是計算高位元空迴圈可是不能忽略！當然對於設計電路的人，固定變量的迴圈展開後就不存在這問題。

效能上，期望的乘法次數與 Right-To-Left 是差不多的！長度為 n bits 的數字，期望值會有 $n/2$ 個 1，因此大約需要 $n/2$ 次乘法。

Left-To-Right(2-bits)

void pow(x, a) {
	pre-computation: x^2, x^3
	R = 1
	for i = n/2 to 0, step -2
		R = R ^ 4
		if (a[i+1]a[i] != 0)
			R = R * x^(a[i+1]a[i])
	return R
}

example: a = 1737 = (01 10 11 00 10 01)
---
#iterator   0   1    2     3     4     5
R          x^1 x^4  x^24  x^108 x^432 x^1736
               x^6  x^27        x^434 x^1737
a[i+1]a[i] 01  10   11    00    10    01

長度為 n bits 的數字，倆倆一起期望值會有 $3n/8$ 個非 0 (00, 01, 10, 11 中 4 個有 3 個 $!= 0$，計算組數只有 $n/2$)，因此大約需要 $3n/8$ 次乘法。比剛剛快上一點呢 ( $3n/8 < n/2$ )！

Left-To-Right(sliding)

void pow(x, a) {
	pre-computation: x^3
	R = 1
	for i = n-1 to 0
		if a[i]a[i-1] = (11)
			R = R ^ 4
			R = R * x^3
			i -= 2
		else if a[i]a[i-1] = (00)
			R = R ^ 4
			i -= 2
		else if a[i] = (0)
			R = R ^ 2
			i -= 1
		else if a[i] = (1)
			R = R ^ 2
			R = R * x
			i -= 1
	return R
}

example: a = (1 10 11 00 10 01)
---
#iterator   0   1    2       3     4      5          6
R          x^11    x^11011     x^11011001      x^11011001001
              x^110     x^1101100    x^1101100100

期望的乘法次數 $n/3$，這很可怕，別問我！

Summary

Algorithm Name	Table Size	#squaring	Average #Multiplication
Right-To-Left	1: $x^{2^i}$	$n$	$n/2$
Left-To-Right	1: $x$	$n$	$n/2$
Left-To-Right(2-bits)	3: $x$, $x^2$, $x^3$	$n$	$3n/8$
Left-To-Right(sliding)	2: $x$, $x^3$	$n$	$n/3$

Attack

上述四種方法中，不外乎都存在 Conditional Jump 出現，會導致執行速度跟程式計數器 (Program Counter) 移動上會有所差別。可以進行實作攻擊，從分析時間、電源不穩攻擊，來找到 $a$ 究竟是何物 (通常要偷的都是 $x^a$ 上面的 $a$)！電源雜訊干擾於當指令執行到 Conditional Jump 時，干擾 $R$ 的計算發生錯誤，如果沒有發生錯誤，表示 $a \left [ i \right ] = 0$，反之就能知道 $a \left [ i \right ] = 1$。

很趣味地是提供一個不需要 Conditional Jump 的寫法 (實作上)，一樣會有這種問題！

error example

R[1] = 1
for i = n-1 to 0, step -1
	R[1] = R[1] ^ 2
	R[a[i]] = R[1] × g
return R[1]

提供一個不相干的垃圾暫存器 (redundancy register) 來減少 Jump 的問題，很明顯地電源雜訊干擾的攻擊仍然存在！這作法很有趣的啊！只是會被攻擊。

Montgomery Ladder

R[0] = 1, R[1] = g
for i = n-1 to 0, step -1
	R[1-a[i]] = R[0] × R[1]
	R[a[i] = R[a[i]] × R[a[i]]
return R[0]

這作法避開之前的問題，解決其中一種被攻擊的方案。

過程中都滿足 $R \left [ 0 \right ] = R \left [ 1 \right ] \times g$，同時 $R \left [ 0 \right ]$ 會是最後的答案。

example: a = 26 = (11010)
---
#iterator  0   1    2      3      4     5
binary     0   1    1      0      1     0
R[0]       1   x    x^3   x^6   x^13  x^26
R[1]       x   x^2  x^4   x^7   x^14

明顯地，$R \left [ 1 \right ]$ 的計算是為了下一次為 $a \left [ i+1 \right ] = 1$ 而存在的！

Read More +

May 16 2015

學校課程►資訊安全

資訊安全期中考筆記

筆記錯誤多多，請以僅供參考的角度去質疑

Problem

Please compare the CFB mode the OFB mode by providing a table indicating at least 5 of their advantage and corresponding disadvantage.
This question is about issues of random access of encryption and decryption. Define notations or symbols you need before providing your answer. Please describe how to use CFB mode and CTR mode to randomly encrypt and decrypt a file Why OFB mode is inappropriate to randomly encrypt and decrypt a file?
What is the one-time pad (please provide a figure to explain it) and what is the main security requirement ?
Follow
1. What is the main weakness (disadvantage) of ECB mode ?
2. How CBC resolves this security problem (explained in mathematical approach) ?
Follow
1. Block ciphers process messages in blocks like an extremely large substitution, but this is very difficult to implement for a very big block size. What is Shannon’s idea to realize a block cipher with big block size ?
2. Feistel cipher structure provides a real implementation of Shannon’s idea. Please explain the main features of Feistel cipher structure.
What is the avalanche effect of a block cipher ?
What is the Triple -DES with two keys ? Please explain the process the derive the complexity of meet-in-the-middle attack on Triple-DES with two keys.
For all AES round operations, which operation(s) provides substitution and which operations(s) provides diffusion ?
Please describe the details of BBS pseudorandom number generator.
Below is the pseduo code of RC4. Please design a modified RC4 version with message dependent property of key stream.

init(master_key) // shuffle S-array with master_key
i = j = 0
for each message byte M
	i = (i + 1) mod 256
	j = (j + S[i]) mod 256
	swap(S[i], S[j])
	t = (S[i] + S[j]) mod 256
	C = M xor S[t]

Notes

Part 1

請參照《資訊安全小考筆記》

Part 2

請參照《資訊安全小考筆記》

Part 3

one-time pad 概念圖如下

                +------------+               +------------+               
                | random key |               | random key |               
                | generator  |               | generator  |               
                +------------+               +------------+               
                      |                             |                     
                      |                             |                     
                      | Ki                          | Ki                  
                      |                             |                     
                      |                             |                     
       Pi          +--v--+           Ci          +--v--+       Pi         
------------------>+ XOR +---------------------->+ XOR +----------------> 
                   +-----+                       +-----+                  
                                                                          
                   From Alice                    To Blob

one-time pad 主要是靠 key 不重複使用來維護資料安全，但是雙方同時產生出相同的 random key 是很困難。由於不重複使用，靠一個 random key 的產生提供 random mask 消除明文和祕聞之間的關係。但是雙方都要相同 random key 是相當困難的，通常 generator 是由某個偽隨機數產生器，由演算法產生的到底是不是隨機數呢？

一定要 random key，不能有任何的 dependent、 不能重複 (reuse) ，否則會有 已知明文攻擊 。

Part 4

ECB mode 在相同明文對應相同的密文，這容易受到大多數的攻擊，如收集已知明文或密文所進行的攻擊。由於明文和密文的關係明確，也因此在 圖片資料 加密傳送，會出現 大量重複 的密文。

CBC mode 提供 random mask 的效果

$$C_{-1} = IV \\ C_{i} = E_{k}(C_{i-1} \text{ XOR } P_{i}) \\$$

從 $C_{i-1} \text{ XOR } P_{i}$ 操作中可以發現到，讓相同的明文對應到不同的密文 (在前一個密文不同時)，解決 ECB 在相同明文加密只會對應種密文。

Part 5

Shannon’s idea 請參照《資訊安全小考筆記》

Feistel cipher structure 藉由三個規則實作

多個回合 (round)
藉由一半的訊息加密另一半的訊息
兩個半段訊息位置交換

Part 6

Avalanche effect 讓相似的明文 Pi, Pj (漢明距離 $H(Pi, Pj) = 1$ … 之類的) 對應的密文 Ci, Cj 能有相當大的差異 (漢明距離 $H(Ci, Cj) = \text{half-bit} $ 的期望值)，將只有一點不同的差異，擴散到密文的每個地方，放大差異的效果。

Part 7

Triple-DES

$$E_{k_{1}}\left [ D_{k_{2}} \left [ E_{k_{1}} \left [ P_{i} \right ] \right ] \right ] = C_{i}$$

當指使用兩次的 DES，受到中間相遇法的攻擊，理論上的複雜度與 1 個 DES 一樣，複雜度大約都在 $O(2^{56})$，因此效果並沒有變得更好。然而在 Triple-DES 複雜度就提升到 $O(2^{112})$。

中間相遇法攻擊

$$X = D_{k_{2}} \left [ E_{k_{1}} \left [ P_{i} \right ] \right ] \\ C_{i} = E_{k_{1}} \left [ Y \right ]$$

從已知的明文、密文，目標是讓 $X = Y$，窮舉 key，如果發生 $X = Y$ 則表示找到一組可行的解。窮舉得到 $X$ 的複雜度為 $O(2^{56} \times 2^{56}) = O(2^{112})$，而 $Y$ 則需要 $O(2^{56})$，當 $X = Y$ 符合時，則表示 key 找到！

當然也可以抽換相遇的地點，如下是另外一種

$$X = E_{k_{1}} \left [ P_{i} \right ] \\ C_{i} = E_{k_{1}} \left [ D_{k_{2}} \left [ Y \right ] \right ]$$

不管怎麼切割，都至少要窮舉兩把 key 來得到其中一個相遇結果，複雜度都落在 $O(2^{112})$。如果說對應兩個表的結果需要 $O(log \text{ n})$ 的時間，則複雜度為 $O(112 \times 2^{112})$。

Part 8

Step	Function
Substition Bytes	substitution
Shift Rows	diffusion
Mix Column	diffusion, substitution
Add Round Key	substitution

比較討厭的是 Shift Rows 為什麼提供是 diffusion，明明對於兩個相似明文加密上，漢明距離沒有增加！但是 diffusion 不只是讓差異數量增加，還要考量差異位置的變動，相鄰差異的位置被轉移到兩個遠處，就能提供 diffusion！這會讓攻擊者無從判定差異的對應。

Part 9

Blum Blum Shub

$$X_{i} = X_{i-1}^2 \text{mod } N \\ N = p \times q \\ p, q \text{ is prime nubmer, } \\ p \equiv 3 (\text{mod } 4) \\ q \equiv 3 (\text{mod } 4)$$

Part 10

message dependent RC4

第一版本

i = j = 0, Cprev = 0
for each message byte M
	i = (i + 1) mod 256
	j = (j + S[i]) mod 256
	swap(S[i], S[j])
	t = (S[i] + S[j] + Cprev) mod 256
	C = M xor S[t]
	if sender
		Cprev = C
	if receiver
		Cprev = M

好像不管怎麼寫兩邊似乎都很難相同。

第二版本

i = j = 0, C = 0
for each message byte M
	i = (i + C) mod 256
	j = (j + S[i]) mod 256
	swap(S[i], S[j])
	t = (S[i] + S[j]) mod 256
	C = M xor S[t]

感覺上述的寫法，萬一 C 被竄改，會導致錯誤擴散，而且是全部失效，這讓我非常納悶。

Read More +

May 15 2015

解題區►解題區 - 其他題目

[Tmt514] Beverage Cup 2 F - No challenge No life

Problem

這次要挑戰的題目為 UVa 12647 - Balloon，由於網路上有一些線段樹的作法，如

http://www.cnblogs.com/yours1103/p/3426212.html

這裡可以看到有一些人利用線段樹來完成操作，實際上的做法根據掃描線，y 座標從高度低到高、或者是高到低的線段依序放入，到時候查找第一個獲最後一個覆蓋的線段編號。

UVa 12647 - Balloon 主要是在問，給予一些天花板，請問放置一個氣球，氣球會沿著天花板歪斜的地方移動 (如果沒歪則停止)，詢問最後停留的位置。有可能會飛到無窮遠，則輸出最後的 x 座標，反之輸出停留的 (x, y) 地點。如果發生一個地點有數個天花板，發生擦邊情況，則氣球會依據第一個碰觸到的天花板進行移動。

Solution

既然發現它們 (搜尋可以找到至少兩個大大的線段樹寫法) 基本上都是按照覆蓋的方式，找到覆蓋編號去完成移動、建造飛行的所有可能。

明顯地，由於天花板線段的斜率有正有負，不能保證根據 y 座標排序可以決定飛行到下一個的高度的 x 範圍。因此交錯 y 座標線段，讓覆蓋方案失效。

下面有數組測資，可以讓史蒂芙掉測資、也會讓網址中的代碼掉。史蒂芙認為覆蓋不好，那用最大最小值去維護如何！這樣也許就好點了吧？但不幸地，這麼做一樣會遇到排序 y 的問題，不管怎麼排序，都會造成建構方法不正確。

challenge 的題目還不太會傳，中間有點小問題。

#include <stdio.h> 
int main() {
//	puts("4 1");
//	puts("3 1 12 4");
//	puts("5 2 2 3");
//	puts("1 4 4 3");
//	puts("7 5 14 5");
//	puts("4");
	puts("3 3");
	puts("5 5 10 4");
	puts("2 2 6 4");
	puts("0 3 4 4");
	puts("0");
	puts("1");
	puts("2");
//	puts("7 4");
//	puts("3 1 12 4");
//	puts("5 2 2 3");
//	puts("1 4 4 3");
//	puts("7 5 14 5");
//	puts("25 5 30 4");
//	puts("22 2 26 4");
//	puts("20 3 24 4");
//	puts("4");
//	puts("20");
//	puts("21");
//	puts("22");
	return 0;
}
/*
3 3
5 5 10 4
2 2 6 4
0 3 4 4
0
1 
2
4 1
3 1 12 4
5 2 2 3
1 4 4 4
7 5 14 5
4
4 1
3 1 12 4
5 2 2 3
1 4 4 3
7 5 14 5
4
*/

Read More +

May 15 2015

解題區►解題區 - 其他題目

[Tmt514] Beverage Cup 2 G - Strange Permutations

Problem

排列 1 到 n 的整數，使得相鄰兩數互質，部分位置一定要填入某些數字，請問剩餘數字的填法方案數為何？

Sample Input

1
2
3

1
8
1 2 0 0 0 0 7 8

Sample Output

Solution

bitmask 下去 dp[N][1<<N][N]，dp[i][j][k] 表示前 i 個位置，已經使用的數字狀態 j，最後一個數字 k。不曉得需不需要滾動，記憶體用量驚人。萬萬沒想到，撰寫過程中坑了一個建表的 gcd[20][20]，當 n = 20 時，直接 index out of bound，先撇開這個蠢錯。滾動數組下去玩，真是誘人的時間限制，再次得到 9.990s TLE 的事蹟！仔細想想，運算過程中只出現加法，將 mod 運算替換成條件判斷 + 減法，

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
const int MAXN = 20;
int dp[2][1<<MAXN][MAXN], used[2][1<<MAXN][MAXN], ucases = 0;
int g[MAXN+20][MAXN+20];
int vaild(int i, int a, int b) { // a contract b
	if (i == 0)	return 1;
	return g[a+1][b+1];
}
int main() {
	for (int i = 1; i <= MAXN; i++) {
		for (int j = 1; j <= MAXN; j++)
			g[i][j] = __gcd(i, j) == 1;
	}
    int testcase, n;
    int A[MAXN];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int cant = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
            if (A[i])
            	cant |= 1<<(A[i]-1);
        }
        
        int flag = 0;
        int mask = (1<<n)-1;
        int ret = 0;
//        memset(dp, 0, sizeof(dp));
        ucases++;
		used[flag][0][0] = ucases;
        dp[flag][0][0] = 1;
        for (int i = 0; i < n; i++) {
            int p = flag, q = !flag;
            flag = 1 - flag;
            ucases++;
//            for (int j = mask; j >= 0; j--)
//            	for (int k = 0; k < n; k++)
//            		dp[q][j][k] = 0;
            for (int j = (1<<n)-1; j >= 0; j--) {
            	for (int k = 0; k < n; k++) {
            		if (used[p][j][k] != ucases-1)
            			continue;
            		int ways = dp[p][j][k];
            		if (ways == 0)
            			continue;
            		if (A[i] == 0) {
            			for (int p = 0; p < n; p++) {
            				if ((j>>p)&1)
            					continue;
            				if (!vaild(i, k, p))
            					continue;
            				if (used[q][j|(1<<p)][p] != ucases)
            					used[q][j|(1<<p)][p] = ucases, dp[q][j|(1<<p)][p] = 0;
            				dp[q][j|(1<<p)][p] += ways;
            				if (dp[q][j|(1<<p)][p] >= MOD)
            					dp[q][j|(1<<p)][p] -= MOD;
            			}
            		} else {
            			for (int p = A[i]-1; p <= A[i]-1; p++) {
            				if ((j>>p)&1)
            					continue;
            				if (!vaild(i, k, p))
            					continue;
            				if (used[q][j|(1<<p)][p] != ucases)
            					used[q][j|(1<<p)][p] = ucases, dp[q][j|(1<<p)][p] = 0;
            				dp[q][j|(1<<p)][p] += ways;
							if (dp[q][j|(1<<p)][p] >= MOD)
            					dp[q][j|(1<<p)][p] -= MOD;
            			}
            		}
            	}
            }
        }
        
        for (int i = 0; i < n; i++) {
        	if (used[flag][(1<<n)-1][i] != ucases)
        		continue;
        	ret += dp[flag][(1<<n)-1][i];
        	ret %= MOD;
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
10
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
4
0 2 4 0
8
1 3 5 0 0 0 0 0
8
1 2 0 0 0 0 7 8
8
1 0 5 8 0 0 0 0
8
0 2 0 7 0 0 0 8
8
0 2 0 0 0 0 0 8
8
0 2 0 0 0 0 0 0
8
0 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0
1
0
*/

Read More +

May 15 2015

解題區►解題區 - 其他題目

[Tmt514] Beverage Cup 2 E - Kirino in Google Code Jam

Problem

2015 Google Code Jam Round 1A 中，C - Logging 有點嚴重的問題！很多精準度不高的代碼都通過了！現在要求去找到測資 tricky cases，讓他們通通 WA！

原題是對於任意平面點，找到要移除最小的平面點，使得自己在凸包邊緣上。標準的極角排序，維護 180 度以內 (半平面) 的點個數。

atan2 esp = 1e-12 not enough for $x, y \in \left [0, 10^6 \right]$，極角排序替代方案！快來戳我的講法，看 POJ 類似的題目，精準度要壓到 1e-16 呢，所以誤差還要抓更小才行。

Solution

等等，challenge 這一題時，自己的代碼也 WA 了！

一開始誤以為是 index out of bound，assert() 下去都沒發生。後來估計是 atan2(y, x) 的誤差，對此誤差早有耳聞，解題撞壁的機會很低。咱很蠢，隨機生了 1000 萬個平面點，按照 atan2 排序，檢查相鄰兩個座標的外積 (叉積) 是否為逆時針，跑一次隨機生成大概能爆出一個誤差的相鄰點，十來次得到 n 個點，隨機組合這 n 個點於四個象限，再亂撒少數個點，再跟自己撰寫的代碼做比對 (中間又測了上萬組)。

atan2 誤差測試

atan2_eps_test

#include <stdio.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <time.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
	Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
	}
    bool operator<(const Pt &a) const {
		if (fabs(x - a.x) > eps)
			return x < a.x;
		if (fabs(y - a.y) > eps)
			return y < a.y;
		return false;
	}
	double length() {
		return hypot(x, y);
	}
	void read() {
		scanf("%lf %lf", &x, &y);
	}
};
double dot(Pt a, Pt b) {
	return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
	return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
	return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
	Pt s, e;
	double angle;
	int label;
	Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
//		angle = atan2(e.y - s.y, e.x - s.x);
	}
	bool operator<(const Seg &other) const {
		if (fabs(angle - other.angle) > eps)
			return angle > other.angle;
		if (cross(other.s, other.e, s) > -eps)
			return true;
		return false;
	}
	bool operator!=(const Seg &other) const {
		return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
	}
};
Pt getIntersect(Seg a, Seg b) {
	Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
	return acos(dot(va, vb) / va.length() / vb.length());
}	
double distSeg2Point(Pt a, Pt b, Pt p) {
	Pt c, vab;
	vab = a - b;
	if (between(a, b, p)) {
		c = getIntersect(Seg(a, b), Seg(p, Pt(p.x+vab.y, p.y-vab.x)));
		return (p - c).length();
	}
	return min((p - a).length(), (p - b).length());
}
Pt rotateRadian(Pt a, double radian) {
	double x, y;
	x = a.x * cos(radian) - a.y * sin(radian);
	y = a.x * sin(radian) + a.y * cos(radian);
	return Pt(x, y);
}
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;
}
const double pi = acos(-1);
int main() {
	srand ( time(NULL));
	
	vector< pair<double, Pt> > V;
	for (int i = 0; i < 10000000; i++) {
		int X, Y;
		X = (rand()*rand())%2000000 - 1000000;
		Y = (rand()*rand())%2000000 - 1000000;
		V.push_back(make_pair(atan2(Y, X), Pt(X, Y)));
	}
	sort(V.begin(), V.end());
	for (int i = 0; i+1 < V.size(); i++) {
		if (cross2(V[i].second, V[i+1].second) != 0 && fabs(V[i].first - V[i+1].first) < 1e-12)
			printf("%.0lf %.0lf %.0lf %.0lf\n", V[i].second.x, V[i].second.y, V[i+1].second.x, V[i+1].second.y);
	}
//	long long a = 599430;
//	long long b = 1428722;
//	long long c = 648824;
//	long long d = 1546451;
//	long long a = 885828;
//	long long b = 737167;
//	long long c = 898961;
//	long long d = 748096;
//
//	printf("%lld\n", a * d - b * c);
//	printf("%lf %lf, %d\n", atan2(b, a), atan2(d, c), fabs(atan2(b, a) - atan2(d, c)) < 1e-12);
	return 0;
}
/*
885828 737167 898961 748096
854425 732894 706721 606199
-971645 988877 -838743 853618
993753 -652232 991850 -650983
620105 659001 916399 973880
*/

誤差數據產生

testdata

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <set>
#include <algorithm>
using namespace std;
double random() {
	int r = rand();
	return (double) r / RAND_MAX;
}
int vvv[20] = {885828, 737167, 898961, 748096,
854425, 732894, 706721, 606199,
-971645, 988877, -838743, 853618,
993753, -652232, 991850, -650983,
620105, 659001, 916399, 973880};
main() {
	int n, m, t, a, b, c, tmp;
	int z, i, j, k, l, p, q;
	srand ( time(NULL));
	freopen("in.txt", "w+t", stdout);
	
	int T = 10000;
	printf("%d\n", T);
	while(T--) {
		int n = 30, m = rand()%n + 1;
		printf("%d\n", n);
		set< pair<int, int> > S;
		S.insert(make_pair(0, 0));
		printf("%d %d\n", 0, 0);
		for (int i = 1; i < n; i++) {
			int x, y;
			do {
				if (rand()%10 < 8) {
					x = vvv[rand()%20], y = vvv[rand()%20];
					if (rand()%2)	x = -x;
					if (rand()%2)	y = -y;
				} else {
					x = rand()%100 - 50, y = rand()%100 - 50;
				}
			} while (S.count(make_pair(x, y)));
			S.insert(make_pair(x, y));
			printf("%d %d\n", x, y);
		}		
	}
	
	return 0;
}

對照組

利用外積的計算方案，誤差情況會更小。又因為是整數座標，基本上是不產誤差。

fixed-bug-Problem-C-Logging

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
#define MAXN 131072
struct Pt {
    double x, y;
    int label;
    Pt(double a = 0, double b = 0, int c = 0):
    x(a), y(b), label(c) {}
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
Pt D[4096];
bool cmp(const Pt& p1, const Pt& p2)
{
    if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
    if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
    if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
    if (p1.y * p2.y < 0) return p1.y > p2.y;
    double c = cross2(p1, p2);
    return c > 0 || c == 0 && fabs(p1.x) < fabs(p2.x);
}
int main() {
    int N, testcase, cases = 0;
    double x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            scanf("%lf %lf", &x, &y);
            D[i] = Pt(x, y);
        }
        printf("Case #%d:\n", ++cases);
        
        if (N == 1) {
            puts("0");
            continue;
        }
        
        for (int i = 0; i < N; i++) {
            vector< Pt > A;
            for (int j = 0; j < N; j++) {
                if (i == j)
                    continue;
                Pt p = D[j] - D[i];
                A.push_back(p);
            }
            sort(A.begin(), A.end(), cmp);
            int M = (int)A.size();
            int l = 0, r = 0, cnt = 1;
            int ret = 0;
            for (l = 0; l < M; l++) {
                if (l == r)
                    r = (r+1)%M, cnt++;
                while (l != r && cross2(A[l], A[r]) >= 0) {
                    r = (r+1)%M, cnt++;
                }
                ret = max(ret, cnt);
                cnt--;
            }
            printf("%d\n", N - ret);
        }
    }
    return 0;
}

Final

生了 10000 組，終於在裡面發現其中幾組。

final

#include <stdio.h>
int main() {
	puts("1\n30\n0 0\n-971645 838743\n748096 -988877\n-652232 -993753\n737167 -838743\n-48 27\n706721 -885828\n606199 854425\n659001 -993753\n898961 885828\n-659001 885828\n748096 -973880\n21 -13\n-748096 606199\n-732894 991850\n13 -12\n659001 -737167\n-32 -32\n737167 -748096\n650983 -971645\n650983 -732894\n854425 -606199\n-606199 885828\n916399 -988877\n652232 -838743\n-606199 988877\n-620105 -652232\n-748096 -737167\n24 -23\n916399 854425\n");
	return 0;
}
/*
1
30
0 0
-971645 838743
748096 -988877
-652232 -993753
737167 -838743
-48 27
706721 -885828
606199 854425
659001 -993753
898961 885828
-659001 885828
748096 -973880
21 -13
-748096 606199
-732894 991850
13 -12
659001 -737167
-32 -32
737167 -748096
650983 -971645
650983 -732894
854425 -606199
-606199 885828
916399 -988877
652232 -838743
-606199 988877
-620105 -652232
-748096 -737167
24 -23
916399 854425
*/

Read More +

May 15 2015

解題區►解題區 - 其他題目

[Tmt514] Beverage Cup 2 D - A Parking Problem

Problem

停車場有 n 個位置呈現單方向，由入口到出口分別編號為 1 到 n，現在有 m 名駕駛準備要停車，每名駕駛的停車方案都會先開到偏愛的車位上，如果發現已經有人停過，則會往後找一個空車位。由於駕駛入停車場任意順序。請問從 m 個駕駛中挑出 n 個駕駛，任意進入停車場，按照他們各自偏愛的停車方法，每一位都有停車位的合法選擇駕駛的方案數。

Sample Input

1
2
3

1
3
2 1 2

Sample Output

Solution

維護前 i 個位置中，挑選 j 名駕駛的方法數！dp[i][j] 表示前 i 個位置，挑選 j 個駕駛的方法數，並且滿足 j >= i，否則會有留空一格造成後續的非法解。窮舉下一個位置挑選的人數 k，得到 dp[i+1][j+k] += (dp[i][j] * C[A[i+1]][k])%MOD;

#include <stdio.h>
const int MOD = 1000000007;
const int MAXN = 64;
long long C[MAXN][MAXN] = {};
int main() {
    C[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i-1][j] + C[i-1][j-1])%MOD;
    }
    int testcase, n;
    int A[MAXN];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        long long dp[MAXN][MAXN] = {};
        
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j <= n; j++) {
                for (int k = 0; k <= A[i+1] && j+k <= n; k++) {
                    dp[i+1][j+k] += (dp[i][j] * C[A[i+1]][k])%MOD;
                    dp[i+1][j+k] %= MOD;
                }
            }
        }
        printf("%lld\n", dp[n][n]);
    }
    return 0;
}
/*
 1
 3
 2 1 2
*/

Read More +

May 15 2015

解題區►解題區 - 其他題目

[Tmt514] Beverage Cup 2 B - Dreamoon's Criterion

Problem

夢月解題目會根據夢月法則？如果題目需要花費大於等於 t 的時間，則定義題目難度為 hard，反之為 easy。小番茄 (求解釋) 準備 n 個題目請求夢月協助，但隨著每解一題，下一題的難度會隨著疲累值增加，疲累值為一個等差為 k 個數列。只打算解決 easy 的題目，請問在相同的 k 下，不同的 t 分別能解決的最多題數。

Sample Input

Sample Output

1
2

4
0

Solution

t 越大，能解的題目肯定越多！難度越低的題目一定會選，因此前 i 小難度的題目都會被挑。利用類似求方程式值的方式 (隨便講講，別太在意 f(x) = a0 + a1x + a2x^2 + a3x^3 … + anx^n，可以在 O(n) 完成的方法) 下去猜測？維護已選題目如果增加 k 不大於 t 且下一個題目難度也小於 t，則所有已選難度都增加 k！離線處理，將詢問的 t 由小到大排序，掃描過去？

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
int A[MAXN], Qt[MAXN], out[MAXN];
int main() {
    int testcase;
    int N, K, Q;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &K);
        for (int i = 0; i < N; i++)
            scanf("%d", &A[i]);
        scanf("%d", &Q);
        for (int i = 0; i < Q; i++)
            scanf("%d", &Qt[i]);
        
        vector< pair<int, int> > QV;
        for (int i = 0; i < Q; i++)
            QV.push_back(make_pair(Qt[i], i));
        
        sort(QV.begin(), QV.end());
        sort(A, A+N);
        
        int idx = -1, sum = 0, t, mx = -0x3f3f3f3f;
        for (int i = 0; i < Q; i++) {
            t = QV[i].first;
            while (idx+1 < N && mx + K <= t && A[idx+1] <= t) {
                idx++, sum++;
                mx = max(mx+K, A[idx]);
            }
            out[QV[i].second] = sum;
        }
        
        for (int i = 0; i < Q; i++)
            printf("%d\n", out[i]);
    }
    return 0;
}
/*
 1
 5 2
 7 3 6 8 5
 2
 9
 1
*/

Read More +

May 15 2015

解題區►解題區 - 其他題目

[Tmt514] Beverage Cup 2 A - Attack and Split

Problem

有一隻史萊姆可以進行分裂和合併，大小為 x 的史萊姆可以分裂成兩個小史萊姆 y 和 z，滿足 x = y + z。當兩個史萊姆大小 p, q 合併時，新的史萊姆為 r = p xor q。請問是否存在數次的分裂和合併，所有史萊姆都消失！

Sample Input

Sample Output

1
2
3

No
Yes
Yes

Solution

亂來的奇偶和判定！以下是不負責任的說法！對於一種合法解 {a1, a2}，則 {a1-1, 1, a2-1, 1} 也一定會合法，不斷地拆分下去，所有史萊姆的大小都是 1，也發現到總和一定是偶數。因此只要判斷總和的奇偶數。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        int n;
        long long x, sum = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            sum += x;
        }
        puts(sum%2 ? "No" : "Yes");
    }
    return 0;
}
/*
 3
 1 1
 2 9 17
 3 12 15 19
*/

Read More +