Coding Challenge

Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.

Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.

Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng

Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.

Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.

Tiếp nối 03 số đầu tiên, các Coding Challenge #04, #05, #06 và #07 tiếp tục ghi nhận sự ủng hộ nhiệt tình của cộng đồng lập trình thi đấu. Hệ thống đã ghi nhận tổng cộng 2086 lượt nộp bài và ~x~ lời giải được gửi về cho Tạp chí.

Đội ngũ tạp chí VNOI xin gửi lời cảm ơn chân thành đến tất cả các bạn đã tích cực tham gia các Coding Challenge và đóng góp những lời giải vô cùng chất lượng trong thời gian qua!

Coding Challenge #6

Coding Challenge #6 có tên là Mua hàng. Đây là bài toán có format đặc biệt trong các số coding challenge vừa qua khi là một bài toán interactive, tức chương trình của thí sinh tương tác với chương trình của giám khảo để đưa ra đáp án. Để có được số điểm tối đa cho bài toán, thí sinh cần áp dụng một vài nhận xét về xác suất vào mô hình chia để trị để xây dựng lời giải. Bài toán Mua hàng đã được 344 thí sinh thử sức và có 14 lời giải xuất sắc đạt được số điểm tối đa.

Để hiểu rõ hơn về lời giải của bài toán, mời các bạn theo dõi lời giải xuất sắc do bạn Nguyễn Hoàng Minh biên soạn.

Đề bài

Bạn đọc có thể theo dõi đề bài gốc và subtasks tại nền tảng VNOJ. Sau đây là bản tóm tắt của đề bài.

Cho một hoán vị ~p~ bị ẩn đi và một số nguyên ~k~. Yêu cầu tìm chỉ số của ~k~ phần tử có giá trị lớn nhất bằng cách sử dụng ít nhất số lượng câu hỏi có dạng như sau:

• Chọn hai số nguyên ~x, y~ (thỏa ~1 \leq x, y \leq n~ và ~x \neq y~), máy chấm sẽ cho biết ~p_x < p_y~ hay ~p_x > p_y~.

Điểm số của thí sinh sẽ là tối đa nếu số lượng câu hỏi ít hơn số câu hỏi mà giám khảo sử dụng; ngược lại, thí sinh càng sử dụng ít câu hỏi hơn sẽ càng nhận được điểm số cao hơn.

Giới hạn:

• ~1 \leq n \leq 1000~

Lời giải

Ý Tưởng

• Bài toán trên có thể được đưa về tìm phần tử lớn thứ ~k~ trong một mảng giá trị với thứ tự bất kì. Cụ thể hơn, nếu ta gọi ~B~ là phần tử lớn thứ ~k~ trong mảng ~n~ phần tử được cho, ~k - 1~ phần tử lớn nhất còn lại (từ phẩn tử lớn thứ nhất đến phần tử lớn thứ ~k - 1~) có thể được xác định bằng cách so sánh giá trị ~B~ với ~n - 1~ phần tử còn lại:
  • Nếu phần tử ~A~ lớn hơn ~B~ thì ~A~ là một trong ~k~ giá trị lớn nhất.
  • Ngược lại, ~A~ thuộc tập ~n - k~ giá trị còn lại.
• Để có thể xác định được giá trị ~B~, chúng ta cần phải thực hiện ít nhất ~\Omega(n)~ phép so sánh bởi mỗi phần tử còn phải được tham gia vào ít nhất một phép so sánh và mỗi phép so sánh chỉ có thể xác định mối quan hệ giữa hai phần tử.
• Một thuật toán mà ta có thể dùng để tìm được giá trị ~B~ nêu trên là thuật toán Quickselect. Thuật toán có thể được miêu tả như sau:
  • Cho một mảng ~P~ gồm các phần tử phân biệt và một số nguyên ~k~; mục tiêu là tìm phần tử lớn thứ ~k~ trong ~P~.
  • Chọn một phần tử làm pivot từ mảng ~P~, sau đó phân hoạch mảng thành hai tập con:
    • ~L~ là tập gồm các phần tử lớn hơn pivot; và
    • ~R~ là tập gồm các phần tử nhỏ hơn pivot.
  • Khi đó:
    • Nếu ~k \leq |L|~, bài toán tương đương với việc tìm phần tử lớn thứ ~k~ trong ~L~.
    • Nếu ~k = |L| + 1~, kết quả bài toán sẽ là pivot.
    • Nếu ~k > |L| + 1~, bài toán tương đương với việc tìm phần tử lớn thứ ~k - |L| - 1~ trong ~R~.
• Nếu ta chọn pivot là một phần tử ngẫu nhiên trong mảng đang xét thì trong trường hợp trung bình, giá trị kỳ vọng của số phép so sánh mà thuật toán trên sử dụng sẽ là ~O(n)~. Trong trường hợp tệ nhất, số phép so sánh mà thuật toán nêu trên có thể dùng là ~O(n^2)~ (ví dụ khi pivot được chọn là phần tử nhỏ nhất hoặc lớn nhất trong mảng, ...). Tuy nhiên, xác suất để thuật toán sử dụng nhiều hơn ~C \cdot n~ phép so sánh, với ~C~ là một hằng số, giảm rất nhanh khi ~C~ tăng dần.
• Việc xác định ~k - 1~ phần tử còn lại có thể được thực hiện với ~O(n)~ thao tác so sánh như đã đề cập ở phần trên. Vì vậy, trong trường hợp trung bình, ý tưởng nêu trên sẽ có giá trị kỳ vọng của số thao tác sử dụng là ~O(n)~, gần tương ứng với cận dưới của số thao tác tối thiểu phải sử dụng nêu trên.

Cài Đặt

• Sau khi xác định phần tử lớn thứ ~k~, ta có thể không cần so sánh giá trị này với từng phần tử trong ~n - 1~ phần tử còn lại để tìm ~k - 1~ phần tử lớn nhất tiếp theo. Điều này là bởi ~k - 1~ phần tử đó có thể được xác định cùng lúc với khi ta thực hiện chia tập trong quá trình tìm kiếm phần tử lớn thứ ~k~. Cụ thể hơn, nếu ta đặt ~X(P, k)~ là tập hợp ~K~ phần tử lớn nhất của tập hợp ~P~ gồm các giá trị phân biệt. Nếu ta chia ~P~ thành hai tập ~L~ và ~R~ theo pivot được định nghĩa như trên, ~X(P, k)~ có thể được xác định một cách đệ quy như sau:
  • Nếu ~k \leq |L|~, ~X(P, k) = X(L, k)~
  • Nếu ~k = |L| + 1~, ~X(P, k) = L \cup \{\text{pivot}\}~
  • Nếu ~k > |L| + 1~, ~X(P, k) = L \cup \{\text{pivot}\} \cup X(R, k - |L| - 1)~
• Dù xác suất để thuật toán nêu trên thực hiện số lượng phép so sánh gần với ~O(n^2)~ là thấp nhưng số lượng này vẫn có thể nhiều hơn số lượng thao tác mà giám khảo để sử dụng. Để có thể đặt được số điểm tối đa ở mỗi test, ta có thể cần phải thử nhiều seed khác nhau cho việc sinh số giả ngẫu nhiên cho đến khi đặt số điểm tối đa toàn bộ test.

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX_N = 1'003;

namespace Interactor {

    int queryResults[MAX_N][MAX_N];

    int query(const int x, const int y) {
        if (x == y)
            return x;
        int result = 0;
        cout << '?' << ' ' << x << ' ' << y << endl;
        cin >> result;
        return result;
    }

    int getQueryResult(const int x, const int y) {
        return queryResults[x][y] ? queryResults[x][y] : (queryResults[x][y] = queryResults[y][x] = query(x, y));
    }

    bool checkSmaller(const int x, const int y) {
        return getQueryResult(x, y) == y;
    }

    bool checkGreater(const int x, const int y) {
        return getQueryResult(x, y) == x;
    }

    int findMaximum(const int x, const int y) {
        return checkGreater(x, y) ? x : y;
    }

    int findMinimum(const int x, const int y) {
        return checkSmaller(x, y) ? x : y;
    }

    int findMaximum(const vector<int> &indices) {
        int result = indices.front();
        for (const int &i : indices) {
            if (i == result)
                continue;
            result = findMaximum(result, i);
        }
        return result;
    }

    int findMinimum(const vector<int> &indices) {
        int result = indices.front();
        for (const int &i : indices) {
            if (i == result)
                continue;
            result = findMinimum(result, i);
        }
        return result;
    }

    void printAnswer(const vector<int> &indices) {
        cout << '!' << ' ' << 1 << ' ' << 1 << endl;
        for (const auto &i : indices)
            cout << i << ' ';
        cout << endl;
        exit(0);
    }
}

template<class T>
vector<T> operator + (vector<T> a, const vector<T> &b) {
    a.insert(a.end(), b.begin(), b.end());
    return a;
}

template<class T>
vector<T> operator - (vector<T> a, const vector<T> &b) {
    const unordered_set<T> s(b.begin(), b.end());
    int length = 0;
    for (const auto &value : a)
        if (s.find(value) == s.end())
            a[length++] = value;
    a.resize(length);
    return a;
}

int getRandomInteger(const int n) {
    return rand() % n;
}

int getRandomSample(const vector<int> &values) {
    return values[getRandomInteger(values.size())];
}

vector<int> getRange(const int l, const int r) {
    vector<int> indices(r - l);
    iota(indices.begin(), indices.end(), l);
    return indices;
}

vector<int> getShuffledList(vector<int> values) {
    random_shuffle(values.begin(), values.end());
    return values;
}

pair<vector<int>, vector<int> > partitionList(const vector<int> &values, const int pivot) {
    vector<int> left, right;
    for (const int &value : values) {
        if (value == pivot)
            continue;
        (Interactor::checkSmaller(value, pivot) ? left : right).push_back(value);
    }
    return make_pair(left, right);
}

class QuickSelect {
private:

    const int n;

    vector<int> runRecursion(const vector<int> &indices, const int k) const {
        if (k == 1)
            return indices;
        const int indexCount = indices.size(), R = indexCount - k + 1;
        if (R == 1)
            return vector<int>(1, Interactor::findMaximum(indices));
        const int L = indexCount - R;
        if (L == 1)
            return indices - (vector<int>(1, Interactor::findMinimum(indices)));
        const int pivot = getRandomSample(indices);
        const auto &[left, right] = partitionList(indices, pivot);
        const int m = left.size() + 1;
        if (m < k)
            return runRecursion(right, k - m);
        const vector<int> includedIndices = (vector<int>(1, pivot)) + right;
        return (m == k) ? includedIndices : (runRecursion(left, k) + includedIndices);
    }

public:

    QuickSelect(const int n): n(n) {};

    vector<int> operator () (const int k) const {
        return runRecursion(getShuffledList(getRange(1, n + 1)), n - k + 1);
    }

};

int main() {
    int n = 0, k = 0;

    cin >> n >> k;

    srand((k <= 400) ? ((n ^ k) + (n & k)) : ((n ^ k) + n + k)); // Update this seed until all tests passed

    Interactor::printAnswer(QuickSelect(n)(k));

    return 0;
}

Độ Phức Tạp

• Các bước xử lý chính của một cách cài đặt cho ý tưởng nêu trên sẽ có có độ phức tạp thời gian tương ứng với số lượng thao tác sử dụng, tức:
  • ~O(n)~ trong trường hợp trung bình; và
  • ~O(n^2)~ trong trường hợp tệ nhất.
• Về độ phức tạp bộ nhớ, tùy vào cách cài đặt mà ta có thể có độ phức tạp ~O(n)~ hoặc ~O(n^2)~.

Một Số Ý Tưởng Khác

Ngoài ra ý tưởng nêu trên để giải bài toán, ta có thể xem xét một số ý tưởng khác. Tuy nhiên, những ý tưởng này có thể không đạt toàn bộ số điểm cho mọi test.

Sắp Xếp

• Ta có thể dùng các thuật toán sắp xếp như heapsort, merge sort, ... để sắp xếp toàn bộ phần tử với ~O(n \log n)~ thao tác. Ta có thể xác định ~k~ phần tử lớn nhất sau khi đã sắp xếp.
• Tuy nhiên so với thuật toán quickselect nêu trên, ý tưởng sử dụng sắp xếp này có thể sử dụng số lượng thao tác lớn hơn nhiều lần trong nhiều trường hợp.

Heap

• Ta có thể duyệt qua từng phần tử và sử dụng một min-heap để lưu tối đa ~k~ phần tử lớn nhất trong các phần tử đã duyệt qua. Cụ thể hơn, khi duyệt qua một phần tử, ta thêm phần tử đó vào heap và loại bỏ phần tử nhỏ nhất khỏi heap nếu heap có nhiều hơn ~k~ phần tử. Mỗi lần thêm một phần tử vào heap hoặc xóa phần tử nhỏ nhất khỏi heap, ta sẽ thực hiện tối đa ~O(\log k)~ thao tác (vì trong trường hợp này, số lượng phần tử tối đa của heap là ~O(k)~).
• Vì vậy, ý tưởng này sử dụng ~O(n \log k)~ thao tác trong trường hợp tệ nhất.
• Để giảm số thao tác sử dụng, nếu ~k > \frac{n}{2}~, ta có thể tìm ~n - k~ phần tử nhỏ nhất (bằng cách sử dụng max-heap) thay vì tìm ~k~ phần tử lớn nhất trực tiếp. Tuy nhiên, cách này chỉ giúp giảm nếu xét về mặt hằng số, số lượng thao tác sẽ vẫn là ~O(n \log k)~.
• Cũng tương tự như ý tưởng dùng thuật toán sắp xếp, ý tưởng dùng heap này có thể sử dụng số lượng thao tác lớn hơn nhiều lần trong nhiều trường hợp, đặc biệt khi ~k~ càng gần với giá trị ~\frac{n}{2}~.

Biến Thể của Quickselect

• Một số biến thể khác của thuật toán quickselect có thể được xem xét cho bài toán này. Điểm khác nhau chính giữa các biến thể này chủ yếu ở cách chọn pivot.

Median of Medians

• Thay vì chọn pivot là một phần tử ngẫu nhiên như ý tưởng được ở phần trên, ta ước tính trung vị của mảng được cho với phương pháp median of medians rồi dùng trung vị này làm pivot.
• Để ước tính trung vị, phương pháp median of medians chia mảng thành các block gồm tối đa ~5~ phần tử liên tiếp và tìm trung vị của từng block. Trung vị của mảng được cho sẽ được ước lượng bằng trung vị của các trung vị của các block.
  • Để tìm trung vị của một block tối đa ~5~ phần tử, ta có thể sắp xếp mọi phần tử trong block (với tối đa ~7~ thao tác so sánh). Khi này, phần tử ở giữa sẽ là trung vị ta cần tìm. Ngoài ra, ta cũng có cách để tìm trung vị trực tiếp với tối đa ~6~ thao tác so sánh.
  • Để tìm trung vị của các trung vị của các block, ta có thể tiếp tục sử dụng thuật toán quickselect để tìm phần tử lớn thứ ~\frac{n}{10}~ trong các trung vị của block (vì ta có ~\frac{n}{5}~ block, phần tử lớn thứ ~\frac{n}{5} \cdot \frac{1}{2} = \frac{n}{10}~ sẽ là phần tử gần trung vị của toàn bộ mảng).
• Trong trường hợp trung bình và tệ nhất, thuật toán này sử dụng ~O(n)~ thao tác so sánh. Tuy nhiên, so với cách chọn pivot là một phần tử ngẫu nhiên, yếu tố hằng số trong việc phân tích số lượng thao tác là lớn hơn nhiều. Vì vậy, cách dùng phương pháp median of medians có thể có số lượng thao tác sử dụng lớn hơn số lượng giám khảo sử dụng trong khi cách chọn ngẫu nhiên lại ít hơn.

Thuật toán Floyd–Rivest

• Một thuật toán khác có thể được xem xét là thuật toán Floyd–Rivest. So với cách chọn pivot là phần tử ngẫu nhiên hoặc trung vị ước lượng, thuật toán Floyd–Rivest có thể có cách cài đặt phức tạp hơn.