toi

TOI19 explorer - นักสํารวจ (Explorer)

🏠 รวมเฉลย TOI19

💎 problem.pdf

🎉 solution.cpp

🤢 Math (การนับ permutation / combination)!!

ให้แปลงลำดับการเดินให้กลายเป็นกราให้ได้ก่อน โดยใช้ stack

เช่น 1 2 4 2 5 2 1 3 1 เป็น

1 => {2, 3}
2 => {4, 5}
3 => {}
4 => {}
5 => {}

แล้วแต่ละ node สามารถสลับลูกได้ตามใจ

• ถ้ามีลูก 0 ตัวก็สลับได้ 1 แบบ ()
• ถ้ามีลูก 1 ตัวก็สลับได้ 1 * ways(1st child) แบบ (1)
• ถ้ามีลูก 2 ตัวก็สลับได้ 2 * ways(1st child) * ways(2nd child) แบบ (12,21)
• ถ้ามีลูก 3 ตัวก็สลับได้ 6 * ways(1st child) * ways(2nd child) * ways(3rd child) แบบ (123,132,213,231,312,321)
• ถ้ามีลูก n ตัวก็สลับได้ factorial(n) * ∏ { i=1..n | ways(i-th child) }

• ∏ คือ N-ARY PRODUCT หมายถึงในเอาทุกตัวใน set มาคูณกัน
• ∑ คือ N-ARY SUMMATION หมายถึงในเอาทุกตัวใน set มาบวกกัน

ตัวอย่างข้างบนจะเป็น

1 => {2, 3}   = fac(2) * ways[2] * ways[3]   = 4 ways *
2 => {4, 5}   = fac(2) * ways[4] * ways[5]   = 2 ways
3 => {}       = fac(0)                       = 1 ways
4 => {}       = fac(0)                       = 1 ways
5 => {}       = fac(0)                       = 1 ways

ส่วนวิธีไล่ stack คือ

• ถ้าตัวถัดไปไม่เคยเดิน => เป็นลูก
• ถ้าตัวถัดเคยเดินมาแล้ว => เป็นพ่อ ให้เดินย้อนกลับไป

แนะนำให้อ่านเรื่อง Tree Traversal Techniques เพิ่มเติม จะเป็นเรื่อง

• Preorder Traversal (Parent …Childs)
• Postorder Traversal (…Childs Parent)
• Inorder Traversal (ChildLeft Parent ChildRight)

ในโจทย์ข้อนี้จะเป็นการผสม Preorder Traversal และ Postorder Traversal โดยถ้าให้รูปแบบการเดินมา 2 แบบข้างบน จะแปลงกลับเป็นกราฟได้