pbrt-v2 加速結構 Realistic Camera 改寫

Ray Sphere Intersection

計算射線和球體的交點,可以參照 /pbrt-v2/shapes/sphere.cppbool Shpere::Intersect() 的算法。

假設球體圓心座標 $O$,射線單位向量 $I$ 的起點座標 $C$,且最近目標交點座標 $P$,原半徑 $\mathrm{radius}$。射線走單位時間 $t$ 會到達球面上。

  • $\overrightarrow{OC} + \overrightarrow{I} \times t = \overrightarrow{OP}$
  • $|\overrightarrow{OP}| = \text{radius}$
  • $|\overrightarrow{OC} + \overrightarrow{I} \times t| = |\overrightarrow{OP}|$
  • $|\overrightarrow{I}|^2 t^2 + 2 \; (\overrightarrow{OC} \cdot \overrightarrow{I}) \; t + |\overrightarrow{OC}|^2 - \text{radius}^2 = 0$

解一元二次方程式之後可以得到 $t$ 得值,並得到交點座標 $P$

Snell’s Law

根據物理法則斯乃爾定律計算折射的方向向量,課程中提供三種做法。

變數解釋:入射介面材質 $\eta_1$,折射介面材質 $\eta_2$,入射單位向量 $\overrightarrow{I}$,交點面法向量 $\overrightarrow{N}$,折射方向向量 $\overrightarrow{T}$

特別小心 ray->d = Normalize(ray->d) 的處理,Heckbert’s Method 計算維持在單位圓上,故不用做最後的正規化計算。

Whitted’s Method

$\sqrt{}$ $/$ $\times$ $+$ compute
1 $n = \eta_1 / \eta_2$
3 3 2 $I' = I / (-I \cdot N)$
3 $J = I' + N$
1 1 8 5 $\alpha = 1 / \sqrt{n^2(I' \cdot I') - (J \cdot J)}$
3 3 $T' = \alpha J - N$
1 3 3 2 $T' = T' / \| T' \|$
2 8 17 15 TOTAL

Heckbert’s Method

$\sqrt{}$ $/$ $\times$ $+$ compute
1 $\eta = \eta_1 / \eta_2$
3 2 $c_1 = - I \cdot N$
1 3 2 $c_2 = \sqrt{1 - \eta^2(1 - c_1^2)}$
7 4 $T = \eta I + (\eta c_1 - c_2) N$
1 1 13 8 TOTAL

Other Method

$\sqrt{}$ $/$ $\times$ $+$ compute
1 $n = \eta_2 / \eta_1$
3 2 $c_1 = - I \cdot N$
1 2 3 $\beta = c_1 \sqrt{n^2 - 1 + c_1^2}$
3 3 3 $T = (I + \beta N ) / n$
1 4 8 8 TOTAL

其中以 Heckbert’s Method 消耗最少計算數。如果除法速度快於乘法,則使用 Other Method,原則上很少有機器運算除法比乘法快。

RasterToCamera

這部分處理後得到 Transform RasterToCamera。若計算錯誤,會造成一片黑或者圖片顯示的大小問題。座標轉換處理細節可以參考實際的例子,如下圖所示:

http://www.scratchapixel.com/lessons/3d-basic-rendering/ray-tracing-generating-camera-rays/generating-camera-rays

  • Raster-To-NDC 轉換矩陣 $A=\text{Scale}(scale, scale, 1)$,進行縮放。
  • NDC-To-Camera 轉換矩陣 $B=\text{Translate}(Vector(0, 0, filedistance)) \times \text{Translate}(Vector(X, -Y, 0))$,進行位移。
  • 最後得到 RasterToCamera 轉換矩陣 $C= B \times A \times \text{Scale}(-1, 1, 1)$,最後將 x 軸顛倒以符合成像問題。

Ray Weight

作業要求經過 float GenerateRay() 回傳 $\mathrm{weight} = \frac{\cos^4 \theta'}{Z^2}$,這麼設置會過暗,根據論文 A Realistic Camera Model for Computer Graphics 中寫道

If the exit pupil subtends a small solid angle from $x'$, $\theta'$ can be assumed to be constant and equal the angle between $x'$ and the center of the disk. This allows us to simplify
$E(x') = \int_{x'' \in D} L(x'', x') \frac{\cos \theta' \cos \theta''}{\| x'' - x'\|} dA''$<span>$to:$</span><!-- Has MathJax -->$E(x’) = L \frac{A}{Z^2} \cos^4 \theta’$
where $Z$ is the axial distance from the film plane to the dist and $A$ is the area of the disk.

A Realistic Camera Model for Computer Graphics: Figure 6

因此需要額外乘上常數 $A$,其中 $A$ 是最裡層的透鏡面積,因為我們是根據最裡層的透鏡面做均勻取樣,得到 $A = \mathit{backLens.radius}^2 \pi$

Sampling

單位圓均勻取樣方法有以下兩種,而非均勻取樣的寫法可參照 Sample 3 (錯誤的做法參照) 出來的效果看出。

Sampling 1

採用內建函數 CencentricSampleDisk(),採用 A Low Distortion Map Between Disk and Square 論文中提到的方案,將一個正方形壓縮到一個圓形中。參照作法如下圖所示

其中給定 $a, b$ 均勻分布 $[0, 1]$,則得到 $r = a, \; \phi = \frac{\pi}{4} \frac{b}{a}$,最後計算得到座標 $x = r \cos \phi, \; y = r \sin \phi$

Sampling 2

採用教科書上提供,其中給定 $a, b$ 均勻分布 $[0, 1]$,令 $r = \sqrt{a}, \; \phi = 2 \pi b$,最後計算得到座標 $x = r \cos \phi, \; y = r \sin \phi$

Sampling 3

分布 $[0, 1]$,令 $r = a, \; \phi = 2 \pi b$,最後計算得到座標 $x = r \cos \phi, \; y = r \sin \phi$。這種寫法在相同半徑下,角度均勻分布,不同半徑下的周長與 $r$ 成正比,導致不同半徑的取樣點不均勻,越靠近中心點取樣越密集,意即容易造成中心點看起來較亮。

Reference

Final Images Rendered Compare 4 samples

Gauss Lens








My Implementation (Sampling 1)



My Implementation (Sampling 2)



My Implementation (Sampling 3)


Fisheye Lens








My Implementation (Sampling 1)



My Implementation (Sampling 2)



My Implementation (Sampling 3)


Telephoto Lens








My Implementation (Sampling 1)



My Implementation (Sampling 2)



My Implementation (Sampling 3)


Wide-Angle Lens








My Implementation (Sampling 1)



My Implementation (Sampling 2)



My Implementation (Sampling 3)


Final Images Rendered Compare 512 samples

Gauss Lens









Reference



My Implementation (Sampling 1)



My Implementation (Sampling 2)



My Implementation (Sampling 3)


Fisheye Lens









Reference



My Implementation (Sampling 1)



My Implementation (Sampling 2)



My Implementation (Sampling 3)


Telephoto Lens









Reference



My Implementation (Sampling 1)



My Implementation (Sampling 2)



My Implementation (Sampling 3)


Wide-Angle Lens









Reference



My Implementation (Sampling 1)



My Implementation (Sampling 2)



My Implementation (Sampling 3)


Read More +

pbrt-v2 加速結構 Height Field 改寫

前情提要 pbrt

一套數位影像生成軟體,盡可能以物理性質為基底打造的,目前已經到了 pbrt-v3。pbrt 主要的工作在於 modeling 後,可以在場景內放置以幾何描述的物體、光源、拍攝曝光 … 等設定,藉由模擬光線走訪得到呈現在螢幕上每一個 pixel 的顏色。

目標工作

Height Field 是一個高度場,測資中以山脈構造為主,等間隔取樣每一平面上的每一點高度的場景,當間隔越小越接近真實場景。原生寫法是將點放置在三維空間,轉換成一堆三角網格,將其丟入 KD-tree 或者是 BVH 等加速結構,加快光線模擬找交點 (三維空間中,一射線和一多面體的交點) 的效能。而現在挑戰用 3D-DDA 的方式進行交點查找。

實作採用 3D-DDA 算法降至 2D Grid 上進行交點測試。Uniform Grid 將會切割成 $N \times M$ 的格子,在 2D 平面上,先找到 ray 進入的格子點,接著使用增量算法找到下一個格子,算法只測試投影到 x-y 平面上時,在 ray 鄰近的格子點做交點測試,時間複雜度 $O(\sqrt{N \times M})$,與預設的其他算法所需要的 traversal 複雜度差不多。

原本預設的 Height Field 拆成好幾個 Triangle,做法類似 Triangle Mesh,接著將這幾個 Triangle 利用 BVH 或者是 KD-tree 的架構進行,原本的做法會考慮三個維度,使用投影的方式只考慮兩個維度下的情況,接著再針對有相交的格子測試,最後才進行 3D Triangle 是否與 ray 相交。

實作 Height Field 時,考慮快取和再計算之間的好壞,則有兩種方法

  1. 預先將預處理每個 3D Triangle 座標 (消耗空間)
  2. 需要時,再創建 Triangle 出來測試 (消耗時間)

由於要找 ray 碰度到 uniform grid 的第一個格子,需要預處理 Height Field Bound Box,計算 Bound Box 需要 $O(N \times M)$,若不預處理會造成 3D-DDA 與暴力法 $O(N \times M)$ 無異。

若對 Height Field 進行 2D-DDA 好處在於一定是數個三角形構成,因此不用等到 ray.maxT 小於下一格交點的 NextCrossingT[stepAxis] 才能結束,一與三角形有交點就可以離開,因為每一格之間都有獨立性。

實作與測試細節

測試環境

一開始為了熟悉 pbrt 架構環境只實作求出交點的函數,

1
2
3
4
bool Heightfield2::Intersect(const Ray &r, float *tHit, float *rayEpsilon,
DifferentialGeometry *dg) const {
// 3D DDA
}

而直接忽略單純詢問交點是否存在,這會導致畫面一片黑,因為每打到一個交點會嘗試從物體表面的交點連到點光源。若下述函數恆真,則不存在光源到交點的路徑,因此產出來的圖片是一片黑。

1
2
3
bool Heightfield2::IntersectP(const Ray &r) const {
return true;
}

紋理模糊

找出紋理的兩個參數 $(u, v)$ 時,從 trianglemesh.cpp 複製過來的 class Trianglebool Triangle::Intersect() 函數得到的 $u, v$ 都是相對於三角形的 $0 \le u, v \le 1$ (直接 rendering 會看起來很多小格子點),因此得到相對的 $u, v$ 和交點 $p_{hit}$ (Object coordinate),則把 $p_{hit}$ 再次投影到 x-y 平面上,由於 height field 在 x-y 平面上長寬都是 1,投影到平面後得到 $p_{projection}$,對於整個 height field $u = p_{projection}.x, \; v = p_{projection}.y$

若測試 texture.pbrt 時,發生過模糊情況,其主要原因在於過多次座標轉換,如 Object -> World -> Object -> World,求出來的 $u, v$ 誤差就會放大。

將 height field 存成好幾個 triangle 可以像 class TriangleMesh 利用 index 標籤來壓縮記憶體,但實作為方便仍然每一個三角形都有實體的 Point,儲存三角形每一個點座標採用 object coordinate,先把 $ray$WorldToObject 得到 $ray'$,得到的交點 $p_{hit}$ 再進行 ObjectToWorld,如此一來模糊情況就會消失。

Phong 圓滑化

Phong interpolation 方法在三角形上面操作時,需要得知三個頂點的法向量,給予 height field 的資訊,並不曉得每一個頂點的法向量為何。得到每一個頂點的法向量,採用預先處理所有頂點的法向量並儲存起來,因為不斷地正規化是很耗時間的 (float sqrt(float x) 儘管採用 fast inverse square root 算法,也要極力避免多餘的運算)。

再計算頂點法向量時,根據影像處理中常用的一次差分 (differentiation) 遮罩

Case 1 邊緣
$$N_x = \begin{bmatrix} 0 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix}, \; N_y = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 0 \\ \end{bmatrix}$$
Case 2 非邊緣
$$N_x = \begin{bmatrix} 0 & 0 & 0 \\ -1 & 0 & 1 \\ 0 & 0 & 0 \\ \end{bmatrix}, \; N_y = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & -1 & 0 \\ \end{bmatrix}$$

上圖矩陣的中心座標為 $(x, y)$,將相鄰座標的高度值 $z$ 相減得到兩個方向的向量 $N_x, \; N_y$,外積得到座標 $(x, y)$ 的法向量 $N_{x, y} = \mathrm{Cross}(N_x, N_y)$

從另一個角度來看,將 height field 三角化後,每一個頂點原則上有 6 個鄰居,可以對每一個鄰居進行差分,接著順時針或者逆時針將兩兩相臨的向量外積,得到 6 個法向量平均後得到 $N_{x, y}$,這做法看起來比上述的差分來得穩定,但初始化消耗的時間會比較長,且撰寫的外積順序不對容易造成零向量的正規化錯誤。

Final Images Rendered with my implementation of heightfield.cpp

 






























hftest.pbrt (without Phong
interpolation)

Timings:


  • Original: 0.125 seconds

  • My implementation: 0.130 seconds (104% original)



landsea-0.pbrt (without Phong
interpolation)

Timings:


  • Original: 0.815 seconds

  • My implementation: 1.050 seconds (128% original)



landsea-1.pbrt (without Phong
interpolation)

Timings:


  • Original: 0.850 seconds

  • My implementation: 1.020 seconds (120% original)



landsea-2.pbrt (without Phong
interpolation)

Timings:


  • Original: 0.780 seconds

  • My implementation: 0.870 seconds (115% original)



texture.pbrt (without Phong
interpolation)

Timings:


  • Original: 0.450 seconds

  • My implementation: 0.520 seconds (120% original)





landsea-big.pbrt (without Phong
interpolation)


Timings:


  • Original: 6.200 seconds

  • My implementation: 2.200 seconds (35% original)


Final Images Rendered with my implementation of heightfield.cpp

 






























hftest.pbrt (with Phong
interpolation)

Timings:


  • My implementation: 0.135 seconds



landsea-0.pbrt (with Phong
interpolation)

Timings:


  • My implementation: 1.100 seconds



landsea-1.pbrt (with Phong
interpolation)

Timings:


  • My implementation: 1.050 seconds



landsea-2.pbrt (with Phong
interpolation)

Timings:


  • My implementation: 0.900 seconds



texture.pbrt (with Phong
interpolation)

Timings:


  • My implementation: 0.530 seconds





landsea-big.pbrt (with Phong interpolation)


Timings:


  • My implementation: 2.300 seconds


Read More +

即時系統 加入排程器

目標

修改 linux kernel,在 kernel/sched.} 相關 scheduler 部分增加 Weighted Round-Robin scheduler、Shortest Job First scheduler 以及 Rate-monotonic scheduler。最後藉由 Project 1 的練習撰寫測試程序驗證 scheduler 是否符合預期結果。

修改檔案列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
.
├── README.md
├── arch
│ └── x86
│ ├── include
│ │ └── asm
│ │ ├── unistd_32.h
│ │ └── unistd_64.h
│ └── kernel
│ └── syscall_table_32.S
├── include
│ └── linux
│ ├── sched.h
│ └── syscalls.h
└── kernel
├── sched.c
├── sched_fair.c
├── sched_rt.c
└── sched_weighted_rr.c

特別注意到,若編譯環境為 x86_64 則需要額外修改 arch/x86/include/asm/unistd_64.h 複製 arch/x86/include/asm/unistd_32.h 增加的 syscall。 同理,增加自己定義的 syscall 時,需要修改 arch/x86 下的那三個檔案 (如果發現編譯 kernel 時,出現 WARNING: syscall NOT IMPLEMENTION. 大多數都是這個造成)。

include/linux/sched.h 中,增加 task 的成員變數,提供接下來針對 task 操作需要的參數,特別的是在 struct sched_rt_entity; 中,相較於一般資料結構的寫法,linux 採用倒過來將節點訊息放在資料內部中,利用 #define container_of(ptr, type, member) 取得物件訊息,這種寫法方便解決 task 在數個 scheduler 中轉換。

因為 syscall 的方式設定 task weighted,增加一個全區變數 int weighted_rr_time_slice;,每一次 syscall 去設定這一個全區變數值,然後 task 建立時,經過 sched_fork,直接利用被修改全區變數作為這一個 task 的 weight。若要特別針對 task 設定 weighted round-robin,在建立前都要呼叫 syscall 設定全區變數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct sched_rt_entity {
...
//+ RTS Proj2: weighted_rr
struct list_head weighted_rr_list_item;
...
};
...
struct task_struct {
...
//+ RTS Proj2: weighted_rr
unsigned int task_time_slice;
//+ RTS Proj2: weighted_rr_prio
unsigned int weighted_time_slice;
//+ RTS Proj2: bonus RMS
int period;
...
};
...
//+ RTS Proj2: weighted_rr
extern int weighted_rr_time_slice;

Part 1. Weighted Round-Robin Scheduler

  • enqueue_task_weighted_rr()
    函數將會給予 task 和 rq,將 task 根據 rq 的資料結構重新將 task 放入。若按照 list 結構,直接模擬 queue 即可,由於 linux 提供 list 本身為雙向串列,直接加入尾端只需要 $\mathcal{O}(1)$ 時間。並且運行 rq->weighted_rr.nr_running++; 增加 rq 中的計數,隨後用來在回報該 scheduler 中有沒有存在 task 需要運行,方便在 $\mathcal{O}(1)$ 時間內完成,由於 Weighted round-robin 只需要確認 list 是否為空,那麼也可以利用 linux 提供的 list_empty() 確認。

  • dequeue_task_weighted_rr()
    當 task 完成任務時,都要呼叫 update_curr_weighted_rr 進行統計運行多久,並且更新與 task 相關的排程權重。接著將 task 從 rq 串列中移除,並且更新 scheduler 的 task 計數 (rq->weighted_rr.nr_running--;)。時間複雜度 $\mathcal{O}(1)$

  • requeue_task_weighted_rr()
    將一個 task 出列,在 Weighted round-robin 只需要直接對將 task.weighted_rr_list_item 移到串列最尾端,由於採用雙向串列,直接跟 scheduler 取得 list head (linux list 的 head 是不存放任何資訊) 直接加入尾端即可。時間複雜度 $\mathcal{O}(1)$

  • yield_task_weighted_rr()
    直接運行 \lstinline{requeue} 即可。

  • pick_next_task_weighted_rr()
    當最上層分配一段時間給 scheduler 運行,運行時會調用這個函數,並拿取要執行的 task,但並不用將其移除串列,並執行 next->se.exec_start = rq->clock; 紀錄 task 的開始運行時間,再呼叫 void update_curr_weighted_rr(struct rq *)。若不更新時間,則計算的相對運行時間會錯誤。

  • task_tick_weighted_rr()
    當 scheduler 運行時,每隔一段固定的時間會呼叫此函數。若程序執行量超過 scheduler 的設定,則需要更新串列,特別注意到 if (p->task_time_slice && --p->task_time_slice) 在原本預設是 unsigned int 型態,處理不當會造成 overflow,另一種情況會是一開始 quantum 設定為 0 所導致。
    需根據不同的 task 要補充不同的量 p->weighted_time_slice,不只要讓這支程式重進進入串列,同時需要呼叫 set_tsk_need_resched(p) (參考 kernel/sched_rt.c 代碼),藉以重新呼叫 pick_next_task_weighted_rr(struct rq*),否則這支程序會運行到結束。

Part 2. Shortest Job First Scheduler

  • enqueue_task_weighted_rr()
    與 Weighted round-robin 類似,利用 list 做插入排序,可以在最慘 $\mathcal{O}(n)$ 時間內維護一個優先權由高至低的 list。需要 task 時,直接將串列的首元素移除。

  • dequeue_task_weighted_rr()
    類同 Weighted round-robin。

  • requeue_task_weighted_rr()
    在最短工作優先排程中,由於 task 優先權會變動,不方便確定執行過一陣子的 task 要移動到哪裡,最簡單的實作方式採用 dequeue 後再一次 enqueue。時間複雜度 $\mathcal{O}(n)$

  • yield_task_weighted_rr()
    直接運行 \lstinline{requeue} 即可。

  • pick_next_task_weighted_rr()
    類同 Weighted round-robin。

  • task_tick_weighted_rr()
    在最短工作優先排程中若按照 Weighted round-robin 的寫法且不補充 quantum,則會變成 non-preemptive SJF。相反地,若要實作 preemptive SJF,需要在 check_preempt_curr_weighted_rr(struct rq*, struct task_struct*, int) 檢查執行的程序是不是串列的首元素,意即是不是最高優先權,如果不是最高優先權,則呼叫 resched_task() 即可完成 (詳見 Bonus RMS 的寫法)。

Bonus RMS

額外增加 syscall,修改三個檔案 unistd_32.h, unistd_64.h, syscall_table_32.S。增加 Rate-monotonic scheduler 的額外週期 (period) 和 syscall 函數主題,修改兩個檔案 sched.h, sched.c

程式碼細節 sched_weighted_rr.c

  • enqueue_task_weighted_rr
    使用與最短工作優先排程相同寫法,但利用週期 (period) 進行由優先權高到低排序。
  • check_preempt_curr_weighted_rr
    週期程式可能會搶之前正在運行程式,若發現運行程式的優先權低於要進入排程器的程式優先權,呼叫 resched_task() 重新排程。
  • 其餘類同 SJF。

測試程序 test_rms.c

參考 Project 1 的寫法,linux 針對每一個 thread 有各自計時的計時器,當 thread 被 context-switch 時,計時器也會隨之停止。

利用 main thread 產生週期性程式,pthread_create 並不會馬上將 thread 立即執行,迫使 main thread 的方式使用 sleep(1),以秒為單位產生週期性程式。由於要考慮週期程式的執行時間,又能在輸出緩衝區觀察順序關係,利用 thread 的計時器,盡可能接近 1ms 才進行一次印出,但這也會造成幾毫秒的誤差,對於一支程序一秒大約印出 1000 個字元,測試程式中,將連續相同字元計數,若相同字元取用四捨五入到秒才進行印出,計時誤差部分就不予輸出。

Github

https://github.com/morris821028/hw-realtime-system

Read More +

初體驗 qemu

若不想在 Windows 上灌 Virtual Box 進行 kernel 修改,那麼在 Linux 上面灌 qemu,在上面測試,假設只要測試 kernel 那麼 qemu 在第一次編譯以及在部分檔案重新編譯都只需要兩三分鐘。若 Windows 上用 Virtual Box 灌 Linux,又在 Linux 上面灌 qemu,容易遭遇到記憶體不夠的窘境。

Ubuntu Environment

Ubuntu 環境需要安裝下列插件。

1
2
$ sudo apt-get install qemu-system
$ sudo apt-get install libncurses5-dev

Buildroot

用 busybox 建造一直失敗,轉向學長推薦的 buildroot,用別人打包好的環境替 qemu 建造 file system。

site

1
2
3
$ wget https://buildroot.uclibc.org/downloads/buildroot-2015.11.1.tar.bz2
$ bzip2 -d FileName.bz2
$ tar xvf FileName.tar

Compile Config

Buildroot 提供很多參數給予選擇

1
$ make menuconfig

這次作業設定,由於需要改寫 kernel 版本為 2.6.32.* 左右,因此相關的 gcc 編譯器等設定如下。同時,根據機器架構設定,助教預設在 visual box 上面,通常為 i386,而我們用實驗室 server,編 x86 64。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Target options --->
Target Architecture (x86_64) --->
x86_64
Toolchain --->
C library (glibc) --->
glibc
Kernel Headers (Manually specified Linux version) --->
custom 2.6.x
2.6.32.6
System configuration --->
[*] Enable root login with password
[*] remount root filesystem read-write during boot
Filesystem images --->
[*] ext2/3/4 root filesystem
[*] tar the root filesystem

Compile

make -j8 用 8 個執行緒編譯,如果機器有很多個 core,那麼可以用 make -j20 在非常短的時間內完成。

接著在 buildroot

1
2
$ make -j8
$ cp output/image/rootfs.ext* WORKSPACE_PATH

Linux kernel config

1
2
$ make defconfig
$ make menuconfig
1
2
3
4
5
6
7
8
9
10
[_] Enable loadable module support
File systems --->
[*] Second extended fs support
[*] ext2
Device Drivers --->
Generic Driver Options --->
[*] Create a kernel maintained /dev tmpfs (EXPERIMENTAL)
[*] Automount devtmpfs at /dev

create arch/x86/boot/bzImage

1
$ make -j20

Test Flow

move test execute file

mnt.sh

1
2
3
sudo mount rootfs.ext2 mnt
sudo cp test_weighted_rr/test_weighted_rr mnt/root/
sudo umount mnt

run.sh

1
qemu-system-x86_64 -M pc -kernel arch/x86/boot/bzImage -hda rootfs-dirty.ext4 -netdev user,id=network0 -device e1000,netdev=network0 -nographic -append "root=/dev/sda console=ttyS0"

How to enlarge the rootfs.ext4

http://stackoverflow.com/questions/3495854/extend-the-size-of-already-existing-ext2-image

1
2
3
$ dd if=/dev/zero of=foo.img count=0 bs=1M seek=2000 # assuming target size is 2000M
# e2fsck -f foo.img
# resize2fs foo.img

Screen Workspace

commond tutorial

執行

1
$ screen
  • ctrl+a c
    開啟新的視窗,並同時切換到這個新的視窗
  • ctrl+a tab
    切換視窗
  • ctrl+a |
    切割垂直視窗,並產生新的視窗。
  • ctrl+a k
    關閉此視窗

之所以用 Screen 指令,主要是因為遠端到工作站上操作 qemu,若程序掛掉,很容易遭遇到要重新連線的麻煩事。

Speical Thanks

  • 蕭光宏 蕭大帥
  • Lab 332 Parallel & Distributed Laboratory

Virtual Box

第一次運行

1
2
3
4
5
6
$ cd /usr/src
$ sudo wget http://newslab.csie.ntu.edu.tw/course/rts2015/projects/linux-2.6.32.60.tar.gz
$ sudo tar -zxvf linux-2.6.32.60.tar.gz
$ cd linux-2.6.32.60
$ sudo make mrproper
$ sudo make menuconfig
1
2
$ scp morris1028@140.112.30.245:~/RTS/linux-2.6.32.60/arch/x86/include/asm/unistd_64.h arch/x86/include/asm/
$ scp morris1028@140.112.30.245:~/RTS/linux-2.6.32.60/kernel/sched_weighted_rr.c kernel/
1
2
3
4
$ sudo make bzImage
$ sudo make modules
$ sudo make modules_install
$ sudo make install
1
2
3
4
5
6
$ sudo vim /etc/default/grub
#Add "#" to comment the following 2 lines
#GRUB_HIDDEN_TIMEOUT=10
#GRUB_HIDDEN_TIMEOUT_QUIET=true
$ sudoupdate-grub2
$ sudoshutdown -r now

Test flow

1
2
3
4
5
$ cd /usr/src/linux-2.6.32.60
$ sudo make bzImage
$ sudo make modules
$ sudo make modules_install
$ sudo make install

Debug by printk

在另一個 terminal 開啟以下代碼,並且等待執行測試 scheduler 得執行檔在 kernel 運行時所打印出的 printk 訊息。

1
$ sudo more /proc/kmsg
Read More +

即時系統 使用排程器

目標

安裝 linux kernel 2.6.32.68、練習 pthread 設定 scheduler 相關函數以利後續修改 kernel source code。

設定 scheduler 問題

  • 設定 thread 可以在哪些 core 運行,由於要測試執行順序,強制讓 pthread 都在 CPU 0 運行。
    編譯時,增加 #define _GNU_SOURCE#include <pthread> 之前,確定 cpu_set_t 型別存在。
1
2
3
4
cpu_set_t mask;
CPU_ZERO(&mask);
CPU_SET(0, &mask);
sched_setaffinity(0, sizeof(mask), &mask);
  • 使用 sched_setscheduler() 時,需查閱 int policy 相關規定去設定 struct sched_param 的 priority 數值。例如 SCHED_FIFO 的 priority 介於 1 到 99 之間,若 priority 錯誤,sched_setscheduler() 會發生錯誤,錯誤訊息可以藉由 printf("Message␣%s\n", mid, strerror(errno)); 查閱。
1
2
3
sched_setaffinity(0, sizeof(mask), &mask);
int sched_setscheduler(pid_t pid, int policy,
const struct sched_param *param);
  • 如果 pid = 0,相當於 caller 的 thread 會被設置對應的 policy 和 sched_param。在 policy 設定 規範中,有兩種 real time scheduler SCHED_FIFOSCHED_RR。當 thread 設置 real time scheduler 時,需要用 root 權限來執行程式,否則會設置失敗。相反地,若使用 non-real time scheduler 則不需要 root 權限,如 SCHED_BATCH
1
2
3
4
5
struct sched_param param;
printf("Thread %d sched_setscheduler()\n", mid);
param.sched_priority = sched_get_priority_max(SCHED_FIFO);
s = sched_setscheduler(0, SCHED_FIFO, &param);
printf("Thread %d sched after %s\n", mid, strerror(errno));

三種方法設定 pthread

方法一

各自的 pthread_create() 後,再呼叫 sched_setscheduler() 進行設定。這種寫法在本次實驗有順序問題,在 create 之後,無法保證執行 sched_setscheduler() 的順序,無法依靠 main thread 中執行 pthread_create() 的順序決定。幸運地,仍可以使用

1
2
3
pthread_barrier_t barrier;
pthread_barrier_wait(&barrier);
pthread_barrier_init(&barrier, NULL, MAX_THREAD);

確保每一個 thread 都設置好各自的 sched_setscheduler() 後統一運行,運行順序取決 priority。

方法二

在 main thread 中,呼叫 pthread_attr_setinheritsched(attr, PTHREAD_INHERIT_SCHED); 接下來 create 出來的 pthread 都將繼承 main thread 的 scheduler 設定。這種寫法很方便,如果需要各自設置 priority 會不方便,倒不如直接用第三種寫法。

方法三

在 main thread 中,手動設置每一個 pthread 的 scheduler。

1
2
3
4
5
6
7
8
9
10
pthread_attr_t *attr = new pthread_attr_t;
struct sched_param *param = new struct sched_param;
// increasing order
param->sched_priority = sched_get_priority_max(SCHED_FIFO) - i;
// set scheduler
pthread_attr_setinheritsched(attr, PTHREAD_EXPLICIT_SCHED);
pthread_attr_setschedpolicy(attr, SCHED_FIFO);
pthread_attr_setschedparam(attr, param);
// create thread
pthread_create(&tid[i], attr, running_print, create_arg(i+1, scheduler))

計時設置

為確定每一個 thread 按照設定的 scheduler 運行,方式採用 print() 進行,但有可能輸出之間間隔距離過短,導致順序容易在輸出上發生無法預期的問題,適時地加入一秒間隔完成。

如何準確地停止一秒?不能呼叫 sleep() 因為這類的 system call 會產生 interrupt,此時 thread 將會降低 priority 或者進入隊列尾端。佔據 CPU time 有以下三種

busy work

只要停留的夠久即可,下面是一種簡單的方法

1
2
3
// busy 1 second
double a = 0;
for (int i = 0; i < 10000000; i++) a += 0.1f;

系統時間

利用 critical section 抓系統時間 int gettimeofday (struct timeval * tv, struct timezone * tz);,這寫法會共用同一份時間,因此需要使用 mutex 完成。仍使用一個迴圈來判定時間是否超過,實際運行時間會超過一秒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static double my_clock(void) {
struct timeval t;
gettimeofday(&t, NULL);
return 1e-6 * t.tv_usec + t.tv_sec;
}
pthread_mutex_lock(&outputlock);
{
double sttime = my_clock();
while (1) {
if (my_clock() - sttime > 1)
break;
}
}
pthread_mutex_unlock(&outputlock);

執行緒運行時間

事實上 Linux 有提供每一個 thread 各自的 clock,用來計算 thread 的執行時間。使用 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t),在舊版本需在編譯參數中加入 -lrt 才能使用。

1
2
3
4
5
static double my_clock(void) {
struct timespec t;
assert(clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t) == 0);
return 1e-9 * t.tv_nsec + t.tv_sec;
}

輸出 console 問題

SCHED_FIFO 這類的 real time scheduler 情況下,thread 輸出無法即時顯示在 terminal 上。

http://man7.org/linux/man-pages/man7/sched.7.html 可以見到 real-time scheduler 安排工作的比例,由於 print() 之後的顯示處理並不是 real-time process,當 real-time process 完全用盡 95\% 的 CPU time 時,顯示處理可能沒辦法在一秒內完成,可能要用好幾秒中的 5% 來完成。這也就是造成一開始會停頓一陣子,隨後才一次輸出數行結果。(註:並不是每一種裝置都會造成這問題,跟 CPU 時脈有關。)

The value in this file specifies how much of the period time can be used by all real-time and deadline scheduled processes on the system. The value in this file can range from -1 to INT_MAX-1. Specifying -1 makes the runtime the same as the period; that is, no CPU time is set aside for non-real-time processes (which was the Linux behavior before kernel 2.6.25). The default value in this file is 950,000 (0.95 seconds), meaning that 5% of the CPU time is reserved for processes that don’t run under a real-time or deadline scheduling policy.

解決這類的問題,可以從 kernel 設定著手,降低 real-time 最大佔有量,讓 print() 處理能即刻印出。這不是好的解決辦法,但可用於實驗。

1
2
3
4
// default
$ sudo /sbin/sysctl -w kernel.sched_rt_runtime_us=950000
// modify
$ sudo /sbin/sysctl -w kernel.sched_rt_runtime_us=500000

又或者採用拉大間隔,讓每一個 thread 都停止數十秒以上。

特別感謝

蕭光宏學長

Github

https://github.com/morris821028/hw-realtime-system

Read More +

2016 Facebook Hacker Cup Round 1

Facebook Hacker Cup Round 1

A. Coding Contest Creation

$N$ 個整數序列,每一個整數表示題目難度,可以在序列中插入整數,目標在序列中依序挑出 4 個整數作為比賽題目配置,並且要求不改變原本序列順序,滿足題目難度嚴格遞增,相鄰題目難度不大於 10,請問至少加入幾道題目。 (意即要插入題目的數量使得序列長度被 4 整除。)

最保守的方式 DP,只需要 $\mathcal{O}(N)$ 時間,記錄狀態 dp[i] 表示前 i 個 (不含) 整數滿足前述要求至少要插入幾個數,得到

$$dp[i] = min(dp[i], dp[j] + 4 - (i-j+1)), \; i -3 \le j \le i, \; c_{j, i} + (i-j+1)\le 4$$

,計算 $c_{j, i}$ 列出 $A_j, A_{j+1}, ..., A_{i}$ 得知至少要插入幾個數,貪心計算兩兩數字之間的差值 $\textit{diff}_k$$c_{j, i} = \sum (\left \lceil \frac{\textit{diff}_k}{10} \right \rceil - 1)$。每一個轉移最多 4 次,故時間複雜度 $\mathcal{O}(N)$

B. Laundro, Matt

小夥伴有 $L$ 件未洗衣物,洗衣店有 $N$ 台洗衣機和 $M$ 台烘衣機,洗衣機和烘衣機一次只能處理一件衣物,而對於每一台洗衣機對於衣物都有不同的處理時間 $W_i$,烘衣機則固定每 $D$ 時間就能烘好一次衣物。小夥伴可以暫存洗好衣物的籃子無限大,同時移動衣物的時間快到可忽略,請問至少要隔多久才能帶著所有洗好烘好的衣物離開洗衣店。

時間軸模擬題,用 priority queue 維護時間軸,在每一個時間戳記下檢查事件發生。模擬兩台機器交換衣物會稍微複雜,事件定義有三種:

  1. 某洗衣機可以在 $t_i$ 時間完成洗好一件衣服,下一次事件發生則是 $t_i + W_i$。不考慮何時放入衣物,每一次抓最近可完成的洗衣機進行清洗,直接當作洗好。
  2. 若有空的烘衣機,將洗好但未烘的衣物放入烘衣機,並將此烘衣機設定忙碌。並且標記 $t_i + D$ 時間此烘衣機會從忙碌變成閒置。
  3. 從忙碌變成閒置的烘衣機,記錄有多少衣物洗好烘好。

時間複雜度 $\mathcal{O}(L \log (N+M))$

C. Yachtzee

宅宅的退休工程師想建造遊艇,預算總額從 $[A, B]$ 隨機地挑一個,請問建造所剩餘金額的期望值為何。建造策略如下:

  1. 造遊艇分成 $N$ 個步驟,每一個步驟各自有其預算 $C_i$
  2. 造完一艘後,便著手建造下一艘,
  3. 直到某一個步驟預算不夠,便放下手上的計劃。(可能建造出半艘船)

數學期望值計算,時間複雜度 $\mathcal{O}(N)$,窮舉在每一個步驟罷工,因為卡在區間 $[A, B]$,計算剩餘金額在此步驟停止會稍微複雜。一艘船需要的預算為 $C$,那麼在某些情況 $C_i$ 會完全被 $[A, B]$ 包含,累計期望值 $\frac{0+C_i}{2}$,接著針對部分在區間 $[A, B]$ 的邊界情況。計算方法很多,在此也不多作解釋。

D. Boomerang Tournament

$2^N$ 個人進行樹狀單淘汰賽,給予每名選手互打的獲勝結果,在還沒公佈對局樹狀圖之前,請問每名選手預期能得到的最好和最壞名次為何。排名為嚴格多於自己的勝場數的選手個數。

選手最多 16 位,直接來個 $\mathcal{O}(16!)$ 絕對不行。當然樹狀圖的對稱性也許足以讓數量變得在時間內可窮舉完畢,但寫起來也複雜許多。

因此,利用位元壓縮 dp[參與選手集合][勝者] = 1/0 記錄子樹的情況,只需要 $\mathcal{O}(2^{16} \times 16)$ 個狀態總數,在集合合併處理需要窮舉子集合,由於我們只需要窮舉特定集合大小,複雜度不會到 $\mathcal{O}(3^{16})$ 這麼慘。合併時根據兩子樹的勝者相對打,同時紀錄兩位可夠晉級的最大最小回合數即可。

### Solution ###

#### A. Coding Contest Creation ####

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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
const int LMAX = 0x3f3f3f3f;
int dp[MAXN];
int main() {
int testcase, n, x;
int cases = 0;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
vector<int> A;
for (int i = 0; i < n; i++)
scanf("%d", &x), A.push_back(x);
for (int i = 0; i <= n; i++)
dp[i] = LMAX;
dp[0] = 0;
for (int i = 0; i < n; i++) {
vector<int> S;
for (int j = 0; j < 4 && i+j < n; j++) {
if (j && A[i+j] <= A[i+j-1])
break;
S.push_back(A[i+j]);
int inner = 0;
for (int k = 0; k < j; k++) {
int diff = S[k+1] - S[k];
inner += max(diff / 10 + (diff % 10 != 0) - 1, 0);
}
// printf("[%2d,%2d] %d %d\n", i, j, inner, (int) S.size());
if (inner + S.size() <= 4) {
// printf("update %d = %d from %d\n", i+j+1, dp[i] + 4 - (int) S.size(), dp[i]);
dp[i+j+1] = min(dp[i+j+1], dp[i] + 4 - (int) S.size());
}
}
}
printf("Case #%d: %d\n", ++cases, dp[n]);
}
return 0;
}

B. Laundro, Matt

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
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
const int LMAX = 0x3f3f3f3f;
int main() {
int testcase;
int cases = 0;
scanf("%d", &testcase);
while (testcase--) {
int L, N, M, D, W, target;
multiset< pair<long long, int> > EMPTYN;
multiset<long long> EMPTYM;
set<long long> timeline;
multiset< pair<long long, int> > S;
scanf("%d %d %d %d", &L, &N, &M, &D);
for (int i = 0; i < N; i++) {
scanf("%d", &W);
EMPTYN.insert({W, W});
timeline.insert(W);
}
target = L;
int basket = 0;
int complete = 0;
long long ret = 0;
timeline.insert(0);
while (timeline.size() != 0) {
long long time = *timeline.begin();
timeline.erase(timeline.begin());
while (L != 0 && EMPTYN.begin()->first <= time) {
pair<long long, int> e = *EMPTYN.begin();
EMPTYN.erase(EMPTYN.begin());
EMPTYN.insert({e.first+e.second, e.second});
timeline.insert(e.first+e.second);
L--, basket++;
}
while (!EMPTYM.empty() && *EMPTYM.begin() <= time) {
EMPTYM.erase(EMPTYM.begin());
M++;
complete++;
if (complete == target)
ret = time;
}
while (basket > 0 && M > 0) {
basket--, M--;
EMPTYM.insert(time + D);
timeline.insert(time + D);
}
}
printf("Case #%d: %lld\n", ++cases, ret);
}
return 0;
}

C. Yachtzee

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
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 131072;
const int LMAX = 0x3f3f3f3f;
long long C[MAXN];
double f(double l, double r) {
// printf("[%lf, %lf]\n", l, r);
return (r - l) * (r + l) / 2;
}
int main() {
int testcase;
int cases = 0;
scanf("%d", &testcase);
while (testcase--) {
int N;
double A, B;
scanf("%d %lf %lf", &N, &A, &B);
for (int i = 0; i < N; i++) {
scanf("%lld", &C[i]);
}
double ret = 0;
double sum = 0, pre = 0;
for (int i = 0; i < N; i++)
sum += C[i];
for (int i = 0; i < N; i++) {
double pp = ceil(A / sum);
double qq = floor(B / sum);
int st = pp, ed = qq;
set<int> S;
for (int j = max(0, st-3); j <= st+3; j++) {
if (S.count(j))
continue;
double l = j * sum + pre, r = j * sum + pre + C[i];
if (max(l, A) <= min(r, B)) {
ret += f(max(l, A) - (j * sum + pre), min(r, B) - (j * sum + pre));
}
S.insert(j);
}
for (int j = max(0, ed-3); j <= ed+3; j++) {
if (S.count(j))
continue;
double l = j * sum + pre, r = j * sum + pre + C[i];
if (max(l, A) <= min(r, B)) {
ret += f(max(l, A) - (j * sum + pre), min(r, B) - (j * sum + pre));
}
S.insert(j);
}
ret += f(0, C[i]) * max((ed-3) - (st+3)-1, 0);
pre += C[i];
}
ret /= (B - A);
printf("Case #%d: %.9lf\n", ++cases, ret);
}
return 0;
}
/*
5
2 100 200
100 100
2 100 200
50 100
*/

D. Boomerang Tournament

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
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 131072;
int g[16][16];
int dp[1<<17][16];
int main() {
int testcase;
int cases = 0, n;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
scanf("%d", &g[i][j]);
}
int ret[16][2], A[16];
A[0] = n/2;
for (int i = 1; i < n; i++)
A[i] = A[i-1]/2;
for (int i = 0; i < n; i++)
ret[i][0] = 0, ret[i][1] = __builtin_ffs(n)-1;
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++)
dp[1<<i][i] = 1;
int round[64] = {1};
for (int i = 0; i < 5; i++)
round[1<<i] = i;
for (int i = 0; i < (1<<n); i++) {
int cnt = __builtin_popcount(i);
if (cnt != (cnt & (-cnt)))
continue;
if (cnt == 1)
continue;
for (int j = (i-1)&i; j; j = (j-1)&i) {
if (__builtin_popcount(j) != cnt/2)
continue;
for (int p = 0; p < n; p++) {
if (dp[j][p])
for (int q = 0; q < n; q++) {
if (dp[i^j][q]) {
if (g[p][q]) {
dp[i][p] = 1;
// printf("%d %d %d\n", cnt, p, q);
ret[p][0] = max(ret[p][0], round[cnt]);
ret[q][1] = min(ret[q][1], round[cnt]-1);
} else {
// printf("%d %d %d\n", cnt, q, p);
dp[i][q] = 1;
ret[p][1] = min(ret[p][1], round[cnt]-1);
ret[q][0] = max(ret[q][0], round[cnt]);
}
}
}
}
}
}
// for (int i = 0; i < n; i++) {
// printf("[%d] %d\n", i, dp[(1<<n)-1][i]);
// }
printf("Case #%d:\n", ++cases);
int rank[16];
for (int i = 0, sum = 0; i < n; i++) {
sum += n>>(i+1);
if ((1<<i) == n)
rank[i] = 1;
else
rank[i] = n - sum + 1;
}
for (int i = 0; i < n; i++) {
int a = ret[i][0];
int b = ret[i][1];
// if (ret[i][1] != n) a = max(a, ret[i][1]);
// if (ret[i][0] != -1) b = min(b, ret[i][0]);
printf("%d %d\n", rank[a], rank[b]);
}
}
return 0;
}
Read More +

2016 Facebook Hacker Cup 資格賽

好一陣子沒用 C++ 解題,感覺新鮮。嗯 …

1
$ awk '{ sub("\r$", ""); print }' out.txt > output.txt

Facebook Hacker Cup 2016 Qualification Round

A. Boomerang Constellations

給予在星空下每顆星的座標,找出由三點構成回力鏢樣貌的組合個數,需滿足一點到兩點距離相等。

窮舉所有可能 $\mathcal{O}(N^3)$ 將會 TLE。窮舉回力鏢中心座標 $O$,統計其餘點到 $O$ 的距離,對於相同距離計數,套用組合公式 $C(n, 2)$ 加總,時間複雜度 $\mathcal{O}(n^2 \log n)$

B. High Security

給予只有兩排的長形棋盤狀的營地,雇用最少警衛監視每一塊區域,有些區域會因遮蔽物擋住警衛視線,而警衛只能監視平行兩軸的連續相鄰格子。求最少警衛個數。

第一眼覺得是 flow 可解,但求最少的模型建不太出來 Orz,就決定貪心。在同一行,連續片段上必然放置一個警衛,優先將連續片段總數匹配另一行連續個數恰好為一,剩下的情況再利用連續個數恰好一個的相互匹配。

C. The Price is Correct

參與一場遊戲,獎品價值為 $P$,給訂 $N$ 個正整數序列,挑選連續的序列總和小於等於 $P$ 即可獲得獎品,請問有多少挑選方式。

由於是序列為正整數,前綴和具有單調性,滑動窗口統計方法數只需要 $\mathcal{O}(N)$。最懶得方式是直接二分搜尋 $\mathcal{O}(n \log n)$

D. Text Editor

$N$ 個不同的單字中,打印恰好 $K$ 個輸出在螢幕上,操作有三種 1. 在尾端插入一個字符 2. 刪除字串尾端一個字符 3. 將緩衝區的字串印出來,並且在操作結束後,緩衝區大小為 0。求最少操作個數為何?

第一次遐想,由於要最少操作個數,想必前綴相似的都必須連續,因此先對所有單字排序,接著按照順序 DP。先不考慮操作 3,最後一定恰好為 $K$ 次,只需要考慮插入和刪除操作,維護最後一個在緩衝區為單字 $i$,轉移到下一個單字 $j$ 的成本是 len(Wi) + len(Wj) - LCP[i, j]*2 (刪除前面 $W_i$ 的後綴再加入 $W_j$ 的後綴),因此要預處理 LCA[i, j],題目給訂範圍應該不用套用 Trie 或者是 Suffix Array 進行查找,暴力計算即可。定義 DP[i][k] 表示目前打了 $k$ 個單字,最後一個單字恰好為 $i$ 的最少操作次數。在 DP 部分,時間複雜度 $\mathcal{O}(N^2 K)$

Solution

Sol. A. Boomerang Constellations

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 <bits/stdc++.h>
using namespace std;
#define MAXN 2048
long long X[MAXN], Y[MAXN];
int main() {
int testcase, cases = 0, n;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
long long ret = 0;
for (int i = 0; i < n; i++)
scanf("%lld %lld", &X[i], &Y[i]);
for (int i = 0; i < n; i++) {
map<long long, int> R;
for (int j = 0; j < n; j++) {
if (i == j)
continue;
long long dist = 0;
dist += (X[i] - X[j])*(X[i] - X[j]);
dist += (Y[i] - Y[j])*(Y[i] - Y[j]);
R[dist]++;
}
for (auto &p : R)
ret += p.second * (p.second-1)/2;
}
printf("Case #%d: %lld\n", ++cases, ret);
}
return 0;
}

Sol. B. High Security

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
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1024
char g[2][MAXN];
int main() {
int testcase, cases = 0, n;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
scanf("%s%s", g[0], g[1]);
int ret = 0;
int A[2][MAXN] = {}, B[2][MAXN] = {};
int used[MAXN] = {};
int gid = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] != '.')
continue;
int x = j, cnt = 0;
while (x < n && g[i][x] == '.')
x++, cnt++;
x = j;
gid++, ret++;
while (x < n && g[i][x] == '.')
A[i][x] = gid, B[i][x] = cnt, x++;
j = x;
}
}
// for (int i = 0; i < 2; i++) {
// for (int j = 0; j < n; j++)
// printf("%d", A[i][j]);
// puts("");
// }
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] != '.')
continue;
if (B[i][j] == 1)
continue;
if (used[A[i][j]])
continue;
int x = j;
while (x < n && g[i][x] == '.') {
if (g[!i][x] == '.' && !used[A[!i][x]] && B[!i][x] == 1) {
used[A[!i][x]] = 1;
ret--;
break;
}
x++;
}
while (x < n && g[i][x] == '.')
x++;
j = x;
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] != '.')
continue;
if (used[A[i][j]])
continue;
if (B[i][j] == 1) {
if (g[!i][j] == '.' && !used[A[!i][j]] && B[!i][j] == 1) {
used[A[!i][j]] = 1;
ret--;
}
}
}
}
printf("Case #%d: %d\n", ++cases, ret);
}
return 0;
}

Sol. C. The Price is Correct

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 131072;
int N;
long long P, B[MAXN], C[MAXN];
int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %lld", &N, &P);
for (int i = 1; i <= N; i++)
scanf("%lld", &B[i]);
C[0] = 0;
for (int i = 1; i <= N; i++)
C[i] = C[i-1] + B[i];
long long ret = 0;
for (int i = 1; i <= N; i++) {
int idx = (int) (lower_bound(C, C + N+1, C[i] - P) - C);
ret += i - idx;
}
printf("Case #%d: %lld\n", ++cases, ret);
}
return 0;
}

Sol. D. Text Editor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
const int MAXS = 131072;
const int MAXN = 512;
const long long LLMAX = 1LL<<60;
char s[MAXS];
int common[MAXN][MAXN];
long long dp[MAXN][MAXN];
int main() {
int testcase, cases = 0;
int N, K;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &N, &K);
vector<string> A;
A.push_back("");
for (int i = 0; i < N; i++) {
scanf("%s", s);
A.push_back(s);
}
sort(A.begin(), A.end());
N = A.size();
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
int cnt = 0, x = i, y = j;
for (int k = 0; k < A[x].length() && k < A[y].length(); k++) {
if (A[x][k] != A[y][k])
break;
cnt++;
}
common[i][j] = common[j][i] = cnt;
}
}
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= K; j++)
dp[i][j] = LLMAX;
}
dp[0][0] = 0;
// for (int i = 0; i < N; i++)
// printf("%s\n", A[i].c_str());
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
if (dp[i][j] == LLMAX)
continue;
for (int k = i+1; k < N; k++) {
long long t = 0;
t += A[k].length() - common[i][k];
t += A[i].length() - common[i][k];
dp[k][j+1] = min(dp[k][j+1], dp[i][j] + t);
}
// printf("%d %d - %lld\n", i, j, dp[i][j]);
}
}
long long ret = LLMAX;
for (int i = 0; i < N; i++)
ret = min(ret, dp[i][K] + (long long) A[i].length());
printf("Case #%d: %lld\n", ++cases, ret+K);
}
return 0;
}
Read More +

神境求生六十天

過了好幾個月沒有寫 Blog,原來說來話長,但絕不是沒有內容可寫,部分生存活動可以在 Github commit 上面見到。大部分時間都在處理批改娘系統 (Judge Girl Online Judge) 的架設,接著都在弄大一程式設計課程的練習題設置,由於追加功能的關係,寫網頁耗掉大量時間,強迫症總是讓我想討戰極限,套一句最近常講的「做好做滿」如果不能做好做滿,敷衍了事就對不起自己的靈魂!

進了台大什麼都不會、什麼都聽不懂,這些事情都已習慣。大學畢業之後,剩下的求學生涯都是 Bonus Time,那段等待死亡的時間看清自己能力的侷限,因此哪敢在這裡奢求什麼,大部分的人都是來求碩士畢業,而我呢?到底是來這裡做些什麼事情?

助教人生

《迷糊餐廳》

開學前幾週才跟幼琳老師 (翼世界站長) 把系統架好,架好之後陸陸續續開始有學生開始上來寫程式,既然是台大學生肯定是很厲害的,畢竟在這四年不斷地被台大學生擊潰,學生中起碼有幾位有如神一樣的存在。有趣的事情有很多,如「雞兔螃蟹同籠問題,好多因為螃蟹十隻腳算不出答案來詢問 … 不是八隻嗎?」看到新血們的努力,心中澎湃的情緒湧出,這些傢伙很快就比我更厲害了。

《迷糊餐廳》

但這件事情還沒有結束,由於幼琳老師換實驗室 (原因在這裡不能說,台大各種黑暗面),而其他學長因為其他雜事不接 TA 的工作,變得老師開得課只有我一個是實驗室的,其他助教是由老師從別的實驗室找來,但操作文件不夠完善,其他 TA 能幫忙的事情並不多,幼琳老師又要應付新實驗室的計畫,然後就開始活著孤立無援的生活。感謝的是,有幾位待畢業的學長 (待畢業原因不能說) 和已經順利畢業的學長偶爾會來實驗室,有問題還可以請他們幫忙看。

《野良神》

逐漸地發現這雜事相當耗時間,儘管這類疲勞是快感,但其他助教幫不上忙讓我有點生氣,明明都是有領錢的,而且它們還有台大原生種,雖然系統上不會操作,但修改題目描述、寫 C 程式驗證和生測資總是沒有下文,原本以為會主動冒出來的,看來總覺得我一個人幹就好,最後幾天看不下去,只好認賠殺出,他們都沒有競賽經驗,這一點令人擔憂。

老師出的小考題目有點競賽水準,絕不是以前大學亂學的語法小考,這一點讓我很興奮也很失望,原來台大學生這麼厲害,幾週內就把好幾個學期的內容學完,失望的地方在哪呢?準備小考題目事件繁重的任務,每一週小考生殺大權都在都在我手上,兩班快兩百人的分數,要是測資沒有處理好,抱怨聲會席捲而來。一個人處理這些事情,心裡好慌好無助,原來大家都為了畢業而努力,其他小事先擱著吧,而我為此犧牲吧。

巧遇劇場

《全部成為 F》

在台大碰巧遇到高中學弟,一下就是四年不見。

「好久不見」
「你怎麼會在這?」似乎沒法理解我為何在這裡
「我也在想『我為什麼會在這 …』」

暗地裡訴說

《四月是你的謊言》

因為題目太難而抱怨被學生責 ,你們是最強的也要成為最強的不是嗎?而真正強的人都忙著自己的事情無法教你們,只能由我來了,真的對不起啊。

Read More +

不懂的點滴

對研究所本身並沒多大的興趣,但仍一不小心有那個資格讀研究所,接著就被眾人催促去讀,的確我在此外沒有專長,但也不表示對這非常擅長,「有些事情,不試試看怎知道。」此話一出,無可奈何。

好不容易畢業,第一個問題除了找教授收留,另一個困擾是住宿,台大抽宿舍在我暑修英文時已經結束,連抽的資格都沒有,扣除掉北北基的同學,中籤率也只有 10% 左右,咱對此也沒有太大想法,每個月算住宿費 5000 到 8000 左右,而外頭找房子也差不多是這個價錢,套房則是接近萬元。

在還沒找到住宿的地點,暫時在別人家暫住一陣子,對台北生態相當不適應,每天搭捷運上下已經成了日常生活,每日開銷多一個麵包錢,以前中央住宿去便利商店要 15 分鐘的路程,現在若要吃點好的,看來要走比較遠去覓食,看到自助餐簡直是救星,也許能連續吃一個月!

研究所想要做什麼?第一次找教授目標就是算法相關,這麼說有點模糊,那用點排除法,網路硬體比較不能測試,個人對其不太感興趣,無法實作表示無法錯誤,更無法驗證理解。或者是數學梯度相關的機器學習、類神經網路,以前線代、微積分沒學好的債務,研究所估計是還不完的。

後來看到平行及分散式的實驗室,感覺實驗內容範圍可以接受,做好在裡面休學的心理準備,原本打算找純算法的教授,但被教授說請三思,的確我這種半吊子的算法理解很危險,那做點稍微應用的。當然平行分散這種加速方法,有很多替代方案,加速計算 = 減少算法複雜度,兩邊可以同時做,但算法設計的概念就不同,死亡 flag 插得穩穩。

進實驗室還有點緊張,在人生地不熟的環境生活,丟個垃圾都覺得麻煩,這裏人有著什麼樣的文化、必須做什麼樣的事都不懂,看著實驗室牆上的 LL 和其他動漫壁紙以及防潮箱的各種手辦,帶有一點親切感,沒想到這兒也有這樣的風情。看著實驗室的一角,充滿紙張的桌面,碩二學長再三問我「確定要選這個實驗室嗎?畢業機率去年好像是 38% 的樣子。而我們這一屆折損了一些人。」學長的話語聽來略帶威嚇,看來我走不出去了。

嗯 … 不久之後要跟教授約中午買便當過去談話,說這幾週做了什麼有趣的,便當問題是一重大挑戰,要是不仔細想想,絕對送坑給教授吃。而今天聽即將學長跟老師談話,沒想到老師打錯學長的名字,學長一度覺得「老師連我的名字都沒記住,還要下星期交出大部份的論文,其實我都只有實作,然而那還不完全,根本沒辦法下筆。」看著學長不斷地訴說學術的黑暗面,他說他要從打開窗戶跳下去,那樣的畫面已經自動浮出。

找教授的第一步,首先被問的是每個科目學了什麼,專題選了什麼,接著問道我解題目有沒有碰過跟實驗室相關的,接著又問近幾年 IOI 的問題有沒有碰,PTC 排程的問題有沒有看到,如果沒有就去寫寫吧!於是找完教授的幾天,過著一如往常的解題生活,順道開了幾個題坑,把以前一直沒解決的問題依序處理。

如果我還活著,下次再做生存回報吧。突然跳下去什麼的 …

Read More +

b500. 子字串集合

Problem

給予一個字串 $S$,求出所有子字串的集合,將集合內除了空字串以外的字串照字典順序輸出。

Sample Input

1
SLEEP

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
E
EE
EEP
EP
L
LE
LEE
LEEP
P
S
SL
SLE
SLEE
SLEEP

Solution

新手上路練習題,沒打算考很難的操作,即便如此信任也破產,看來出成變態題的機會高一點導致釣不到人來寫。

直觀作法是窮舉所有子字串,去掉重複即可,時間複雜度 $O(N^3)$,由於 $N = 500$ 也要考慮輸出的成本,所以不可能出太大。儘管如此,來比較算法之間的空間和時間用量。

首先,最常見到的 set 作法,若直接儲存字串空間用量 $O(N^3)$,為了避免空間太多,可以自己寫一個 compare function 來完成,因此 set 只要記錄子字串的起始位置和長度即可,時間複雜度 $O(N^3)$,空間降到 $O(N^2)$

接著,進入到後期,常用到字典樹 trie,若把所有後綴插入到字典中,接著在 trie 走訪輸出所有結果即可,時間複雜度 $O(N^2)$,空間 $O(N^2 \times 26)$。可以使用 double-array trie 捨棄掉一點時間,降低節點的空間使用量。

最後,比較強悍的後綴自動機,在劉汝佳的書上主要是用 DAWG (directed acyclic word graph) 來描述 suffix automaton,後綴自動機可以在線構造,時間和空間複雜度都是 $O(N)$,後綴自動機可以接受 $S$ 所有的後綴,關於建造時間和狀態總數的證明可以參考 《Suffix Automaton 杭州外国语学校 陈立杰》 的簡報。

若不想這麼詳細的證明狀態總數和時間複雜度,可以從 AC 自動機的建構概念來思考,一樣有 fail 指針,來維護當一個後綴失去匹配,移除前綴要移動到的狀態。特別的是,每一次增加最多兩個節點,最後一次增加的節點為 accept state (後綴自動機只有一個或兩個 accept state),其中一個節點是解決當前字串的後綴長度 1 的轉移。

根據這一題的需求,走訪一次後綴自動機就能印出所有子字串。

  • set 解法一 AC (0.2s, 25.2MB)
  • set 解法二 AC (0.4s, 3.8MB)
  • trie AC (0.1s, 12.1MB)
  • Double-array trie AC (0.2s, 7.7MB)
  • 後綴自動機 suffix automaton AC (64ms, 240KB)

後綴自動機

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
#include <bits/stdc++.h>
class SuffixAutomaton {
public:
static const int MAXN = 500<<1;
static const int MAXC = 26;
struct Node {
Node *next[MAXC], *pre;
int step;
Node() {
pre = NULL, step = 0;
memset(next, 0, sizeof(next));
}
} _mem[MAXN];
int size;
Node *root, *tail;
void init() {
size = 0;
root = tail = newNode();
}
Node* newNode() {
Node *p = &_mem[size++];
*p = Node();
return p;
}
int toIndex(char c) { return c - 'A'; }
char toChar(int c) { return c + 'A'; }
void add(char c, int len) {
c = toIndex(c);
Node *p, *q, *np, *nq;
p = tail, np = newNode();
np->step = len;
for (; p && p->next[c] == NULL; p = p->pre)
p->next[c] = np;
tail = np;
if (p == NULL) {
np->pre = root;
} else {
if (p->next[c]->step == p->step+1) {
np->pre = p->next[c];
} else {
q = p->next[c], nq = newNode();
*nq = *q;
nq->step = p->step + 1;
q->pre = np->pre = nq;
for (; p && p->next[c] == q; p = p->pre)
p->next[c] = nq;
}
}
}
void build(const char *s) {
init();
for (int i = 0; s[i]; i++)
add(s[i], i+1);
}
void dfs(Node *u, int idx, char path[]) {
for (int i = 0; i < MAXC; i++) {
if (u->next[i]) {
path[idx] = toChar(i);
path[idx+1] = '\0';
puts(path);
dfs(u->next[i], idx+1, path);
}
}
}
void print() {
char s[1024];
dfs(root, 0, s);
}
} SAM;
int main() {
char s[1024];
while (scanf("%s", s) == 1) {
SAM.build(s);
SAM.print();
}
return 0;
}

set ver 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main() {
char s[512];
while (scanf("%s", s) == 1) {
set<string> S;
int n = strlen(s);
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
char c = s[j+1];
s[j+1] = '\0';
S.insert(s+i);
s[j+1] = c;
}
}
for (auto &x : S)
puts(x.c_str());
}
return 0;
}

set ver 2

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 <bits/stdc++.h>
using namespace std;
char s[512];
struct cmp {
bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
for (int i = 0; i < a.second && i < b.second; i++) {
if (s[a.first+i] != s[b.first+i])
return s[a.first+i] < s[b.first+i];
}
return a.second < b.second;
}
};
int main() {
while (scanf("%s", s) == 1) {
set< pair<int, int>, cmp > S;
int n = strlen(s);
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
S.insert({i, j-i+1});
}
}
for (auto &x : S) {
int base = x.first, len = x.second;
char c = s[base+len];
s[base+len] = '\0';
puts(s + base);
s[base+len] = c;
}
}
return 0;
}

trie

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
#include <bits/stdc++.h>
using namespace std;
class Trie {
public:
static const int MAXN = 130000;
static const int MAXC = 26;
struct Node {
Node *next[MAXC];
void init() {
memset(next, 0, sizeof(next));
}
} nodes[MAXN];
Node *root;
int size;
Node* newNode() {
assert(size < MAXN);
Node *p = &nodes[size++];
p->init();
return p;
}
void init() {
size = 0;
root = newNode();
}
inline int toIndex(char c) {
return c - 'A';
}
inline int toChar(char c) {
return c + 'A';
}
void insert(const char str[]) {
Node *p = root;
for (int i = 0, idx; str[i]; i++) {
idx = toIndex(str[i]);
if (p->next[idx] == NULL)
p->next[idx] = newNode();
p = p->next[idx];
}
}
void dfs(Node *u, int idx, char path[]) {
for (int i = 0; i < MAXC; i++) {
if (u->next[i]) {
path[idx] = toChar(i);
path[idx+1] = '\0';
puts(path);
dfs(u->next[i], idx+1, path);
}
}
}
void print() {
char s[1024];
dfs(root, 0, s);
}
} tree;
char s[1024];
int main() {
while (scanf("%s", s) == 1) {
int n = strlen(s);
tree.init();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
char c = s[j+1];
s[j+1] = '\0';
tree.insert(s+i);
s[j+1] = c;
}
}
tree.print();
}
return 0;
}

DA trie

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
#include <bits/stdc++.h>
using namespace std;
class DATrie {
public:
static const int MAXN = 500000;
static const int MAXC = 27;
struct Node {
int check, base, fail, val;
} A[MAXN + MAXC];
int node_size, mem_size, emp_size;
//
int son_pos[MAXC], find_pos;
inline int toIndex(char c) {
return c - 'A' + 1;
}
inline int toChar(char c) {
return c + 'A' - 1;
}
inline bool isEMPTY(int u) {
return u < MAXN && A[u].check < 0 && A[u].base < 0;
}
void init() {
for (int i = 1; i < MAXN; i++)
A[i].check = -(i+1), A[i].base = -(i-1);
for (int i = MAXN; i < MAXN + MAXC; i++)
A[i].check = INT_MAX;
A[MAXN-1].check = -1, A[1].base = -(MAXN-1);
A[0].check = -1, A[0].base = 0;
node_size = mem_size = emp_size = 0, find_pos = 1;
}
inline void rm_node(int x) {
if (find_pos == x) find_pos = abs(A[x].check);
A[-A[x].base].check = A[x].check;
A[-A[x].check].base = A[x].base;
node_size++;
mem_size = max(mem_size, x);
}
inline void ad_node(int x) {
A[x].check = MAXN, A[x].base = MAXN;
emp_size++;
}
bool insert(const char *s) {
int st = 0, to, c;
int flag = 0;
for (int i = 0; s[i]; i++) {
c = toIndex(s[i]);
to = abs(A[st].base) + c;
if (st == abs(A[to].check)) {
st = to;
} else if (isEMPTY(to)) {
rm_node(to);
A[to].check = st, A[to].base = to;
st = to;
} else {
int son_sz = 0;
int pos = find_empty(st, c, son_sz);
relocate(st, pos, son_sz-1);
i--;
}
}
A[st].base = -abs(A[st].base);
return 1;
}
int find(const char *s) {
int st = 0, to, c;
for (int i = 0; s[i]; i++) {
c = toIndex(s[i]);
to = abs(A[st].base) + c;
if (st == abs(A[to].check))
st = to;
else
return 0;
}
return A[st].base < 0;
}
int find_empty(int st, int c, int &sz) {
sz = 0;
int bs = abs(A[st].base);
for (int i = 1, j = bs+1; i < MAXC; i++, j++) {
if (abs(A[j].check) == st)
son_pos[sz++] = i;
}
son_pos[sz++] = c;
int mn_pos = min(son_pos[0], c) - 1;
for (; find_pos && (find_pos < bs || find_pos < mn_pos); find_pos = abs(A[find_pos].check));
for (; find_pos; find_pos = abs(A[find_pos].check)) {
int ok = 1;
for (int i = 0; i < sz && ok; i++)
ok &= isEMPTY(find_pos + son_pos[i] - mn_pos);
if (ok)
return find_pos - mn_pos;
}
printf("Memory Leak -- %d\n", find_pos);
exit(0);
return -1;
}
void relocate(int st, int to, int sz) { // move ::st -> ::to
for (int i = sz-1; i >= 0; i--) {
int a = abs(A[st].base) + son_pos[i]; // old
int b = to + son_pos[i]; // new
rm_node(b);
A[b].check = st, A[b].base = A[a].base;
int vs = abs(A[a].base);
for (int j = 1, k = vs+1; j < MAXC; j++, k++) {
if (abs(A[k].check) == a)
A[k].check = b;
}
ad_node(a);
}
A[st].base = (A[st].base < 0 ? -1 : 1) * to;
}
void dfs(int u, int idx, char path[]) {
for (int i = 1; i < MAXC; i++) {
int to = abs(A[u].base) + i;
if (u == abs(A[to].check)) {
path[idx] = toChar(i);
path[idx+1] = '\0';
puts(path);
dfs(to, idx+1, path);
}
}
}
void print() {
char s[1024];
dfs(0, 0, s);
}
} tree;
char s[1024];
int main() {
while (scanf("%s", s) == 1) {
int n = strlen(s);
tree.init();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
char c = s[j+1];
s[j+1] = '\0';
tree.insert(s+i);
s[j+1] = c;
}
}
tree.print();
}
return 0;
}
Read More +