USACO 2021 - US Open - Hạng Vàng

Liên hiệp Bò của Farmer John (UCFJ) đang cử một đoàn đại biểu tham dự Olympic Tin học Bò Quốc tế (IOI).

Có \(N\) con bò tham gia quá trình tuyển chọn (\(1\le N\le2\cdot10^5\)). Chúng đang đứng thành một hàng, và con bò thứ \(i\) thuộc giống \(b_i\).

Đoàn đại biểu sẽ là một đoạn liên tiếp gồm ít nhất hai con bò, tức các con bò \(l\ldots r\) với hai số nguyên \(l\) và \(r\) thỏa mãn \(1\le l<r\le N\). Hai con bò ở hai đầu đoạn được chọn làm “trưởng đoàn”. Để tránh xung đột trong cùng giống, mỗi trưởng đoàn phải thuộc một giống khác với tất cả thành viên còn lại của đoàn, bất kể thành viên đó có phải trưởng đoàn hay không.

Hãy giúp UCFJ xác định, vì lý do thuế, số cách chọn đoàn đại biểu tham dự IOI.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Dòng thứ hai chứa \(N\) số nguyên \(b_1,b_2,\ldots,b_N\), mỗi số thuộc đoạn \([1,N]\).

Dữ liệu ra

In số đoàn đại biểu có thể chọn trên một dòng.

Lưu ý rằng do các số nguyên trong bài có thể rất lớn, bạn có thể cần dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++.

Phân nhóm

• Các test 1-3 thỏa mãn \(N\le100\).
• Các test 4-8 thỏa mãn \(N\le5000\).
• Các test 9-20 không có ràng buộc bổ sung.

Ví dụ

7
1 2 3 4 3 2 5

13

Mỗi đoàn đại biểu tương ứng với một trong các cặp trưởng đoàn sau:

Nguồn

USACO 2021 US Open, Gold - United Cows of Farmer John: https://usaco.org/index.php?page=viewproblem2&cpid=1137

Tác giả: Benjamin Qi.

Bessie đang ở trong một mạng lưới gồm \(N\) đỉnh (\(2\le N\le10^5\)) được đánh số \(1\ldots N\) và \(2N\) cổng được đánh số \(1\ldots2N\). Mỗi cổng nối hai đỉnh phân biệt \(u\) và \(v\) (\(u\ne v\)). Nhiều cổng có thể nối cùng một cặp đỉnh.

Mỗi đỉnh \(v\) kề với bốn cổng phân biệt. Danh sách các cổng kề với \(v\) là \(p_v=[p_{v,1},p_{v,2},p_{v,3},p_{v,4}]\).

Vị trí hiện tại của bạn được biểu diễn bằng cặp có thứ tự \((\text{\u0111ỉnh hiện tại},\text{cổng hiện tại})\), tức một cặp \((v,p_{v,i})\) với \(1\le v\le N\) và \(1\le i\le4\). Bạn có thể dùng một trong hai thao tác sau để thay đổi vị trí hiện tại:

1. Thay đổi đỉnh hiện tại bằng cách đi qua cổng hiện tại.
2. Chuyển cổng hiện tại. Tại mỗi đỉnh, hai cổng đầu tiên trong danh sách được ghép thành một cặp, và hai cổng cuối cũng cũng được ghép thành một cặp. Cụ thể, nếu vị trí hiện tại là \((v,p_{v,2})\) thì bạn có thể chuyển sang cổng \((v,p_{v,1})\) và ngược lại. Tương tự, bạn có thể chuyển qua lại giữa \((v,p_{v,3})\) và \((v,p_{v,4})\). Không được phép chuyển theo bất kỳ cách nào khác; chẳng hạn, không thể chuyển từ \(p_{v,2}\) sang \(p_{v,4}\).

Có tổng cộng \(4N\) vị trí phân biệt. Đáng tiếc là có thể không phải mọi vị trí đều đến được từ mọi vị trí khác bằng một chuỗi thao tác. Vì vậy, với chi phí \(c_v\) moonie (\(1\le c_v\le1000\)), bạn có thể hoán vị danh sách cổng kề với \(v\) theo bất kỳ thứ tự nào. Sau đó, hai cổng đầu tiên trong danh sách mới được ghép với nhau, và hai cổng cuối cũng cũng được ghép với nhau.

Ví dụ, nếu bạn hoán vị các cổng kề với \(v\) thành thứ tự \([p_{v,3},p_{v,1},p_{v,2},p_{v,4}]\), thì tại đỉnh \(v\):

• có thể chuyển qua lại giữa \(p_{v,1}\) và \(p_{v,3}\);
• có thể chuyển qua lại giữa \(p_{v,2}\) và \(p_{v,4}\);
• không còn có thể chuyển qua lại giữa \(p_{v,1}\) và \(p_{v,2}\), hay giữa \(p_{v,3}\) và \(p_{v,4}\).

Hãy tính tổng số moonie nhỏ nhất cần dùng để sửa đổi mạng sao cho có thể đến mọi vị trí từ mọi vị trí khác. Dữ liệu bảo đảm tồn tại ít nhất một cách sửa đổi mạng hợp lệ.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo mô tả một đỉnh. Dòng \(v+1\) chứa năm số nguyên cách nhau bởi dấu cách \(c_v,p_{v,1},p_{v,2},p_{v,3},p_{v,4}\).

Với mỗi \(v\), bốn giá trị \(p_{v,1},p_{v,2},p_{v,3},p_{v,4}\) đều phân biệt. Mỗi cổng xuất hiện trong danh sách kề của đúng hai đỉnh.

Dữ liệu ra

In trên một dòng tổng số moonie nhỏ nhất cần dùng để sửa đổi mạng sao cho có thể đến mọi vị trí từ mọi vị trí khác.

Phân nhóm

• Trong các test 2-4, \(c_v=1\) với mọi \(v\).
• Các test 5-12 không có ràng buộc bổ sung.

Ví dụ

5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 5

13

Chỉ cần hoán vị danh sách kề của các đỉnh \(1\) và \(4\). Việc này tốn tổng cộng \(c_1+c_4=13\) moonie. Ta có thể đặt \(p_1=[1,9,4,8]\) và \(p_4=[7,4,6,3]\).

Nguồn

USACO 2021 US Open, Gold - Portals: https://usaco.org/index.php?page=viewproblem2&cpid=1138

Tác giả: Benjamin Qi.

Bessie có \(N\) điểm phân biệt yêu thích trên lưới hai chiều (\(3\le N\le40\)), trong đó không có ba điểm nào thẳng hàng. Với mỗi \(1\le i\le N\), điểm thứ \(i\) được biểu diễn bằng hai số nguyên \(x_i\) và \(y_i\) (\(0\le x_i,y_i\le10^4\)).

Bessie vẽ một số đoạn thẳng giữa các điểm như sau:

1. Cô chọn một hoán vị \(p_1,p_2,\ldots,p_N\) của \(N\) điểm.
2. Cô vẽ các đoạn thẳng nối \(p_1\) với \(p_2\), \(p_2\) với \(p_3\), và \(p_3\) với \(p_1\).
3. Sau đó, lần lượt với mỗi số nguyên \(i\) từ \(4\) đến \(N\), cô vẽ đoạn thẳng từ \(p_i\) đến \(p_j\) với mọi \(j<i\) sao cho đoạn thẳng đó không giao với bất kỳ đoạn thẳng nào đã vẽ trước đó, ngoại trừ tại các đầu mút.

Bessie nhận thấy với mỗi \(i\), cô đã vẽ đúng ba đoạn thẳng mới. Hãy tính số hoán vị mà Bessie có thể đã chọn ở bước 1 và thỏa mãn tính chất này, lấy phần dư theo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i\) và \(y_i\) cách nhau bởi dấu cách.

Dữ liệu ra

In số hoán vị lấy phần dư theo \(10^9+7\).

Phân nhóm

• Các test 1-6 thỏa mãn \(N\le8\).
• Các test 7-20 không có ràng buộc bổ sung.

Ví dụ

4
0 0
0 4
1 1
1 2

0

4
0 0
0 4
4 0
1 1

24

5
0 0
0 4
4 0
1 1
1 2

96

Giải thích ví dụ 1. Không có hoán vị nào thỏa mãn.

Giải thích ví dụ 2. Mọi hoán vị đều thỏa mãn.

Giải thích ví dụ 3. Một hoán vị thỏa mãn tính chất là \((0,0),(0,4),(4,0),(1,2),(1,1)\). Với hoán vị này:

1. Đầu tiên, Bessie vẽ các đoạn thẳng giữa mọi cặp điểm trong \((0,0),(0,4)\) và \((4,0)\).
2. Sau đó, cô vẽ các đoạn thẳng từ \((0,0)\), \((0,4)\) và \((4,0)\) đến \((1,2)\).
3. Cuối cùng, cô vẽ các đoạn thẳng từ \((1,2)\), \((4,0)\) và \((0,0)\) đến \((1,1)\).

Hình minh họa:

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_5fb5745a.png

Hoán vị không thỏa mãn tính chất nếu bốn điểm đầu tiên là \((0,0)\), \((1,1)\), \((1,2)\) và \((0,4)\) theo một thứ tự bất kỳ.

Nguồn

USACO 2021 US Open, Gold - Permutation: https://usaco.org/index.php?page=viewproblem2&cpid=1139

Tác giả: Benjamin Qi.