T-414-ÁFLV Lecture 1 Homework

再來一篇短篇, 今天在公司趁有空, 把上一篇介紹的那個Course 的第一課所有功課都完成了

這些功課都是在一個叫 Kattis 的Online Judge上提交的, 這個OJ還算可以吧, 算漂亮的

由於是第一課, 都是一些比較基本的題目...

有好些題還有印象曾做過了

曾經會為了做到這些題目高興呢

但現在看來也只是Div. 2 A-C 的難度吧....

這個Course 每一課都有一些相關題目, 這第一課 "Introduction" 的功課大多是Ad-hoc

除了 Bonus 那2題還算有趣 , Bonus 那2題其中有一題太麻煩了所以沒做 就做了另一題

(這個Course每一課都有Bonus的高難度題目)

Ad-hoc的Bonus題, 難度大多在於I/O Format...超麻煩的

我選了一題非Bonus的題目, 和一題Bonus的題目來記下

下一篇文章會返回現在的程度的東西...這篇就當是熱身 / 遊戲的題目吧...

絕對不能因為會做這些沒什麼思路的題目而開心呢

T-414-ÁFLV Lecture 1 Homework

普通題目: Chess (Ad-hoc, STL)

https://open.kattis.com/problems/chess

很肯定在比賽生涯很早期 (早到只懂scanf printf 那些) 有做過
現在覺得沒什麼好想的 倒是怎樣code 有聰明有笨的方法吧...

思路是查parity是否能到 (題目連parity都告訴你了...)
能去到的話, 最多只要2步, 證明很簡單, 任何 2個格子, 打個交叉
不難想像這2個交叉肯定會在某一格相遇,  所以最多可以從起點到那一格再到終點

實作上來也是直接這樣做了...code起上來才發現這樣code也沒多短....
先用2個SET 儲起2個交叉的點  再查一查那一格是相遇的一格
特別處理0步, 1步能到的情況

好像沒多聰明, 應該怎樣都比當時的我要好吧...能過就好了...

Bonus題目: Booking (Ad-hoc, Graph, Greedy)

https://open.kattis.com/problems/booking

這題絕對有資格做Bonus題目...
我是第一次做的, 除了Input Format麻煩之外...
背後的思路 對於一個初學者來說也是麻煩的...

肯好我正重溫CSC2110不久
這題正是赤裸裸的 Interval Graph (Minimum) Coloring!

正好這題也清了我一些很久以前的concept 特意記下
(連同上一篇SPOJ 那一題 我曾說不知是Sort by 什麼...也是有關係的)

這兒先說一下
首先Graph Colouring 的問題,  就是要找Minimum Number to Color a Graph (Chromatic Number)

In general, 這問題是 NP-Complete的!!

但還是有些特例, 有些 Positive Result 很好利用的

例如某些graph 的 chromatic number X(G)是肯定的:

1. X(Tree) = X(Bipartite Graph) = 2
2. X(K-complete graph) = K
3. Simple cycle = 2 if even,  3 if odd
4. Wheel = 3 if even, 4 if odd

當中第 2 個property 會導出另一個結果:
任何Graph 的 X(G) >= K where K is maximum complete sub-graph size

這個很直觀就不特別解釋了...

然後對於一種很特別的Graph:  Interval Graph (有頭有尾的segment作為vertex , overlap / conflict的話則有edge), Chromatic Number是有P解的!

這種Graph 有一個有趣的property, X(G) = K where K is maximum complete sub-graph size
是Strict 的 Bound

證明是用Maximum Degree Ordering的結果, 再證明任何 Interval Graph 如果存在K complete sub-graph的話必定可以把點以這個Order 排序, results follow (詳情看2110 notes, 思路很有用)

由證明的過程直致導出P的解法: (Greedy的想法)

1. 把 Interval 按 Ending Time 排序
2. 從最後的Interval開始, 看之後有多少Interval 的Start Time < 該Interval的End Time
   這個數字就是一個 K complete subgraph 的K
3. Loop 所有Interval 找出第2步的 K, 取最大值 就是 X(G)了

1棍AC, 複雜度是O(n^2)  直覺上絕對有更快的做法, 但這題 n 是5000, 就沒多想了...

再來我做了個實驗的說, Sort by Start time 再做可以嗎?

算法也差不多, 也是取某 Interval, 然後看所有之前 (之後) 的 Interval 有沒有conflict, 求K

果斷WA!!  想了良久終於發現重點了....也解決了心中良久的疑問 

假設這是sort by start time後的排序...在處理第 i 個interval時

i 之後有多少interval 跟 i conflict, 這兒是 3

但明顯 實際答案是 2...問題在那?

答案是: 當第 j 個interval 跟第 i 個interval 有conflict, (j > i) 不代表所有其中的interval 可以組成complete sub-graph!!!

以上面的例子, i+1跟i+2 沒有conflict,  i, i+1, i+2 根本組不成 3-complete sub-graph

上面的P解法源至那個Proof, 為什麼上面AC了的做法可以?

因為那個做法確保了 所有跟第 i 個interval 有conflict 的 interval 肯定是complete sub-graph

證明是: 我們已經sort by end time, 所以所有 j 的interval 肯定比 i interval 遲完結

有conflict 代表第 j 個interval 的start time 比 i interval的end time 早...

這樣已經肯定所有跟第 i 個interval 有conflict 的 intervals 能組成complete graph了...

因為在第 i 個interval 的end time 打直劃一筆, 肯定能穿過所有跟它有conflict的intervals..!

理解完這些後, 我就想了, 所以重點在於 判定 i-th 跟 j-th interval有conflict時, 要肯定所有這樣的 j-intervals 跟 i-th interval 可以組成 complete graph吧...?

那麼sort by start time, 由第一個interval 開始loop 也是可以的吧?

只要我看的是第 i 個interval的start time, 要是 j (j < i)  的end time 比 i-th interval 的start time

後的話, 

這些intervals 肯定能各自相互在 i-th interval的start time conflict, 組成complete graph!

想完後立刻做做看...結論是....AC!!

所以我立即想通了...sort by start time / end time其實不是重點, Loop的方向也不是重點, 重點是sort 完之後, 要確保一個property: 就是在判定conflict時, 要肯定所有跟 第 i 個interval 有conflict的 interval 能組成complete sub-graph!

這題就是這樣了...很好的重溫

實作方面也很不錯 (麻煩), 由於是Date Time的format, 用C++很不好處理

肯好前天理解Segment Tree時已經有在寫Struct, 這題也很直接地用2個Struct 加一些operation overload 解決

這兒是第一種解決方法的Code (Sort by End Time)

實際上由於還要把那個datetime 加minute, 有潤年(題目有提醒...算很好了)

所以有點長

https://open.kattis.com/submissions/717128

順帶重溫了Struct中怎樣overload operator...很多時都有用呢 (尢其要用有comp的STL時)
為什麼要const, 要 &, 我不知道

bool operator<(const datetime& x)const{}

bool operator==(const datetime &x)const{}