# Tips for your homework --- ## 手寫 / Hand-Written --- #### 如何寫數學證明？ - 精簡 - 清楚的標示出你會需要用到的引理 - 了解「估計與構造」的寫作過程 - 你可以參考一些有用的網站，例如[這裡](https://web.evanchen.cc/handouts/english/english.pdf) - 一開始還不太會寫不用太氣餒 ---- #### How to write a mathematical proof - Simplify your proof - Mark the lemma or theorem you used clearly - Understand the process of explaining your "Estimation and Construction" - Checkout some websites [here](https://web.evanchen.cc/handouts/english/english.pdf) - Don't be discouraged when you fail in the beginning --- #### 演算法證明？ - 一道演算法證明中必須要有 - 演算法的內容 - 正確性證明 - 時間複雜度的分析 - 除非題目特別提及，否則**缺一不可** ---- #### Proofs about algorithm - A complete proof of an algorithm should contain - Description of your algorithm. - Proof of the correctness - Analysis of the time complexity - They are **indispensable** unless specified in the problem description. --- #### 適當的省略不必要的資訊 - 判斷出一道證明的重點，省去非重點部份的細節 - 尤其當題目希望你「briefly describe」你的證明時，這表示我們只希望看見你「具有證明該題的能力」，大多數細節在此即可被忽略 ---- #### Skip unimportant information - Try to find out the most crucial part of a proof. Skip those unimportant details - Especially when a problem wishes you to "briefly describe" your proof, we only want to know that you "are able to prove this problem", most of the details can be skipped in this case. --- ## 程式 / Programming --- #### 出 bug 了 QQ (RE) * 使用太多記憶體 * 使用到不合法的記憶體 * 除以 0 * 可以試著開 sanitizer 來找找看 * `g++ code.cpp -fsanitize=undefined,address -g` * `-D_GLIBCXX_DEBUG` 可以印出 STL 的 debug 訊息 ---- #### Got verdict "RE" QQ * Allocate too many memory * Access illegal memory address * Division by zero * Try the sanitizer provided by the compiler * `g++ code.cpp -fsanitize=undefined,address -g` * `-D_GLIBCXX_DEBUG` prints more debug messages of STL containers. --- #### 出 bug 了 QQ (TLE) * 估算 worst case（助教們都會生這種測資的）的時間複雜度 * 代入題目的範圍 * 如果算出來的數字 $>$ 秒數$\times 10^8$，那高機率會 TLE * 例：$N = 2000$ 的題目中，$O(N^2)$ 不會 TLE，$O(N^3)$ 會 ---- #### Got verdict "TLE" QQ * Estimate the worst case of the time complexity * Bring in the range of the input in the problem * You will probably get a time limit exceeded if the number you get is more than $\text{number of seconds} \times 10^8$ * For example, in a problem with $N = 2000$, $O(N^2)$ won't get time limit exceeded but $O(N^3)$ will. --- #### 出 bug 了 QQ (WA) * 測試你的程式碼 * **範例測資** * **範例沒包含的 case** * **極端狀況** * 找到一個會 WA 的測試資料 * 寫一個比較慢但是**正確性是對**的程式 * 用上面那個程式來找出會 WA 的資料 ---- #### Got verdict "WA" QQ * watch your code and meditate * **Sample Testcases** * **Testcases that are not in samples** * **Corner cases/Edge Cases** * Find a testdata that your program gets "WA" on it. * Write another program which you have more confidence that **it is correct** (it may be slower though) * Use the above program (maybe with a testdata generator) to find the testdata. --- #### 出 bug 了（各種其他問題） QQ * 問同學 * 問 TA * 問認識的人 * 問不認識的人 ---- #### Still can't get "AC" QQ * Ask your classmates * Ask TA * Ask someone you know * Ask someone you don't know