Codechef March Long Challenge 2020 - Division 2

Long Challenge đợt này có rất nhiều điều để nói. Nhìn chung mình solve được 3 bài 1 2 3 + 1 task bài 4, tổng cộng là 330 điểm. Trong lúc đợi editorial task bài 4, mình tranh thủ viết cho 3 bài mình giải full task.

Nhấn mạnh là bài lần này có rất nhiều điều để nói. Trong số những cái để nói đó có những cái thực sự hữu ích và cũng có những cú lừa cực mạnh. Đề nghị quý vị giữ thật chặt não của mình kẻo nó bay đi mất. Bắt đầu nào:

Tấm hình huyền thoại của series contest codechef

Bài 1: Pintu and Fruits - đề bài tiếng Việt

Đề bài này yêu cầu tìm ra loại hoa quả có số lượng giỏ ít nhất (tất nhiên là > 0 có giỏ nào) và tính tổng giá bán của loại hoa quả đó. Bài này có thể dùng map cho nhanh.

Code mẫu (C++)

Bài 2: XOR Engine - đề bài tiếng Việt

Một điều cam đoan với các bạn rằng, nếu làm theo kiểu duyệt trâu thì maximum bạn chi ăn được 30 điểm. Muốn ăn full task 100 điểm thì phải đi sâu vào nguyên lý của toán tử XOR: 

Xét các trường hợp sau:

1. A = 1001, B = 1001 => A ^ B = 0000
   A = 1001, B = 1100 => A ^ B = 0101
   A = 1001, B = 0110 => A ^ B = 1111
   A = 1101, B = 0111 => A ^ B = 1010
   A = 0001, B = 1101 => A ^ B = 1100
   A = 10000001, B = 11011101 => A ^ B = 01011100
   A = 00011000, B = 11000000 => A ^ B = 11011000
   A = 10000000, B = 00011100 => A ^ B = 10011100
   A = 10000000, B = 11100000 => A ^ B = 01100000
   Dễ dàng nhận thấy: nếu số lượng bit 1 của A và số lượng bit 1 của B cùng chẵn hoặc cùng lẻ, thì kết quả A ^ B sẽ có số lượng bit 1 là chẵn.
2. Vậy ngược lại, nếu số lượng bit 1 của A và B không cùng chẵn hoặc cùng lẻ, thì A ^ B sẽ cho ra kết quả có số lượng bit 1 là lẻ.

Từ đây ta rút ra được quy tắc: đếm số lượng bit 1 của mỗi số hạng A và B, chia ra 2 loại: có số lượng bit 1 chẵn và có số lượng bit 1 lẻ. Sau đó tùy thuộc vào số P có số lượng bit 1 chẵn hay lẻ mà đưa ra kết quả phù hợp.

Đến đây vẫn chưa đủ. Mình vẫn dính TLE, mặc dù đã thử nhiều cách: từ truyền thống (chia 2 liên tục lấy dư), dùng dịch bit đến dùng builtin function những vẫn dính TLE. Bỗng dưng mình chú ý là các successful submissions đầu tiên có người dùng C compiler. Vậy là mình chỉnh từ cin/cout sang scanf/printf và bùm, 100pts.

(Minh chứng cho sự khác nhau về tốc độ giữa scanf/printf và cin/cout, đọc post này từ Geeksforgeeks)

Về vấn đề này mính xin nói thêm rằng mình đã dùng sync_with_stdio và cin cout tie đàng hoàng. Nhưng rõ ràng tốc độ đọc/ghi của scanf/printf là chìa khóa quyết định bạn ăn full điểm hay chấp nhận thiếu 1 task. Rút kinh nghiệm từ nay về sau mình sẽ dùng scanf/printf, trừ những trường hợp khoai quá mới cin/cout :(

Code mẫu (C++).

Bài 3: Ada Bishop 2 - đề bài tiếng Việt

Giữ não của mình cẩn thận nào, chúng ta bắt đầu vào khúc cua đây.

Bí quyết để ăn trọn 100 điểm bài này rất đơn giản: nghiền ngẫu từng câu từng chữ trong bài là ổn. Đề bài yêu cầu đưa ra một đường đi hợp lý < 64 bước, sao cho quân tượng đi qua hết tất cả các ô đen trên bàn cờ 8 x 8, có thể có nhiều kết quả.

Vậy giả sử ta xây dựng một đường đi từ trước thì sao?

Một trong những cách đi. Chống chỉ định người cần hình chính xác, chỉ cần hiểu nôm na là nó giống cái xương cá.

Dựng một đường đi < 64 bước, cuối cùng in ra và vậy là xong.

Bạn sẽ nghĩ "đùa tôi chắc?". Trên thực tế, hãy xem thử submission #3, #4 và #1. Cách ăn trọn 100 điểm bài này, dễ nhất và nhanh nhất chính là xây dựng một đường đi sẵn và chỉ việc in nó ra thôi.

Code mẫu của cái xương cá bên trên (C++). Trên thực tế, nó là một phiên bản phức tạp hóa bằng cách dùng vector pair. Code dễ hiểu hơn của cái xương cá bên trên ở đây (cũng là C++).

Đến đây thôi, tóm lại Long Challenge lần này quá nhiều cú lừa và cua quẹo. Mong rằng lần sau đề sẽ ít bẻ lái cua khét hơn, và trình mình sẽ cao hơn được xí, giải được nhiều bài hơn.

Happy coding!