Codechef March Lunchtime 2020 - Khi COVID-19 lan rộng đến đấu trường CP

Trước cơn bão COVID-19 đang quay cuồng trên toàn thế giới, nhiều người đã chọn lựa ở yên trong nhà xem Netflix, lưới Facebook hay nghe Spotify để bảo toàn tính mạng cho người thân, gia đình và xã hội. Không gian mạng từ lâu đã là chốn đi về lý tưởng cho các geek khi cái xã hội đau thương bi ai ngoài kia quá khắc nghiệt đối với họ. Họ cho rắng khi đã lên mạng, tham gia các contest CP, nộp những bài code và giành vài điểm rating là một cái thú vui tao nhã không thể nào bị suy chuyển bởi kinh tế thế giới, biến động chính trị hay thiên tai dịch bệnh.

Mình đã tham gia các cuộc thi CP trên Codechef từ tháng 10/2019. Tối nay đúng lịch sẽ diễn ra Codechef Lunchtime tháng 3, mình đã chuẩn bị sẵn template code, đồ ăn thức uống, mọi thứ đều đã sẵn sàng để xin ít rating và nhảy lên cao thêm chút.

Thế mà, contest này diễn ra theo chiều hướng tệ hơn mình tưởng. Website contest sập 15 phút, lúc 20h15 IST các nhà tổ chức thông báo sẽ thêm 15 phút bù giờ cho khoảng thời gian contest bị delay. Vấn đề là sau 15 phút, đề bài vẫn chưa thể mở, lỗi 500 vẫn diễn ra thường xuyên, downfor.io nhận định Codechef đã down.

Và đến khi Codechef trở lại, mọi thứ còn tệ hơn gấp nhiều lần.

Các submission không thể được chấm đúng giờ vì có quá nhiều submission. Nhiều đến nỗi mình sub 2 sub đầu thì mất hơn 15 phút mỗi sub mới cho ra WA verdict, đến 4 sub sau thì mỗi sub tốn gần 30 phút mới cho ra WA. Tình thế khiến mỗi competitor phải chờ mòn mỏi verdict là một, phải đau đầu vì không mở được đề mới là hai. Họ bắt đầu lập các topics trên discuss forum để khiếu nại.

Đến cuối cùng, admin đã quyết định đóng contest tháng 3. Tất nhiên là các submissions không được tính vào rating, cũng như một lời xin lỗi chân thành của đội ngũ admin đã làm cho cộng đồng dịu lại. Nhưng hơn cả, mình biết nguyên nhân của sự cố này không đến từ admin, kỹ thuật hay cộng đồng. Contest này thu hút quá đông người tham gia, và tất nhiên họ tham gia vì không thể tìm được một thú tiêu khiển nào khác.

Vâng, COVID-19 đã ảnh hưởng đến một đấu trường online, nơi được xem như là bất khả xâm phạm đối với vi trùng / virus. COVID không đánh trực tiếp bằng cách làm server bệnh rồi ngã lăn đùng ra chết; nó hạn chế con người ta ra ngoài đường, hạn chế tụ tập, khiến họ phải tập trung vào những giải đấu online vốn rất ít người tham gia. 

Nếu nhắc đến COVID-19, đây chắc chắn sẽ là kỷ niệm khó quên nhất đối với mình.

Nhưng vẫn có solution cho problem 1 của contest này nhé, đợi mình viết xong editorial rồi sẽ post sau. 

Codechef March Cookoff 2020 - Division 2

Contest này solve được có 1 bài :( Rating tụt thê thảm nhưng vẫn ở rate xanh.

GIFTSRC - Find Your Gift - Link bản tiếng Việt

Tóm tắt đề: bạn đang đứng ở tọa độ (0, 0). Mỗi lần bạn chỉ được di chuyển theo 1 trục khác với lần di chuyển trước. Ví dụ, bạn đang đứng ở (0, 0), bạn bước sang trái đến ô (-1, 0). Bước tiếp theo bạn chỉ có thể bước lên ô (-1, 1) hoặc bước xuống ô (-1, -1), vì nếu tiếp tục bước sang trái hay bước sang phải vẫn sẽ trùng với trục của bước di chuyển trước. Tương tự với việc bước lên / bước xuống.

Hướng dẫn giải: Chỉ cần xác định những bước đi không cùng trục với nhau, rồi tính toán tọa độ dựa trên những bước đi đó là ta có kết quả.

Link hướng dẫn giải + code mẫu

Happy coding!

EDIT - Edit Distance Again

Ngoài lề:

Rất lâu rồi mình mới quay lại SPOJ, một phần vì contest của Codechef cuốn quá, một phần vì Codechef có ban Việt ngữ nên những problem Codechef mình ít phải tự dịch. Nay cái problem này là cái problem mình tự dịch tay sau một thời gian dài bỏ bê dịch diếc, nên có sai sót cũng thông cảm giúp mình ạ :(

Đọc đề bài trên SPOJ

Hướng dẫn giải + code mẫu

Happy coding!

Shitpost đêm khuya #7

Mình vẫn ở Bến Tre. Nước vẫn mặn, dịch COVID vẫn đang hoành hành.

Nhưng bài viết hôm nay không phải về những vấn đề bên trên. KTX ĐHQG-HCM vừa được trưng dụng làm khu cách ly bệnh nhân COVID từ nước ngoài về. Tình hình ở TPHCM có vẻ khá nghiêm trọng, khi KTX ĐHQG được dọn dẹp trong vòng 2 ngày để bắt đầu đón người cách ly.

"Dọn dẹp" ở đây nghĩa là, đồ dùng của sinh viên bỏ lại được thu gom, đóng gói rồi lưu trữ trong một phòng riêng. Tủ đồ của bọn mình được niêm phong, những vật dụng được kiểm đếm đàng hoàng. Thế nhưng vẫn có một số sinh viên, trong đó có mình, kêu trời vì mọi việc quá gấp gáp mà sinh viên cũng chẳng kịp lên thu dọn đồ đạc, tìm chỗ ở mới.

Bọn mình có đồ đạc tại KTX đều có lý do của nó. Trước ngày 03/02, bọn mình hoàn toàn không lường trước được tình hình dịch bệnh sẽ diễn biến phức tạp. Thực chất, mình đã có mặt tại KTX ngày 03/02, chuẩn bị cho sáng hôm sau nhập học môn GDQP thì tối hôm đó có thông báo nghỉ. Bọn mình rời KTX với tâm thế là được nghỉ thêm 1 tuần lễ, không nghĩ đến việc bọn mình phải rời để nhường chỗ cho một khu cách ly.

Thế nhưng mà, nếu to miệng la làng về vấn đề đồ đạc ở KTX bây giờ sẽ bị cho là "thiếu tinh thần yêu nước". Cái bọn mình la, là vấn đề thông tin của KTX. Bọn mình đã liên hệ từ 1 tuần trước, hỏi rằng có được lên KTX thu dọn đồ hay không. Mọi thông tin có được đều bảo là "không", đến cuối tuần trước thì trung tâm quản lý KTX lại đăng một "thư ngỏ", thay vì một thông báo chính thức về cái quái gì chuẩn bị xảy ra.

Đành rằng đây là thời điểm khó khăn của đất nước, nhưng thông tin quá mù mịt, khiến bọn mình cũng chẳng kịp trở tay. Vật dụng của bọn mình được niêm phong, nếu xui quá thì có thể mất mát đi và có thể mua lại được, nhưng niềm tin của bọn mình vào BQL KTX, có lẽ đã bị hao mòn đôi chút. Dù gấp rút đến đâu, chúng mình cũng đã hỏi ít nhất là 1 tuần. Những thông tin KTX có thể được trưng dụng làm khu cách ly đã có từ đầu tháng 3, đến nay đã 2 tuần. Những nhà quản lý đã có thể thông báo từ lúc đó, vậy tại sao phải canh còn có 2 ngày rồi mới thông báo?

Vấn đề vẫn là, ở thời điểm này mọi quan điểm trái ngược với các luận điệu của truyền thông sẽ được xem là phản động, không yêu nước. Đành rằng những người Việt hải ngoại cũng là đồng bào của ta, cũng nên yêu thương họ, nhưng vậy còn những sinh viên đã và đang ở trong KTX, họ cũng là người Việt, cũng là đồng bào, sao không ai yêu thương mà cảm thông với tình cảnh của họ vậy?

Xem như kỳ nghỉ Tết vẫn còn. Chúc mừng năm mới!

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++).

LIFELTD - Life Limited

Đọc đề bài trên Codechef

Hướng dẫn giải & code mẫu

Happy coding!

Shitpost đêm khuya #6

VNUHCM cho sinh viên nghỉ hết tháng 3. Hà Nội đã chính thức xác nhận ca nhiễm nCoV thứ 17 của Việt Nam.

Từ đầu tuần, báo chí cứ đưa tin việc ông chủ tịch TPHCM muốn mượn KTX VNUHCM làm nơi cách ly người nghi nhiễm nCoV. Mình cứ nghĩ đây là đòn dương đông kích tây, nhưng ca nhiễm nCoV tại Hà Nội lại khơi gợi một khả năng nào đó, là dịch bệnh sẽ bùng phát mạnh.

16 người nhiễm nCoV mà Việt Nam chữa khỏi mới là khởi đầu, là cơn giông lớn trước cơn bão biển sắp đổ bộ vào Việt Nam. Mình vẫn mong là thực sự cơn bão nCoV sẽ không đổ bộ ào ạt vào Việt Nam như mình dự đoán, nhưng nếu tình hình tiếp tục leo thang thì nỗi sợ về cơn bão biển đó sẽ ngày một lớn, ngày một chân thực.

Đến sáng ngày mai các báo chí sẽ đồng loạt đăng những tin tức xoa dịu dư luận, nhưng nhìn đi nhìn lại hiện thực vẫn ở trước mắt, rằng cơn bão biển nCoV vẫn chưa đổ bộ vào đất liền Việt Nam.

Trước cơn bão lớn, đất liền thường tĩnh lặng, yên ả. 24 ngày báo chí hết mực ca ngợi y tế, ca ngợi tầm vóc, nhưng chỉ sau cơn bão sắp tới chúng ta mới thực sự biết được ai giỏi, ai tài, ai đoàn kết.

Codechef February Lunchtime 2020 - Division 2

Contest này mình solve được bài 1 + 1 task bài 2. Tưởng là tụt rating ai ngờ rating mình dương :D Vậy là mình đã trở về 3* rồiiiii

Bài 1: At the Gates

(dịch luôn vì solve được trọn vẹn có bài này)

Đề bài:

Bạn là Dastan, Hoàng tử xứ Ba Tư!

Sau một khoảng thời gian dài tìm kiếm "Cát thời gian", cuối cùng bạn đã đến được cổng thành phố có một ngôi đền cổ thờ các vị thần. Tuy nhiên, cánh cổng này đã bị khóa và chỉ có thể mở được với một mật mã bí mật - thứ mà bạn sẽ có được nếu giải câu đố sau:

Có một cái bàn trước mặt bạn, trên đó có đặt N đồng xu, các đồng xu được đánh số thứ tự lần lượt từ 1 đến N từ trái qua phải. Với mỗi đồng xu, bạn biết được ban đầu nó đang nằm sấp hoặc ngửa. Bạn phải thực hiện đúng K bước. Với mỗi bước, bạn phải bỏ đồng xu ở ngoài cùng bên phải, nếu đồng xu này đang nằm ngửa trước khi bạn bỏ nó đi thì bạn phải lật tất cả các đồng xu trước nó lại (lật xu nghĩa là nếu một đồng xu đang nằm ngửa thì bạn lật nó nằm sấp và ngược lại).

Mật mã mở cửa thành phố là số lượng đồng xu, mà sau K bước, chưa bị bỏ đi và đang nằm ngửa. Bạn có thể tìm con số này không? Vận mệnh của xứ Ba Tư đang nằm trong tay bạn!

Input:

• Dòng đầu mỗi input là một số nguyên T  - số lượng testcases. Tiếp theo đó là T dòng như mô tả bên dưới.
• Dòng đầu tiên mỗi testcase là 2 số nguyên N và K cách nhau bởi 1 dấu cách.
• Dòng thứ hai của mỗi test case là N ký tự, mỗi ký tự cách nhau bởi 1 dấu cách. Ký tự thứ i sẽ là 'H' nếu đồng xu đang nằm ngửa và 'T' nếu đồng xu đang nằm sấp.

Output:

Với mỗi testcase, in ra màn hình 1 số nguyên duy nhất - số lượng đồng xu đang nằm ngửa sau K bước.

Ràng buộc:

• 1 <= T <= 200
• 1 <= K < N <= 100

Input mẫu:

3

5 3

H T T H T

7 4

H H T T T H H

6 1

T H T H T T

Output mẫu:

1

2

2

Hướng dẫn giải:

Ta thực hiện theo đề bài, tiến hành lật xu rồi đếm thôi :D

Code mẫu (C++)

Lên xanh trở lại rồi nèeeeee

Happy coding!