APIO 2020

Đã lâu rồi kể từ lần cuối cùng Pak Dengklek sơn tường cho ngôi nhà của mình, vì vậy anh ấy muốn sơn lại nó. Tường nhà bao gồm \(N\) mảng tường, được đánh số từ \(0\) đến \(N-1\). Trong bài toán này, giả thiết là có \(K\) màu khác nhau, mỗi màu được biểu thị bằng một số nguyên từ \(0\) đến \(K-1\) (ví dụ: màu đỏ được biểu thị bằng \(0\), màu xanh lam được biểu thị bằng \(1\), v.v.). Pak Dengklek muốn sơn mảng tường thứ \(i\) bằng màu \(C[i]\).

Để sơn tường, Pak Dengklek thuê một công ty thầu khoán với \(M\) nhà thầu, được đánh số từ \(0\) đến \(M-1\). Thật không may cho Pak Dengklek, các nhà thầu chỉ sẵn sàng sơn những màu mà họ thích. Cụ thể, nhà thầu thứ \(j\) chỉ thích \(A[j]\) màu và chỉ muốn sơn một mảng tường bằng một trong các màu \(B[j][0], B[j][1], \ldots, B[j][A[j]-1]\).

Pak Dengklek có thể đưa ra một số bản hướng dẫn cho công ty thầu khoán. Với một bản hướng dẫn, Pak Dengklek sẽ đưa ra hai tham số \(x\) và \(y\), trong đó \(0 \le x < M\) và \(0 \le y \le N-M\). Công ty thầu khoán sẽ hướng dẫn nhà thầu thứ \(((x+l) \bmod M)\) sơn mảng tường \((y+l)\) với mọi \(0 \le l < M\). Nếu tồn tại một giá trị \(l\) mà nhà thầu thứ \(((x+l) \bmod M)\) không thích màu \(C[y+l]\), thì bản hướng dẫn này không hợp lệ.

Pak Dengklek phải trả tiền cho mỗi bản hướng dẫn mà anh ta đưa ra, do đó anh ta muốn biết số lượng bản hướng dẫn tối thiểu phải đưa ra để sơn tất cả các mảng tường bằng màu dự kiến ban đầu của chúng, hoặc xác nhận rằng điều đó là không thể. Cùng một mảng tường có thể được sơn nhiều lần, nhưng nó phải luôn được sơn bằng màu dự kiến ban đầu của nó.

Chi tiết cài đặt

Bạn phải cài đặt hàm có chữ ký C++ chính xác như sau:

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B);

Hàm minimumInstructions được trình chấm gọi đúng một lần.

• N: số lượng mảng tường.
• M: số lượng nhà thầu.
• K: số lượng màu sơn.
• C: mảng gồm \(N\) số nguyên biểu diễn màu dự kiến của các mảng tường.
• A: mảng gồm \(M\) số nguyên biểu diễn số lượng màu mà các nhà thầu thích.
• B: mảng gồm \(M\) mảng số nguyên biểu diễn các màu mà các nhà thầu thích; mảng thứ \(j\) có \(A[j]\) phần tử.
• Hàm phải trả về một số nguyên biểu diễn số lượng nhỏ nhất các bản hướng dẫn mà Pak Dengklek phải đưa ra để sơn tất cả các mảng tường bằng màu dự kiến của chúng, hoặc \(-1\) nếu không có phương án thực hiện.

Ví dụ

8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4

3

Trong ví dụ này, \(N=8\), \(M=3\), \(K=5\), \(C=[3,3,1,3,4,4,2,2]\), \(A=[3,2,2]\) và \(B=[[0,1,2],[2,3],[3,4]]\).

Pak Dengklek có thể đưa ra các bản hướng dẫn như sau:

1. \(x=1\), \(y=0\). Đây là một bản hướng dẫn hợp lệ vì nhà thầu thứ \(1\) có thể sơn mảng tường thứ \(0\), nhà thầu thứ \(2\) có thể sơn mảng tường thứ \(1\), và nhà thầu thứ \(0\) có thể sơn mảng tường thứ \(2\).
2. \(x=0\), \(y=2\). Đây là một bản hướng dẫn hợp lệ vì nhà thầu thứ \(0\) có thể sơn mảng tường thứ \(2\), nhà thầu thứ \(1\) có thể sơn mảng tường thứ \(3\), và nhà thầu thứ \(2\) có thể sơn mảng tường thứ \(4\).
3. \(x=2\), \(y=5\). Đây là một bản hướng dẫn hợp lệ vì nhà thầu thứ \(2\) có thể sơn mảng tường thứ \(5\), nhà thầu thứ \(0\) có thể sơn mảng tường thứ \(6\), và nhà thầu thứ \(1\) có thể sơn mảng tường thứ \(7\).

Dễ dàng thấy rằng Pak Dengklek không thể đưa ra ít hơn \(3\) bản hướng dẫn để sơn toàn bộ các mảng tường, vì vậy minimumInstructions(8, 3, 5, [3, 3, 1, 3, 4, 4, 2, 2], [3, 2, 2], [[0, 1, 2], [2, 3], [3, 4]]) trả về \(3\).

5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3

-1

Trong ví dụ này, \(N=5\), \(M=4\), \(K=4\), \(C=[1,0,1,2,2]\), \(A=[2,1,1,1]\) và \(B=[[0,1],[1],[2],[3]]\). Do nhà thầu thứ \(3\) chỉ thích màu \(3\) và không có mảng tường nào được sơn bằng màu \(3\), Pak Dengklek không thể đưa ra bất kỳ bản hướng dẫn hợp lệ nào. Do đó, minimumInstructions(5, 4, 4, [1, 0, 1, 2, 2], [2, 1, 1, 1], [[0, 1], [1], [2], [3]]) trả về \(-1\).

Ràng buộc

Với \(0 \le k < K\), gọi \(f(k)\) là số lượng chỉ số \(j\) sao cho nhà thầu thứ \(j\) thích màu \(k\). Ví dụ, nếu \(f(1)=2\) thì có hai nhà thầu thích màu \(1\).

• \(1 \le N \le 100\,000\).
• \(1 \le M \le \min(N,50\,000)\).
• \(1 \le K \le 100\,000\).
• \(0 \le C[i] < K\).
• \(1 \le A[j] \le K\).
• \(0 \le B[j][0] < B[j][1] < \ldots < B[j][A[j]-1] < K\).
• Tổng các \(f(k)^2 \le 400\,000\).

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo khuôn dạng sau:

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

Trình chấm mẫu in ra giá trị trả về bởi hàm minimumInstructions.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2020: Painting Walls.

Có \(N\) thành phố ở Indonesia, được đánh số từ \(0\) đến \(N-1\). Ngoài ra, còn có \(M\) con đường hai chiều, được đánh số từ \(0\) đến \(M-1\). Mỗi con đường nối hai thành phố khác nhau. Con đường thứ \(i\) kết nối thành phố \(U[i]\) với thành phố \(V[i]\) và tiêu thụ \(W[i]\) đơn vị xăng khi đi qua bằng ô tô. Các thành phố được kết nối với nhau sao cho có thể đi lại giữa bất kỳ cặp thành phố nào thông qua các con đường này.

Trong mỗi ngày của \(Q\) ngày tiếp theo, một cặp thành phố muốn thiết lập mối quan hệ chính trị. Cụ thể, vào ngày thứ \(j\), thành phố \(X[j]\) muốn thiết lập mối quan hệ chính trị với thành phố \(Y[j]\). Để thực hiện điều này, thành phố \(X[j]\) sẽ cử một người đại diện đi đến thành phố \(Y[j]\) bằng ô tô. Tương tự, thành phố \(Y[j]\) cũng sẽ cử một người đại diện đi đến thành phố \(X[j]\) bằng ô tô.

Để tránh ùn tắc, hai ô tô không được gặp nhau vào bất kỳ thời điểm nào. Cụ thể, hai ô tô không được ở trong cùng một thành phố vào cùng một thời điểm. Hai ô tô cũng không được đi trên cùng một con đường theo hai hướng ngược nhau vào cùng một thời điểm. Hơn nữa, khi ô tô đi trên một con đường thì phải đi hết con đường và đến thành phố đích; nói cách khác, ô tô không được phép quay đầu ở giữa đường. Tuy nhiên, ô tô được phép đến cùng một thành phố hoặc đi trên cùng một con đường nhiều hơn một lần. Ô tô cũng có thể chờ ở bất kỳ thành phố nào vào bất kỳ thời điểm nào.

Vì ô tô có dung tích bình nhiên liệu lớn sẽ đắt tiền, hai thành phố muốn chọn tuyến đường cho hai ô tô sao cho dung tích bình nhiên liệu lớn nhất của hai ô tô là nhỏ nhất. Ở mỗi thành phố đều có trạm xăng với nguồn cung cấp xăng vô hạn, do đó dung tích bình nhiên liệu mà một ô tô cần bằng mức tiêu thụ xăng lớn nhất trong tất cả các con đường mà ô tô đó đi qua.

Chi tiết cài đặt

Bạn phải cài đặt hai hàm có chữ ký C++ chính xác như sau:

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W);

int getMinimumFuelCapacity(int X, int Y);

Hàm init

Hàm init được trình chấm gọi đúng một lần trước mọi lời gọi getMinimumFuelCapacity.

• N: số lượng thành phố.
• M: số lượng con đường.
• U: mảng gồm \(M\) số nguyên biểu diễn đầu mút thứ nhất của các con đường.
• V: mảng gồm \(M\) số nguyên biểu diễn đầu mút thứ hai của các con đường.
• W: mảng gồm \(M\) số nguyên biểu diễn mức tiêu thụ xăng của các con đường.
• Hàm không trả về giá trị.

Hàm getMinimumFuelCapacity

Hàm getMinimumFuelCapacity được trình chấm gọi đúng \(Q\) lần.

• X: thành phố thứ nhất.
• Y: thành phố thứ hai.
• Hàm phải trả về một số nguyên biểu diễn giá trị nhỏ nhất có thể của dung tích bình nhiên liệu lớn nhất trong hai ô tô, sao cho một người đại diện từ thành phố \(X\) có thể đến thành phố \(Y\) và một người đại diện từ thành phố \(Y\) có thể đến thành phố \(X\) theo các quy tắc đã nêu; trả về \(-1\) nếu không tồn tại cách thực hiện.

Ví dụ

5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

3
10
4

Trong ví dụ này, \(N=5\), \(M=6\), \(U=[0,0,1,1,1,2]\), \(V=[1,2,2,3,4,3]\), \(W=[4,4,1,2,10,3]\), \(Q=3\), \(X=[1,2,0]\) và \(Y=[2,4,1]\). Ví dụ được minh họa bằng hình dưới đây:

{{asset:apio20swap/example-1.png}}

Trình chấm gọi init(5, 6, [0, 0, 1, 1, 1, 2], [1, 2, 2, 3, 4, 3], [4, 4, 1, 2, 10, 3]). Sau đó, trình chấm gọi:

• getMinimumFuelCapacity(1, 2): đầu tiên, ô tô ở thành phố \(1\) có thể đi đến thành phố \(3\). Tiếp theo, ô tô ở thành phố \(2\) có thể đi đến thành phố \(1\), đồng thời ô tô ở thành phố \(3\) có thể đi đến thành phố \(2\). Do đó, dung tích bình nhiên liệu lớn nhất của hai ô tô là \(3\) đơn vị nhiên liệu, cần để đi từ thành phố \(3\) đến thành phố \(2\). Không có tuyến đường nào cho phép dung tích bình nhiên liệu nhỏ hơn, do đó hàm trả về \(3\).
• getMinimumFuelCapacity(2, 4): bất kỳ ô tô nào đi đến hoặc đi từ thành phố \(4\) đều cần dung tích bình nhiên liệu \(10\) đơn vị, do đó hàm trả về \(10\).
• getMinimumFuelCapacity(0, 1): hàm trả về \(4\).

3 2
0 1 5
0 2 5
1
1 2

-1

Trong ví dụ này, \(N=3\), \(M=2\), \(U=[0,0]\), \(V=[1,2]\), \(W=[5,5]\), \(Q=1\), \(X=[1]\) và \(Y=[2]\). Ví dụ được minh họa bằng hình dưới đây:

{{asset:apio20swap/example-2.png}}

Trình chấm gọi init(3, 2, [0, 0], [1, 2], [5, 5]), sau đó gọi getMinimumFuelCapacity(1, 2). Không thể để ô tô ở thành phố \(1\) đi đến thành phố \(2\) mà không gặp ô tô kia tại một thời điểm nào đó, do đó hàm trả về \(-1\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(N-1 \le M \le 200\,000\).
• \(0 \le U[i] < V[i] < N\).
• Có nhiều nhất một con đường giữa mỗi cặp thành phố.
• Có thể đi lại giữa bất kỳ cặp thành phố nào thông qua các con đường.
• \(1 \le W[i] \le 10^9\).
• \(1 \le Q \le 200\,000\).
• \(0 \le X[j] < Y[j] < N\).

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu đầu vào theo định dạng sau:

N M
U[0] V[0] W[0]
U[1] V[1] W[1]
.
.
.
U[M-1] V[M-1] W[M-1]
Q
X[0] Y[0]
X[1] Y[1]
.
.
.
X[Q-1] Y[Q-1]

Với mỗi lời gọi getMinimumFuelCapacity, trình chấm mẫu in ra giá trị trả về bởi hàm.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2020: Swapping Cities.

Có \(N\) điểm tham quan trong công viên chủ đề lớn nhất ở Jakarta, được đánh số từ \(0\) đến \(N-1\). Các điểm tham quan này được nối với nhau bằng \(N-1\) con đường hai chiều sao cho giữa hai điểm tham quan bất kỳ có duy nhất một cách đi thông qua các con đường này. Các con đường được đánh số từ \(0\) đến \(N-2\). Con đường thứ \(i\) nối điểm tham quan \(A[i]\) và điểm tham quan \(B[i]\), và mất \(1\) giờ để đi bộ. Để tránh tắc đường, mỗi điểm tham quan là đầu mút của nhiều nhất \(3\) con đường.

Bạn muốn tạo một chuyến đi thăm tất cả các điểm tham quan, mỗi điểm đúng một lần. Việc phải đi qua nhiều con đường để di chuyển từ điểm tham quan này đến một điểm tham quan khác thì buồn chán. Vì vậy, bạn muốn tạo một chuyến tham quan vui vẻ bằng cách xếp thứ tự các điểm tham quan sao cho thời gian cần để di chuyển đến điểm tham quan tiếp theo không lớn hơn thời gian cần để di chuyển đến điểm tham quan trước đó. Nói cách khác, bạn muốn tìm một dãy \(P[0],P[1],\ldots,P[N-1]\) chứa tất cả các số nguyên từ \(0\) đến \(N-1\), mỗi số đúng một lần, sao cho thời gian cần để di chuyển từ điểm tham quan \(P[i]\) tới điểm tham quan \(P[i+1]\) không lớn hơn thời gian cần để di chuyển từ điểm tham quan \(P[i-1]\) tới điểm tham quan \(P[i]\), với mọi \(0<i<N-1\).

Bạn không có bản đồ đầy đủ của các điểm tham quan. Vì vậy, bạn phải hỏi trung tâm thông tin một số câu hỏi để có thể tạo được chuyến tham quan vui vẻ. Bạn có thể hỏi tối đa \(Q\) câu hỏi, mỗi câu hỏi có hai tham số \(X\) và \(Y\), trong đó \(0 \le X,Y < N\). Mỗi câu hỏi thuộc một trong hai dạng sau:

• Cần bao nhiêu giờ để đi từ điểm tham quan \(X\) đến điểm tham quan \(Y\)? Đặc biệt, nếu \(X=Y\) thì câu trả lời là \(0\).
• Có bao nhiêu điểm tham quan \(Z\) mà đường đi từ điểm tham quan \(X\) đến điểm tham quan \(Z\) phải đi qua điểm tham quan \(Y\)? Điểm tham quan \(Y\) cũng được tính. Đặc biệt, nếu \(X=Y\) thì câu trả lời là \(N\).

Chi tiết cài đặt

Bạn phải cài đặt hàm createFunTour. Hàm này được phép gọi hai hàm hoursRequired và attractionsBehind của trình chấm. Các chữ ký C++ chính xác là:

int hoursRequired(int X, int Y);

int attractionsBehind(int X, int Y);

std::vector<int> createFunTour(int N, int Q);

Hàm thí sinh cài đặt: createFunTour

Hàm createFunTour được trình chấm gọi đúng một lần.

• N: số điểm tham quan.
• Q: số lượng tối đa các câu hỏi.
• Hàm phải trả về một mảng gồm đúng \(N\) số nguyên, biểu diễn một hoán vị của các điểm tham quan trong chuyến đi vui vẻ.
• Tổng số lần gọi hoursRequired và attractionsBehind không được vượt quá \(Q\).

Hàm của trình chấm: hoursRequired

• X: điểm tham quan thứ nhất.
• Y: điểm tham quan thứ hai.
• Hàm trả về một số nguyên biểu diễn số giờ cần để đi từ điểm tham quan \(X\) đến điểm tham quan \(Y\).
• Đặc biệt, nếu \(X=Y\) thì hàm trả về \(0\).
• Nếu một trong hai giá trị \(X\) hoặc \(Y\) không nằm trong khoảng từ \(0\) đến \(N-1\), bài làm nhận kết quả WA.

Hàm của trình chấm: attractionsBehind

• X: điểm tham quan thứ nhất.
• Y: điểm tham quan thứ hai.
• Hàm trả về một số nguyên biểu diễn số lượng điểm tham quan \(Z\) mà đường đi từ điểm tham quan \(X\) đến điểm tham quan \(Z\) phải đi qua điểm tham quan \(Y\); điểm tham quan \(Y\) cũng được tính.
• Đặc biệt, nếu \(X=Y\) thì hàm trả về \(N\).
• Nếu một trong hai giá trị \(X\) hoặc \(Y\) không nằm trong khoảng từ \(0\) đến \(N-1\), bài làm nhận kết quả WA.

Ví dụ

7 400000
0 1
0 5
0 6
1 2
1 4
2 3

3 6 4 5 2 0 1

Trong ví dụ này, \(N=7\), \(Q=400\,000\), \(A=[0,0,0,1,1,2]\) và \(B=[1,5,6,2,4,3]\). Ví dụ được minh họa bằng hình dưới đây:

{{asset:apio20fun/example.png}}

Trình chấm gọi createFunTour(7, 400000).

• Nếu thí sinh gọi hoursRequired(3, 5), hàm trả về \(4\).
• Nếu thí sinh gọi hoursRequired(5, 4), hàm trả về \(3\).
• Nếu thí sinh gọi attractionsBehind(5, 1), hàm trả về \(4\). Đường đi từ điểm tham quan \(5\) đến mỗi điểm tham quan \(1\), \(2\), \(3\), \(4\) đều phải đi qua điểm tham quan \(1\).
• Nếu thí sinh gọi attractionsBehind(1, 5), hàm trả về \(1\).
• Thí sinh có thể trả về \([3,6,4,5,2,0,1]\) vì số giờ cần thiết để đi đến điểm tham quan tiếp theo theo thứ tự trên là \([4,3,3,3,2,1]\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(Q=400\,000\).
• Có thể di chuyển giữa bất kỳ cặp điểm tham quan nào thông qua các con đường trên.
• Mỗi điểm tham quan là đầu mút của không quá \(3\) con đường.

Phân nhóm

1. Đường đi từ điểm tham quan \(T\) đến điểm tham quan \(j\) phải đi qua điểm tham quan \(i\) khi và chỉ khi \(L[i] \le j \le R[i]\).
2. Nếu \(L[i]<i\), có đúng một điểm tham quan \(X\) sao cho \(L[i] \le X<i\) và có một con đường nối \(i\) với \(X\).
3. Nếu \(i<R[i]\), có đúng một điểm tham quan \(Y\) sao cho \(i<Y \le R[i]\) và có một con đường nối \(i\) với \(Y\). |
   | 5 | 34 | Không có ràng buộc gì thêm. |

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu đầu vào theo định dạng sau:

N Q
A[0] B[0]
A[1] B[1]
.
.
.
A[N-2] B[N-2]

Trình chấm mẫu ghi các số nguyên trả về từ hàm createFunTour nếu hàm trả về đúng một mảng gồm \(N\) số nguyên biểu diễn một hoán vị của các điểm tham quan trong chuyến đi vui vẻ và tổng số lần gọi cả hai hàm hoursRequired và attractionsBehind không quá \(Q\). Ngược lại, trình chấm mẫu in ra một thông báo câu trả lời sai.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2020: Fun Tour.