Như các bạn đã biết, một số bài hiện nay có bộ test "hơi" yếu. Điều này đã được phản ánh khá nhiều. Tuy nhiên vì số lượng bài tập rất lớn nên ban quản trị không thể kiểm soát hết được. Vì thế, mình muốn nhờ các bạn giúp đỡ một tính năng tương tự như uphack bên Codeforces. Để uphack một bài nộp của người khác, các bạn có thể ấn vào nút: "Báo cáo/Report an issue" rồi viết theo format sau:

• Submission: Link tới bài submission mà các bạn muốn uphack, ví dụ http://lqdoj.edu.vn/submission/1
• Input/Output: có thể upload lên một drive nào đó rồi chia sẻ link (nếu file có kích thước lớn), hoặc có thể gửi trực tiếp file nhỏ hoặc code sinh test.

Hiện tại mình chưa biết sẽ có phần thưởng cụ thể gì, nhưng người uphack sẽ được vinh danh trong các thông báo sau khi rejudge. Các bạn cũng có thể đề xuất phần thưởng trong phần comment của post này :v

Chào các bạn, lại là chúng mình, team ami and fans, hân hạnh mang đến cho các bạn một kì contest siêu hoành tráng. Đây là kì thi thử trước khi bước vào kì thi Olympic Tin học Miền Trung và Tây Nguyên.

Lần này sẽ có 2 kì thi chạy song song. Nếu các bạn là lớp 10 trở xuống, các bạn bắt thuộc phải đăng kí vào kì thi cho lớp 10. Nếu các bạn là lớp 11 trở lên, các bạn cần đăng kí cho lớp 11. Mọi thí sinh đăng kí 2 kì thi cùng lúc sẽ nhận hình phạt.

Cả 2 kì thi sẽ diễn ra vào lúc 08 giờ 00 phút 00 giây ngày 7 tháng 6 năm 2020 thế kì 21. Mỗi kì thi sẽ gồm 4 bài, và các bạn sẽ có 3 giờ để giải quyết.

Kỳ thi thử lần thứ 2, kì thi Olympic Tin học Miền Trung và Tây Nguyên.

• Cả 2 khối thi sẽ diễn ra vào lúc 08 giờ 00 phút 00 giây ngày 14 tháng 6 năm 2020
• Mỗi khối thi sẽ gồm 3 bài, và các bạn sẽ có 3 giờ để giải quyết.

Rút kinh nghiệm từ kì thi trước, kì thi lần này đã được coordinator ami kiểm tra chất lượng kĩ càng. Với đội ngũ ra đề và tester cực kì hùng hậu - cuom1999, dungde99, CaiWinDao - mình tin tưởng đây sẽ là một kì thi cực kì đáng tham gia. Hi vọng các bạn sẽ tham gia nhiệt tình. Chúc các bạn đạt thứ hạng cao và thu được những kiến thức bổ ích.

Update:

• Bạn nào muốn theo dõi quá trình rejudge với bộ test chính thức thì có thể nhấn nút "Tham gia ảo"/"Virtual join" (sau khi kết thúc thời gian dự thi) rồi click vào mục "SUBMISSIONS" để xem các kết quả chấm lại.
• Thêm thông báo về kỳ thi thử lần thứ 2
• Kỳ thi thử lần thứ 2 sẽ được chấm trên bộ test chính thức thay vì pretest, mỗi bạn vẫn sẽ có tối đa 5 lần nộp bài.

Đây là đôi lời về kì thi quốc tế thiếu nhi 2020 vừa qua.

Đầu tiên, xin chúc mừng 5 bạn đạt điểm cao nhất

Tiếp theo là những bạn AC đầu tiên cho từng bài

Chúc mừng một kì contest nữa lại trôi qua. Đây là kì contest đầu tiên do ami làm coordinator (a.k.a chỉ đạo, đốc thúc các testers và người ra đề, ...)

Bài B được đánh giá không phải là bài quá khó. Và ami nghĩ sẽ có nhiều bạn AC hơn. Tuy nhiên có lẽ việc đánh giá đã đi lệch lạc quá nhiều. Là một người chỉ đạo, ami xin nhận lấy mọi sự chỉ trích và sẽ họp bàn để rút kinh nghiệm.

Bài D là một bài cũng được đánh giá là không quá khó. Thực tế chỉ ra, có zipdang04 đã tiến rất gần đến việc AC, tuy nhiên vì sự công tâm của bộ test, zipdang04 vẫn chưa hoàn toàn chinh phục được bài này. Điều đáng nói ở đây, là thứ tự bài D rất không hợp lý.

Bài C là bài không dễ và nên được thay đổi vị trí với bài D.

Bài A vẫn là chưa đủ để các bạn làm nóng máy. Tuy nhiên, đây có lẽ được coi là bài thành công nhất dựa trên tiêu chí của ami.

Tóm lại, một kì contest vẫn được xem là bổ ích về mặt kiến thức, tuy nhiên, vẫn tồn tại sự bất hảo trong contest lần này. Mong các bạn thông cảm và tiếp tục ủng hộ team "ami and fans (a.k.a CaiWinDao , cuom1999, dungde99)".

Editorial

Đang cập nhật, ami sẽ đốc thúc các fans update nhanh, mong các bạn thông cảm.

"Hãy thiết lập trạng thái bình thường mới, vừa đẩy mạnh phát triển kinh tế xã hội, vừa chống dịch hiệu quả!"

Câu khẩu hiệu khi bắt đầu mỗi cuộc gọi thật súc tích nhưng vẫn có thể gợi lên cho chúng ta một áp lực không nhỏ trước việc phải cân bằng được hai mục tiêu hết sức đối trọng với nhau. Giai đoạn giãn cách xã hội kết thúc cũng là lúc mỗi bạn học sinh phải vùi đầu vào một nhịp sống và học hành cực kỳ hối hả, căng thẳng, thậm chí đôi lúc còn dấy lên một chút mệt mỏi và tuyệt vọng, đến mức các bạn quên mất một ngày mà nhân loại dành ra để tôn vinh chính các bạn: Quốc tế thiếu nhi 1/6.

Tuy nhiên, đội ngũ admin chúng mình - CaiWinDao, cuom1999 và ami - không bao giờ quên mất dịp trọng đại đó: Chúng mình đã dày công chuẩn bị một programming contest thật hoành tráng để làm tiền đề tinh thần cho các bạn trải nghiệm một dịp quốc tế thiếu nhi đầy dấu ấn trí tuệ và sảng khoái. Với ~4~ bài toán được xây dựng và kiểm thử kỹ lưỡng, contest sẽ bắt đầu vào lúc 18h30 ngày Chúa nhật 31/05 và kéo dài 180 phút đồng hồ. Các bài toán sẽ được chấm theo kiểu OI và các bạn chỉ có thể nhìn thấy kết quả chấm pretest trong thời gian thi. Một điểm mới ở contest này là các bạn chỉ có thể submit tối đa 5 lần cho mỗi bài toán.

Xin cảm ơn và rất mong có được sự tham gia đầy đủ của tất cả các bạn!

P/s: Như thường lệ, các bạn học sinh ở các lớp của thầy Small nếu bị phát hiện có code giống nhau thì sẽ được vinh dự bao thầy Small 3 ly cafe. Các bạn học sinh IT NBK có hành vi tương tự thì sẽ được đứng vào hàng ngũ đẩy giúp xe ô tô thầy Lĩnh vào cổng trường sau khi thầy xuống xe tắt máy theo quy định.

Update: Contest sẽ diễn ra vào 18h30 thay vì 19h00 như dự định ban đầu, để khỏi bị xung đột thời gian với Codeforces Round 646.

Vậy là 5 series của Happy School đã kết thúc, hãy cùng ami tổng kết lại kì thi nào.

Chúc mừng 5 bạn đạt điểm cao nhất

Đây là những người AC đầu tiên cho từng bài

Bằng một cách vi diệu nào đó, thoi_bay_corona không được tính vào bảng rank vì bị kẻ mưu hại set quyền admin. Chúng tôi đang điều tra và sẽ xử lý kẻ gian trong thời gian sớm nhất.

Ngoài ra, contest Happy School đã phá vỡ kỷ lục về số người tham dự, các bạn hãy vỗ tay chúc mừng team ami and fans (a.k.a CaiWinDao, cuom1999, dungde99). Team ami and fans xin cảm ơn các bạn đã bỏ thời gian quý báu tham dự, hi vọng contest đã không phụ lòng các bạn.

Editorial

Các bạn có thể vào từng bài để đọc lời giải. (ví dụ lời giải bài A ở đây)

Chào các bạn,

Mình là ami và cuom1999 hân hạnh được chào đón các bạn trong website mới của Lê Quý Đôn-oj.

Cùng chung không khí hân hoan nhân kỉ niệm 1 tuần ngày toàn dân đưa trẻ quay lại trường, mình và cuom1999 xin góp vui bằng một kỳ thi nhẹ nhàng và đơn giản. Kì thi sẽ diễn ra vào ngày 15/5/2020, lúc 19:00. Các bạn sẽ có 3 giờ để giải quyết 6 bài tập. Kì thi sẽ tính rating cho tất cả các bạn. Kì thi lần này sẽ tuyệt đối cân bằng. Nếu mức độ khó của đề không làm hài lòng các bạn, xin các bạn cứ góp ý và blame cuom1999.

Cuối cùng, mình xin cảm ơn thầy Small, admin và là người tài trợ cho trang web. Cảm ơn cuom1999 đã giúp mình chuẩn bị kì thi này. cuom1999 là người lên ý tưởng, làm bộ test, đảm bảo độ cân bằng cho 6/6 bài, là người gánh team, penta kill, .... Cảm ơn các bạn sẽ tham gia nhiệt tình. Chúc các bạn thu được nhiều kiến thức. Top 3 học sinh của thầy Small giải được 4/6 bài hoặc nhiều hơn sẽ vinh dự được thầy Small mời cafe miễn phí.

Update : Các bài nộp cuộc thi sẽ được chấm trên pretest, nhưng vẫn tính điểm theo kiểu OI. Sau khi kì thi kết thúc, các bài nộp sẽ được chấm với bộ test hoàn chỉnh. Ngoài ra, các bạn là học sinh của thầy Small, nếu bị hệ thống phát hiện code trùng nhau, sẽ được bao thầy Small 3 ly cafe.

Update : Ngày giờ cuộc thi đã được điều chỉnh.

Update : Cảm ơn dungde99 đã giúp kiểm tra đề thi và bộ test, cảm ơn CaiWinDao đã giúp các vấn đề về hệ thống và giải đáp thắc mắc.

Update : Cảm ơn các bạn đã tham gia thử thách cùng ami. Lời giải cho các thử thách đã được post, các bạn có thể truy cập vào các bài để đọc.

Vậy là contest lqdoj004 đã được tổ chức thành công! Ngoại trừ một sự cố "nho nhỏ" về phần website khiến cho trang bị sập trong vòng hơn 1 tiếng, còn ngoài ra thì cuộc thi này đã diễn ra rất tốt đẹp =)).

BTC xin chúc mừng 5 thí sinh đứng đầu bảng rank:

Và đây là những người AC đầu tiên cho từng bài (Do web bị sập giữa lúc thi nên số liệu cho những bài đầu có thể không đúng với thực tế):

Sau đây là lời giải cho 7 bài:

A - Doraemon và cuộc phiêu lưu ở hòn đảo kho báu [Bản dễ]

Bài này ta chỉ việc làm theo đề bài: Kiểm tra tất cả bộ ~(i, j) \, (L \leq i < j \leq R)~ và tìm giá trị tối thiểu của ~(i \times j) \bmod M~.

Độ phức tạp: ~O((R-L)^2)~

B - Doraemon và những chú khỉ khá là không liên quan

Ta thấy rằng khi học sinh đến sớm thứ ~x~ đi vào lớp thì lúc đó lớp có tổng cộng ~x~ học sinh - nói cách khác, học sinh thứ ~i~ đến sớm thứ ~A_i~. Vậy ta chỉ cần sắp xếp lại mảng ~A~ và tìm vị trí ban đầu của mỗi phần tử sau khi sắp xếp.

Độ phức tạp: ~O(N \log N)~ hoặc ~O(N)~ tùy cách cài đặt.

C - Doraemon và thử thách đầu tiên [Bản dễ]

Xét hàng thứ ~i~, nếu như lúc đầu trên hàng đó có ~0~ hoặc ~1~ con quái vật thì ta chỉ có ~1~ cách tô màu duy nhất (màu trắng hoặc màu của con quái vật tương ứng); còn nếu có ~2~ quái vật thì ta có ~2~ cách tô màu (tùy vào con quái vật bên trái hay bên phải tô màu trước). Vậy đáp án cho bài này là ~2^x~, với ~x~ là số hàng có ~2~ con robot.

Độ phức tạp: ~O(N)~.

D - Doraemon và cuộc phiêu lưu ở hòn đảo kho báu [Bản khó]

Do bài này có giới hạn ~L, R \leq 10^9~ nên có thể các bạn nghĩ là sẽ không thể giải được bài này dùng thuật của bản dễ ;) . Tuy nhiên, ai tinh ý thì sẽ phát hiện ra rằng:

• Trong ~M~ số tự nhiên liên tiếp nhau thì sẽ luôn có 1 số chia hết cho ~M~.

Vậy nếu như ~(R - L + 1) \geq M~ thì đáp án sẽ luôn là ~0~, ngoài ra thì các bạn có thể dùng thuật của bản dễ để giải bài này.

Độ phức tạp: ~O(M^2)~

E - Doraemon tự kỷ với trò chơi mới

Bài này rất đơn giản, chỉ cần làm theo yêu cầu đề bài: Với mỗi ô trống, đặt bánh rán nâu vào và kiểm tra xem có thể lật được bao nhiêu bánh rán trắng là xong.

Độ phức tạp: ~O(N^3)~, ~O(N^2 \log N)~ hoặc ~O(N^2)~ ~(N = 8)~ tùy cách cài đặt.

F - Doraemon, chú mèo máy đến từ tương lai

Ta có vài nhận xét sau:

• ~x \oplus x = 0~. (1)

• Nếu không bit ~1~ nào của ~x~ có cùng vị trí với bit ~1~ của ~y~ (2) thì ~x \oplus y = x + y~.

• Do ~M \leq 10^9~ nên bit có giá trị cao nhất có thể của ~M~ là ~30~ (Do ~2^{30} = 1073741824 > 10^9~). (3)

• Nếu ~M | x~ và ~M | y~ (4) thì ~M | (x + y)~.

Không mất tính tổng quát, giả sử ~x \leq y \leq z~. Ta có ~x \oplus y \oplus z = 0 \Leftrightarrow x \oplus y = z~ (1). Nếu ta có thể tìm được ~x~ và ~y~ thỏa mãn (2) và (4) thì khi ta lấy ~z = x + y~ thì ta sẽ có ~1~ bộ ba ~(x, y, z)~ thỏa mãn. Dựa vào ~(3)~, ta có thể chọn ~x = M~ và ~y = M \times 2^{30}~.

Vậy ~1~ bộ ba có thể là ~x = M, y = M \times 2^{30}, z = M + M \times 2^{30}~.

Độ phức tạp: ~O(T)~

G - Doraemon và thử thách đầu tiên [Bản khó]

Đầu tiên ta sẽ loại bỏ hết các hàng và cột không có quái vật nào vì chúng không quan trọng trong bài này.

Gọi ~X~ và ~Y~ là số hàng và cột có quái vật ~(1 \leq X \leq N, 1 \leq Y \leq M)~.

Ta ánh xạ một cách tô màu với một đường đi từ ô ~(0, 0)~ đến ô ~(X, Y)~ như sau:

Xuất phát tại ô ~(0, 0)~, tại một thời điểm mà ta đang đứng ở ô ~(x, y)~, ta đi sang ô ~(x + 1, y)~ nếu ô ~(x + 1, y)~ là ô cuối cùng có màu của hàng ~x + 1~, nếu không ta đi sang ô ~(x, y + 1)~, và ô ~(x, y + 1)~ là ô cuối cùng có màu của cột ~y + 1~ (vì nếu cả hai không phải ô cuối cùng thì ô ~(x + 1, y + 1)~ sẽ có màu của cả hàng ~x + 1~ và cột ~y + 1~).

Ánh xạ là đơn ánh vì với mỗi cách tô màu, ta có một và chỉ một cách đi. Ánh xạ là toàn ánh vì với mỗi cách đi ta chỉ có một cách tô màu. Cách biến đổi từ đường đi về một cách tô màu như sau:

Giả sử ta đang đứng tại vị trí ~(x, y)~. Nếu tại lượt sau ta đi sang ô ~(x + 1, y)~ thì ô này phải là ô cuối cùng có màu của hàng ~x + 1~. Ta tô các ô từ ~(x + 1, 1)~ đến ~(x + 1, y)~ bằng màu của hàng ~x + 1~, sau đó tiếp tục làm tiếp. Khi đến một ô ~(x, y)~, ta đã tô màu cả bảng từ ~(1, 1)~ đến ~(x, y)~ nên sau khi làm xong tất cả các ô đều được tô màu.

Vậy ánh xạ là song ánh, suy ra số cách tô màu bằng số đường đi từ ô ~(0, 0)~ đến ô ~(X, Y)~ hay ~\binom{X + Y}{X}~.

Ở dưới là một ví dụ về ánh xạ giữa cách tô màu và đường đi:

Độ phức tạp: ~O(N \log N)~ hoặc ~O(N)~ tùy vào cách cài đặt.