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

\(N\) con bò của Farmer John (\(1 \le N \le 100\,000\)) đang đứng tại nhiều vị trí khác nhau dọc theo một hàng rào dài một chiều. Con bò thứ \(i\) đứng tại vị trí \(x_i\) (một số nguyên trong đoạn từ \(0\) đến \(1\,000\,000\,000\)) và thuộc giống \(b_i\) (một số nguyên trong đoạn từ \(1\) đến \(8\)). Không có hai con bò nào đứng cùng một vị trí.

Farmer John muốn chụp ảnh một đoạn liên tiếp gồm các con bò để mang đến hội chợ hạt, nhưng ông muốn tất cả các giống xuất hiện trong ảnh được đại diện một cách công bằng. Vì vậy, với những giống có mặt trong ảnh, ông muốn số bò của mỗi giống đều bằng nhau. Chẳng hạn, một bức ảnh có \(27\) con thuộc mỗi giống \(1\) và \(3\) là hợp lệ; một bức ảnh có \(27\) con thuộc mỗi giống \(1\), \(3\) và \(4\) cũng hợp lệ; nhưng một bức ảnh có \(9\) con giống \(1\) và \(10\) con giống \(3\) thì không hợp lệ. Farmer John còn muốn trong ảnh có ít nhất \(K\) giống (\(K \ge 2\)) trong tổng số \(8\) giống.

Hãy giúp Farmer John chụp một bức ảnh công bằng bằng cách tìm kích thước lớn nhất của một bức ảnh thỏa mãn các điều kiện trên. Kích thước của bức ảnh là hiệu giữa vị trí lớn nhất và vị trí nhỏ nhất của các con bò trong ảnh. Nếu không có bức ảnh nào thỏa mãn các điều kiện, hãy in ra \(-1\).

Dữ liệu vào

• Dòng đầu tiên chứa \(N\) và \(K\), cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo, mỗi dòng mô tả một con bò bằng hai số nguyên cách nhau bởi một dấu cách: vị trí \(x(i)\) và chỉ số giống của nó.

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(K \ge 2\) và có tổng cộng \(8\) giống.
• \(0 \le x_i \le 1\,000\,000\,000\).
• \(1 \le b_i \le 8\).
• Không có hai con bò nào đứng cùng một vị trí.

Dữ liệu ra

• In ra một số nguyên duy nhất là kích thước lớn nhất của một bức ảnh công bằng. Nếu không có bức ảnh như vậy, in ra \(-1\).

Ví dụ

9 2
1 1
5 1
6 1
9 1
100 1
2 2
7 2
3 3
8 3

6

Chỉ số giống: 1 2 3 - 1 1 2 3 1  - ...  -   1
Vị trí:       1 2 3 4 5 6 7 8 9 10 ... 99 100

Nguồn

USACO 2014 US Open, Gold — Problem 1: Fair Photography

Tác giả đề: Brian Dean, 2014.

Những cô bò của Farmer John muốn tổ chức một bữa tiệc khiêu vũ trong chuồng, kèm theo một màn trình diễn ánh sáng laser. Không may, chiếc laser duy nhất còn hoạt động mà chúng tìm được lại nằm cách chuồng rất xa và quá nặng để di chuyển, nên chúng dự định dùng một dãy gương để chuyển hướng tia laser tới chuồng.

Trên sơ đồ trang trại, laser nằm tại vị trí \((0,0)\) và chiếu về phía bắc, tức theo chiều dương của trục \(y\); chuồng nằm tại \((Bx,By)\). Có thể coi cả laser và chuồng là các điểm trên mặt phẳng hai chiều. Đã có \(N\) con bò (\(1 \le N \le 100\,000\)) đứng rải rác khắp trang trại, mỗi con cầm một chiếc gương tạo với các trục tọa độ góc \(45\) độ. Chẳng hạn, một chiếc gương có hướng \ sẽ phản xạ một tia sáng đi vào từ phía dưới sang bên trái. Các gương cũng được coi là nằm tại các điểm trên mặt phẳng hai chiều.

Ngay trước khi nhấn chiếc nút lớn màu đỏ để kích hoạt laser, Bessie nhận ra một thiếu sót nghiêm trọng trong kế hoạch: với cấu hình gương hiện tại, tia laser không thể chiếu tới chuồng! Vì vậy, cô dự định chạy ra cánh đồng và cầm thêm đúng một chiếc gương, cũng được đặt nghiêng một góc \(45\) độ, để chuyển hướng tia laser vào chuồng. Hãy đếm số vị trí trên cánh đồng mà Bessie có thể đứng để đạt được mục tiêu này.

Mọi tọa độ đều là số nguyên nằm trong đoạn từ \(-1\,000\,000\,000\) đến \(1\,000\,000\,000\). Bảo đảm mọi chiếc gương có thể được đặt thêm cũng nằm trong phạm vi này. Những cô bò vận hành laser yêu cầu tia sáng không bao giờ quay lại \((0,0)\) sau khi rời vị trí này; với cấu hình gương ban đầu, bảo đảm điều đó không xảy ra. Không có hai con bò nào đứng cùng một điểm, và Bessie không được đứng cùng vị trí với một con bò đã có mặt.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(N\), \(Bx\) và \(By\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) mô tả chiếc gương thứ \(i\) bằng ba phần: tọa độ \((x,y)\) và hướng của gương, là \ hoặc /.

Ràng buộc

• \(1 \le N \le 100\,000\).
• Mọi tọa độ là số nguyên trong đoạn từ \(-1\,000\,000\,000\) đến \(1\,000\,000\,000\).
• Không có hai con bò nào đứng cùng một điểm; Bessie không được đứng tại vị trí của một con bò đã có mặt.
• Tia sáng không được quay lại \((0,0)\) sau khi rời vị trí này; với cấu hình gương ban đầu, bảo đảm điều đó không xảy ra.

Dữ liệu ra

• In ra một số nguyên duy nhất là số vị trí mà Bessie có thể đứng để chuyển hướng tia laser tới chuồng.

Ví dụ

4 1 2
-2 1 \
2 1 /
2 2 \
-2 2 /

2

Nguồn

USACO 2014 US Open, Gold — Problem 2: Cow Optics

Tác giả đề: Brian Dean, 2014.

Những cô bò cứ liên tục gây rắc rối vì lấy máy kéo của Farmer John đi chơi, nên ông đã giấu chìa khóa máy kéo trong một chiếc két sắt mới rất tinh xảo đặt tại văn phòng. Không hề nản lòng, những cô bò quyết tâm tìm cách phá khóa chiếc két này.

Két sắt được bảo vệ bởi một hệ thống mật mã khá phức tạp. Hệ thống nhập mật mã được bố trí dưới dạng một cây có gốc gồm \(N\) đỉnh (\(1 \le N \le 20\,000\)), mỗi đỉnh cần được gán một chữ số từ \(0\) đến \(9\). Các đỉnh được đánh số từ \(0\) đến \(N-1\).

Thông tin duy nhất những cô bò có được là một số dãy độ dài \(5\) không xuất hiện dọc theo những đường đi cụ thể hướng lên trên cây.

Ví dụ, giả sử cây có dạng sau và có gốc tại \(A\):

A <- B <- C <- D <- E
               ^
               |
               F

Những cô bò có thể biết rằng dãy 01234 không xuất hiện khi bắt đầu tại \(F\), và dãy 91234 không xuất hiện khi bắt đầu tại \(E\). Thông tin này loại trừ \(19\) mật mã: tất cả các mật mã có dạng

4 <- 3 <- 2 <- 1 <- *
               ^
               |
               0

hoặc

4 <- 3 <- 2 <- 1 <- 9
               ^
               |
               *

Số mật mã bị loại là \(19\) sau khi tính đến việc mật mã

4 <- 3 <- 2 <- 1 <- 9
               ^
               |
               0

xuất hiện hai lần.

Cho \(M\) dãy độ dài \(5\) (\(1 \le M \le 50\,000\)) cùng với đỉnh bắt đầu tương ứng của chúng trên cây, hãy giúp những cô bò xác định có bao nhiêu mật mã đã bị loại trừ. Hãy tính kết quả theo modulo \(1234567\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi một dấu cách.
• Các dòng từ \(2\) đến \(N\): dòng thứ \(i+1\) chứa một số nguyên \(p(i)\), là cha của đỉnh \(i\) trên cây, với \(0 \le p(i) < i\).
• Các dòng từ \(N+1\) đến \(N+M\): dòng thứ \(N+i\) mô tả dãy thứ \(i\) được biết là không xuất hiện trong mật mã. Dòng này chứa \(v(i)\) và \(s(i)\) cách nhau bởi một dấu cách, trong đó \(v(i)\) là đỉnh bắt đầu của dãy, còn \(s(i)\) là một xâu gồm \(5\) chữ số được biết là không xuất hiện khi bắt đầu tại \(v(i)\) và đi dần lên trên cây. Bảo đảm gốc cây cách \(v(i)\) ít nhất \(4\) bước theo hướng đi lên.

Ràng buộc

• \(1 \le N \le 20\,000\).
• \(1 \le M \le 50\,000\).
• \(0 \le p(i) < i\).
• Mỗi \(s(i)\) là một xâu gồm đúng \(5\) chữ số.
• Gốc cây cách mỗi \(v(i)\) ít nhất \(4\) bước theo hướng đi lên.

Dữ liệu ra

• In ra một số nguyên duy nhất là số cấu hình mật mã bị loại trừ, theo modulo \(1234567\).

Ví dụ

6 2
0
1
2
3
3
4 01234
5 91234

19

Nguồn

USACO 2014 US Open, Gold — Problem 3: Code Breaking

Tác giả đề: Jacob Steinhardt, 2014.