Stuff about CP

General idea
- ลองคิด bruteforce ดู ถ้า bruteforce ได้ส่วนใหญ่ก็ dp ได้ (พวกแนวๆเลือก/ไม่เลือก, แบ่งช่วง, เลือกตัวต่อไป, เลือกว่าจะทำอะไร ไรเงี้ย)
- ลองแปลงคำถามดู แทนที่จะหาน้อยสุดมากสุด ลองหาว่า "ทำ x ได้มั้ย" ถ้ามันตรวจง่ายๆ แล้วคำตอบมันเรียง ก็ binary search ได้
- **อย่าพยายามยึดติดกับ pattern ใดๆ ลองคิดให้กว้าง หลายๆข้อต้องผสมผสานกันหลายอย่าง**

Common bugs
- true ไม่ใช่ 1, false ไม่ใช่ 0 อย่าเอามาบวกเลข ถ้าอยากบวกแปลงเป็น int ก่อน (x?1:0)
- timeout? เผลอใช้ฟังก์ชันอะไรที่มันใช้เวลาเกินคาดรึป่าว
- *******************
- PRINT แม่งทุกอย่างที่ขวางหน้า
- เรียกฟังก์ชัน? ปรินท์แม่งเลยว่าเข้าฟังก์ชัน เรียก argument อะไร ออกฟังก์ชัน คำตอบอะไร
- ลูป? ปรินท์ i j k ไปด้วยแม่งเลย
- มีตาราง/array? ปรินท์แม่งทุกรอบที่มีการเปลี่ยนแปลง
- ปรินท์แม่งให้หมด
- PRINT PRINT PRINT PRINT PRINT
- ********************

DP common bugs
- topdown ลองปรินท์ argument ทุกรอบที่โดนเรียกฟังก์ชัน ละก็ปรินท์คำตอบที่ return ด้วย (รวมถึง base case****)
- topdown memo ระวัง อาจจะใช้ 0 แทน "ยังไม่เคยมา" ไม่ได้ตลอด (พวกคำตอบเป็น 0 ได้ หรือว่าเป็น boolean ไรงี้)
- topdown ลืม memo
- เช็ค base case ทุกแบบที่เป็นไปได้ดูว่ามันให้คำตอบตรงกับนิยามจริงมั้ย (ลองดูแม่งทุกแบบเลย เช่นถ้ามีสามตัวแปรก็ลองดูว่า i=0, j=0, k=0, i=j=0, i=k=0, j=k=0, i=j=k=0 ถูกมั้ย)
- bottomup ปรินท์ตาราง **รวมถึงปรินท์ base case ทุกช่องด้วย** แล้วดูว่า base case ให้ผลตรงกับ topdown มั้ย
- bottomup เช็คลำดับการหาให้ดีๆ
- bottomup base case ดีจริงรึป่าว มีเกินขอบมั้ย
- เช็คว่าเรียกฟังก์ชัน topdown/เอาค่าจากตาราง bottomup มาหาคำตอบครบยัง (หาแค่ตัวสุดท้ายอย่างเดียว? ต้องหา sum? หา min/max?)
- **ไม่ควรหา min/max ระหว่างเรียกฟังก์ชัน/ทำตาราง dp เพราะจะงง หาตอนท้ายเอา**
- ระวัง memo เกินขอบตาราง (เลขติดลบ? sum เยอะเกิน?)

Binary search common bugs
- เช็ค bound เริ่มต้น/จบ ให้ดีๆ ต้องเป็นช่วงคำตอบที่เป็นไปได้
- กรณีที่ไม่มีคำตอบล่ะ? ต้องเช็คก่อนรึป่าว แล้วตอบ -1?
- ตัวฟังก์ชัน check รันแต่ละรอบต้องเป็นปัญหาแยกจากกันเลย อย่าลืมรีเซตตัวแปร
- เช็คว่าคำตอบที่ได้จากการ check แต่ละรอบเรียงมั้ย** (1,1,1,1,0,0,0,0,0... โอเค แต่ว่า 1,1,0,1,0,0,0 เงี้ย จะ bsearch หาไม่ได้ เพราะว่าไม่ได้เรียง อาจจะต้อง linear ไป)