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.

Cho một xâu ~S~ có độ dài ~n~ chỉ gồm các chữ cái in thường. Biết rằng có thể thêm hoặc sửa không quá ~K~ kí tự trong ~S~ để thu được một xâu đối xứng (palindrome).

Nhiệm vụ của bạn là tìm độ dài dãy con đối xứng dài nhất của ~S~.

Một xâu T được coi là dãy con của xâu S nếu từ xâu S, ta có thể xoá đi một số kí tự (có thể là không xoá kí tự nào) để thu được xâu T.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~K~ ~(1 \le n \le 5 \times 10^6,~ ~0 \le K \le 500)~ lần lượt là độ dài xâu và số thao tác tối đa.
• Dòng thứ hai chứa xâu ~S~ gồm ~n~ chữ cái in thường.

Output

• In ra một số nguyên duy nhất là độ dài dãy con đối xứng dài nhất của ~S~.

Scoring

Sample Input 1

7 2
adbcbea

Sample Output 1

5

Note

Dãy con đối xứng dài nhất của xâu ~adbcbea~ là ~abcba~ (chọn các vị trí ~1, 3, 4, 5, 7~), có độ dài ~5~. Có thể kiểm tra rằng chỉ cần thêm ~2~ kí tự vào xâu ~adbcbea~ là thu được một xâu đối xứng, ví dụ thêm ~a~ và ~d~ để được ~adbcbcbda~.

Bạn hãy tải những tài liệu cần thiết cho bài tại đây: https://drive.google.com/file/d/1U9BFu3Y2EvZIDjA7_sl66IPI-qvBhzKf/view?usp=sharing

Giáo sư Khoo muốn theo đuổi giấc mơ cả đời là trở thành họa sĩ, nên ông quyết định rời MI6 để khai sinh một phong cách hội họa mới rất kỳ lạ: Gridism.

Để tạo ra một bức tranh theo phong cách Gridism, bạn bắt đầu với một lưới gồm 100 hàng và 100 cột.

• Các hàng được đánh số từ ~0~ đến ~99~ theo hướng từ bắc xuống nam.
• Các cột được đánh số từ ~0~ đến ~99~ theo hướng từ tây sang đông.
• Ô ở hàng ~r~, cột ~c~ được ký hiệu là ~(r, c)~.

Trong hình là bức tranh trong test mẫu có trong phần ví dụ mẫu ở bên dưới, ô bắt đầu được đánh dấu "S".

Tiếp theo, bạn chọn một ô bắt đầu và đặt cây cọ của mình ở đó, với đầu cọ đã nhúng sơn đen.

Có 4 loại bước đi, mỗi loại được ký hiệu bằng một chữ cái in hoa:

• N: di chuyển cọ lên trên 1 ô.
• S: di chuyển cọ xuống dưới 1 ô.
• E: di chuyển cọ sang phải 1 ô.
• W: di chuyển cọ sang trái 1 ô.

Trong suốt quá trình, bạn không được đưa cọ ra ngoài lưới, cũng không được nhấc cọ lưới, mọi ô mà cọ đi qua ít nhất một lần, bao gồm cả ô bắt đầu và ô kết thúc, sẽ được tô màu đen.

Khi nhìn vào một bức tranh hoàn chỉnh, bạn chỉ thấy mỗi ô là màu đen hay màu trắng. Tuy nhiên, bạn không biết ô bắt đầu là ô nào, cũng không biết dãy bước đi đã được thực hiện ra sao.

MI6 vẫn cần đến tài năng phát minh thiên tài của Khoo, nên ông nhờ bạn nghĩ ra một chiến lược để mã hóa thông điệp bí mật thành các bức tranh Gridist.

Nhiệm vụ của bạn là viết hai hàm:

• một hàm để mã hóa một dãy bit thành một bức tranh,
• một hàm để giải mã bức tranh đó.

Thông điệp bạn mã hóa được càng dài thì điểm số của bạn càng cao.

Chi tiết cài đặt

Trong bài này, bạn không được đọc từ standard input, không được ghi ra standard output, cũng không được tương tác với bất kỳ file nào.

Bạn cũng không được tự cài đặt hàm main.

Thay vào đó, chương trình của bạn phải bắt đầu bằng:

#include "art.h"

và tương tác đúng theo các mô tả dưới đây.

Các hàm cần cài đặt

Bạn phải cài đặt hai hàm encode và decode.

string encode(string S);

• S là một xâu gồm các ký tự 0 và 1, biểu diễn thông điệp cần mã hóa.
• Xâu này luôn có đúng ~10000~ ký tự.
• Mỗi lần hàm này được gọi, bạn phải gọi init đúng một lần.
• Hàm này phải trả về một xâu dài không quá ~20000~ ký tự, chỉ gồm các ký tự N, S, E, W, biểu diễn dãy bước đi của cọ.

• Trong quá trình di chuyển, bạn không được đưa cọ ra ngoài lưới.

  void init(int r, int c, int b);

• Hàm này thiết lập ô bắt đầu là ô ~(r, c)~.

• Đồng thời khai báo rằng bạn đang mã hóa ~b~ bit đầu tiên của xâu S vào bức tranh hiện tại.

• Bạn phải thỏa:

  • ~0 <= r < 100~
  • ~0 <= c < 100~
  • ~1 <= b <= 10000~

  string decode(int b, vector<vector<int>> painting);

• b là độ dài của thông điệp đã được mã hóa trong bức tranh này, tức là đúng giá trị b đã truyền vào init bên phía encode.

• painting là một lưới ~100 x 100~ hai chiều mô tả màu của mỗi ô.
• painting[r][c] = 1 nếu ô ~(r, c)~ là màu đen, ngược lại bằng 0.
• Hàm này phải trả về một xâu độ dài đúng bằng ~b~, và xâu này phải đúng với thông điệp đã được mã hóa.

Nếu bạn vi phạm bất kỳ điều kiện nào ở trên, lời giải của bạn sẽ bị chấm sai và nhận ~0%~ số điểm của test đó.

Cách chấm

Bộ chấm sẽ khởi chạy hai phiên bản tách biệt của chương trình của bạn:

• một phiên bản encoder,
• một phiên bản decoder.

Quy trình chấm như sau:

• Đầu tiên, bộ chấm chọn ~x~ thông điệp và gọi encode đúng ~x~ lần ở phía encoder.
• Sau đó, bộ chấm gọi decode đúng ~x~ lần ở phía decoder, mỗi lần với một bức tranh do encoder tạo ra, theo một thứ tự bất kỳ.

Điều này có nghĩa là:

• mọi thông tin bạn lưu trong biến static hoặc biến toàn cục ở phiên bản encoder
• sẽ không thể truy cập được bên trong decode, vì đó là một tiến trình khác.

Thời gian chạy của lời giải được tính là tổng thời gian của cả hai phiên bản encoder và decoder.

Subtasks

Bài này chỉ có một subtask duy nhất.

Với mọi test:

• ~1 <= x <= 5~

Chấm điểm

Gọi ~m~ là giá trị nhỏ nhất của ~b~ trong số ~x~ lần gọi decode.

Khi đó:

• Nếu ~m < 10~, bạn được ~0~ điểm.

• Nếu ~10 \le m < 600~, bạn được ~ 5 + 15 \cdot \frac{m - 10}{600 - 10} ~ điểm.

• Nếu ~600 \le m < 6000~, bạn được ~ 20 + 25 \cdot \frac{m - 600}{6000 - 600} ~ điểm.

• Nếu ~6000 \le m < 8750~, bạn được ~ 45 + 55 \cdot \frac{m - 6000}{8750 - 6000} ~ điểm.

• Nếu ~8750 \le m~, bạn được ~100~ điểm.

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:

• art.cpp
• art.h
• grader.cpp

Bạn nên sửa file art.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 art.cpp grader.cpp -o art

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

./art

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

Sample grader đọc từ standard input theo định dạng:

• Dòng đầu tiên chứa số nguyên ~x~, là số thông điệp cần mã hóa.
• ~x~ dòng tiếp theo, mỗi dòng là một xâu gồm các ký tự 0 và 1, có độ dài không quá ~10000~.

Lưu ý:

• Bạn có thể cung cấp ít hơn ~10000~ bit cho sample grader.
• Tuy nhiên, sample grader sẽ bị crash nếu bạn gọi init với giá trị b lớn hơn số bit thực sự có trong xâu đầu vào.

Với mỗi thông điệp, sample grader sẽ:

• gọi encode để tạo ra một bức tranh,
• rồi ngay lập tức gọi decode,
• sau đó in xâu mà decode trả về ra standard output.

Lưu ý rằng bộ chấm thật có thể hành xử khác sample grader, đặc biệt là như đã mô tả ở phần Cách chấm.

Ví dụ một tương tác hợp lệ

Sample grader có thể nhận input như sau:

2
0010001001
10101111

Với thông điệp thứ nhất:

• Bộ chấm gọi encode("0010001001").
• Thí sinh gọi init(1, 3, 5), rồi trả về xâu SSWNEENNW.
• Bộ chấm gọi decode(5, [0001100..., 0001100..., 0011100..., 0011000..., 0000000..., ...]), tương ứng với bức tranh thứ nhất trong đề.
• Thí sinh trả về 00100, và sample grader in xâu này ra.

Với thông điệp thứ hai:

• Bộ chấm gọi encode("10101111").
• Thí sinh gọi init(0, 2, 4), rồi trả về xâu WWESS.
• Bộ chấm gọi decode(4, [11100..., 01000..., 01000..., ...]), tương ứng với bức tranh thứ hai trong đề.
• Thí sinh trả về 1010, và sample grader in xâu này ra.