Screen record - VNOI CUP 2022 - Round 3
đã đăng vào 3, Tháng 7, 2022, 4:34Đâ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