ข้อสอบท้ายค่าย 2 ศูนย์ สอวน. มหาวิทยาลัยขอนแก่น ข้อ แห (OTOG ข้อที่ 862)

Author: Nagorn Phongphasura

Problem

สรุปโจทย์

มีปลาเรียงเป็นเส้นตรง \(N\) ตัว ปลาตัวที่ \(i\) อายุ \(A_i\) ซึ่งปลาที่ดี คือปลาที่มีอายุเป็นจำนวนเฉพาะ

สิ่งที่ต้องทำ

หาช่วงที่ติดกันที่เล็กที่สุด ที่มีปลาที่อายุเป็นจำนวนเฉพาะ ครบ \(K\) ตัว

Constraints

\(2 \leq N \leq 5 \times 10^5\) (จำนวนปลา)
\(1 \leq K \leq N\) (จำนวนปลาที่ดีที่อยากได้)
\(1 \leq A_i \leq N\) (อายุของปลาแต่ละตัว)

Prerequisites

Sieve of Eratosthenes
Sliding Window

Solution

โจทย์ข้อนี้ จะแยกเป็น 2 ส่วน เป็นหลัก ได้แก่:

แยกจำนวนเฉพาะ
เช็กหาคำตอบ ซึ่งคือขนาดช่วงที่เล็กที่สุดที่มี ปลาที่ดี \(\geq k\) ตัว

1. แยกจำนวนเฉพาะ : Sieve of Eratosthenes

Q → ทุกคนคงจะสงสัยกันอยู่ว่า What is "Sieve of Eratosthenes"?
A → Sieve of Eratosthenes เป็นวิธีการหาว่า ในตัวเลขตั้งแต่ \(1\) ถึง \(K\) ตัวไหนเป็นจำนวนเฉพาะบ้าง ซึ่งจะมีหลักการทำงานคล้ายๆ "ตะแกรง" จึงได้มีชื่อว่า Sieve นั่นเอง

→ 1.1. หลักการทำงานของ "Sieve of Eratosthenes"

Sieve of Eratosthenes จะเริ่มจากว่า:

สมมติให้ เลขทุกตัวเป็นจำนวนเฉพาะ
loop จาก \(2\) ถึง \(\sqrt N\) โดย:

2.1. ถ้าเลขไหนยังไม่ถูกตัดทิ้ง แปลว่ามันเป็นจำนวนเฉพาะ แต่ถ้าถูกขีดฆ่าไปแล้ว ก็ข้ามเลย

2.2. กรณีที่เป็นจำนวนเฉพาะ ให้ "ขีดฆ่า" พหุคูณของมันทั้งหมด (ไม่ขีดฆ่าตัวเอง เช่น 2 ก็ลบ 4,6,8,... → 3 ก็ลบ 6,9,12,...) เพราะตัวเลขเหล่านั้นมีตัวประกอบแน่นอน

Time Complexity: \(O(N\) \(log\) \(log\) \(N)\) (อ่านบทพิสูจน์ได้ที่นี่)

2. เช็กหาขนาดช่วงที่เล็กที่สุด : Sliding Window

Sliding Window คือการเก็บ “ช่วงข้อมูลที่ติดกัน” โดบเราจะเอาของใส่เข้าใหม่ทางขวา และเอาของเก่าออกทางซ้ายเรื่อยๆ นั่นคือ

ด้านขวา เราจะต้อง ใส่ข้อมูลเพิ่มเข้าไป
ด้านซ้าย เราจะต้อง ดึงข้อมูลที่ไม่ใช้ออกมา

→ 2.1. หลักการทำงานของ "Sliding Window"

คิดง่ายๆว่า Window ทำหน้าที่เก็บข้อมูลที่เราสนใจ ณ ปัจจุบันทั้งหมด (จะเป็นช่วงๆ) โดยขั้นตอนจะเป็น:

loop ตามทุกๆข้อมูล ตั้งแต่ \(1\) ถึง \(N\)

1.1. เพิ่มค่า: เราอ่านข้อมูลตัวใหม่เข้าไป แล้วอัปเดตค่าที่เราเก็บ (เช่น sum, mx, etc.)

1.2. ตัดทิ้ง: ถ้า Window "ตรงเงื่อนไขแล้ว" → ดึงค่าที่ไม่มีประโยชน์ออกมา (ส่วนใหญ่เราจะต้องการ "ช่วง" ที่เล็กที่สุด เราจึงจะดึงข้อมูลออกให้ Window เรามีขนาดเล็กที่สุด)

1.3. อัปเดต: ระหว่างการ pop เราก็คอยอัปเดตคำตอบ

สังเกตว่า ข้อมูลทุกตัว จะ เข้า Window ครั้งเดียว และ ออกจาก Window ครั้งเดียว ดังนั้น จะได้ว่า:

Time Complexity : \(O(N)\)

→ 2.2. Implementation

การเขียน Sliding Window เราจะต้องการที่จะ:

ใส่ข้อมูลเข้าไปด้านหลัง มองได้เป็นการ \(push\_back()\) (\(push\) ไปด้านหลัง)
ดึงข้อมูลด้านหน้าออกมา มองได้เป็นการ \(pop\_front()\) (\(pop\) จากด้านหน้า)

ซึ่งเป็นสิ่งที่มี Data Structure หนึ่งที่ทำได้ ซึ่งคือ Deque นั่นเอง โดยสามารถเขียนได้โดยตรง จากขั้นตอนในข้อ 2.1 และดัดแปลงตามโจทย์ต่างๆ

→ 2.3. ลักษณะโจทย์ที่ใช้ Sliding Window

Sliding Window เหมาะกับปัญหาแบบที่ต้อง หาช่วงที่ตรงเงื่อนไขบางอย่าง

เพราะโจทย์เหล่านี้ ทุกๆข้อจะเหมือนกันตรงที่: เราสนใจ "ช่วง" ของข้อมูล ทำให้สามารถแก้ได้โดยการ "เลื่อนหน้าต่าง" นั่นเองครับ

สามารถอ่านเพิ่มเติมได้ที่นี่

วิธีทำ

→ ก่อนอื่น เราก็จะเช็กว่า ตัวเลขตั้งแต่ \(1\) ถึง \(N\) มีตัวไหนเป็น จำนวนเฉพาะ บ้าง โดยการใช้ Sieve of Eratosthenes → แล้วสำหรับการหาช่วงของปลาที่สั้นที่สุด ทำได้โดยการ:

สร้าง \(dq\) (Deque) ไว้เป็นหน้าต่าง, \(sum\) (int) ไว้เก็บจำนวนปลาที่ดีใน Window ปัจจุบัน, \(ans\) (int) ไว้เก็บคำตอบ
loop จาก \(1\) ถึง \(N\) โดยในรอบที่ \(i\):

2.1. อ่านค่า: \(push\_back()\) เข้าไปว่า ตัวปัจจุบันเป็นจำนวนเฉพาะหรือไม่

2.2. ตัดทิ้ง: ถ้า Window ยังมีจำนวนปลาดี \(\geq K\) ก็ตัดตัวด้านหน้าทิ้ง และลบออกจากค่า \(sum\)

2.3. อัปเดต: ให้ \(ans = min(ans, dq.size())\) (นั่นคือ ให้คำตอบเป็นค่าที่น้อยกว่า ระหว่าง คำตอบปัจจุบัน กับ ขนาดช่วงปัจจุบัน (ขนาดหน้าต่าง))

Code

otog_862.cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

vector <int> prime(N, 1); // ตั้ง Array ซึ่งเริ่มต้นโดยการสมมติให้ทุกตัวเป็นจำนวนเฉพาะ (ตั้งเป็น 1)

// Sieve of Eratosthenes สำหรับแยกจำนวนเฉพาะ
void sieve_of_eratosthenes() {
    prime[0] = prime[1] = 0;
    for (int i = 2; i * i <= N; i++) { // เช็คแค่ถึง sqrt(N)
        if (prime[i]) { // ถ้า i เป็นจำนวนเฉพาะ ->
            for (int j = i + i; j <= N; j += i) { // -> ไล่ตัดเลขที่มี i เป็นตัวประกอบ (ไม่ตัด i)
                prime[j] = 0; // ตั้งว่า เลขดังกล่าวไม่เป็นจำนวนเฉพาะ
            }
        }
    }
}

int main() {
    // แยกจำนวนเฉพาะก่อน
    sieve_of_eratosthenes();

    // input
    int n, k; cin >> n >> k;
    vector <int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i];

    // sliding window ↓
    deque <int> dq;
    int sum = 0; // ไว้เก็บจำนวนปลาใน "หน้าต่าง" ปัจจุบัน (deque)
    int ans = n; // ไว้เก็บคำตอบ โดยตั้งเป็น n เวลาเช็ก min ค่าจะได้น้อยลง
    for (int i = 1; i <= n; i++) {
        dq.push_back(prime[a[i]]);          // ดันค่าปัจจุบันเข้าไปด้านหลัง
        sum += prime[a[i]];                 // จำนวนปลาที่ "ดี" ที่อยู่ใน deque
        while (!dq.empty() && sum >= k) {   // (ระหว่างที่ deque ยังมีปลาอยู่) และ (จำนวนปลาที่ดีใน deque ยังมีเยอะกว่า k)
            ans = min(ans, dq.size());      // ถ้าขนาด deque น้อยกว่าคำตอบปัจจุบันที่มี ก็ตั้งเข้าไป
            // ลบตัวด้านหน้าออก แล้วเอาออกจากหน้าต่าง ↓
            sum -= dq.front(); 
            dq.pop_front();
        }
    }

    // output
    cout << ans << "\n";
}

Total Time Complexity

\(O(N\) \(log\) \(log\) \(N)\)