อาคารเรียน (campus)

1139

โจทย์ข้อนี้กำหนดให้มีหออยู่ NN หอ โดยแต่ละหอมีพิกัด xix_i กับ yiy_i และมีนักเรียน sis_i คน โจทย์ต้องการให้หาว่าหากเลือกพิกัด xx yy ให้ดีที่สุดจะทำให้ Σisi(∣xi−x∣+∣yi−y∣)\Sigma_i s_i (| x_i - x| + |y_i - y|) ได้ต่ำสุดเท่าไหร่

สำหรับข้อนี้สามารถสังเกตว่า Σisi∗(∣xi−x∣+∣yi−y∣)=Σisi∣xi−x∣+Σisi∣yi−y∣\Sigma_i s_i * (| x_i - x| + |y_i - y|) = \Sigma_i s_i | x_i - x| + \Sigma_i s_i |y_i - y| จึงสามารถพิจารณาระยะทางในพิกัด xx กับพิกัด yy แยกกันในการหาคำตอบ

ค่ามัธยฐาน

คุณสมบัติที่สำคัญที่ต้องใช้การแก้ข้อนี้คือ Σi=1N∣ai−a∣\Sigma_{i=1}^N | a_i - a| จะมีค่าต่ำสุดเมื่อเลือก aa เป็นค่ามัธยฐานของ (a1,a2,…,aN)(a_1, a_2, \dots, a_N) โดยนิยามค่ามัธยฐาน mm เป็นค่าที่ทำให้มีจำนวน aia_i ที่ไม่น้อยกว่า mm อย่างน้อยครึ่ง และจำนวน aia_i ที่มีค่าไม่เกิน mm อย่างน้อยครึ่ง (ตามนิยามนี้อาจมีค่ามัธยฐานมากกว่า 1 ค่า เช่น สำหรับ 1,2,3,4,5,61, 2, 3, 4, 5, 6 ทั้ง 3,43, 4 และ 3.53.5 ต่างเป็นค่ามัธยฐาน)

เนื่องจากข้อนี้ยังมีค่า sis_i ที่ต้องพิจารณาด้วยเราจะพิสูจน์ว่าพิกัด xx ที่ต้องการคือค่า mm ที่ทำให้ Σi,m≤xisi≥Σisi2\Sigma_{i,m \leq x_i} s_i \geq \frac{\Sigma_i s_i}{2} และ Σi,m≥xisi≥Σisi2\Sigma_{i,m \geq x_i} s_i \geq \frac{\Sigma_i s_i}{2} กล่าวคือนักเรียนที่อยู่ที่พิกัด xx ที่ไม่น้อยกว่า mm มีอย่างน้อยครึ่ง และไม่มากกว่า mm อย่างน้อยครึ่ง

สำหรับการหา Σisi∣xi−m∣\Sigma_i s_i | x_i - m| สังเกตว่า Σisi∣xi−m∣=Σi,m≥xisi(m−xi)+Σi,m<xisi(xi−m)\Sigma_i s_i | x_i - m| = \Sigma_{i,m \geq x_i} s_i (m - x_i) +\Sigma_{i,m < x_i} s_i (x_i -m) สมมติว่า Σi,m≥xisi<Σi,m<xisi\Sigma_{i,m \geq x_i} s_i < \Sigma_{i,m < x_i} s_i จะได้ว่าถ้าเพิ่มค่า mm เป็น m+ϵm + \epsilon โดยที่ 0<ϵ<min⁡xi<m(m−xi)0< \epsilon < \min_{x_i<m} (m-x_i) จะทำให้ผลรวมนี้ลดลง เนื่องจาก Σi,m≥xisi(m+ϵ−xi)+Σi,m<xisi(xi−m−ϵ)=Σisi∣xi−m∣+ϵ(Σi,m≥xisi−Σi,m<xisi)<Σisi∣xi−m∣\Sigma_{i,m \geq x_i} s_i (m + \epsilon - x_i) +\Sigma_{i,m < x_i} s_i (x_i -m - \epsilon) = \Sigma_i s_i | x_i - m| + \epsilon (\Sigma_{i,m \geq x_i} s_i - \Sigma_{i,m < x_i} s_i) < \Sigma_i s_i | x_i - m| (เลือก ϵ<min⁡xi<m(m−xi) \epsilon < \min_{x_i<m} (m-x_i) เพราะจะทำให้ทุก xix_i ยังอยู่ในทางซ้ายหรือขวาของ mm อยู่ฝั่งเดิมเมื่อเปลี่ยนเป็น m+ϵm + \epsilon)

ดังนั้นสำหรับ mm ที่ทำให้ผลรวมที่ต้องการมีค่าต่ำสุดจะต้องได้ว่า Σi,m≥xisi≥Σi,m<xisi  ⟹  Σi,m≥xisi+Σi,m≥xisi≥Σi,m<xisi+Σi,m≥xisi=Σisi  ⟹  Σi,m≥xisi≥Σisi2\Sigma_{i,m \geq x_i} s_i \geq \Sigma_{i,m < x_i} s_i \implies \Sigma_{i,m \geq x_i} s_i + \Sigma_{i,m \geq x_i} s_i \geq \Sigma_{i,m < x_i} s_i + \Sigma_{i,m \geq x_i} s_i = \Sigma_i s_i \implies \Sigma_{i,m \geq x_i} s_i \geq \frac{\Sigma_i s_i}{2} ตามที่ต้องการ เราสามารถพิสูจน์ด้วยวิธีเดียวกันว่าจะต้องได้ว่า Σi,m≤xisi≥Σisi2\Sigma_{i,m \leq x_i} s_i \geq \frac{\Sigma_i s_i}{2} เช่นกัน

โดยสรุปคือเราต้องการเลือกพิกัด x=mx=m ที่ทำให้ และ Σi,m≥xisi≥Σisi2\Sigma_{i,m \geq x_i} s_i \geq \frac{\Sigma_i s_i}{2} และ Σi,m≤xisi≥Σisi2\Sigma_{i,m \leq x_i} s_i \geq \frac{\Sigma_i s_i}{2} กล่าวคือต้องการเลือกค่ามัธยฐานของพิกัด xx ของนักเรียนทุกคนนั่นเองซึ่งพิกัด xx ที่เป็นอันดับที่ ⌊Σisi2⌋\lfloor \frac{\Sigma_i s_i}{2} \rfloor จะเข้าทั้งสองเงื่อนไขไม่ว่า Σisi\Sigma_i s_i จะเป็นจำนวนคู่หรือจำนวนคี่

การเลือกค่ามัธยฐานโดยตรงด้วยการ sort ทั้ง xx และ yy และนับผลรวม sis_i จะช้าเกินไปสำหรับ N=500000N=500000 เนื่องจากข้อนี้ให้เวลาเพียง 0.5 วินาที และการ sort ใช้เวลา O(Nlog⁡N)\mathcal{O}(N \log N)

Quickselect

ขั้นตอนวิธีมาตรฐานในการเลือกค่าอันดับที่ kk คือ Quickselect ซึ่งมี Expected Time Complexity O(N)\mathcal{O}(N)

Quickselect จะรับค่าเป็น Array A[b..e]A[b..e] และค่า kk ซึ่งแทนอันดับที่ต้องการ และ return ค่าที่เป็นอันดับ kk ใน A[b..e]A[b..e]

Quickselect มีลักษณะคล้าย Quicksort คือในแต่ละขั้น Quickselect จะสุ่มเลือก pivot มาเพื่อแยกข้อมูลที่ยังพิจารณาเป็น 2 กลุ่ม คือกลุ่มที่มาก่อนและมาหลัง pivot จากนั้นจะเรียก Quickselect อีกรอบแบบ recursive ในกลุ่มที่มีค่าอันดับที่ต้องการ สำหรับข้อนี้จะต้องดัดแปลงให้สามารถพิจารณาจำนวนนักเรียน sis_i ในแต่ละหอด้วย

ขั้นตอนวิธี Quickselect สามารถเขียนเป็น

  1. หากข้อมูลที่พิจารณามีเพียง 1 หอ ให้ return ค่า xx ของหอนี้
  2. สุ่มเลือกหอหนึ่งมาเป็น pivot และแยกข้อมูลเป็น 2 ส่วน คือหอที่มีค่า x<xpivotx < x_{pivot} และหอที่มีค่า x>xpivotx > x_{pivot} (สำหรับหอที่มีค่า xx เท่ากันให้สุ่มว่าจะไว้กลุ่มแรกหรือหลังแบบสุ่มครึ่งครึ่ง) ให้ pp เป็นจำนวนหอในกลุ่มแรกบวก 1 สามารถเอา pivot ไปไว้ที่ตำแหน่ง A[p]A[p] และสลับกลุ่มแรกมาไว้ใน A[b..(p−1)]A[b..(p-1)] และกลุ่มหลังไว้ใน A[(p+1)..e]A[(p+1)..e] จะทำให้ทุกหอใน A[b..(p−1)]A[b..(p-1)] มีพิกัด xx ไม่เกิน xpivotx_{pivot} และใน A[(p+1)..e]A[(p+1)..e] ไม่ต่ำกว่า xpivotx_{pivot}
  3. ให้ผลรวม sis_i ในกลุ่มหน้าเป็น SfrontS_{front} และในกลุ่มหลังเป็น SbackS_{back} ถ้า Sfront≥kS_{front} \geq k ให้ Quickselect ค่าที่ kk ใน A[b..(p−1)]A[b..(p-1)] และ return ค่าที่ได้ ถ้า Sback>kS_{back} > k ให้ Quickselect ค่าที่ k−spivot−Sbackk - s_{pivot} - S_{back} ใน A[(p+1)..e]A[(p+1)..e] หากไม่เข้าทั้งสองกรณีให้ return ค่า xpivotx_{pivot} เพราะจะเป็นค่าที่เป็นอันดับ kk แล้ว

สังเกตว่าขั้นตอนวิธีนี้มี Worst Case Time Complexity O(N2)\mathcal{O}(N^2) เช่นเดียวกับ Quicksort เช่นหากเลือกหอที่มี xx ต่ำสุดในทุกรอบ อย่างไรก็ตามเราสามารถพิสูจน์ว่า Expected Time Complexity ของขั้นตอนวิธีนี้เป็นเพียง O(N)\mathcal{O}(N)

ให้เวลาที่ขั้นตอนวิธีนี้ใช้สำหรับ NN ค่าเป็น T(N)T(N) จะได้ recurrence ว่า E[T(N)]=1NΣi=1NE[T(i)]+O(N)E[T(N)] = \frac{1}{N}\Sigma_{i=1}^N E[T(i)] + \mathcal{O}(N) โดย E[T(1)]=T(1)=1E[T(1)] = T(1) = 1 ซึ่งจะพิสูจน์โดย induction ได้ว่า E[T(N)]=O(N)E[T(N)] = \mathcal{O}(N) (เพราะจะได้ E[T(N)]=1NΣi=1NE[T(i)]+O(N)=1NΣi=1NO(i)+O(N)≤1NΣi=1NCi+O(N)=CN(N−1)2N+O(N)=CN−12+O(N)=O(N)E[T(N)] = \frac{1}{N}\Sigma_{i=1}^N E[T(i)] + \mathcal{O}(N) = \frac{1}{N}\Sigma_{i=1}^N \mathcal{O}(i)+ \mathcal{O}(N) \leq \frac{1}{N}\Sigma_{i=1}^N Ci+ \mathcal{O}(N) = \frac{C \frac{N(N-1)}{2}}{N} + \mathcal{O}(N) = C\frac{N-1}{2} + \mathcal{O}(N) = \mathcal{O}(N) )

Solution

เมื่อรู้แล้วว่าค่า xx และ yy ที่จะทำให้ระยะทางต่ำสุดเป็นค่ามัธยฐานของพิกัดนักเรียนในแต่ละแกน เราสามารถใช้ Quickselect เลือกค่า xx และ yy ดังกล่าวและคำนวน Σisi∣xi−x∣+Σisi∣yi−y∣ \Sigma_i s_i | x_i - x| + \Sigma_i s_i |y_i - y| โดยตรง โดยทั้งหมดใช้ Expected Time Complexity O(N)\mathcal{O}(N)