Egg Drop ข้อถัดมา Egg Drop โจทย์เกี่ยวกับการทดลองโยนไข่จากตึก เพื่อหาว่าไข่จะแตกจากชั้นที่เท่าไหร่ โดย input จะมี จำนวนชั้นของตึก (F) จำนวนไข่ (D) จำนวนไข่ที่แตกได้ (B) ข้อนี้ข้อเดียวให้หาถึง 3 คำตอบ จำนวนชั้นของตึกที่มากที่สุด (FMax) จำนวนไข่ที่น้อยที่สุด (DMin) จำนวนไข่ที่แตกได้น้อยที่สุด (BMin) ลองไปอ่านเพิ่มเติม ที่นี่ เริ่มจาก FMax ข้อนี้สามารถ Solve ได้โดยง่ายด้วย Dynamic Programming คือ แทนที่จะคิดว่าจะหาสูตรอะไรเพื่อคำนวนได้ FMax เราก็แตก FMax เป็น subproblem แทน ได้มาเป็นสูตรนี้ FMax(d, b) = 1 + FMax(d-1,b) + FMax(d-1,b-1) 1 ตัวแรกคือ เมื่อโยนไข่ 1 ที เราก็รู้ว่าชั้นที่โยนแตกหรือไม่แตก FMax(d-1,b) คือ ถ้าโยนแล้วไม่แตก เราก็ขึ้นไปชั้นบนเพื่อโยนต่อไป d-1 คือ จำนวนไข่จะลดลง 1 และ b คือ จำนวนไข่ที่แตกยังเท่าเดิม เพราะโยนแล้วไม่แตก FMax(d-1,b-1) คือ ถ้าโยนแล้วแตก เราจะลงชั้นล่าง เพื่อโยนต่อไป คราวนี้จะเห็นว่าเป็น b-1 คือ จำนวนไข่ที่แตกลดลงไป 1 โดยมาก Dynamic Programming จะมาคู่กับ Memoization เพราะเราอาจจะเรียก input แบบเดิมซ้ำแล้วซ้ำอีก เราควรจะบันทึกคำตอบ ดีกว่าจะคำนวนใหม่อีกครั้ง นี้เป็นคำสั่ง Memoize let memoize f = หลักๆ คือใช้ dict ถ้าเคยเห็น input (n) แบบนี้แล้ว ก็ return value (v) ทันที แต่ถ้าไม่เคย ก็คำนวน (f) แล้วเอาค่ามาเก็บใน dict คราวนี้มาต่อกับ FMax let rec maxF = วิธีการหา result อธิบายไปแล้วด้านบน มีเพิ่มจากที่อธิบายไปก่อนหน้านิดนึง โจทย์สั่งว่าถ้า result มีค่ามากกว่าเท่ากับ 232 ให้ return -1 และถัดมา cache คือ การสั่ง memoize เพื่อจำคำตอบ อะไรที่เรียกจาก cache จะมีการคำนวนเพียงครั้งเดียวเท่านั้น ถัดมา คือการคืนค่าโดยไม่ต้องผ่าน cache ซึ่งค่าบางอย่าง เราสามารถคำนวนสดได้เลย ไม่ต้องผ่าน dynamic programming เริ่มจาก ถ้า b = 1 คือ ไข่แตกได้แค่ฟองเดียว ถ้ามีไข่อยู่ 10 ฟอง แต่แตกได้แค่ฟองเดียว เราก็โยนจากชั้นล่างขึ้นไปเรื่อยๆ จำนวนชั้นที่มากที่สุดคือ 10 ชั้น ดังนั้น ถ้า b = 1 และ d = 10 คือตอบคือ 10 และถ้า d = b มันจะกลายเป็น binary search ทันที จำนวน search space มากที่สุด สำหรับการค้นหา b ครั้งคือ 2b - 1 ซึ่งสามารถแปลงเป็น (1L <<< b) - 1L แต่ function maxF ยังมีจุดอ่อนคือ ถ้าจำนวนไข่ (d) มากกว่าจำนวนไข่ที่แตกได้ (b) มากๆ เช่น จำนวนไข่มี 2 พันล้าน แต่ไข่ที่แตกได้มีแค่ 2 ทำให้เกิดการ recursion เกือบ 2 พันล้านครั้ง แน่นอนว่าจะเกิด stack overflow และต่อให้ไม่เกิด stack overflow ก็ใช้เวลา search นานอยู่ดี แต่เนื่องจากโจทย์บอกว่า ถ้า result เกิน 232 ให้ return -1 เสมอ อีกสูตรที่เราควรหาคือ หาว่า input ของ function maxF จะเป็น overflow หรือไม่ วิธีหาก็ brute force เลยครับ let isOverflow = จากด้านบน คำสั่ง maxD เราก็แค่เพิ่ม d ไปเรื่อยๆ จนเจอ -1 เราก็หยุด และก็มี function จัดการนิดหน่อยเพื่อไม่ต้องเรียกจาก cache เช่น ถ้า b = 1 แล้ว d จะมีค่าเท่ากับ f เสมอ ตามที่อธิบายด้านบน ดังนั้นจึงไม่มีทาง overflow และถ้า b > 32 และ d จะมีค่าน้อยที่สุดคือ เท่ากับ b และเมื่อเข้าสูตร binary search แล้ว f จะมีค่ามากกว่า 232 เสมอ คราวนี้เราเริ่มหาค่า FMax ได้ด้วย function นี้ครับ let rec solveF d b = ถ้าจำนวนไข่ (d) น้อยกว่าจำนวนไข่ที่แตกได้ (b) เช่น มีไข่อยู่ 8 ใบ แต่สามารถแตกได้ 10 ใบ เมื่อไข่แตกไปแล้ว 8 ใบ จำนวนไข่ก็หมดไม่สามารถแตกได้อีกต่อไป ดังนั้น กรณีนี้ จำนวนไข่ที่แตกได้ จะไม่มีวันมากกว่าจำนวนไข่เสมอ ถัดมา หาค่า DMin ถ้าจำนวนชั้น (f) มีค่า 2 พันล้านชั้น และไข่ที่แตกได้ (b) มีแค่ใบเดียว จำนวนไข่ทั้งหมดที่ต้องมีคือ 2 พันล้านใบ search space ขนาดนี้ binary search สามารถเอาอยู่ let solveD f b = ถัดมา หาค่า BMin อันนี้เรารู้จากด้านบนแล้วว่า ถ้า b มีค่าเกิน 32 จะ overflow ดังนั้นค่า b จะมีค่าแค่ 1-32 เท่านั้น ใช้ brute force ไปเลยสะดวกที่สุด let solveB f d = สุดท้าย พิมพ์คำตอบ let solve f d b = จบ thx u crab
โดย: Kavanich96
![]() |