Phân tích: Magic Trick

Trong cách sắp xếp đầu tiên, khi người tình nguyện nói với nhà ảo thuật hàng chứa lá bài của cô ấy, nhà ảo thuật có thể thấy một tập hợp gồm bốn lá bài trong hàng đó. Tương tự, trong cách sắp xếp thứ hai, nhà ảo thuật có thể thấy một tập hợp bốn lá bài khác trong hàng được chọn.

Do đó, sau khi nghe hai câu trả lời của người tình nguyện, nhà ảo thuật sẽ có hai tập hợp các lá bài:

• Tập hợp thứ nhất gồm bốn lá bài nằm ở hàng được chọn trong cách sắp xếp thứ nhất, và
• Tập hợp thứ hai gồm bốn lá bài nằm ở hàng được chọn trong cách sắp xếp thứ hai.

Để biết người tình nguyện đã chọn lá bài nào, nhà ảo thuật phải tìm được đúng một lá bài nằm trong cả hai tập hợp (tức là kích thước giao của hai tập hợp phải bằng một). Nếu có nhiều hơn một lá bài nằm trong cả hai tập hợp (tức là kích thước giao lớn hơn một), điều đó có nghĩa là nhà ảo thuật không thể xác định được lá bài nào người tình nguyện đã chọn vì có nhiều hơn một lá bài khả thi (nhà ảo thuật đã làm không tốt). Nếu không có lá bài nào trong tập hợp thứ nhất nằm trong tập hợp thứ hai (tức là kích thước giao bằng không), thì không có lá bài nào phù hợp với câu trả lời của người tình nguyện (người tình nguyện đã gian lận).

Dữ liệu mẫu bao gồm tất cả ba trường hợp có thể xảy ra:

Trong Case #1, hai tập hợp là {5, 6, 7, 8} và {9, 10, 7, 12}. Có đúng một lá bài (đó là lá bài 7) nằm trong cả hai tập hợp, và do đó lá bài người tình nguyện chọn phải là 7.

Trong Case #2, hai tập hợp là {5, 6, 7, 8} và {5, 6, 7, 8}. Lá bài được chọn bởi người tình nguyện có thể là bất kỳ lá nào trong số {5, 6, 7, 8} vì tất cả chúng đều nằm trong cả hai tập hợp. Nhà ảo thuật tồi! (Bad magician!)

Cuối cùng, trong Case #3, hai tập hợp là {5, 6, 7, 8} và {9, 10, 11, 12}. Không có lá bài nào trong tập hợp thứ nhất nằm trong tập hợp thứ hai. Người tình nguyện chắc chắn đã gian lận! (Volunteer cheated!)

Dựa trên phân tích chính thức của Google Code Jam.