AntInLoop

Problem Modeling (Translating Problems into Graphs & DP)

Problem Modeling maps real-world or word-problem scenarios onto canonical structures—graphs, DAGs, flow networks, intervals, or state machines—so standard algorithms solve them immediately.

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

Problem Modeling

The hardest step in competitive programming and system design is rarely coding the algorithm—it is recognizing what model hides beneath the story:

| Problem Signal | Canonical Model | Go-To Algorithm |

| :--- | :--- | :--- |

| "Minimum steps / moves / transformations" | Unweighted State Graph | BFS |

| "Prerequisites / ordering / dependencies" | Directed Acyclic Graph (DAG) | Topological Sort |

| "Connect everything with minimum cost" | Undirected Weighted Graph | Kruskal / Prim |

| "Minimize the maximum / maximize the minimum" | Monotonic Feasibility Predicate | Binary Search on Answer |

| "Pair left items with right items / cut dependencies" | Flow Network | Dinic's Max Flow |

---

Example: Modeling Word Ladder as Shortest Path in a Graph

Each word is a vertex; two words differing by 1 character share an undirected edge. Shortest transformation length = BFS distance!

<details>

<summary>Show C++ Example</summary>

#include <iostream>
#include <queue>
#include <string>
#include <unordered_set>
#include <vector>

int wordLadder(const std::string& begin, const std::string& end, const std::vector<std::string>& dict) {
    std::unordered_set<std::string> words(dict.begin(), dict.end());
    if (!words.count(end)) return 0;
    std::queue<std::pair<std::string, int>> q;
    q.push({begin, 1});
    words.erase(begin);

    while (!q.empty()) {
        auto [cur, dist] = q.front(); q.pop();
        if (cur == end) return dist;
        for (size_t i = 0; i < cur.size(); ++i) {
            char orig = cur[i];
            for (char c = 'a'; c <= 'z'; ++c) {
                cur[i] = c;
                if (words.erase(cur)) q.push({cur, dist + 1});
            }
            cur[i] = orig;
        }
    }
    return 0;
}

int main() {
    std::cout << wordLadder("hit", "cog", {"hot", "dot", "dog", "lot", "log", "cog"}) << "\n"; // 5
    return 0;
}

</details>

---

Related Topics