ข้อนี้เป็นโจทย์ Dynamic Programming แบบ Sliding Window

Naive Dynamic Programming Solution

แนวคิดพื้นฐานของข้อนี้คือใช้ Dynamic Programming ในการคำนวณ $min\_cost[i]$ ซึ่งนิยามเป็นค่าใช้จ่ายที่ต่ำที่สุดที่จะทำให้สามารถต่อจากแปลงที่ $1$ ไปยังแปลงที่ $i$ (รวมถึงสร้างแปลงที่ $i$)

การคำนวน $min\_cost[i]$ ต้องพิจารณาเพียงแปลง $i-k$ ถึงแปลง $i-1$ และเลือกอันที่มี $min\_cost$ ต่ำสุด

แนวคิดนี้สามารถเขียนเป็นโค้ด:

min_cost[1] = P[1];
for (int i = 2; i <= N; i++) {
  min_cost[i] = 1000000001; // inf
  for(int j = max(i - k, i); j < i; j++) {
    min_cost[i] = min(min_cost[i], min_cost[j] + P[i]);
  }
}

ผลลัพธ์สำหรับตัวอย่างข้อมูลนำเข้าชุดแรก

(อธิบายสัญกรณ์: $min\_cost[a..b]$ คือ Array ของค่า $min\_cost[j]$ สำหรับ $a \leq j \leq b$) เช่น $min\_cost[5]$ คำนวณจาก $min(min\_cost[2..4]) + P[5] = 3 + 2 = 5$

สังเกตว่าในโค้ดนี้ต้องคำนวณ $min\_cost[i]$ สำหรับ $2 \leq i \leq N$ ซี่งทุก $i$ จะต้องพิจารณาอย่างมาก $k$ ค่าเพื่อหาค่าต่ำสุดในช่วง $min\_cost[max(i-k,1)..i-1]$

วิธีนี้จึงมี Time Complexity เป็น $\mathcal{O}(Nk)$ ซึ่งมากเกินไปสำหรับ $N=500000, k=2000$

Full Solution

หากใช้โครงสร้างข้อมูลเพื่อลด Time Complexity ของการหาค่าต่ำสุดใน $k$ ค่าที่ผ่านมาให้เหลือ $\mathcal{O}(1)$ ได้จะทำให้ Time Complexity เหลือ $\mathcal{O}(N)$ ซึ่งเร็วพอสำหรับ $N=500000$

สังเกตว่าทุกครั้งที่ Query หาค่าต่ำสุดนี้เราจะ Query หาค่าต่ำสุดในช่วง (Window) ที่ขยับไปทางขวาทุกครั้ง

ดังนั้นเราจึงสามารถใช้ Minimum Sliding Window

Sliding Window

Sliding Window ที่จะใช้ในข้อนี้เป็นโครงสร้างข้อมูลที่รองรับ Operation สองแบบ:

• Query(i): หาดัชนี $j$ ที่ทำให้ $min\_cost[j]$ เป็นค่าต่ำสุดในช่วง $i-k \leq j \leq i-1$ โดย $i$ ที่ถูก Query ต้องไม่ลดลงจาก Operation ที่แล้ว
• Insert(i): เพิ่มดัชนี $i$ เข้าไปในช่วงที่พิจารณา โดย $i$ ที่ถูก Insert ต้องไม่ลดลงจาก Operation ที่แล้ว ทั้งสอง Operation ต้องใช้เวลา Amortized $\mathcal{O}(1)$

แนวคิดของ Sliding Window

Sliding Window จะเก็บดัชนีในช่วงจากน้อยไปมาก และ $min\_cost$ ที่แต่ละดัชนีจะเรียงจากน้อยไปมากเช่นกัน

แนวคิดหลักของ Sliding Window คือเมื่อเรา Insert(i) ใหม่ที่มีค่า $min\_cost[i]$ ต่ำกว่า $min\_cost[j]$ สำหรับ $j < i$ เราจะไม่ต้องพิจารณา $min\_cost[j]$ อีกเลยเพราะ $i$ จะอยู่ในช่วงที่พิจารณานานกว่า $j$ (เพราะช่วงขยับไปทางขวาเสมอ) และ $i$ เป็นตัวเลือกที่ดีกว่า $j$ เสมอ

ดังนั้นหากใส่ค่า $i$ ที่ $min\_cost[i]$ ที่มีค่าต่ำกว่าค่าท้ายสุดก่อนใส่ สามารถเอาค่าท้ายสุดใน Sliding Window ออกจนเหลือเพียงค่า $j$ ที่ $min\_cost[j]$ ไม่มากกว่า $min\_cost[i]$ และค่อยใส่ $i$ เข้าไปเป็นค่าท้ายสุดใหม่

สังเกตว่าเนื่องจาก $min\_cost$ ของดัชนีใน Sliding Window เรียงกันก่อนหน้าที่จะทำการ Insert(i) ครั้งนี้ $min\_cost$ จะยังเรียงจากน้อยไปมากเช่นเดิมหลังการ Insert

สำหรับการ Query เนื่องจากค่า $min\_cost$ ของดัชนีใน Sliding Window เรียงกันจากน้อยไปมาก เราต้องพิจารณาเพียงดัชนีแรกที่เหลืออยู่ใน Sliding Window ที่ไม่น้อยกว่า $i-k$ (เพื่อให้อยู่ในช่วง $i-k$ ถึง $i-1$)

หากดัชนีแรกไม่อยู่ในช่วงแล้วสามารถเอาออกจาก Sliding Window ได้ เนื่องจากดัชนีดังกล่าวจะไม่อยู่ในช่วงสำหรับ Query ต่อๆ ไปอีกเลย (เพราะช่วง Query ขยับไปทางขวาเสมอ) จึงสามารถเอาดัชนีแรกออกจนดัชนีแรกไม่น้อยกว่า $i-k$

หลังการ Query ค่า $min\_cost$ ของดัชนีใน Sliding Window จะเรียงจากน้อยไปมากเช่นเดิม เช่นเดียวกับการ Insert

Deque

สังเกตว่าการ Query / Insert ใช้เพียง 5 Operation รองรับ คือ 1) เอาค่าหน้าสุดออก 2) เอาค่าท้ายสุดออก 3) ใส่ค่าใหม่เป็นค่าสุดท้าย 4) หาค่าหน้าสุด 5) หาค่าท้ายสุด จึงสามารถ Implement ด้วย Deque (Double-ended Queue) ซึ่่งรองรับทั้ง 5 Operation

หากใช้ภาษา C++ จะสามารถใช้ std::deque ที่มีอยู่ใน Library <deque> ของ Standard Template Library

เราต้องการใช้ 5 Operation ของ std::deque คือ

• pop_front(): เอาค่าหน้าสุดออก
• pop_back(): เอาค่าท้ายสุดออก
• push_back(value): ใส่ค่า value เข้าไปเป็นค่าหลังสุด
• front(): return ค่าหน้าสุด
• back(): return ค่าท้ายสุด

ทั้ง 5 Operation ใช้เวลา Amortized $\mathcal{O}(1)$

Implementation

Query(i)

การ Query ต้องเอาดัชนีแรกออกจนดัชนีแรกไม่ต่ำกว่า $i-k$ และดัชนีแรกใน Sliding Window จะเป็นดัชนี $j$ ที่ค่า $min\_cost[j]$ ต่ำสุดในช่วง $i-k \leq j \leq i-1$

  while (sliding_window.front() < i - k)
    sliding_window.pop_front();

  // sliding_window.front() <- ค่าต่ำสุด

Insert(i)

การ Insert ต้องเอาดัชนีท้ายสุดออกจน $min\_cost$ ของดัชนีท้ายสุดไม่มากกว่า $min\_cost[i]$ แล้วจึงใส่ดัชนี $i$ เข้าไปในตำแหน่งสุดท้าย

  while (!sliding_window.empty() && min_cost[sliding_window.back()] > min_cost[i])
    sliding_window.pop_back();
  sliding_window.push_back(i);

สังเกตว่าในการ Query / Insert สำหรับดัชนีใดๆ เมื่อโดน push_back หนึ่งครั้งจะสามารถโดน pop_front / pop_back ได้อย่างมากหนึ่งครั้ง ทั้งสอง Operation จึงใช้เวลา Amortized $\mathcal{O}(1)$

Code

deque < int > sliding_window;

min_cost[1] = P[1];
sliding_window.push_back(1);

for (int i = 2; i <= N; i++) {
  while (sliding_window.front() < i - k)
    sliding_window.pop_front();

  min_cost[i] = P[i] + min_cost[sliding_window.front()];

  while (!sliding_window.empty() && min_cost[sliding_window.back()] > min_cost[i])
    sliding_window.pop_back();
  sliding_window.push_back(i);
}

คำอธิบายโค้ด:

• เราต้องเลือกแปลงหมายเลข 1 เสมอ จึงตั้ง $min\_cost[1] = P[1]$ และใส่ดัชนี 1 เข้าไปใน Sliding Window
• สำหรับแปลงที่ 2 ถึง $N$ เราจะ:
  • Query(i) ใน Sliding Window เพื่อค่าต่ำสุดในช่วง $i-k$ ถึง $i-1$
  • ตั้ง $min\_cost[i] = P[i] + min\_cost[sliding\_window.front()]$ ($min\_cost[sliding\_window.front()]$ คือค่าต่ำสุดในช่วง)
  • Insert(i) เข้าไปใน Sliding Window สำหรับการ Query ต่อๆ ไป
• คำตอบคือ $min\_cost[N]$

การ Query / Insert ใช้เวลา Amortized $\mathcal{O}(1)$ และถูกเรียก $\mathcal{O}(N)$ รอบ Algorithm นี้จึงใช้เวลารวม $\mathcal{O}(N)$

Time Complexity: $\mathcal{O}(N)$

ผลลัพธ์สำหรับตัวอย่างข้อมูลนำเข้าชุดแรก เมื่อแสดงเพียงค่า $min_cost$ ของดัชนีที่เหลืออยู่ใน Sliding Window ในแต่ละ Query