Screen record - VNOI CUP 2022 - Round 3
BJMinhNhut
đã đă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