Đây là clip ghi lại quá trình làm Round 3 VNOI CUP 2022 của mình, mong mọi người thích. Link Youtube: https://youtu.be/RnphZbtQp3k

Round 3 này mình thấy đề có vẻ khó hơn Round 1, (tiếc là mình không làm Round 2 nên không so sánh được). Mình bug khá ngu ở bài A, tuy nhiên thì bài B và các sub ở bài C và E mình làm khá mượt nên may mắn được lên rank 36 :33.

Sau đây là ý tưởng của mình cho các bài/subtask mình đã làm được:

• Bài A:

Đây là một bài Adhoc với một chút toán. Nhận xét quan trọng nhất chính là số nước đi tối đa là ~2~. Và chia từng trường hợp cho các nước đi. Trường hợp in ra ~-1~ là khi ô xuất phát và ô đích khác màu nhau.

• Bài B:

Nhận xét của mình là số thao tác sẽ bằng số cặp () ở trong chuỗi đang xét. Từ đó mình dựng một mảng tiền tố tính tổng các vị trí có () trong chuỗi, rồi trả lời trong ~O(1)~.

• Sub 3 Bài C:

Bài này mình chỉ làm được đến Sub 3. Nhận xét của mình là để một con robot có độ cao X nào đó, thì các cây táo mà nó có tham gia đều có độ cao X trong kế hoạch. Từ đó suy ra mỗi con robot có tối đa 2 giá trị cần thử. Vì vậy mình quay lui sau đó kiểm tra để tìm kết quả trong ~O(2^n \cdot m)~.

• Sub 1 Bài E:

Bài này mình làm được Sub 1, có lẽ bài này khá khó nên không ai AC bài này trong thời gian diễn ra contest. Ở sub 1 mình nhận thấy số trạng thái của các hũ gạo là không nhiều ~(6^6)~. Vì vậy mình bfs từ trạng thái ban đầu để tìm kết quả, với chi phí chuyển mỗi trạng thái là ~O(n^2)~. Độ phức tạp vào khoảng ~O(6^6 \cdot 6^2 \cdot log_2(6^6))~ do mình dùng map và vector để lưu các trạng thái.

Tóm lại thì contest này mình thấy mình khá là choke bài C khi các bạn có cùng điểm ~300~ với mình đa số AC bài này. :sadge:

Follow me on:

📍Codeforces: https://codeforces.com/profile/BJMinhNhut

📍VNOJ: https://oj.vnoi.info/user/BJMinhNhut

📍Facebook: https://www.facebook.com/pusheentapcode