15. 0-1 BFS & Deque Optimization | (AtCoder Small Multiple)

Diving deeper into Phase 4 with a masterclass in weight optimization. In this lecture, we tackle AtCoder "Small Multiple" and introduce the 0-1 BFS algorithm using a Double-Ended Queue (std::deque).

When traversing a state space where edge weights are strictly either 0 or 1, standard BFS fails and Dijkstra's algorithm is computationally wasteful. We break down how to map the digit sum operations into a binary-weighted graph: multiplying by 10 costs 0 (push to the front), while adding 1 costs 1 (push to the back). By routing these modulo remainders through a deque, we guarantee the absolute shortest path in strict O(K) time.

🔗 Problem Link: https://atcoder.jp/contests/arc084/tasks/arc084_b

👋 𝐖𝐞𝐥𝐜𝐨𝐦𝐞 𝐭𝐨 𝐭𝐡𝐞 𝐜𝐡𝐚𝐧𝐧𝐞𝐥!⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣ ⁣⁣⁣⁣⁣⁣
I create content on Competitive Programming, Data Structures & Algorithms (DSA), and now Software Development with Go.
If you find this video helpful, don’t forget to:
👍 Like the video
💬 Comment your doubts/questions (I reply to everyone!)
🔔 Subscribe and turn on notifications to never miss upcoming tutorials
⁣⁣⁣⁣⁣⁣
📌 𝐂𝐨𝐧𝐧𝐞𝐜𝐭 𝐰𝐢𝐭𝐡 𝐦𝐞:⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣ ⁣⁣⁣⁣⁣⁣
🐦 X: https://x.com/Yash_Poonia_
💼 LinkedIn: https://www.linkedin.com/in/yashpoonia/
💻 GitHub: https://github.com/yash7xm/
🌐 Discord: https://discord.gg/dAp2PbKFpV

#BFS #CompetitiveProgramming #GraphTheory #AtCoder #Algorithms #Cplusplus #SoftwareEngineering

Видео 15. 0-1 BFS & Deque Optimization | (AtCoder Small Multiple) канала Yash Poonia