LIFTME - Lift Requests (Codechef April Cookoff 2020 - Divison 2)

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: Một cái thang máy đang ở tầng 0 (tầng trệt). Mỗi truy vấn bạn sẽ nhận vào 2 tham số d và f, theo đó thang máy sẽ đi đến tầng d để đón người và trả ở tầng f. Trong mỗi truy vấn thang máy sẽ không dừng lại ở tầng nào, aka phải thực hiện hết truy vấn này đến truy vấn khác. Đếm số lượng tầng mà thang máy đã đi qua, biết rằng đi từ d đến f sẽ đi qua | f - d | tầng.

Giải thích output mẫu:

• Ở truy vấn thứ 1: 1 2, thang máy ban đầu ở tầng 0 -> 1, rồi từ 1 -> 2 => 2 tầng.
• Ở truy vấn thứ 2: 0 1, thang máy đang ở tầng 2 -> 0, rồi từ 0 -> 1 => 3 tầng.
• Ở truy vấn thứ 3: 1 0, thang máy đang ở tầng 1 -> 0 => 1 tầng

Tổng cộng: 6 tầng.

Hướng dẫn: Bài này duyệt cơ bản, điểm bắt đầu của truy vấn sau là điểm đích của truy vấn trước. Kiểu dữ liệu để long là dư sức AC.

Link code mẫu (C++)

Happy coding!

Codechef April Long Challenge 2020 - Division 2

Contest lần này đánh vào number theory khá nhiều nên mình solve được tận 5 bài :D Cơ mà số lượng bài nhiều quá, viết editorial trong 1 post thì hơi khoai nên mình sẽ chia ra nhiều post rồi dẫn link lại post này:

Bài 1: CARSELL - Sell All The Cars

Bài 2: COVIDLQ - COVID Pandemic and Long Queue

Bài 3: STRNO - Strange Number

Bài 4: UNITGCD - Unit GCD

Bài 5: SQRDSUB - Squared Subsequence

Happy coding!

SQRDSUB - Squared Subsequence

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: bạn được cho một mảng A gồm N phần tử. Một đoạn "tốt" là một dãy các phần tử liên tiếp có tích biểu diễn được dưới dạng hiệu của hai số chính phương. Đếm số lượng đoạn "tốt" trong mảng A.

Khái niệm "đoạn con" sử dụng trong bài được định nghĩa là dãy các phần tử liên tiếp. Một phần tử cũng được tính là một đoạn con.

Hướng dẫn giải: Để một số có thể biểu diễn dưới dạng hiệu của hai số chính phương thì số đó phải là số lẻ hoặc là bội của 4 (để tập trung vào giải thuật, phần chứng minh các bạn đọc thêm trên MathExchange: chứng minh một số lẻ bất kỳ có thể được biểu diễn dưới dạng hiệu của hai số chính phương và chứng minh một số là bội của 4 có thể biểu diễn dưới dạng hiệu của hai số chính phương). Trái lại, một số chẵn mà không chia hết cho 4 sẽ không thể biểu diễn dưới dạng hiệu của hai số chính phương.

(*) Từ phần xanh lá, ta có thể đưa bài toán về bài toán "đếm số lượng đoạn không thể biểu diễn dưới dạng hiệu của hai số chính phương (U)", sau đó dùng tổng số lượng đoạn con có thể tạo trừ đi U sẽ thu được kết quả cần tìm.

Tổng quát: số lượng đoạn con có thể tạo từ một dãy N phần tử là . 

Để một đoạn con có tích chia hết cho 2 nhưng không chia hết cho 4, ta chỉ cần xác định vị trí của các phần tử mà biểu diễn dưới dạng tích các số nguyên tố của nó chỉ có 1 số 2 duy nhất, gọi là số neo. 1 số chẵn nhân với 1 số lẻ ra một số chẵn, mà số chẵn ban đầu không chia hết cho 4 dẫn đến kết quả sau khi nhân số lẻ cũng sẽ không chia hết cho 4. Do vậy, công việc của ta là đếm số lượng số lẻ ở 2 bên của số neo, tính tổng số lượng đoạn con có thể tạo thành.

Cần chú ý là nếu 2 bên của số neo không có số lẻ nào thì độ dài dãy đó bằng 1. Làm theo (*) là ta có được kết quả đề bài.

CU;WTF?: tìm trong mảng A những số chia hết cho 2 mà không chia hết cho 4. Với mỗi số đó, đếm xem bên trái có bao nhiêu số lẻ, bên phải có bao nhiêu số lẻ, cộng 2 cái đó lại, cộng thêm 1 là số 2 đứng giữa. Tính theo công thức  là tìm được tổng số đoạn con dạng U. Lặp lại đến hết mảng A, rồi lấy tổng số đoạn con của mảng A trừ tổng số đoạn con dạng U là ra kết quả.

Bài này không khó nhưng cài thuật ad-hoc rất khó.

Code mẫu (C++)

Happy coding!

UNITGCD - Unit GCD

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: bạn có 1 quyển sách được đánh số từ 1 đến N. Mỗi ngày bạn được đọc một số trang nhất định sao cho chỉ số của các trang đó là các cặp số nguyên tố cùng nhau. Tìm số ngày ít nhất để đọc hết cuốn sách cũng như cách đọc trong từng ngày. Chú ý là mỗi ngày bạn được đọc một số trang sao cho chỉ số của các trang đó là các cặp số nguyên tố cùng nhau, nghĩa là mỗi ngày bạn phải đọc ít nhất là 2 trang.

Hướng dẫn giải: Đây là Nguyên lý Chuồng bồ câu (hay Nguyên lý Dirichlet) trong Toán rời rạc. Từ 1 đến N, cứ 2 số nguyên liên tiếp sẽ tạo thành 1 cặp số nguyên tố cùng nhau. Số ngày tối thiểu để đọc hết N trang sách là trang - cũng là số cặp số nguyên tố cùng nhau không lặp lại có thể chia được. Trong đó, trường hợp N lẻ chúng ta có tập kết quả lớn nhất gồm 3 phần tử {1, 2, 3}, còn lại là các cặp nguyên tố cùng nhau. Công việc cần là phân loại theo điều kiện N và in kết quả ra thôi.

CU;WTF (Cannot Understand, WTF?): in ra các tập 2 phần tử. Ví dụ: N = 4 => {1, 2}, {3, 4}. Nếu N lẻ thì in 3 phần tử đầu rồi cứ in 2 phần tử làm tới. VD: N = 5 => {1, 2, 3}, {4, 5}; N = 9 => {1, 2, 3}, {4, 5}, {6, 7}, {8, 9}. Chú ý trường hợp N = 1 thì chỉ in ra 1 phần tử thôi.

Code mẫu (C++)

Happy coding!

STRNO - Strange Number

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: bạn được cho 2 số nguyên dương X và K. Xác định xem tồn tại một số nguyên dương A sao cho A có đúng X ước số, trong X ước số đó có K ước số là số nguyên tố.

Ví dụ: với X = 4, K = 2, ta có thể tìm được A = 6. Số 6 có 4 ước (1, 2, 3, 6), trong đó 2 ước (2, 3) là số nguyên tố.

Hướng dẫn giải:

Lý thuyết: Phân tích một số nguyên A ra thừa số nguyên tố  (với p là một số nguyên tố). Khi đó tổng số ước N bằng .

Ở đây A chỉ có đúng K ước nguyên tố, nghĩa là trong đa thức   tồn tại ít nhất K đa thức có dạng . Để giải được bài này, ta cần phải đếm xem có thể phân tích X thành số nguyên tố bao nhiêu lần. Mỗi số nguyên tố của X sau khi phân tích sẽ ứng với một đa thức  , và nếu tổng số đa thức >= K thì ta có thể xây dựng được số A.

Code mẫu (C++)

Happy coding!

COVIDLQ - COVID Pandemic and Long Queue

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: Có một dãy N chỗ đứng, chỗ thứ i được đánh dấu là "1" nếu có người đứng và "0" nếu không có ai đứng. Khoảng cách giữa chỗ thứ i và i + 1 là 1 feet. Dịch COVID đang hoành hành, mỗi người được khuyến khích phải đứng cách nhau 6 feet trở lên (>= 6 feet). Xác định xem trong hàng đó có người nào vi phạm khoảng cách an toàn hay không?

Hướng dẫn giải: bài này duyệt bình thường, kiểm tra 2 vị trí liên tiếp có người đứng (aka 2 số "1" liên tiếp) cách nhau bao xa, nếu < 6 feet thì vi phạm. 

Code mẫu (C++)

Happy coding!

CARSELL - Sell All The Cars

Link đề bài - Link bản tiếng Việt

Tóm tắt đề bài: bạn có N chiếc xe và cần phải bán hết N chiếc xe đó, mỗi năm chỉ được bán 1 chiếc. Chiếc xe thứ i có giá P[i] đồng, sau mỗi năm thì giá của mỗi chiếc xe sẽ giảm đi 1 đồng. hãy tìm cách bán sao cho đến khi bán xong chiếc xe cuối cùng bạn sẽ thu về được nhiều tiền nhất.

Hướng dẫn giải: Phương pháp tham lam. Cách tốt nhất để bán hết xe và nhận về lợi nhuận cao nhất chính là sắp xếp xe theo giá giảm dần rồi bán từ từ, chú ý trường hợp giá xe tụt xuống < 0 thì sẽ tính là = 0.

Chú ý: với các phép toán có sử dụng modulo:

Phép cộng: (a + b) mod c = ((a mod c) + (b mod c)) mod c

Phép trừ: (a - b) mod c = ((a mod c) - (b mod c)) mod c

Phép nhân: (a * b) mod c = ((a mod c) * (b mod c)) mod c

Code mẫu (C++)

Happy coding!

UCV2013I - Tambourine

Link đề bài 
Link hướng dẫn giải + code mẫu

Happy coding!

UCV2013J - Valences

Một bài toán có Hóa nhưng không phải về Hóa, có Cây nhưng không phải về Cây :)

Link đề bài
Link hướng dẫn giải + code mẫu

Happy coding!

SWPDGT - Codechef March Lunchtime 2020 - Division 2

Mình vẫn nợ 1 bài code Lunchtime tháng 3 chưa viết editorial, cũng là bài duy nhất mình giải được trong contest này :(

Link đề bài trên Codechef - bản dịch tiếng Việt

Hướng dẫn giải:

Xét một số nguyên trong đoạn [1, 99]. Số đó có thể được biểu diễn dưới dạng 10*A + B, với A và B lần lượt là các số nguyên. VD: 28 = 10*2 + 8 (A = 2, B = 8), 56 = 10 * 5 + 6 (A = 5, B = 6).

Nếu lấy 28 + 56, ta có các khả năng swap vị trí như sau: 28 + 56, 68 + 52, 25 + 86. Chúng ta không xét tới các khả năng 58 + 26 hay 26 + 58, vì 2 khả năng này cho kết quả như nhau (và cùng bằng 28 + 56), lý do là vì tính chất giao hoán của phép cộng đều cho kết quả như nhau.

Đối với trường hợp phép cộng giữa một số có 2 chữ số với một số chỉ có 1 chữ số (VD: 12 + 9), ta vẫn swap vị trí như trên, nhưng lúc này chỉ còn 1 vị trí có thể swap (91 + 2). Trường hợp còn lại là phép cộng giữa 2 số có 1 chữ số thì tổng lớn nhất là tổng của 2 số đó, không cần swap.

Code mẫu (C++)

Happy coding!

Shitpost đêm khuya #8

Hôm nay là 1/4 (April's Fool Day). Mọi người còn online ngoài kia đua nhau đi tỏ tình, trêu đùa với bạn bè, người thân của mình. Riêng chỉ có mình ngồi 1 mình trong phòng khách, bên cạnh là ca cafe đã tan hết đá, cùng với chiếc laptop hơi bám bụi, lụi cụi gõ ít dòng tâm sự.

Giữa lựa chọn được đi nước ngoài và ở lại Việt Nam, mình chọn đi nước ngoài. Dạo gần đây có một vài quan điểm cho rằng những du học sinh ra nước ngoài là những cậu ấm, cô chiêu, những "xã hội Đỏ, thái tử Đảng" được cử ra nước ngoài tìm vé định cư và một sân bay an toàn để sau này quý thân sinh có đường băng hạ cánh an toàn. Mình có một người bạn cấp 2, đã sang Australia học tập từ cuối tháng 9. Trong một comment, khi được hỏi "Sao không về Việt Nam tránh dịch?", cậu ấy đã bảo là "Có gan đi thì dám ở".

Và thật sự là như vậy, một khi đã chọn con đường ra đi tìm kiếm sự nghiệp, vươn tới một chân trời mới thì phải có bản lĩnh, gan dạ mà chịu trách nhiệm cho những hành động của mình. Đã gần 20 tuổi, mình thật sự chưa hình dung được cuộc sống của mình ở nước ngoài (nếu giả sử mình được ra nước ngoài sinh sống / học tập) như thế nào. Và nếu có được cơ hội đó, liệu mình có đủ bản lĩnh bám trụ lại như cậu bạn bên trên không?

Xoay đi quay lại, cũng có vài lý do khác để mình cảm thấy rằng bản thân mình chẳng có chút bản lĩnh nào. Mình đã nói dối về ngành học tương lai gần 2 năm. Ngày ấy mình bảo mình chọn Vật lý hạt nhân, khiến cho gia đình phải khuyên đi khuyên lại hết lời, nhưng cơ bản trong thâm tâm mình vẫn chọn IT vì mình đã gắn bó từ cấp 2, chỉ dương Đông kích Tây để khỏi bị soi mói thôi. Chẳng qua là mình không đủ bản lĩnh để đối mặt với thực tại, đối mặt với mọi người. Nhưng sau khi đỗ, may sao, mọi người vẫn hiểu cho mình.

Rồi mình không chọn trở thành một người lập trình làm việc tại các công ty, viết những phần mềm giúp ích cho xã hội. Mình lại chọn CS, vì đơn giản mình không muốn phí những gì mình đã được học - một lời bao biện cho sự thiếu tự tin. Mình không tự tin vào kỹ năng lập trình, không tự tin vào khả năng tư duy hay khả năng giải quyết vấn đề dưới áp lực. Thế là mình lại chọn CS.

Và cuối cũng, mình viết bài post này vì lý do chính là mới xem được tốc độ gõ phím của SGO48 Ashley là 111WPM trong khi của mình chỉ có 50WPM. Mình viết post này chỉ nhằm mục đích luyện gõ phím, nhưng cũng là tâm sự đôi chút. Thật lòng đấy ạ, không đùa đâu.