IOI 2024 - Ngày 2

Một nhóm các nhà nghiên cứu đang nghiên cứu những điểm tương đồng giữa các dãy chữ tượng hình. Họ biểu diễn mỗi chữ tượng hình bằng một số nguyên không âm. Để thực hiện nghiên cứu, họ sử dụng các khái niệm sau đây về các dãy.

Với một dãy \(A\) cố định, dãy \(S\) được gọi là dãy con của \(A\) khi và chỉ khi \(S\) có thể nhận được bằng cách xoá bỏ một số phần tử (hoặc không xoá phần tử nào) của \(A\).

Bảng sau cho thấy một số ví dụ về dãy con của dãy \(A = [3, 2, 1, 2]\).

Mặt khác, \([3, 3]\) hoặc \([1, 3]\) không phải dãy con của \(A\).

Xét hai dãy chữ tượng hình, \(A\) và \(B\). Một dãy \(S\) được gọi là dãy con chung của \(A\) và \(B\) khi và chỉ khi \(S\) là dãy con của cả \(A\) và \(B\). Hơn nữa, ta nói dãy \(U\) là dãy con chung vũ trụ của \(A\) và \(B\) khi và chỉ khi hai điều kiện sau thoả mãn:

• \(U\) là dãy con chung của \(A\) và \(B\).
• Mọi dãy con chung của \(A\) và \(B\) đều là dãy con của \(U\).

Có thể chứng minh được rằng mọi cặp dãy \(A\) và \(B\) có nhiều nhất một dãy con chung vũ trụ.

Các nhà nghiên cứu đã tìm thấy hai dãy chữ tượng hình \(A\) và \(B\). Dãy \(A\) có \(N\) chữ tượng hình và dãy \(B\) có \(M\) chữ tượng hình. Hãy giúp các nhà nghiên cứu tìm ra dãy con chung vũ trụ của hai dãy \(A\) và \(B\), hoặc xác định dãy như vậy không tồn tại.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau.

std::vector<int> ucs(std::vector<int> A, std::vector<int> B)

• \(A\): mảng có độ dài \(N\) mô tả dãy đầu tiên.
• \(B\): mảng có độ dài \(M\) mô tả dãy thứ hai.
• Nếu tồn tại dãy con chung vũ trụ của \(A\) và \(B\), hàm cần trả về mảng chứa dãy này. Ngược lại, hàm cần trả về \([-1]\) (mảng có độ dài \(1\), có đúng một phần tử \(-1\)).
• Hàm này được gọi đúng một lần cho mỗi trường hợp test.

Các ràng buộc

• \(1 \leq N \leq 100\,000\)
• \(1 \leq M \leq 100\,000\)
• \(0 \leq A[i] \leq 200\,000\) với mỗi \(i\) thoả mãn \(0 \leq i < N\)
• \(0 \leq B[j] \leq 200\,000\) với mỗi \(j\) thoả mãn \(0 \leq j < M\)

Các subtasks

Các ví dụ

Ví dụ 1

Xét lời gọi hàm sau.

ucs([0, 0, 1, 0, 1, 2], [2, 0, 1, 0, 2])

Trong đó, các dãy con chung của \(A\) và \(B\) là: \([\ ]\), \([0]\), \([1]\), \([2]\), \([0, 0]\), \([0, 1]\), \([0, 2]\), \([1, 0]\), \([1, 2]\), \([0, 0, 2]\), \([0, 1, 0]\), \([0, 1, 2]\), \([1, 0, 2]\) và \([0, 1, 0, 2]\).

Vì dãy \([0, 1, 0, 2]\) là dãy con chung của \(A\) và \(B\), và mọi dãy con chung của \(A\) và \(B\) là dãy con của dãy \([0, 1, 0, 2]\), hàm cần trả về mảng \([0, 1, 0, 2]\).

Ví dụ 2

Xét lời gọi hàm sau.

ucs([0, 0, 2], [1, 1])

Trong đó, dãy con chung duy nhất của \(A\) và \(B\) là dãy rỗng \([\ ]\). Vì vậy, hàm cần trả về mảng rỗng \([\ ]\).

Ví dụ 3

Xét lời gọi hàm sau.

ucs([0, 1, 0], [1, 0, 1])

Trong đó, dãy con chung của \(A\) và \(B\) là \([\ ], [0], [1], [0, 1]\) và \([1, 0]\). Có thể chứng minh rằng dãy con chung vũ trụ không tồn tại. Vì vậy, hàm cần trả về mảng \([-1]\).

Trình chấm mẫu

Định dạng dữ liệu vào:

N  M
A[0]  A[1]  ...  A[N-1]
B[0]  B[1]  ...  B[M-1]

Định dạng kết quả ra:

T
R[0]  R[1]  ...  R[T-1]

Trong đó, \(R\) là mảng trả về bởi hàm ucs và \(T\) là độ dài của nó.

Nguồn: Olympic Tin học Quốc tế (IOI) 2024. Bản dịch tiếng Việt chính thức do ban tổ chức cung cấp.

Salma dự định tô màu một bức tranh khảm đất sét trên tường. Bức tranh là một lưới \(N \times N\), được tạo thành từ \(N^2\) ô vuông \(1 \times 1\) chưa tô màu. Các hàng của bức tranh được đánh số từ \(0\) đến \(N-1\) từ trên xuống dưới, và các cột được đánh số từ \(0\) đến \(N-1\) từ trái sang phải. Ô vuông ở hàng \(i\) và cột \(j\) (\(0 \leq i < N\), \(0 \leq j < N\)) được kí hiệu là \((i,j)\). Mỗi ô phải được tô màu trắng (kí hiệu là \(0\)) hoặc đen (kí hiệu là \(1\)).

Để tô màu cho bức tranh, trước tiên Salma chọn hai mảng \(X\) và \(Y\) có độ dài \(N\), chỉ gồm các giá trị \(0\) và \(1\), thỏa mãn \(X[0] = Y[0]\). Cô ấy tô màu các ô của hàng trên cùng (hàng \(0\)) theo mảng \(X\), sao cho màu của ô \((0,j)\) là \(X[j]\) (\(0 \leq j < N\)). Cô ấy cũng tô màu các ô của cột ngoài cùng bên trái (cột \(0\)) theo mảng \(Y\), sao cho màu của ô \((i,0)\) là \(Y[i]\) (\(0 \leq i < N\)).

Sau đó, cô ấy lặp lại các bước sau cho đến khi tất cả các ô đều được tô màu:

• Cô ấy tìm một ô \((i,j)\) bất kì chưa tô màu mà có ô kề cạnh bên trên (ô \((i-1, j)\)) và ô kề cạnh bên trái (ô \((i, j-1)\)) đều đã được tô màu.
• Sau đó, cô ấy tô màu ô \((i,j)\) thành màu đen nếu cả hai ô kề này đều có màu trắng; trái lại, cô ấy tô màu ô \((i, j)\) thành màu trắng.

Có thể thấy rằng màu cuối cùng của các ô không phụ thuộc vào thứ tự các ô được Salma tô màu.

Yasmin rất tò mò về màu của các ô trong bức tranh. Cô ấy hỏi Salma \(Q\) câu hỏi, được đánh số từ \(0\) đến \(Q-1\). Trong câu hỏi \(k\) (\(0 \leq k < Q\)), Yasmin chỉ định một hình chữ nhật con của bức tranh bởi:

• Hàng trên cùng \(T[k]\) và hàng dưới cùng \(B[k]\) (\(0 \leq T[k] \leq B[k] < N\)),
• Cột ngoài cùng bên trái \(L[k]\) và cột ngoài cùng bên phải \(R[k]\) (\(0 \leq L[k] \leq R[k] < N\)).

Câu trả lời cho câu hỏi là số ô màu đen trong hình chữ nhật con này. Cụ thể, Salma cần đếm có bao nhiêu ô \((i, j)\) mà \(T[k] \leq i \leq B[k]\), \(L[k] \leq j \leq R[k]\), và màu của ô \((i,j)\) là màu đen.

Hãy viết một chương trình trả lời các câu hỏi của Yasmin.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau.

std::vector<long long> mosaic(
    std::vector<int> X, std::vector<int> Y,
    std::vector<int> T, std::vector<int> B,
    std::vector<int> L, std::vector<int> R);

• \(X\), \(Y\): hai mảng có độ dài \(N\) tương ứng mô tả màu của các ô ở hàng trên cùng và cột ngoài cùng bên trái.
• \(T\), \(B\), \(L\), \(R\): các mảng có độ dài \(Q\) mô tả các câu hỏi do Yasmin đặt ra.
• Hàm cần trả về một mảng \(C\) có độ dài \(Q\), mà \(C[k]\) là câu trả lời cho câu hỏi \(k\) (\(0 \leq k < Q\)).
• Hàm này được gọi đúng một lần cho mỗi trường hợp test.

Các ràng buộc

• \(1 \leq N \leq 200\,000\)
• \(1 \leq Q \leq 200\,000\)
• \(X[i] \in \{0, 1\}\) và \(Y[i] \in \{0, 1\}\) với mỗi \(i\) thỏa mãn \(0 \leq i < N\)
• \(X[0] = Y[0]\)
• \(0 \leq T[k] \leq B[k] < N\) và \(0 \leq L[k] \leq R[k] < N\) với mỗi \(k\) thỏa mãn \(0 \leq k < Q\)

Các subtasks

Ví dụ

Xét lời gọi hàm sau

mosaic([1, 0, 1, 0], [1, 1, 0, 1], [0, 2], [3, 3], [0, 0], [3, 2])

Ví dụ này được minh họa trong các hình bên dưới. Hình bên trái cho biết màu của các ô trong bức tranh. Hình ở giữa và bên phải tương ứng cho biết hình chữ nhật con trong câu hỏi thứ nhất và thứ hai của Yasmin.

Câu trả lời cho các câu hỏi (tức là số lượng số 1 trong các hình chữ nhật được tô đậm) lần lượt là 7 và 3. Do đó, hàm cần trả về \([7, 3]\).

Trình chấm mẫu

Định dạng dữ liệu vào:

N
X[0]  X[1]  ...  X[N-1]
Y[0]  Y[1]  ...  Y[N-1]
Q
T[0]  B[0]  L[0]  R[0]
T[1]  B[1]  L[1]  R[1]
...
T[Q-1]  B[Q-1]  L[Q-1]  R[Q-1]

Định dạng kết quả ra:

C[0]
C[1]
...
C[S-1]

Trong đó, \(S\) là độ dài của mảng \(C\) được trả về bởi hàm mosaic.

Nguồn: Olympic Tin học Quốc tế (IOI) 2024. Bản dịch tiếng Việt chính thức do ban tổ chức cung cấp.

Tượng Nhân Sư có một câu đố dành cho bạn. Bạn được cho một đồ thị có \(N\) đỉnh. Các đỉnh được đánh số từ \(0\) đến \(N - 1\). Đồ thị có \(M\) cạnh, đánh số từ \(0\) đến \(M-1\). Mỗi cạnh nối một cặp đỉnh phân biệt và là cạnh vô hướng. Cụ thể, đối với mỗi \(j\) từ \(0\) đến \(M - 1\) (kể cả \(0\) và \(M-1\)) cạnh \(j\) nối các đỉnh \(X[j]\) và \(Y[j]\). Có nhiều nhất một cạnh nối một cặp đỉnh bất kỳ. Hai đỉnh được gọi là kề nhau nếu chúng được nối với nhau bởi một cạnh.

Một dãy các đỉnh \(v_0, v_1, \ldots, v_k\) (với \(k \ge 0\)) được gọi là một đường đi nếu mỗi hai đỉnh liên tiếp \(v_l\) và \(v_{l+1}\) (với mỗi \(l\) sao cho \(0 \le l < k\)) là kề nhau. Ta nói rằng đường đi \(v_0, v_1, \ldots, v_k\) kết nối các đỉnh \(v_0\) và \(v_k\). Trong đồ thị đã cho, mỗi cặp đỉnh được kết nối bởi một đường đi nào đó.

Có \(N + 1\) màu, được đánh số từ \(0\) đến \(N\). Màu \(N\) là màu đặc biệt và được gọi là màu của Nhân Sư. Mỗi đỉnh được gán một màu. Cụ thể, đỉnh \(i\) (\(0 \le i < N\) ) có màu \(C[i]\). Có thể có nhiều đỉnh cùng màu nhau, và có thể có những màu không được gán cho bất kỳ đỉnh nào. Không có đỉnh nào có màu của Nhân Sư, nghĩa là \(0 \le C[i] < N\) ( \(0 \le i < N\)).

Đường đi \(v_0, v_1, \ldots, v_k\) (với \(k \ge 0\)) được gọi là đơn sắc nếu như tất cả các đỉnh của nó có cùng màu, tức là \(C[v_l] = C[v_{l+1}]\) (với mỗi \(l\) thoả mãn \(0 \le l < k\)). Ngoài ra, chúng ta nói rằng các đỉnh \(p\) và \(q\) (\(0 \le p < N\), \(0 \le q < N\)) có cùng thành phần đơn sắc khi và chỉ khi chúng được kết nối bởi một đường đi đơn sắc.

Bạn biết các đỉnh và cạnh, nhưng bạn không biết mỗi đỉnh có màu gì. Bạn muốn tìm ra màu sắc của các đỉnh, bằng cách thực hiện thí nghiệm tô màu lại.

Trong một thí nghiệm tô màu lại, bạn có thể tô màu lại nhiều đỉnh tùy ý. Cụ thể, để thực hiện một thí nghiệm tô màu lại, đầu tiên bạn chọn một mảng \(E\) có kích thước \(N\), trong đó đối với mỗi \(i\) (\(0 \le i < N\) ), \(E[i]\) nằm giữa \(-1\) và \(N\) bao gồm cả \(-1\) và \(N\). Sau đó, màu của mỗi đỉnh \(i\) trở thành \(S[i]\), trong đó giá trị của \(S[i]\) là:

• \(C[i]\), tức là màu gốc của đỉnh \(i\), nếu \(E[i] = -1\), hoặc
• \(E[i]\), trái lại.

Lưu ý điều này có nghĩa là bạn có thể sử dụng màu của Nhân Sư khi tô màu lại.

Cuối cùng, Tượng Nhân Sư công bố số lượng các thành phần đơn sắc trong đồ thị, sau khi thiết lập màu của mỗi đỉnh \(i\) thành \(S[i]\) (\(0 \le i < N\)). Việc tô màu mới chỉ được áp dụng cho thí nghiệm tô màu lại này, vì vậy màu của tất cả các đỉnh sẽ trở về màu ban đầu sau khi thí nghiệm kết thúc.

Nhiệm vụ của bạn là xác định màu của các đỉnh trong đồ thị bằng cách thực hiện tối đa \(2\,750\) thí nghiệm tô màu lại. Bạn cũng có thể nhận được một phần điểm nếu bạn xác định đúng cho mọi cặp đỉnh kề nhau liệu chúng có cùng màu hay không.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau.

std::vector<int> find_colours(int N,
    std::vector<int> X, std::vector<int> Y)

• \(N\): số lượng đỉnh trong đồ thị.
• \(X\), \(Y\): các mảng độ dài \(M\) mô tả các cạnh.
• Hàm này cần trả về một mảng \(G\) độ dài \(N\), biểu diễn màu của các đỉnh trong đồ thị.
• Hàm này được gọi đúng một lần cho mỗi trường hợp test.

Hàm trên có thể thực hiện các lời gọi đến hàm sau để thực hiện các thí nghiệm tô màu lại:

int perform_experiment(std::vector<int> E)

• \(E\): mảng độ dài \(N\) chỉ ra các đỉnh cần được tô màu lại thế nào.
• Hàm này trả về số lượng các thành phần đơn sắc sau khi tô lại các đỉnh theo \(E\).
• Hàm này có thể được gọi tối đa \(2\,750\) lần.

Trình chấm là không thích ứng, nghĩa là, màu của các đỉnh được cố định trước khi thực hiện một lời gọi find_colours.

Các ràng buộc

• \(2 \le N \le 250\)
• \(N - 1 \le M \le \frac{N \cdot (N - 1)}{2}\)
• \(0 \le X[j] < Y[j] < N\) với mỗi \(j\) thoả mãn \(0 \le j < M\).
• \(X[j] \neq X[k]\) hoặc \(Y[j] \neq Y[k]\) với mỗi \(j\) và \(k\) thoả mãn \(0 \le j < k < M\).
• Mỗi cặp đỉnh được kết nối bởi đường đi nào đó.
• \(0 \le C[i] < N\) với mỗi \(i\) thoả mãn \(0 \le i < N\).

Các subtasks

Trong mỗi subtask, bạn có thể nhận được một phần điểm nếu chương trình của bạn xác định đúng cho mỗi cặp đỉnh kề nhau liệu chúng có cùng màu hay không.

Cụ thể, bạn nhận được toàn bộ điểm của một subtask nếu trong tất cả các trường hợp test của subtask đó, mảng \(G\) được trả về bởi find_colours hoàn toàn giống với mảng \(C\) (tức là \(G[i] = C[i]\) với mọi \(i\) thoả mãn \(0 \le i < N\)). Trái lại, bạn nhận được \(50\%\) số điểm đối với một subtask nếu các điều kiện sau đây thoả mãn trong tất cả các trường hợp test của subtask đó:

• \(0 \le G[i] < N\) với mỗi \(i\) thoả mãn \(0 \le i < N\);
• Với mỗi \(j\) thoả mãn \(0 \le j < M\):
• \(G[X[j]] = G[Y[j]]\) khi và chỉ khi \(C[X[j]] = C[Y[j]]\).

Ví dụ

Xét lời gọi sau.

find_colours(4, [0, 1, 0, 0], [1, 2, 2, 3])

Đối với ví dụ này, giả sử rằng màu (ẩn) của các đỉnh được đưa ra bởi \(C = [2, 0, 0, 0]\). Tình huống này được thể hiện trong hình sau. Màu cũng được biểu thị bằng các con số trên nhãn màu trắng gắn ở mỗi đỉnh.

Hàm này có thể gọi perform_experiment như sau.

perform_experiment([-1, -1, -1, -1])

Trong lời gọi này, không có đỉnh nào được tô màu lại vì tất cả các đỉnh đều giữ nguyên màu gốc.

Xét đỉnh \(1\) và đỉnh \(2\). Cả hai đều có màu \(0\) và đường đi \(1, 2\) là đường đi đơn sắc. Kết quả là, các đỉnh \(1\) và \(2\) nằm trong cùng một thành phần đơn sắc.

Xét đỉnh \(1\) và đỉnh \(3\). Mặc dù cả hai đều có màu \(0\), chúng có các thành phần đơn sắc khác nhau vì không có đường đi đơn sắc nào kết nối chúng.

Như vậy, có \(3\) thành phần đơn sắc, với các đỉnh \(\{0\}\), \(\{1, 2\}\) và \(\{3\}\). Do đó, lời gọi này trả về \(3\) .

Bây giờ hàm có thể gọi perform_experiment như sau.

perform_experiment([0, -1, -1, -1])

Trong lời gọi này, chỉ có đỉnh \(0\) được đổi màu thành màu \(0\), do đó, việc tô màu như trong hình sau.

Lời gọi này trả về \(1\) vì tất cả các đỉnh đều thuộc cùng một thành phần đơn sắc. Bây giờ ta có thể suy ra rằng các đỉnh \(1\) , \(2\) và \(3\) có màu \(0\) .

Do đó, hàm có thể gọi perform_experiment như sau.

perform_experiment([-1, -1, -1, 2])

Trong lời gọi này, đỉnh \(3\) được tô màu lại thành màu \(2\), do đó, việc tô màu như trong hình sau.

Lời gọi này trả về \(2\) vì có \(2\) thành phần đơn sắc, tương ứng với các đỉnh \(\{0, 3\}\) và \(\{1, 2\}\). Ta có thể suy ra rằng đỉnh \(0\) có màu \(2\) .

Do đó, hàm find_colours trả về mảng \([2, 0, 0, 0]\). Vì \(C = [2, 0, 0, 0]\) nên kết quả đạt điểm tối đa.

Lưu ý rằng cũng có nhiều giá trị trả về để đạt được \(50\%\) số điểm, ví dụ \([1, 2, 2, 2]\) hoặc \([1, 2, 2, 3]\) .

Trình chấm mẫu

Định dạng dữ liệu vào:

N  M
C[0]  C[1] ... C[N-1]
X[0]  Y[0]
X[1]  Y[1]
...
X[M-1]  Y[M-1]

Định dạng kết quả ra:

L  Q
G[0]  G[1] ... G[L-1]

Trong đó, \(L\) là độ dài của mảng \(G\) trả về bởi find_colours, và \(Q\) là số lượng lời gọi tới perform_experiment.

Nguồn: Olympic Tin học Quốc tế (IOI) 2024. Bản dịch tiếng Việt chính thức do ban tổ chức cung cấp.