วิเคราะห์โจทย์จาก TOI18 ข้อ Constellation

โจทย์

มีแผนที่ท้องฟ้าขนาด $R\times C$ อยู่ แต่ละพิกัดจะถูกระบุด้วย 2 สัญลักษณ์

• . แทนพิกัดนั้นไม่มีดาว
• # แทนพิกัดนั้นมีดาวอยู่

เราต้องการหาจำนวนกลุ่มดาวทั้งหมดในแผนที่ท้องฟ้า โดยวิธีหากลุ่มดาวมีดังนี้

1. เลือกจุดศูนย์กลางของกลุ่มดาวที่พิกัด $(x,y)$ โดยที่พิกัดนี้ต้องอยู่ในแผนที่
2. เลือกดาวทั้งหมด $K$ ดวงที่ระยะห่างแบบ Manhattan(L1) จากจุดศูนย์กลางเท่ากัน ซึ่งระยะห่างตรงนี้จะยาวเท่าไหร่ก็ได้

โจทย์อยากทราบว่ามีวิธีการเลือกกลุ่มดาวได้ทั้งหมดกี่รูปแบบ โดยแสดงเศษจากหารจำนวนวิธีในการเลือกกลุ่มดาวด้วย $1\,000\,003$

---

ข้อมูลนำเข้า

บรรทัดแรก ระบุจำนวนเต็ม $R,C,K$ จำนวนแถว จำนวนคอลัมน์ของแผนที่ดาว และขนาดของกลุ่มดาว ($1 ≤ R,C ≤ 300$, $2 \leq K \leq 600$)
$R$ บรรทัดต่อมา ระบุสายอักขระความยาว $C$ ที่ทุกตัวอักษร . หรือ # เท่านั้น

ข้อมูลส่งออก

มีทั้งหมด 1 บรรทัด แสดงจำนวนเต็ม $1$ จำนวน แทนค่าวิธีการเลือกกลุ่มดาว โดยแสดงเศษจากการหารด้วย $1\,000\,003$

---

ตัวอย่างข้อมูลนำเข้าและข้อมูลส่งออก

---

วิเคราะห์โจทย์

ก่อนอื่นเลย เราจะมาดูก่อนว่าจะเลือกกลุ่มดาวยังไงดี

เลือกจากจุดศูนย์กลางก่อน

แน่นอนแหละว่า ถ้าไม่มีจุดศูนย์กลางเราก็จะไม่สามารถทำอะไรต่อจากเดิมได้ซักเท่าไหร่ ซึ่งการจะกำหนดจุดศูนย์กลางทำได้ค่อนข้างง่ายเพราะก็แค่ไล่ลูปทุกพิกัดที่เป็นไปได้ก็แค่นั้น แต่ปัญหาจะเริ่มเกิดขึ้นในขั้นตอนถัดๆ มาซะมากกว่า

ปัญหา 1: เลือกดาวให้กลุ่มดาว

หลังจากเลือกจุดศูนย์กลางเสร็จแล้ว เรียกว่าเป็นจุด $(x,y)$ ละกัน ทีนี้เดี๋ยวเราจะต้องไปหาให้ได้ว่าดาวที่จะต้องเลือกมาทั้ง $K$ ดวงที่ระยะห่างจาก $(x,y)$ เท่ากันทั้งหมดมันมีกี่แบบ

ด้วยความที่โจทย์ไม่ได้ลิมิตระยะห่างของดาว เราก็แค่ต้องไล่ลูประยะจากระยะห่าง 1 ไปจนถึงขอบตารางเพื่อจะได้คิดทุกรูปแบบ

แต่ๆๆๆ คำถามต่อมาคือ ถึงรู้แล้วว่ามีกี่ดวงในระยะ แล้วเราจะเลือกจำนวนรูปแบบของดาวที่เป็นไปได้ยังไงล่ะ

ปัญหา 2: แล้วเลือกได้กี่แบบล่ะ?

เราจะมาลองดูอีกปัญหานึงหลังจากเรื่องการหาดาวคือ ถ้าเรารู้แล้วว่ามีดาวที่เลือกได้ทั้งหมด $p$ ดวง แล้วต้องการจะเลือกมาเพียง $q$ ดวง จะทำยังไงดี?

เพื่อความง่าย เราจะลองเอาดาวมาเรียงเป็นเส้นตรง แล้วเลือกดาวในแต่ละตำแหน่งดู

ตำแหน่งที่ 1 เราจะเลือกดาวได้ทั้งหมด $p$ รูปแบบ
ตำแหน่งที่ 2 เราจะเลือกดาวได้ทั้งหมด $p-1$ รูปแบบ
ตำแหน่งที่ 3 เราจะเลือกดาวได้ทั้งหมด $p-2$ รูปแบบ

ถ้าคิดต่อไปจนถึง
ตำแหน่งที่ $q$ เราจะเลือกดาวได้ทั้งหมด $p-q-1$ รูปแบบ

ซึ่งรวมๆแล้วแปลว่าทำได้ทั้งหมด $\frac{p!}{(p-q)!}$ แบบเมื่อ $p!$ คือผลคูณตั้งแต่ 1 ถึง $p$

แต่การทำแบบนี้จะเห็นได้ว่าลำดับการเลือกในแต่ละตำแหน่งส่งผลต่อจำนวนรูปแบบที่เกิดขึ้นได้ (permutation) ซึ่งเราไม่ต้องการแบบนั้น

เราก็เลยต้องหาต่อว่าการสลับที่จากดาวที่เลือกมามีกี่รูปแบบ ในที่นี้เราเลือกดาวมา $q$ ดวง ก็เลยสลับได้ $q!$ แบบ (เลือก $q$ ช่องจาก $q$ ช่องโดยคิดเรื่องลำดับ)

ทีนี้เราจะเอาจำนวนรูปแบบทั้งหมด ($\frac{p!}{(p-q)!}$) มาหารด้วยจำนวนลำดับจากการ permutation ของในกลุ่มเดียวกันทิ้ง ($q!$) ทำให้สุดท้ายเหลือจำนวนรูปแบบเป็น $\frac{p!}{q!(p-q)!}$ (ในทางคณิตศาสตร์จะเรียกว่า Combination)

เราสามารถเรียก Combination ตรงส่วนนี้ว่า $\binom{p}{q}$ เป็นการเลือกดาว $q$ ดวงจากดาว $p$ ดวง ซึ่งในส่วนนี้เราสามารถคำนวณเอาไว้แล้วเก็บค่าลงในอาเรย์เอาไว้เพื่อใช้ต่อทีหลังได้ จะได้ไม่ต้องคำนวณใหม่เรื่อยๆ

แต่ทีนี้เราจะคำนวณ $\binom{p}{q}$ ให้เร็วๆได้ยังไง?

Preprocess ค่าวิธีเลือก

การหาค่า $\binom{p}{q}$ สามารถทำได้จากการใช้สามเหลี่ยม Pascal ได้เลย ซึ่งก็คือ $\binom{p}{q} = \binom{p-1}{q-1}+\binom{p-1}{q}$

เนื่องจากว่าจำนวนดาวมากสุดที่เป็นไปได้ในการเลือกมีอยู่ประมาณ $R+C$ ดวง และเราก็เลือกแค่ $K$ ดวงอยู่แล้ว

ทำให้เราไม่ต้องคิดทั้งสามเหลี่ยม Pascal ทั้งอัน และคำนวณ preprocess แค่ถึง $\binom{2*(R+C)}{K}$ ซึ่งทำได้ใน $\mathcal{O}((R+C)K)$

สามเหลี่ยม Pascal

ถ้าสนใจว่าค่าจากสามเหลี่ยม Pascal มายังไงก็สามารถอ่านต่อได้เลย หรือจะข้ามไปส่วนต่อไปเพื่อไปใช้ดูว่าเอาสามเหลี่ยม Pascal ไปใช้ในโจทย์ยังไงดี

ทีนี้เราจะมาโฟกัสที่ปัญหานึงกัน ปัญหาที่ว่าคือเราต้องการเลือกของจากทั้งหมด $p$ ชิ้นมาจำนวน $q$ ชิ้นโดยไม่สนใจลำดับในการหยิบ ซึ่งจะมาคิดแยกเป็น 2 วิธีกัน

1. ใช้นิยามการเลือกตรงๆ ไปเลย ก็จะได้ว่ามีค่าเป็น $\binom{p}{q} = \frac{p!}{q!(p-q)!}$
2. คิดว่าการเลือกที่ว่านั้นมีความเป็นไปได้ 2 รูปแบบที่ครอบคลุมตามการเลือกเริ่มต้น แล้วมารวมกัน
   • มีของทั้งหมด $p-1$ ชิ้นแล้วเลือก $q-1$ ชิ้นไปแล้วก่อนหน้านั้น ทำให้ชิ้นที่ $p$ ต้องเลือกแน่ๆ ($\binom{p-1}{q-1}$)
   • มีของทั้งหมด $p-1$ ชิ้นแล้วเลือกครบ $q$ ชิ้นไปแล้วก่อนหน้านั้น ทำให้ชิ้นที่ $p$ ยังไงก็ไม่เลือกแน่ๆ ($\binom{p-1}{q}$)

ซึ่งวิธีพิสูจน์แบบนี้ก็มีชื่อเรียกเฉพาะก็คือ Combinatorial Proof ถ้าสนใจก็ไปอ่านต่อกันได้ 😁

กลับมาที่การหาจำนวนดาวในระยะต่างๆ

หลังจากได้วิธีการคิดจำนวนวิธีการเลือกดาวแล้ว ทีนี้เราจะกลับมาหาว่าในแต่ละระยะมีดาวกี่ดวงกันแน่

ทางที่ง่ายที่สุดก็คือในทุกๆ จุดศูนย์กลาง $(x,y)$ เราสามารถไล่หาทั้งตารางเทียบกับ $(x,y)$ ที่กำลังดูอยู่ว่า ดาวแต่ละพิกัดมันห่างจากจุดศูนย์กลางเท่าไหร่ แล้วก็เก็บว่าแต่ละระยะมีดาวทั้งหมดกี่ดวง ซึ่งในการไล่ตรวจทั้งตารางจะใช้เวลา $\mathcal{O}(R\times C)$ เพราะทั้งตารางมีขนาด $R\times C$

แล้วเราก็แค่ต้องทำแบบนี้ไปเรื่อยๆทุกจุดศูนย์กลางเอง ซึ่งก็มีอีก $R \times C$ จุด ดังนั้นแค่จะมองหาว่ามีดาวกี่ดวงอยู่รอบๆก็ใช้ไปแล้ว $\mathcal{O}(R^2C^2)$

ต่อมาตอนเราจะคำนวณจำนวนวิธี ก็จะไปดูในทุกระยะจากจุดศูนย์กลางว่า แต่ละระยะเลือกนั้นเป็นไปได้กี่รูปแบบ ทำให้เรียกใช้ค่า $\binom{S_d}{K}$ ได้ เมื่อ $S_d$ คือจำนวนดาวที่ระยะห่าง $d$ จากพิกัด $(x,y)$ เพราะเราต้องการเลือกดาวมาแค่ $K$ ดวง จาก $S_d$ ดวงทั้งหมดในระยะนั้นๆ

ซึ่งระยะทางที่ว่ามีค่ามากที่สุดได้ถึง $R+C-2$ ฃดังนั้นเราจะต้องคำนวณค่า $\binom{S_d}{K}$ ในทุกระยะที่เป็นไปได้ ซึ่งก็จะใช้เวลา $\mathcal{O}(R+C)$ ส่วนค่าที่ต้องคำนวณก็ไปดึงเอามาจากอาเรย์ที่เก็บไว้จากที่คิดเมื่อในสเต็ปที่แล้วได้เลย

ละก็เหมือนเดิมที่ก็ต้องไปคิดแบบนี้ในทุกๆจุดศูนย์กลาง ก็เลยใช้เวลาในพาร์ทนี้เป็น $\mathcal{O}(RC(R+C))$

ทีนี้เราจะมาค่อยๆดูว่าจะ optimize วิธีคิดจากส่วนไหนกันต่อได้บ้าง เพื่อให้ผ่านโจทย์ข้อนี้ไปได้ 😅

• การไล่ลูปหาจุดศูนย์กลาง: ใช้เวลา $\mathcal{O}(RC)$ ซึ่งก็น่าจะดีที่สุดแล้ว เพราะไม่มีวิธีคิดรวบทีเดียวหลายๆจุด เนื่องจากแต่ละจุดมีจำนวนดาวรอบๆไม่เท่ากัน
• หาจำนวนวิธีเลือกดาวในแต่ละระยะ: ก็เรียกใช้จากที่ preprocess จากสามเหลี่ยม Pascal มาได้เลย ซึ่งเรียกใน $\mathcal{O}(1)$ และ preprocess ใน $\mathcal{O}((R+C)K)$ ตอนแรกสุด ซึ่งก็ไม่ได้แย่อีก
• นับจำนวนดาวที่อยู่ในแต่ละระยะ: ใช้เวลาคำนวณระยะทุกช่องในตาราง $\mathcal{O}(RC)$ เพื่อให้ได้ทุกระยะต่อ 1 จุดศูนย์กลาง ซึ่งดูแย่ที่สุด ทำให้เราจะมา optimize ต่อในส่วนนี้

หาจำนวนดาวแบบเร็วๆ

จากการเลือกดาวในแต่ละระยะจะสังเกตได้ว่า ถ้าเรา fix ระยะเป็นค่าๆนึง ระยะนั้นจะประกอบด้วยเส้นทแยงมุมทั้งหมด 4 เส้นมารวมกัน ทำให้เราจะใช้ประโยชน์จากข้อสังเกตนี้กัน

มองเพิ่มอีกนึดนึงเราจะเห็นว่าเส้นทแยงมุมทั้ง 4 เส้นเนี่ย จริงๆมันมีแค่ 2 แนวเอง คือทแยงจากบนซ้ายไปล่างขวา กับบนขวาไปล่างซ้าย

เราจะทำการเก็บผลรวมของดาวในตามแนวทแยง (Quicksum) ทั้งสองแนวกันก่อน ซึ่งก็จะสร้างอาเรย์ 2 มิติเก็บผลรวมมาทั้งหมด 2 อาเรย์ สมมติว่าเป็น $qs1, qs2$ และให้จำนวนดาวที่พิกัด $(i,j)$ คือ $S_{i,j}$ (มีค่าเป็น 0 หรือ 1)

• มุมจากซ้ายบนไปขวาล่าง: สำหรับพิกัด $(i,j)$ ใดๆ เราจะเก็บค่า $qs1[i][j]$ เป็น $qs1[i-1][j-1]+S_{i,j}$
• มุมจากขวาบนไปซ้ายล่าง: สำหรับพิกัด $(i,j)$ ใดๆ เราจะเก็บค่า $qs2[i][j]$ เป็น $qs2[i-1][j+1]+S_{i,j}$

ทีนี้พอจะหาว่าในเส้นทแยงมุมว่ามีกี่จุดก็แค่เอาผลรวมของเส้นทแยงมุมมาหักลบกันเพื่อดูว่าในช่วงๆนึงของเส้นกี่จุด เท่านี้ก็สามารถหาได้แล้วว่าในระยะที่เราต้องการหาจะมีดาวกี่ดวง

รวมทุกอย่างเข้าด้วยกัน

ทีนี้เราก็จะใช้ค่าที่ preprocess ได้ มาคู่กับลูปเรื่องระยะ ทำให้ในแต่ละระยะเราแค่เรียกผลรวมแนวทแยงทั้ง 4 ด้านมาใช้ได้โดยใช้เวลาใน $\mathcal{O}(1)$ ซึ่งลดเวลาจาก $\mathcal{O}(RC)$ เหลือแค่ $\mathcal{O}(R+C)$ ต่อ 1 จุดศูนย์กลาง เพราะเหลือแค่ต้องลูปเรื่องระยะแทน

สุดท้ายทำให้หาค่าจำนวนกลุ่มดาวได้ภายใน $\mathcal{O}(RC(R+C))$ ซึ่งก็ทำให้ผ่านข้อนี้ได้แล้ว 🎉

ลิงก์

ลิ้งโจทย์ TOI18 - Constellation

https://programming.in.th/tasks/toi18_constellation

Combinatorial Proof

https://en.wikipedia.org/wiki/Combinatorial_proof