ข้อ Electricity จาก TOI8

โจทย์

ความยาก ★★★☆☆

มีที่ดินทั้งหมด $N$ แปลงเรียงกันเป็นเส้นตรง หมายเลข 1 ถึง $N$ แต่ละแปลงจะมีราคา $P_i$ สำหรับแปลงที่ $i$

เราสามารถสร้างโรงไฟฟ้าบนแปลงเหล่านี้ทั้งหมดกี่โรงก็ได้ โดยที่แต่ละโรงจะส่งกระแสไฟฟ้าไปหากันได้เมื่อห่างจากโรงไฟฟ้าทางซ้ายและทางขวาไม่เกิน $K$ แปลง (หมายความว่าถ้าจะสร้างโรงไฟฟ้าในแปลงที่ $X$ ในแปลงก่อนหน้าที่ $X-K$ ถึง $X-1$ จำเป็นต้องมีโรงไฟฟ้าอย่างน้อย 1 แปลง)

โจทย์ข้อนี้จะถามว่าหากต้องการสร้างโรงไฟฟ้าให้โรงไฟฟ้าบนแปลงที่ 1 ส่งกระแสไฟฟ้าไปที่โรงไฟฟ้าแปลงที่ $N$ (ต้องสร้างแปลงที่ 1 และ $N$) โดยมีราคารวมแปลงที่สร้างน้อยที่สุด ราคารวมคือเท่าไหร่

---

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

บรรทัดแรก ระบุจำนวนแปลงที่ดิน $N$ ($2 ≤ N ≤ 500\,000$) ที่กระแสไฟจะถูกส่งผ่าน
บรรทัดที่สอง ระบุค่า $k$ ($1 \leq K \leq N,K \leq20\,000$) แทนระยะห่างซึ่งเป็นจำนวนแปลงที่มากที่สุดระหว่างโรงไฟฟ้าสองแห่งที่สามารถส่งไฟฟ้าถึงกันได้โดยตรง
บรรทัดที่สาม ประกอบด้วยเลขจำนวนเต็ม $N$ จำนวน คั่นด้วยช่องว่าง เลขเหล่านี้แทนราคาที่ดินของแต่ละแปลงคือ ตามลำดับ $P_1, P_2, \dots, P_n$ ($1 ≤ P_i ≤ 2\,000$)

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

มีบรรทัดเดียว แสดงค่าใช้จ่ายรวมที่น้อยที่สุดในการซื้อที่ดินเพื่อตั้งโรงไฟฟ้าทั้งหมดสำหรับการส่งกระแสไฟฟ้าตามเงื่อนไข

---

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

คำอธิบายตัวอย่างแรก:

สร้างโรงไฟฟ้าที่ตำแหน่ง 1, 3, 5, 7 ทำให้ราคารวมเป็น $1+2+2+2=7$

คำอธิบายตัวอย่างที่สอง:

สร้างโรงไฟฟ้าที่ตำแหน่ง 1, 2, 6, 10 ทำให้ราคารวมเป็น $2+1+1+3=7$

---

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

สังเกตว่ายังไงที่ดินหมายเลข $1$ และ $N$ ก็ต้องซื้ออยู่แล้ว เพราะโจทย์มันว่ามาอย่างนั้น แปลว่าตอนที่เราจะเริ่มคำนวณ เราสามารถใช่ที่ดินหมายเลข $1$ เป็นตำแหน่งเริ่มได้เลย

หาที่ดินที่ต้องซื้อถัดไป

ตอนแรกเลยที่เรามีที่ดินหมายเลข $1$ แน่ๆ สิ่งที่คิดได้ต่อก็จะเป็นว่า ก็คงต้องซื้อสักที่นึงที่ถัดออกไปไม่เกิน $K$ ช่อง ซึ่งก็คือ สักที่นึงในระหว่างช่อง $2$ ถึง $K+1$

ทีนี้ปัญหาใหม่ก็ตามมาทันทีเลยคือ แล้วซื้อช่องไหนดีล่ะ?

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

แต่ถ้ามองอีกมุมนึง เราหันไปมองอีกแบบได้เหมือนกัน

ถ้าเปลี่ยนใหม่เป็นว่าอยากซื้อที่ดิน $i$ …แล้วก่อนหน้านี้ต้องซื้อที่ไหนล่ะ?

อย่างเช่น ถ้าเราอยากจะวางโรงไฟฟ้าที่ช่องที่ $2$ เราก็รู้ทันทีว่า เราต้องใช้โรงไฟฟ้าจากที่ดินแปลงที่ $1$ แล้วก็คำนวณได้ทันทีเลยว่าต้องจ่ายรวมเท่าไหร่ (เพราะเรารู้ว่าที่แปลงที่ $1$ จ่ายเท่าไหร่อยู่แล้ว)

ถัดไปลองมาดูที่ที่ดินแปลงที่ $3$ ก็คิดเหมือนกันเลยว่าต้องมีโรงไฟฟ้าจากไม่แปลงที่ $1$ ก็แปลงที่ $2$ นั่นแหละ(สมมติว่า $K$ ยาวไปถึง $1$ ได้นะ) เราก็แค่เปรียบเทียบเลยว่าซื้อที่ไหนดี

แล้วถ้าเราจะไปซื้อแปลงที่ $i$ เราก็แค่ต้องไปดู $K$แปลงก่อนหน้า (แปลงที่ $i-K$ ถึงแปลงที่ $i-1$) แล้วเลือกแปลงที่ราคาสร้างมาถึงแปลงก่อนหน้านั้นที่น้อยที่สุด มารวมกับราคาแปลงที่ $i$

ตัวอย่างเช่น

— ตารางที่ดินโชว์แค่แปลง 9 ถึง 12 ที่มีค่า ราคาที่ดินกับ ราคารวมในการสร้างโรงไฟฟ้าที่ถูกที่สุดถ้าจะตั้งโรงไฟฟ้า ณ ที่ดินตรงนั้น —

หากจะหาราคารวมที่สร้างในแปลงที่ 12 (cost) โดยสมมติว่า $K=3$ เราจะต้องไปดูแปลง 9 ถึง 11 ว่าในแต่ละแปลงราคารวมของแปลงไหนน้อยที่สุด ซึ่งกรณีนี้คือแปลง 10 แล้วก็จะเลือกแปลงนั้นมารวมกับราคาที่ดินแปลง 12 ทำให้ได้ cost = 150+10 = 160

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

ทำให้โปรแกรมรันเร็วขึ้นอีก

วิธีใหม่กับวิธีแรกจะต่างกันนิดหน่อยคือ วิธีแรกเรายังไม่รู้คำตอบของตัวถัดไปและต้องไปค้นหาต่อเรื่อยๆ แต่วิธีหลังใช้หลักการที่สร้างคำตอบมาจากคำตอบที่เคยมีอยู่แล้วแทน (Bottom-up Dynamic Programming)

แล้วทีนี้ด้วยความว่าเรามีคำตอบของตัวก่อนหน้านี้อยู่แล้ว (หมายความว่าเมื่อเรากำลังจะคิดหาคำตอบของแปลงที่ $i$ เราก็รู้คำตอบตั้งแต่แปลงที่ $1$ ถึง $i-1$ แล้ว)

ทีนี้ถ้าสมมติว่าเราตอบได้เร็วขึ้นว่าคำตอบของใน $K$ ช่องก่อนหน้า ช่องไหนมีค่าใช้จ่ายน้อยสุด เราก็จะหาคำตอบได้เร็วกว่า $\mathcal{O}(NK)$ ซึ่งในกรณีนี้ก็อยู่ที่การเลือก Data Structure ละว่าอยากจะใช้ตัวไหน ตอนนี้ที่ใช้อยู่คือแค่ Array เปล่าๆเก็บคำตอบ ซึ่งในการค่าน้อยสุดของ $K$ ช่องก็จะใช้ $\mathcal{O}(K)$

แต่ถ้าใช้ Data Structure ตัวอื่นๆ หรือเทคนิคอื่นๆเช่น Set, Multi-set, หรือ Monotonic-queue เข้ามาเสริมจะทำให้คำนวณได้เร็วยิ่งขึ้น ซึ่งจะเป็น $\mathcal{O}(N\log_2K), \mathcal{O}(N\log_2K), \mathcal{O}(N)$ ตามลำดับ ซึ่งเร็วพอให้ผ่านโจทย์ข้อนี้แล้ว

Monotonic queue

Monotonic queue จริงๆ แล้วก็เป็นแค่การเก็บอะไรบางอย่างไว้ใน deque โดยที่ค่าที่เก็บจะมีการเรียงลำดับบางอย่าง(แล้วแต่ว่าอยากให้เรียงตามอะไร) ซึ่งเราจะพยายามให้มันเรียงกันตลอดด้วยการใส่ค่า หรือลบค่าบางอย่างออกตลอดการทำงาน

ปกติแล้วถ้าจะเรียงข้อมูลโดยการใช้ Set จะเวลามากกว่าแค่ $\mathcal{O}(1)$ ไม่เหมือน deque เพราะว่า การใส่ค่าของ Set จะเป็นการค้นหาตำแหน่งที่ต้องใส่ค่าเพิ่มลงไป ซึ่งจะใช้เวลา $\mathcal{O}(\log_2N)$ ในการใส่ข้อมูล

แต่ทีนี้ monotonic queue ก็อาจจะใช้เวลาเยอะเหมือนกันถ้าต้องเอาค่าออกจาก queue ทั้งหมด แล้วค่าในนั้นอาจจะมีได้สูงสุดถึง $N$ ตัว ทีนี้การใส่ค่าก็จะกลายเป็น $\mathcal{O}(N)$ ต่อครั้งสิ 🧐

เพื่อไม่ให้ใช้เวลามากเกินไป เราจะเพิ่มกฎอีก 1 ข้อให้ Monotonic queue คือ ค่าที่ถูกเอาออกแล้วจะไม่ถูกใส่กลับเข้าไปใน deque อีกเลย ทำให้แต่ละค่ารับประกันว่าจะถูกใส่เข้าและเอาออกจาก deque ไม่เกิน 1 ครั้ง เวลาในการทำงานโดยเฉลี่ยของการใส่ค่า $N$ ครั้งจึงเป็น $\mathcal{O}(N)$

ตัวอย่างเช่น

ให้ 200 คือ front ของ deque และ -19 คือ back ของ deque

สมมติจะใส่ค่า 60 ลงใน deque แทนที่เราพยายามแทรก 60 ลงไประหว่าง 85 กับ -10 เพื่อให้มันเรียงกันเหมือนเดิม

เราจะทำการเอา -19 และ -10 ออกไปเลย แล้วใส่ 60 ลงไปที่ด้านหลังแทน

หรือถ้าจะใส่ค่า 105 จากทางด้านหน้า ก็จะทำการเอา 200 และ 107 ออกแล้วใส่ 105 ลงไปที่ด้านหน้าเข้าไป

ส่วนในข้อ Electricity นี้ เราก็สามารถให้ว่าตัวหน้าเป็นค่าใช้จ่ายที่น้อยที่สุดโดยเรียงจากน้อยไปมากก็ได้ แล้วก็เช็กว่าตัวไหนควรจะเอาออกเมื่อหลุดช่วงของ $K$ ตัวที่ดูอยู่โดยการเก็บค่าประเภท pair เข้า monotonic queue ได้

Extra Challenge

1. ถ้าเปลี่ยนจากสร้างห่างกันไม่เกิน $K$ เป็นว่าต้องสร้างในระยะอย่างน้อย $L$ และไม่เกิน $R$ จะแตกต่างจากวิธีเดิมยังไงบ้าง
2. ถ้าแต่ละช่องมีค่า $K$ ของตัวเองจะแตกต่างจากวิธีเดิมยังไงบ้าง

ลิงก์

ลิงก์โจทย์ Programming.in.th

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

ข้อเดียวกันกับ TOI8-Electricity แหละ ไม่รู้เหมือนกันทำไมมีสองข้อ

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