| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Bovine Genomics | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Modern Art 2 | 100 (p) | 4.0s | 512M |
Farmer John sở hữu \(N\) con bò có đốm và \(N\) con bò không có đốm. Vừa hoàn thành một khóa học về di truyền học ở bò, ông tin rằng các đốm trên bò của mình là do những đột biến trong hệ gen của bò.
Farmer John phải bỏ ra một khoản chi phí rất lớn để giải trình tự hệ gen của đàn bò. Mỗi hệ gen là một chuỗi độ dài \(M\) được tạo bởi bốn ký tự A, C, G và T. Khi căn chỉnh hệ gen của các con bò, ông thu được một bảng như sau, minh họa với \(N=3\) và \(M=8\):
Vị trí: 1 2 3 4 5 6 7 8
Bò đốm 1: A A T C C C A T
Bò đốm 2: A C T T G C A A
Bò đốm 3: G G T C G C A A
Bò không đốm 1: A C T C C C A G
Bò không đốm 2: A C T C G C A T
Bò không đốm 3: A C T T C C A T
Quan sát kỹ bảng này, ông phỏng đoán rằng đoạn trình tự từ vị trí \(2\) đến vị trí \(5\) đủ để giải thích đặc điểm có đốm. Nghĩa là chỉ cần nhìn vào các ký tự tại những vị trí này (tức các vị trí \(2 \ldots 5\)), Farmer John có thể dự đoán con bò nào có đốm và con bò nào không có đốm. Chẳng hạn, nếu thấy các ký tự GTCG tại những vị trí này, ông biết con bò chắc chắn có đốm.
Hãy giúp FJ tìm độ dài của đoạn vị trí liên tiếp ngắn nhất có thể giải thích đặc điểm có đốm.
Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 500\)) và \(M\) (\(3 \leq M \leq 500\)). \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi gồm \(M\) ký tự, mô tả hệ gen của các con bò đốm. \(N\) dòng cuối mô tả hệ gen của các con bò không đốm. Không có con bò đốm nào có hệ gen hoàn toàn giống một con bò không đốm.
In độ dài của đoạn vị trí liên tiếp ngắn nhất đủ để giải thích đặc điểm có đốm. Một đoạn vị trí giải thích được đặc điểm có đốm nếu chỉ bằng cách quan sát các vị trí đó trong hệ gen, ta có thể dự đoán hoàn toàn chính xác đặc điểm có đốm trong quần thể bò của Farmer John.
Ví dụ 1
3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT4USACO 2017 US Open Contest, Gold — Bovine Genomics. Tác giả đề: Brian Dean.
Sau khi chán các tác phẩm nghệ thuật hai chiều thông thường (và cũng bực bội vì người khác sao chép tác phẩm của mình), nữ họa sĩ bò vĩ đại Picowso đã quyết định chuyển sang phong cách một chiều tối giản hơn.
Mặc dù giờ đây các bức vẽ của cô có thể được mô tả bằng một mảng màu một chiều độ dài \(N\) (\(1 \leq N \leq 100\,000\)), phong cách vẽ của cô vẫn không thay đổi: cô bắt đầu với một bức vẽ trống rồi phủ lên đó lần lượt các "hình chữ nhật" bằng sơn; trong trường hợp một chiều này, chúng đơn giản là các đoạn. Cô sử dụng mỗi màu từ \(1 \ldots N\) đúng một lần, mặc dù cũng như trước đây, đến cuối cùng một số màu có thể bị che phủ hoàn toàn.
Picowso vô cùng thất vọng khi đối thủ Moonet dường như đã tìm ra cách sao chép ngay cả những bức vẽ một chiều này bằng một chiến lược tương tự như trong bài trước: Moonet sẽ tô một tập hợp các đoạn đôi một không giao nhau, đợi chúng khô, sau đó tô một tập hợp các đoạn đôi một không giao nhau khác, và cứ tiếp tục như vậy. Trong toàn bộ quá trình, Moonet chỉ có thể tô nhiều nhất một đoạn bằng mỗi màu. Hãy tính số lượt như vậy cần thiết để Moonet sao chép một bức vẽ một chiều cho trước của Picowso.
Dòng đầu tiên chứa \(N\). \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên trong khoảng \(0 \ldots N\), biểu thị màu của từng ô trong bức vẽ một chiều (\(0\) là một ô trống).
In số lượt ít nhất cần thiết để sao chép bức vẽ, hoặc \(-1\) nếu đây không thể là một tác phẩm đích thực của Picowso (tức là cô không thể vẽ nó bằng cách phủ lần lượt các đoạn, mỗi màu một đoạn).
Ví dụ 1
7
0
1
4
5
1
3
32Trong ví dụ này, đoạn màu \(1\) phải được tô ở một lượt sớm hơn các đoạn màu \(4\) và \(5\), vì vậy cần ít nhất hai lượt.
USACO 2017 US Open Contest, Gold — Modern Art 2. Tác giả đề: Brian Dean.