วิเคราะห์โจทย์ข้อ The Wall-The Sequel จาก TOI17

โจทย์

มีอิฐทั้งหมด $N$ ก้อน เริ่มตั้งแต่ก้อนที่ 1 แต่ละก้อนมีคุณภาพ $A_i$

มีคำสั่งทั้งหมด $Q$ คำสั่ง แต่ละคำสั่งจะให้ค่ามาทั้งหมด 3 ค่าคือ $L,M,R$
คำสั่งแต่ละครั้ง จะถามว่าคุณภาพของอิฐก้อนที่ $L, L + M, L + 2M, \dots$ รวมกันไปเรื่อยๆ(แต่ไม่เกินก้อนที่ $R$ ) มีมูลค่ารวมเท่าไหร่

โจทย์อยากให้เราคำนวณว่าค่าคุณภาพรวมของอิฐ ที่คำนวณได้ในแต่ละคำสั่งเป็นเท่าไหร่

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

บรรทัดแรก ระบุจำนวนเต็ม $N,Q$ แทนจำนวนอิฐและจำนวนคำสั่ง ( $1 ≤ N,Q ≤ 100\,000$ )

บรรทัดต่อมา ระบุจำนวนเต็ม $N$ จำนวน แทนคุณภาพของอิฐ ( $A_i$ ) ของอิฐก้อนที่ $i$ ( $-5\,000 \leq A_i \leq 5\,000$ )

$Q$ บรรทัดต่อมา ระบุจำนวนเต็ม $L,M,R$ แทนค่าของแต่ละคำสั่ง ( $1 \leq L,M,R \leq N, L\leq R$ )

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

มีทั้งหมด 1 บรรทัด แสดงจำนวนเต็ม $Q$ จำนวนโดยคั่นด้วยช่องว่าง แทนค่าคุณภาพรวมของอิฐที่คำนวณได้ในแต่ละคำสั่ง

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

Input	Output
11 2 1 5 2 4 7 3 9 2 2 1 5 3 2 8 2 5 8	18 14
5 7 4923 4743 -3836 -484 -1009 1 1 2 1 4 3 1 3 4 2 4 3 1 5 2 4 5 5 2 5 4	9666 4923 4439 4743 4923 -484 4743
9 3 7 8 -2 45 2 1 2 -8 11 2 3 9 4 2 8 3 1 9	2 38 51

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

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

วิธีที่ 1 - กระโดดบวกไปตรงๆ

เริ่มแรกคือเราจะเอาค่าของที่ L และไล่บวกค่าไปเรื่อยๆ ตั้งแต่ L, L+M, L+2M, L+3M ไปถึง R

สมมติว่าให้ L=3, M=2, R=9 แล้วเราจะได้ว่าค่าที่เราต้องการคือ $A_3 + A_5 + A_7 + A_9$

-2

-4

-7

-4

ตัวอย่างอิฐ 10 ช่อง โดยเริ่มต้นที่ ตำแหน่ง 3 ข้ามทีละ 2 ก้อน และคิดถึงแค่ช่องที่ 9

ถ้าลองมาดูอีกตัวอย่าง: ถ้าเราให้ L=1, M=6, R=7 ค่าที่เราต้องการคิดแค่ $A_1 + A_7$ เอง

-2

-4

-7

-4

ตัวอย่างอิฐ 10 ช่อง โดยเริ่มต้นที่ ตำแหน่ง 1 ข้ามทีละ 6 ก้อน และคิดถึงแค่ช่องที่ 7

จะเห็นได้ว่าเวลาในการทำแต่ละคำสั่งคือ $\mathcal{O}(\frac{N}{M})$ ซึ่งถ้าค่า $M$ น้อยๆ ในทุกคำสั่งจะทำให้เวลาขึ้นสูงไปถึง $\mathcal{O}(N)$ ได้ ซึ่งพอถามทั้งหมด $Q$ ครั้ง จะทำให้ใช้เวลา $\mathcal{O}(N\times Q)$ เลย (ซึ่งเยอะเกินไป 😭)

ทีนี้เราจะมาลองดูอีกวิธีนึง โดยใช้เทคนิคการ preprocess (คำนวณบางอย่างไว้ก่อน) เพื่อช่วยลดเวลาในการหาค่าแต่ละคำสั่งในวิธีถัดมากัน

วิธีที่ 2 - preprocess ข้อมูลเพื่อเรียกตอบ

วิธีนี้เราจะจำค่าบางอย่างลง array เพื่อให้สามารถตอบค่าผลรวมในเวลา $\mathcal{O}(1)$ ได้โดยแลกกับการใช้เวลา preprocess ข้อมูลผลรวมมาไว้ก่อน

เราจะให้ $S_{i,j}$ แทนผลรวมของอิฐทั้งหมดจากที่ให้กระโดดข้ามอิฐทีละ $i$ ก้อน และสิ้นสุดที่ก้อนที่ $j$ พอดี
จะได้ว่า $S_{i,j}$ จะเป็นไปได้ 2 แบบคือ

ถ้ามีอิฐก่อนหน้า เราจะรวมกับค่าอิฐก่อนหน้านั้น ทำให้ได้ว่า $S_{i,j-i}+A_j$ หรือ
ถ้าอิฐก้อนที่ $j$ เป็นก้อนแรก (ไม่มีอิฐก้อนก่อนหน้า $j$ ที่กระโดดมาได้) เราจะใช้ $A_j$ เลย

ซึ่งสามารถเขียนเป็นสมการได้ดังนี้

S_{i,j} = \begin{cases} S_{i,j-i}+A_j\ ; j-i \geq 1 \\ A_j\ ; j-i < 1 \end{cases}

ทีนี้พอเวลาเราจะหาค่าของคำสั่ง เราก็สามารถหาอิฐก่อนสุดท้ายก่อนที่จะเกินช่วง ( $x$ ) ได้โดยนับจำนวนการกระโดด ( $\lfloor \frac{R-L}{M}\rfloor$ ) คูณด้วยระยะกระโดด และบวกด้วยตำแหน่งเริ่มต้นที่กระโดด จนเป็นสมการดังนี้

x=L+\lfloor \frac{R-L}{M}\rfloor \times M

ต่อมาเราจะใช้ค่าของ $S_{i,j}$ และ $x$ มาหาค่าผลรวม ซึ่งก็คือเรียก $S_{i,x} - S_{i,L} + A_L$ ได้เลย ทำให้สามารถตอบทุกคำสั่งได้ภายใน $\mathcal{O}(1)$

อย่างเช่นเมื่อ L=3, M=2, R=9 เราจะไปดูผลรวมที่คำนวณไว้ก่อน โดยจะไปหาค่า $S_{2,9}$ และ $S_{2,3}$ แล้วนำมาลบกันและบวกค่า $A_3$ ได้ผลรวมที่ต้องการ

โดยที่ช่อง $S_{2,9}$ จะเป็นค่าผลรวมของอิฐตั้งแต่ 1, 3, 5, 7 และ 9 อย่างในตารางด้านล่าง

-2

-4

-7

-4

ค่าผลรวมของช่อง S_2,9

เราก็เลยจะมาลบกับ $S_{2,3}$ ที่เป็นค่าผลรวมของอิฐช่องที่ 1 และ 3

-2

-4

-7

-4

ค่าผลรวมของช่อง S_2,3

แล้วบวก $A_3$ ที่เป็นค่าของอิฐที่ 3 คืนกลับไปเพื่อให้ได้ผลรวมที่ต้องการ

-2

-4

-7

-4

ดังนั้นถ้าเรามีข้อมูลผลรวมพวกนี้เก็บไว้อยู่แล้ว จะคำนวณหาค่าของแต่ละคำสั่งก็ไม่ใช่เรื่องยาก และใช้เวลาแค่ $\mathcal{O}(1)$ ต่อคำสั่งเอง

ทีนี้จะติดปัญหาต่อมาว่า ขนาด array ต้องมีขนาด $N\times N$ เพื่อรองรับคำสั่งทุกรูปแบบที่เป็นไปได้ ทั้งจบที่อิฐก้อนไหน และกระโดดกี่ก้อนต่อครั้ง

ถ้าเราจะสร้างข้อมูลตรงนี้มาก่อน เวลาที่ใช้สำหรับ preprocess และ memory ก็เลยจะกลายเป็น $\mathcal{O}(N^2)$ เลย ซึ่งก็ทำไม่ทันอยู่ดี (แถม memory เกินกว่าที่โจทย์ต้องการเยอะด้วย 🥲) แล้วจะทำยังไงดีล่ะ

ข้อสังเกต

ในวิธีแรกการกระโดดยาวๆนี่ดีมาก เพราะแทบไม่ต้องคำนวณเลย แต่ถ้าค่า $M$ น้อยๆ จะเสียเวลาค่อยๆคิดมากๆ
แต่ในวิธีที่ 2 ช่วยแก้ปัญหาได้แค่เรื่องกระโดดทีละสั้นๆ( $M$ น้อยๆ) แต่ตอนที่ต้องกระโดดข้ามหลายๆก้อนนี่แทบไม่มีประโยชน์เลย

ถ้างั้นเราควรต้องสร้าง array มาเพื่อ preprocess ข้อมูลก่อนแต่ไม่ใช่ทั้งหมด แล้วทีนี้เราจะเลือกสร้างขนาดเท่าไหร่ดีล่ะ

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

วิธีที่ 3 - รวมร่าง 2 วิธีแรก

ลองสมมติให้ค่า $P$ เป็นตัวแบ่งแทนว่าจะใช้วิธีไหน หรือก็คือถ้าค่า $M$ มากกว่า $P$ จะทำวิธีแรก ถ้าไม่ใช่จะทำวิธีที่สอง

จากที่วิเคราะห์เวลาของทั้ง 2 วิธีจะได้ว่า

วิธีที่ 1: เวลาขึ้นอยู่กับค่า $M$ ต่อคำสั่ง ( $\mathcal{O}(\frac{N}{M})$ )
วิธีที่ 2: เวลาขึ้นอยู่กับขนาดตาราง (preprocess $\mathcal{O}(P\times N)$ เมื่อ $P$ คือขนาดตาราง)

ทีนี้การแบ่งว่าเราจะให้คำสั่งไหนทำวิธีที่ 1 หรือ 2 นั้น เราจะทำให้ทั้งสองวิธีใช้เวลาในกรณีที่แย่ที่สุด (Worst case) พอๆ กัน ซึ่งค่า $P$ ที่แบ่งดีที่สุดจะหาได้จาก

วิธีแรกจะยิ่งใช้เวลาเยอะถ้าค่า $M$ มันน้อย แล้วถ้าจะให้ $P$ เป็นค่าน้อยสุดก่อนจะเปลี่ยนไปใช้อีกวิธี แปลว่าเวลาแย่สุดต่อคำสั่งนึงก็จะเป็น $\frac{N}{P}$ ถ้าสมมติมี $N$ คำสั่งไปเลย ก็จะใช้เวลา $\frac{N}{P} \times N$
วิธีที่สอง ต้องคำนวณตาราง array ไว้ก่อนเลยซึ่งยังไงก็ใช้ $N \times P$ แน่ๆ

เราต้องการให้สองค่านี้มันใกล้เคียงกันก็เลยจะได้ว่า:

\frac{N}{P}\times N = N\times P \\ N = P^2 \\ P = \sqrt{N}

ทำให้ได้ค่า $P$ ที่เหมาะสมคือประมาณ $\sqrt{N}$

ทำไมถึงเวิร์คล่ะ?

คำถามหลักที่จะตามมาคือ วิธีที่ 3 จะทำผ่านได้จริงเหรอ ทีนี้เราจะมาพิสูจน์คร่าวๆ กัน

กรณีที่ 1 - $M\leq \sqrt{N}$

ในกรณีนี้ จะใช้วิธีที่ 2 ทำให้ใช้เวลาคงที่คือ $\mathcal{O}(1)$ ต่อคำสั่ง และใช้ $\mathcal{O}(N\sqrt{N})$ ในการ preprocess ผลรวมของอิฐ

กรณีที่ 2 - $M>\sqrt{N}$

ในส่วนที่เหลือจะเข้าไปทำวิธีที่ 1 เพราะใช้การกระโดดไปถึงจุดจบ ( $R$ ) น้อยลงแล้ว ทำให้กรณีแย่ที่สุดคือ $M=\sqrt{N}+1$ ทำให้ใช้เวลาแย่ที่สุดคือ $\mathcal{O}(\frac{N}{\sqrt{N}+1})=\mathcal{O}(\sqrt{N})$ ต่อคำสั่ง ซึ่งถึงทุกคำสั่งถามแบบเดียวกันหมดก็จะใช้เวลาแค่ $\mathcal{O}(Q\sqrt{N})$ อยู่ดี

สรุป

ที่เกริ่นไปซะยาวนี่เพื่อจะแนะนำเทคนิคที่ชื่อว่า Square Root Decomposition ซึ่งอันนี้จะเป็นวิธีนึงการแบ่งคำถามเป็นหลายๆ ส่วน เพื่อใช้วิธีที่ดีเฉพาะในบางคำถาม และเลือกใช้วิธีที่เหมาะสมที่สุดกับคำถามนั้นๆ มาหาค่าให้เร็วที่สุด

จริงๆ แล้วตัว Square Root Decomposition เนี่ยสามารถใช้ได้หลากหลายมากๆ ตัวอย่างเช่น

เก็บค่าที่จะ update แยกลงอีก array นึง พอมีค่า มากพอแล้วค่อยไปแค่หาใน array หลักรวดเดียว
สร้างช่วงใหม่ไว้เก็บค่า operation บนช่วงของช่อง (ช่วง 1 เก็บผลรวมช่อง 1 ถึง $\sqrt{N}$ , ช่วง 2 เก็บผลรวมช่อง $\sqrt{N}+1$ ถึง $2\sqrt{N}$ ไปเรื่อยๆ)
เก็บ version ของการ update ว่าถ้า update ค่าถึงคำสั่งเท่านี้แล้วจะมีค่าเท่าไหร่ (Persistent Data Structure)
เอาคำสั่งหลายๆ อันมา sort เป็นกลุ่มๆ เพื่อลดเวลาหาค่าโดยรวม (Mo’s algorithm)

ซึ่งยังมีอีกหลายวิธีที่ดัดแปลงได้จาก Square Root Decomposition เช่นบางครั้งเราไม่จำเป็นต้องแบ่ง 2 กรณีโดยใช้ Square Root ก็ได้ ซึ่งก็ขึ้นกับเวลาทั้งสองกรณีอีกว่ามีจุดกึ่งกลางที่เท่าไหร่

ไว้มีคนมาถามเพิ่ม หรือมีอารมณ์เขียนเรื่องนี้เดี๋ยวจะมาเขียนใหม่นะฮะ

สุดท้ายนี้อยากจะฝากว่า บางครั้งเราไม่จำเป็นต้องแก้โจทย์ด้วยอัลกออันเดียวก็ได้ ขอแค่เราเอาอัลกอง่ายๆ มารับมือกับปัญหาเฉพาะส่วนให้สุดท้ายแล้วมันครอบคลุมก็พอ 😁