418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 4

ในปัญหาข้อนี้เราจะใช้ binary search เหมือนกับปัญหาข้อที่ผ่านๆ มา แต่วัตถุที่เราทำการค้นหาจะแตกต่างจากข้ออื่นมาก

เพื่อความสะดวก เราจะกำหนดให้อะเรย์ $A\,$ และ $B\,$ มีช่อง $A[0]\,$ และ $B[0]\,$ โดยที่ $A[0]=-\infty \,$ และ $B[0]=-\infty \,$ กล่าวคือ $A[0]\,$ และ $B[0]\,$ จะมีค่าน้อยกว่าอะเรย์ช่องอื่นๆ ทั้งหมด แต่เราจะไม่นับว่าช่องที่เพิ่มมาใหม่นี้เป็นส่วนหนึ่งของอะเรย์

เราจะพิสูจน์ข้อความสามข้อความต่อไปนี้

lemma 1: ถ้า $i\,$ และ $j\,$ เป็นจำนวนเต็มที่

• $0\leq i\leq m\,$ และ
• $0\leq j\leq n\,$ และ
• $i+j=k-1\,$ และ
• $A[i+1]>B[j]\,$ และ
• $B[j+1]>A[i]\,$

แล้วสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ $k\,$ ในอะเรย์ $A\,$ และ $B\,$ คือ $\min(A[i+1],B[j+1])\,$

พิสูจน์: ให้ $x\,$ เป็นจำนวนที่น้อยกว่าระหว่าง $A[i+1]\,$ และ $B[j+1]\,$ แล้วจะได้ว่ามีจำนวน $i\,$ ตัวใน $A\,$ ที่น้อยกว่า $x\,$ และจำนวน $j\,$ ตัวใน $B\,$ ที่น้อยกว่ามัน ฉะนั้นมีจำนวน $i+j=k-1\,$ ตัวใน $A\,$ และ $B\,$ ที่น้อยกว่ามันพอดี ดังนั้น $x\,$ เป็นสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ $k\,$ พอดี

lemma 2: ถ้า $A[i+1]\,$ คือจำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ $k\,$ ใน $A\,$ และ $B\,$ โดยที่ $0\leq i\leq m\,$ แล้ว หากให้ $j=k-1-i\,$ แล้ว เราจะได้ว่า $A[i+1]>B[j]\,$ และ $B[j+1]>A[i]\,$

พิสูจน์: เนื่องจาก $A[i+1]\,$ เป็นสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ $k\,$ ดังนั้นจะต้องมีสมาชิกใน $A\,$ และ $B\,$ ที่น้อยกว่ามัน $k-1\,$ ตัวพอดี และเนื่องจากมีสมาชิกที่น้อยกว่า $A[i+1]\,$ อยู่ $i\,$ ตัวในอะเรย์ $A\,$ จะต้องมีสมาชิกที่้น้อยกว่า $A[i+1]\,$ อยู่ $k-1-i=j\,$ ตัวใน $B\,$ ซึ่งนี่หมายความว่า $A[i+1]>B[j]\,$

อนึ่ง เราจะได้ว่า $B[j+1]>A[i+1]>A[i]\,$ ด้วย ฉะนั้น lemma เป็นจริง

lemma 3: ถ้า $B[j+1]\,$ คือจำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ $k\,$ ใน $A\,$ และ $B\,$ โดยที่ $0\leq j\leq n\,$ แล้ว หากให้ $i=k-1-j\,$ แล้ว เราจะได้ว่า $A[i+1]>B[j]\,$ และ $B[j+1]>A[i]\,$

พิสูจน์: ใช้วิธีพิสูจน์เดียวกันกับ lemma 2

สังเกตว่า lemma 2 และ lemma 3 เป็น converse ของ lemma 1 ฉะนั้นเราสามารถสรุปได้ว่า

Proposition 4: เราสามารถหาสมาชิกตัวที่มีค่าน้อยที่สุดเป็นอันดับ $k\,$ ในอะเรย์ $A\,$ และ $B\,$ ได้โดยการหาจำนวนเต็ม $i\,$ และ $j\,$ ที่ทำให้ (1) $i+j=k-1\,$ และ (2) $A[i+1]>B[j]\,$ และ (3) $B[j+1]>A[i]\,$ แล้วจึีงหาคำตอบด้วยการหาค่าที่น้อยกว่าระหว่าง $A[i+1]\,$ และ $B[j+1]\,$

(ข้อสังเกต: lemma 2 และ lemma 3 เป็นข้อความที่มีความสำคัญมากเนื่องจากมันรับประกันว่าจะีมี $i\,$ และ $j\,$ เีพียงคู่เดียวเท่านั้นที่จะสอดคล้องกับเงื่อนไขทั้งหมดใน lemma 1)

อัลกอริทึม

อาศัย Proposition 4 เราจะแก้ปัญหานี้ด้วยการทำ binary search บนวัตถุคู่ำลำดับ $(i,j)\,$ โดยที่ $i+j=k-1\,$ โดยเราจะได้ว่าคู่ำลำดับนี้จะมีอยู่อย่างมาก $k\,$ ตัวด้วยกัน ได้แต่ $(0,k-1),(1,k-2),(2,k-3),\ldots ,(k-2,1),(k-1,0)\,$

สำหรับวัตถุแต่ละอัน เราจะทำการเปรียบเทียบสองครั้ง ได้แก่ (1) เปรียบเทียบ $A[i+1]\,$ กับ $B[j]\,$ และ (2) เปรียบเทียบ $B[j+1]\,$ กับ $A[i]\,$ โดยการเปรียบเทียบนี้เกิดผลได้ 3 แบบด้วยกัน

• $A[i+1]>B[j]\,$ และ $B[j+1]>A[i]\,$: ในกรณีเราจะได้ว่าเราหา $(i,j)\,$ ที่ต้องการเจอแล้ว เราสามารถหยุดการทำงานของ binary search ได้

• $A[i+1]>B[j]\,$ และ $B[j+1]<A[i]\,$: ในกรณีเราพบว่าสำหรับคู่ลำดับ $(i',j')\,$ อื่นๆ ที่ $i'>i\,$ เราจะได้ว่า $A[i'+1]>A[i+1]>B[j]>B[j']\,$ และ $B[j'+1]\leq B[j]<A[i]<A[i']\,$ ด้วยเหตุนี้ $(i',j')\,$ จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ $k\,$ ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ $(i',j')\,$ โดยที่ $i'>i\,$ ออกจากวัตถุที่เป็นไปได้ทั้งหมด

• $A[i+1]<B[j]\,$ และ $B[j+1]>A[i]\,$: ในกรณีเราพบว่าสำหรับคู่ลำดับ $(i',j')\,$ อื่นๆ ที่ $i'<i\,$ เราจะได้ว่า $A[i'+1]<A[i+1]<B[j]<B[j']\,$ และ $B[j'+1]>B[j+1]>A[i]>A[i']\,$ ด้วยเหตุนี้ $(i',j')\,$ จึีงไม่สามารถนำไปสู่จำนวนที่มีค่าน้อยที่สุดเป็นอันดับที่ $k\,$ ได้ ฉะนั้นในกรณีนี้เราสามารถตัดวัตถุ $(i',j')\,$ โดยที่ $i'<i\,$ ออกจากวัตถุที่เป็นไปได้ทั้งหมด

จากแนวคิดข้างต้น เราสามารถเขียน pseudocode ของอัลกอริืทึมได้ดังต่อไปนี้

<geshi lang="c"> Search(A, B, k) {

   i_left = 0
   i_right = k-1

   while i_left <= i_right do
   {
      i = (i_left + i_right) / 2
      j = k - 1 - i

      if A[i+1] > B[j] and B[j+1] > A[i] then
           return min(A[i+1], B[j+1])
      else if A[i+1] > B[j] and B[j+1] < A[i] then
           i_right = i-1
      else if A[i+1] < B[j] and B[j+1] > A[i] then
           i_left = i+1
   }

} </geshi>

เนื่องจากในการเช็คเงื่อนไขแต่ละครั้งเราสามารถตัดวัตถุที่เป็นไปได้ออกประมาณครึ่งหนึ่ง เราจะได้ว่าจะมีการวนลูปใน pseudocode อย่างมาก $O(\log k)=O(\log(m+n))=O(\log m+\log n)\,$ ครั้ง ฉะนั้นอัลกอริทึมข้างบนจึงทำงานภายในเวลา $O(\log n+\log m)\,$ ตามต้องการ