Bạn hãy tải những files cần thiết cho bài tại đây: Link Download

Tiểu Vân gần đây đang học thuật toán cho bài toán tập độc lập trọng số lớn nhất.

Theo định nghĩa, trong một đồ thị vô hướng, một tập con đỉnh ~I~ được gọi là tập độc lập nếu với mọi cặp đỉnh trong ~I~, hai đỉnh đó không kề nhau trong đồ thị gốc.
Một tập độc lập trọng số lớn nhất là một tập độc lập có tổng trọng số các đỉnh lớn nhất trong tất cả các tập độc lập có thể.

Hôm nay, Tiểu Vân nhận ra rằng nếu đồ thị vô hướng đó là một đường thẳng, thì việc tìm tập độc lập trọng số lớn nhất trở nên rất đơn giản. Sau khi chia sẻ điều này với Tiểu Thành, Tiểu Thành hỏi lại:

Vậy bạn có biết cách trả lời hiệu quả các truy vấn MWIS trên đoạn của một đường thẳng hay không?

Sau một thời gian nghiên cứu, Tiểu Vân phát hiện rằng ngay cả khi không biết trọng số cụ thể của từng đỉnh trên đường thẳng, ta vẫn có thể tìm được tập độc lập trọng số lớn nhất của nó, thậm chí còn có thể dùng điều này để trả lời các truy vấn trên đoạn.

Cụ thể, cho một đường thẳng gồm ~n~ đỉnh được đánh số từ ~1~ đến ~n~. Với mọi ~1 \le i < n~, có một cạnh vô hướng nối đỉnh ~i~ và đỉnh ~i+1~. Mỗi đỉnh ~i~ có trọng số là một số nguyên dương ~w_i~.

Bạn cần trả lời ~q~ truy vấn. Mỗi truy vấn cho một đoạn ~[l, r]~, và bạn phải xác định tập độc lập trọng số lớn nhất của các đỉnh ~l, l+1, \dots, r~.

Tất nhiên, nếu không có bất kỳ thông tin nào về trọng số thì không thể giải được bài toán. Vì vậy, bạn được phép thực hiện một số truy vấn kiểu so sánh tổng trọng số của hai tập đỉnh:

• Bạn chọn tùy ý hai tập con đỉnh.
• Bộ chấm sẽ cho bạn biết tập nào có tổng trọng số nhỏ hơn.

Hãy giúp Tiểu Thành trả lời tất cả các truy vấn, đồng thời cố gắng dùng càng ít lần so sánh càng tốt.

Chi tiết cài đặt

Bạn cần cài đặt hai hàm init() và range_MWIS_query():

void init(int n);

std::vector<int> range_MWIS_query(int l, int r);

• Với mỗi test, bộ chấm chính thức sẽ gọi hàm init() đúng một lần.
• n là số lượng đỉnh trên đường thẳng.
• Với mỗi test, bộ chấm chính thức sẽ gọi hàm range_MWIS_query() đúng ~q~ lần.
• Bảo đảm hàm này chỉ được gọi sau khi init() đã được gọi.
• Hàm này phải trả về một mảng ~x_1, x_2, \dots, x_m~.
• Mảng này biểu diễn tập độc lập trọng số lớn nhất của đoạn truy vấn.
• Với mọi ~1 \le i \le m~, phải có ~l \le x_i \le r~.
• Với mọi ~1 \le i < j \le m~, phải có ~|x_i - x_j| > 1~.

Ngoài ra, trong quá trình cài đặt, bạn có thể gọi hàm sau:

bool compare_subsets(const std::vector<int>& a, const std::vector<int>& b);

• a là một mảng mô tả một tập con của ~\{1,2,\dots,n\}~.
• b là một mảng mô tả một tập con của ~\{1,2,\dots,n\}~.
• Trong a không được có phần tử trùng nhau.
• Trong b không được có phần tử trùng nhau.
• Nếu tổng trọng số các đỉnh trong a nhỏ hơn tổng trọng số các đỉnh trong b, hàm sẽ trả về true.
• Ngược lại, hàm trả về false.
• Cài đặt compare_subsets() trong sample grader và trong bộ chấm chính thức là hoàn toàn giống nhau.

Ràng buộc

• ~1 \le n \le 2000~
• ~1 \le q \le 2000~
• ~1 \le l \le r \le n~

Định dạng input của sample grader

Sample grader sử dụng định dạng input sau:

n q
w[1] w[2] ... w[n]
l[1] r[1]
l[2] r[2]
...
l[q] r[q]

Lưu ý rằng bộ chấm chính thức không dùng định dạng input này.
Bạn không được tự xử lý input/output trong lời giải của mình.

Sample grader trước tiên gọi init(n), sau đó gọi range_MWIS_query(l_i, r_i) đúng ~q~ lần.

Nếu trong quá trình gọi compare_subsets() từ init() hoặc range_MWIS_query() mà có bất kỳ lời gọi không hợp lệ nào, sample grader sẽ in ra:

Wrong Answer: msg

và dừng chương trình ngay lập tức, trong đó msg là một trong các lỗi sau:

• Invalid vertex number: v
  Mảng truyền vào compare_subsets() có chứa một số ~v~ không nằm trong đoạn từ ~1~ đến ~n~.

• Duplicate vertex numbers: v
  Mảng truyền vào compare_subsets() có chứa phần tử trùng nhau là ~v~.

Nếu không có lỗi, sample grader sẽ in ra theo định dạng:

m1
x[1][1] x[1][2] ... x[1][m1]
m2
x[2][1] x[2][2] ... x[2][m2]
...
mq
x[q][1] x[q][2] ... x[q][mq]
Accepted: Qinit Qquery

Trong đó:

• ~m_i~ là độ dài mảng bạn trả về ở lần gọi range_MWIS_query() thứ ~i~.
• ~x_{i,j}~ là phần tử thứ ~j~ trong mảng trả về ở lần gọi thứ ~i~.
• Qinit và Qquery là các giá trị dùng để chấm điểm, được định nghĩa ở phần chấm điểm.

Chấm điểm

Với mỗi test:

• Gọi ~x~ là số lần compare_subsets() được gọi trong hàm init().
• Gọi ~y_i~ là số lần compare_subsets() được gọi trong lần thứ ~i~ của range_MWIS_query().

Cách thử trên máy

Để thử lời giải trên máy của mình, trước tiên hãy tải ba file:

• grader.cpp
• mwis.h
• mwis.cpp

Bạn nên sửa file mwis.cpp, trong đó đã có sẵn một cài đặt ví dụ cơ bản.

Biên dịch bằng lệnh:

g++ -std=c++17 -O2 -Wall mwis.cpp grader.cpp -o mwis

Lệnh này sẽ tạo ra file mwis.exe, và bạn có thể chạy bằng:

./mwis

Ta định nghĩa:

~ Qinit = \left\lceil \frac{x}{n} \right\rceil ~

~ Qquery = \max_{1 \le i \le q} y_i ~

Từ đó, ta tính hai hệ số:

~ Winit = \begin{cases} 1.0 & \text{nếu } Qinit \le 3 \\ 1.0 - 0.07 \cdot (Qinit - 3) & \text{nếu } 3 < Qinit \le 10 \\ 0.5 - 0.04 \cdot (Qinit - 10) & \text{nếu } 10 < Qinit \le 20 \\ 0 & \text{nếu } Qinit > 20 \end{cases} ~

~ Wquery = \begin{cases} 1.0 & \text{nếu } Qquery \le 1 \\ 1.0 - 0.1 \cdot (Qquery - 1) & \text{nếu } 1 < Qquery \le 10 \\ 0 & \text{nếu } Qquery > 10 \end{cases} ~

Hệ số cuối cùng của test là:

~ W = Winit \cdot Wquery ~

Bài có 3 subtask. Điểm của bạn trên mỗi subtask bằng giá trị nhỏ nhất của ~W~ trên mọi test trong subtask, nhân với điểm của subtask đó.

Subtasks

Subtask 1 (16 điểm)

• ~l = 1~

Subtask 2 (11 điểm)

• Với mọi truy vấn ~[l, r]~, tập độc lập trọng số lớn nhất của đoạn ~[1, r]~ là duy nhất và không chứa đỉnh ~l+1~.

Subtask 3 (73 điểm)

• Không có ràng buộc bổ sung.

Tải tài liệu bài ở đây: https://drive.google.com/drive/folders/1gPW-SBKagDijmn8BmOEYncaBl0yVNLUZ?usp=sharing

An và Bình sắp làm một bài kiểm tra về từ vựng chữ Nôm.

Hai bạn biết ~N~ chữ Nôm, được đánh số từ ~0~ đến ~N-1~, và ~M~ từ, được đánh số từ ~0~ đến ~M-1~. Từ số ~i~ bắt đầu bằng chữ ~A[i]~, kết thúc bằng chữ ~B[i]~, và mất ~C[i]~ đơn vị thời gian để viết.

• ~A[i] \ne B[i]~ với mọi ~i~.
• Mỗi cặp ~(A[i], B[i])~ là duy nhất.

Ta có thể xem mỗi từ như một cạnh có hướng từ ~A[i]~ đến ~B[i]~ với trọng số ~C[i]~.

Trong bài kiểm tra có ~Q~ câu hỏi. Câu hỏi thứ ~j~ yêu cầu:

Hãy viết một chuỗi nối từ bắt đầu từ chữ ~S[j]~ và kết thúc ở chữ ~T[j]~.

Một chuỗi nối từ là một dãy từ sao cho chữ cuối của từ trước trùng với chữ đầu của từ sau. Chuỗi dùng để trả lời câu hỏi ~j~ phải thỏa:

• từ đầu tiên bắt đầu bằng ~S[j]~,
• từ cuối cùng kết thúc bằng ~T[j]~,
• tổng thời gian viết là nhỏ nhất có thể.

Nếu có nhiều đáp án tối ưu thì Bình có thể in ra bất kỳ đáp án nào.

Tình huống

Ngay trước giờ kiểm tra, Bình quên mất thời gian viết của đúng ~K~ từ:

~ U[0], U[1], \dots, U[K-1] ~

Điểm đặc biệt là các từ này đều có cùng chữ bắt đầu:

~ A[U[0]] = A[U[1]] = \cdots = A[U[K-1]] ~

An vẫn nhớ toàn bộ dữ liệu. Trong lúc làm bài, An có thể gửi cho Bình một dãy bit. Mỗi lần An chỉ gửi được đúng một bit 0 hoặc 1.

Bạn cần thiết kế chiến lược để:

• Bình luôn trả lời đúng tất cả câu hỏi.
• Số bit An phải gửi là ít nhất có thể.

Nhiệm vụ

Trong bộ chấm của bài này, bạn chỉ nộp một file C++ và cài đặt hai namespace:

namespace An {
    std::vector<int> tap_sequence(
        int N, int M,
        std::vector<int> A, std::vector<int> B, std::vector<long long> C,
        int Q, std::vector<int> S, std::vector<int> T,
        int K, std::vector<int> U
    );
}

namespace Binh {
    std::vector<std::vector<int>> solve(
        int N, int M,
        std::vector<int> A, std::vector<int> B, std::vector<long long> C,
        int Q, std::vector<int> S, std::vector<int> T,
        int K, std::vector<int> U,
        std::vector<int> X
    );
}

Ý nghĩa các hàm

An::tap_sequence

Hàm này đóng vai An.

• Nhận toàn bộ dữ liệu thật của đề, bao gồm cả mảng thời gian C.
• Phải trả về một dãy bit X.
• Mỗi phần tử của X phải là 0 hoặc 1.
• Độ dài của X không được vượt quá 1000.

Binh::solve

Hàm này đóng vai Bình.

• Nhận cùng dữ liệu đầu vào như phía An.
• Tuy nhiên, với mọi chỉ số i thuộc tập {U[0], U[1], ..., U[K-1]}, ta có C[i] = -1.
• X là dãy bit mà An::tap_sequence đã gửi.

Hàm phải trả về một mảng answers gồm đúng ~Q~ phần tử, trong đó:

• answers[j] là danh sách chỉ số các từ Bình dùng để trả lời câu hỏi j.
• answers[j] phải không rỗng.
• Các từ trong answers[j] phải xuất hiện theo đúng thứ tự viết ra.

Điều kiện đúng

Lời giải được coi là đúng nếu đồng thời thỏa tất cả các điều kiện sau:

• Dãy X do An::tap_sequence trả về có độ dài không quá 1000.
• Mọi phần tử của X đều là 0 hoặc 1.
• Binh::solve trả về đúng ~Q~ câu trả lời.
• Với mỗi câu hỏi j, dãy answers[j] tạo thành một chuỗi nối từ hợp lệ.
• Với mỗi câu hỏi j, từ đầu tiên phải bắt đầu bằng S[j] và từ cuối cùng phải kết thúc bằng T[j].
• Với mỗi câu hỏi j, tổng thời gian viết phải là nhỏ nhất có thể theo dữ liệu thật.

Nếu có nhiều đáp án tối ưu cho một câu hỏi thì trả về đáp án nào cũng được.

Lưu ý chấm

• Đây là bản đóng gói một file. Về ý tưởng, An::tap_sequence và Binh::solve tương ứng với hai phía giao tiếp độc lập của bài gốc.
• Không dùng biến toàn cục để truyền trực tiếp thông tin từ namespace An sang namespace Binh. Bình chỉ được suy luận từ dữ liệu đầu vào của mình và dãy bit X.

Bạn sẽ được cung cấp một khung code dạng:

#include <vector>
using namespace std;

namespace An {
    vector<int> tap_sequence(
        int N, int M,
        vector<int> A, vector<int> B, vector<long long> C,
        int Q, vector<int> S, vector<int> T,
        int K, vector<int> U
    ) {
        (void)N; (void)M; (void)A; (void)B; (void)C;
        (void)Q; (void)S; (void)T; (void)K; (void)U;
        return {};
    }
}

namespace Binh {
    vector<vector<int>> solve(
        int N, int M,
        vector<int> A, vector<int> B, vector<long long> C,
        int Q, vector<int> S, vector<int> T,
        int K, vector<int> U,
        vector<int> X
    ) {
        (void)N; (void)M; (void)A; (void)B; (void)C;
        (void)Q; (void)S; (void)T; (void)K; (void)U; (void)X;
        return {};
    }
}

Định dạng input của bộ chấm cục bộ

• Dòng 1: N M Q K
• M dòng tiếp theo: A[i] B[i] C[i]
• Q dòng tiếp theo: S[j] T[j] Z[j]
• K dòng cuối: U[k]

Trong đó Z[j] là tổng thời gian nhỏ nhất của một đáp án hợp lệ cho câu hỏi j.

Ràng buộc

• ~2 \le N \le 300~
• ~1 \le M \le N(N-1)~
• ~0 \le A[i], B[i] < N~
• ~A[i] \ne B[i]~
• ~(A[i], B[i]) \ne (A[j], B[j])~ với mọi ~i \ne j~
• ~1 \le C[i] \le 10^{16}~
• ~1 \le Q \le 60~
• ~0 \le S[j], T[j] < N~
• ~S[j] \ne T[j]~
• ~(S[i], T[i]) \ne (S[j], T[j])~ với mọi ~i \ne j~
• Với mọi câu hỏi, luôn tồn tại ít nhất một chuỗi nối từ từ S[j] đến T[j]
• ~1 \le K \le 5~
• ~0 \le U[k] < M~
• Các giá trị U[k] đôi một khác nhau
• Các từ Bình quên đều có cùng chữ bắt đầu

Subtasks

Subtask 1 (10 điểm)

• ~Q \le 10~
• Với mọi câu hỏi, luôn tồn tại một đáp án dùng không quá ~10~ từ
• Độ dài dãy bit gửi đi không vượt quá 1000

Subtask 2 (22 điểm)

• Độ dài dãy bit gửi đi không vượt quá 180

Subtask 3 (8 điểm)

• Độ dài dãy bit gửi đi không vượt quá 160

Subtask 4 (40 điểm)

• Độ dài dãy bit gửi đi không vượt quá 90

Subtask 5 (20 điểm)

Gọi ~L~ là độ dài dãy bit gửi đi lớn nhất trên mọi test của subtask này.

• Nếu ~L \le 64~: được 20 điểm
• Nếu ~64 < L < 90~: được

~ \left\lfloor \left( \frac{90 - L}{90 - 64} \right)^2 \cdot 20 \right\rfloor ~

điểm

• Nếu ~L \ge 90~: được 0 điểm

Ví dụ

Sample Input

4 5 3 2
2 1 10
0 2 20
3 1 30
0 1 40
3 0 50
3 0 50
3 1 30
0 1 30
1
3

Giải thích

Bình quên thời gian của hai từ 1 và 3, đều là các từ xuất phát từ chữ 0.

Ba câu hỏi có đáp án tối ưu lần lượt là:

• 3 -> 0: dùng từ 4, tổng thời gian 50
• 3 -> 1: dùng từ 2, tổng thời gian 30
• 0 -> 1: dùng hai từ 1, 0, tổng thời gian 30

Một chiến lược hợp lệ là:

• An::tap_sequence trả về dãy bit 0, 0, 1, 0
• Binh::solve trả về:
  • câu 1: 4
  • câu 2: 2
  • câu 3: 1 0