toi

TOI17 sequel - กำแพงนคร: ภาคต่อ (The Wall: The Sequel)

🏠 รวมเฉลย TOI17

💎 problem.pdf

🎉 solution.cpp

square root decomposition + quicksum

ถ้าสมมติเรา ทำตรงๆ

for (i = L; i <= R: i += step) sum += input[i];

แบบนี้จะใช้เวลา O(question * (n / step)) ถ้า step มีค่า 1,2,3,4,5 ก็จะมีค่าประมาณ O(question * n)

เราเลยต้องคิดว่า

• ถ้า step มันน้อย ตอนหาคำตอบต้อง วน for เยอะ (เพราะขยับนิดเดียว)
• ถ้า step มันเยอะ ตอนหาคำตอบต้อง วน for น้อย (เพราะขยับทีละมากๆ)

เราก็เลยจะคำนวนตัวน้อยๆไว้ก่อน เช่น คำนวน step=1 ด้วย quicksum ปกติ

• แต่ถ้า step=2 เราก็ต้องแยกเคสว่าตำแหน่งเริ่มต้นเป็นอะไรใน 0, 1
• แต่ถ้า step=3 เราก็ต้องแยกเคสว่าตำแหน่งเริ่มต้นเป็นอะไรใน 0, 1, 2
• แต่ถ้า step=4 เราก็ต้องแยกเคสว่าตำแหน่งเริ่มต้นเป็นอะไรใน 0, 1, 2, 3
• แต่ถ้า step=k เราก็ต้องแยกเคสว่าตำแหน่งเริ่มต้นเป็นอะไรใน 0, 1, 2, 3, ..., k-2, k-1

quicksum[step, i] = quicksum[step, i - step] + input[i]

แล้วทำถึงค่า k ที่เท่าไหร่ถึงจะดีหละ ?

ก็ตั้งสมการ

• ตอนสร้าง quicksum สร้างถึง k ใช้ O(n * k)
• ตอบคำถาม ตอบ q ครั้ง
  • ถ้าคำถาม < k คำนวนใน O(1) เพราะมี quicksum ที่คำนวนไว้แล้ว
  • ถ้าคำถาม > k คำนวนใน O(n / k) เพราะต้องวน for
  • worse case การตอบคำถามทุกครั้งเลยเป็น O(q * n / k)

เวลารวม = O(n * k) + O(q * n / k) = O(n * (k + q / k))

ต้องการให้เวลารวมน้อยสุด คือให้ k = sqrt(q) จะได้ = O(n * (sqrt(q) + sqrt(q))) เป็นเวลาที่ทำได้ดีสุดใน worse case แล้ว ถ้าเราให้ n = q ก็จะได้คำตอบเป็น O(n * sqrt(n))