Google Code Jam 2014 - Round 1A

Shota là một nông dân và anh ấy đang gặp vấn đề. Anh ấy vừa chuyển đến một trang trại mới xây, nhưng hóa ra các ổ cắm điện không được cấu hình đúng cho tất cả các thiết bị của anh ấy. Là một nông dân hiện đại, Shota sở hữu rất nhiều điện thoại thông minh, máy tính xách tay và thậm chí cả một chiếc máy tính bảng cho con bò Wagyu yêu thích của mình. Tổng cộng, anh ấy có \(N\) thiết bị khác nhau.

Vì các thiết bị này có thông số kỹ thuật khác nhau và được sản xuất bởi nhiều công ty khác nhau, mỗi thiết bị yêu cầu một dòng điện khác nhau để sạc. Tương tự, mỗi ổ cắm trong nhà cung cấp một dòng điện cụ thể. Một dòng điện có thể được biểu diễn bằng một chuỗi các ký tự 0 và 1 có độ dài \(L\).

Shota muốn có thể sạc tất cả \(N\) thiết bị của mình cùng một lúc. Thật trùng hợp, có đúng \(N\) ổ cắm trong ngôi nhà mới của anh ấy. Để cấu hình dòng điện từ các ổ cắm, có một bảng điều khiển trung tâm với \(L\) công tắc. Công tắc thứ \(i\) sẽ đảo ngược bit thứ \(i\) của dòng điện từ mọi ổ cắm trong nhà. Ví dụ, nếu dòng điện từ các ổ cắm là:

Outlet 0: 10
Outlet 1: 01
Outlet 2: 11

Thì việc bật công tắc thứ hai sẽ cấu hình lại dòng điện thành:

Outlet 0: 11
Outlet 1: 00
Outlet 2: 10

Nếu Shota có một chiếc điện thoại thông minh cần dòng điện 11 để sạc, một chiếc máy tính bảng cần dòng điện 10 và một chiếc máy tính xách tay cần dòng điện 00, thì việc bật công tắc thứ hai sẽ khiến anh ấy rất hạnh phúc!

Misaki đã được Shota thuê để giúp giải quyết vấn đề này. Cô ấy đã đo dòng điện từ các ổ cắm trong nhà và nhận thấy rằng chúng đều khác nhau. Hãy quyết định xem Shota có thể sạc tất cả các thiết bị của mình cùng một lúc hay không, và nếu có thể, hãy tìm số lượng công tắc tối thiểu cần phải bật, vì các công tắc này rất lớn và nặng, Misaki không muốn bật nhiều hơn mức cần thiết.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). Tiếp theo là \(T\) bộ thử nghiệm. Mỗi bộ thử nghiệm gồm ba dòng:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(L\) cách nhau bởi dấu cách.
• Dòng thứ hai chứa \(N\) chuỗi độ dài \(L\) cách nhau bởi dấu cách, đại diện cho dòng điện ban đầu từ các ổ cắm.
• Dòng thứ ba cũng chứa \(N\) chuỗi độ dài \(L\) cách nhau bởi dấu cách, đại diện cho dòng điện yêu cầu bởi các thiết bị của Shota.

Dữ liệu ra

Với mỗi bộ thử nghiệm, xuất một dòng chứa Case #x: y, trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là số lượng công tắc tối thiểu cần bật để Shota có thể sạc tất cả các thiết bị của mình. Nếu không thể, y phải là chuỗi NOT POSSIBLE. Lưu ý rằng giám khảo không phân biệt chữ hoa chữ thường cho chuỗi này, nhưng chúng tôi khuyên bạn nên sao chép đúng chuỗi NOT POSSIBLE.

Ràng buộc

• \(1 \le T \le 100\).
• Ban đầu, không có hai ổ cắm nào có cùng dòng điện.
• Không có hai thiết bị nào yêu cầu cùng một dòng điện.

Phân nhóm

• Small dataset: \(1 \le N \le 10\); \(2 \le L \le 10\).
• Large dataset: \(1 \le N \le 150\); \(10 \le L \le 40\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
3 2
01 11 10
11 00 10
2 3
101 111
010 001
2 2
01 10
10 01

Case #1: 1
Case #2: NOT POSSIBLE
Case #3: 0

Outlet 0: 00
Outlet 1: 10
Outlet 2: 11

Nguồn

Google Code Jam 2014, Vòng 1A, bài Charging Chaos.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Một cây là một đồ thị liên thông không có chu trình.

Một cây có gốc là một cây trong đó một đỉnh đặc biệt được gọi là gốc. Nếu có một cạnh giữa \(X\) và \(Y\) trong một cây có gốc, ta nói \(Y\) là con của \(X\) nếu \(X\) gần gốc hơn \(Y\) (nói cách khác, đường đi ngắn nhất từ gốc đến \(X\) ngắn hơn đường đi ngắn nhất từ gốc đến \(Y\)).

Một cây nhị phân đầy đủ (full binary tree) là một cây có gốc mà mỗi nút có đúng 2 con hoặc 0 con.

Bạn được cho một cây \(G\) với \(N\) nút (được đánh số từ \(1\) đến \(N\)). Bạn được phép xóa một số nút. Khi một nút bị xóa, các cạnh nối với nút đó cũng bị xóa. Nhiệm vụ của bạn là xóa ít nút nhất có thể sao cho các nút còn lại tạo thành một cây nhị phân đầy đủ với một cách chọn gốc nào đó từ các nút còn lại.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test. Dòng đầu tiên của mỗi bộ test chứa một số nguyên duy nhất \(N\), số lượng nút trong cây. \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách: \(X_i\) \(Y_i\), cho biết \(G\) chứa một cạnh vô hướng giữa \(X_i\) và \(Y_i\).

Dữ liệu ra

Với mỗi bộ test, xuất một dòng chứa "Case #\(x\): \(y\)", trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là số lượng nút tối thiểu cần xóa khỏi \(G\) để tạo thành một cây nhị phân đầy đủ.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le X_i, Y_i \le N\).
• Mỗi bộ test sẽ tạo thành một cây liên thông hợp lệ.

Phân nhóm

• Small dataset: \(2 \le N \le 15\).
• Large dataset: \(2 \le N \le 1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
3
2 1
1 3
7
4 5
4 2
1 2
3 1
6 4
3 7
4
1 2
2 3
3 4

Case #1: 0
Case #2: 2
Case #3: 1

Nguồn

Google Code Jam 2014, Vòng 1A, bài Full Binary Tree.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

Một hoán vị kích thước \(N\) là một dãy gồm \(N\) số, mỗi số nằm trong khoảng từ \(0\) đến \(N-1\), trong đó mỗi số xuất hiện đúng một lần. Chúng có thể xuất hiện theo bất kỳ thứ tự nào.

Có rất nhiều (\(N!\) hoán vị, chính xác là vậy, nhưng điều đó không quan trọng trong bài toán này) hoán vị kích thước \(N\). Đôi khi chúng ta chỉ muốn chọn ngẫu nhiên một hoán vị, và tất nhiên chúng ta muốn chọn ngẫu nhiên một cách đều: mỗi hoán vị kích thước \(N\) nên có cùng xác suất được chọn.

Dưới đây là mã giả cho một trong những thuật toán khả thi để đạt được mục tiêu đó (chúng ta sẽ gọi nó là thuật toán tốt bên dưới):

for k in 0 .. N-1:
  a[k] = k
for k in 0 .. N-1:
  p = randint(k .. N-1)
  swap(a[k], a[p])

Trong đoạn mã trên, randint(a .. b) trả về một số nguyên ngẫu nhiên đều giữa \(a\) và \(b\), bao gồm cả hai đầu.

Nói cách khác, chúng ta bắt đầu với hoán vị đồng nhất: tất cả các số từ \(0\) đến \(N-1\) được viết theo thứ tự tăng dần. Sau đó, với mỗi \(k\) từ \(0\) đến \(N-1\), chúng ta chọn một số nguyên ngẫu nhiên đều độc lập \(p_k\) từ \(k\) đến \(N-1\), và tráo đổi phần tử tại vị trí \(k\) (tính từ 0) trong hoán vị của chúng ta với phần tử tại vị trí \(p_k\).

Ví dụ với \(N=4\). Chúng ta bắt đầu với hoán vị đồng nhất:
0 1 2 3

Bây giờ \(k=0\), và chúng ta chọn một \(p_0\) ngẫu nhiên từ \(0\) đến \(3\). Giả sử chúng ta chọn \(2\). Chúng ta tráo đổi phần tử thứ \(0\) và thứ \(2\), hoán vị trở thành:
2 1 0 3

Bây giờ \(k=1\), và chúng ta chọn một \(p_1\) ngẫu nhiên từ \(1\) đến \(3\). Giả sử chúng ta lại chọn \(2\). Chúng ta tráo đổi phần tử thứ \(1\) và thứ \(2\), hoán vị trở thành:
2 0 1 3

Bây giờ \(k=2\), và chúng ta chọn một \(p_2\) ngẫu nhiên từ \(2\) đến \(3\). Giả sử chúng ta chọn \(3\). Chúng ta tráo đổi phần tử thứ \(2\) và thứ \(3\), hoán vị trở thành:
2 0 3 1

Bây giờ \(k=3\), và chúng ta chọn một \(p_3\) ngẫu nhiên từ \(3\) đến \(3\). Lựa chọn duy nhất là \(3\). Chúng ta tráo đổi phần tử thứ \(3\) với chính nó, nghĩa là hoán vị không đổi:
2 0 3 1

Quá trình kết thúc, và đây là hoán vị ngẫu nhiên của chúng ta.

Có nhiều thuật toán khác cũng tạo ra hoán vị ngẫu nhiên đều. Tuy nhiên, cũng có nhiều thuật toán trông rất giống thuật toán này nhưng không đều — một số hoán vị có khả năng được tạo ra cao hơn những hoán vị khác.

Dưới đây là một thuật toán xấu thuộc loại này. Lấy thuật toán tốt ở trên, nhưng ở mỗi bước, thay vì chọn \(p_k\) ngẫu nhiên từ \(k\) đến \(N-1\), chúng ta chọn nó ngẫu nhiên từ \(0\) đến \(N-1\). Đây là một thay đổi rất nhỏ, nhưng giờ đây một số hoán vị có khả năng xuất hiện cao hơn những hoán vị khác!

Mã giả cho thuật toán này (chúng ta sẽ gọi là thuật toán xấu):

for k in 0 .. N-1:
  a[k] = k
for k in 0 .. N-1:
  p = randint(0 .. N-1)
  swap(a[k], a[p])

Trong mỗi trường hợp kiểm thử, bạn sẽ được cung cấp một hoán vị được tạo ra theo cách sau: đầu tiên, chúng tôi chọn thuật toán tốt hoặc xấu với xác suất \(50\%\) mỗi loại. Sau đó, chúng tôi tạo một hoán vị bằng thuật toán đã chọn. Bạn có thể đoán thuật toán nào đã được chọn chỉ bằng cách nhìn vào hoán vị không?

Giải bài toán này

Bài toán này hơi bất thường đối với Code Jam. Bạn sẽ được cung cấp \(T = 120\) hoán vị, mỗi hoán vị có \(N = 1000\) số, và bạn nên in ra câu trả lời cho mỗi hoán vị. Tuy nhiên, bạn không cần phải trả lời đúng tất cả! Lời giải của bạn sẽ được coi là đúng nếu bạn trả lời đúng ít nhất \(G = 109\) trường hợp. Tuy nhiên, bạn phải tuân thủ định dạng đầu ra cho mọi trường hợp. Điều duy nhất có thể sai là tráo đổi GOOD thành BAD hoặc ngược lại; nhưng bạn vẫn phải in GOOD hoặc BAD cho mỗi trường hợp.

Đảm bảo rằng các hoán vị được tạo ra theo phương pháp trên và độc lập với nhau.

Vì bài toán có tính ngẫu nhiên, ngay cả lời giải tốt nhất cũng có thể không đạt được \(109\) dự đoán đúng cho một đầu vào nhất định. Do đó, bài toán này không có bộ dữ liệu Large, và chỉ có bộ Small mà bạn có thể thử lại nếu thấy mình không may mắn. Lưu ý rằng vẫn có hình phạt 4 phút cho các lần nộp sai nếu sau đó bạn giải được.

Trong kinh nghiệm của chúng tôi, việc bị sai do ngẫu nhiên đã xảy ra; vì vậy nếu bạn tin tưởng vào thuật toán của mình mà vẫn thất bại, thử lại cùng một lời giải có thể là một chiến thuật hợp lý.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\) (luôn là \(120\)). Mỗi bộ test gồm hai dòng: dòng đầu chứa số nguyên \(N\) (luôn là \(1000\)), dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách - hoán vị được tạo ra.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng "Case #\(x\): \(y\)", trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là "GOOD" hoặc "BAD".

Ràng buộc

• \(T = 120\)
• \(G = 109\)
• \(N = 1000\)
• Mỗi số trong hoán vị từ \(0\) đến \(N-1\), và mỗi số xuất hiện đúng một lần.

Phân nhóm

Đề bài sử dụng một tập dữ liệu duy nhất với các giới hạn nêu trên.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
3
0 1 2
3
2 0 1

Case #1: BAD
Case #2: GOOD

Nguồn

Google Code Jam 2014, Vòng 1A, bài Proper Shuffle.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.