Reading and Modeling a Problem

Extract inputs/outputs, constraints, edge cases, invariants, and expected complexity.

Extract inputs/outputs, constraints, edge cases, invariants, and expected complexity. Translate the story into arrays, graphs, intervals, states, or optimization variables.

A modeling checklist

Restate the task in one sentence with precise inputs and outputs.

Read the constraints — they suggest the target complexity (Module 58).

Name the objects: items with positions (array), relations (graph), time spans (intervals), choices over time (states for DP or search).

Find what changes and what is fixed: updates versus queries, online versus offline.

List edge cases before coding: empty input, one element, duplicates, extremes, disconnected parts.

Pick the simplest correct algorithm, then optimise only if the constraints demand it.

Worked example

*A warehouse robot moves on a grid of free cells and shelves. Moving to a neighbouring cell takes 1 second; some cells are conveyor tiles that carry the robot one cell in a fixed direction for free. Find the fastest route from the dock to a target cell.*

Objects: cells are vertices, moves are edges.

Weights: ordinary moves cost 1, conveyor moves cost 0 → a 0–1 graph.

Algorithm: 0–1 BFS (Module 29) in O(cells); Dijkstra would also work but is slower; plain BFS would be wrong because it treats every edge as cost 1.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<string> g = {"D>>>>.", "#####.", "T....."};   // D dock, T target, > conveyor (moving east from it is free), # shelf
    int R = 3, C = 6, sr = 0, sc = 0, tr = 2, tc = 0;
    vector<vector<int>> d(R, vector<int>(C, INT_MAX));
    deque<pair<int, int>> dq; d[sr][sc] = 0; dq.push_back({sr, sc});
    int dr[] = {0, 1, 0, -1}, dc[] = {1, 0, -1, 0};
    while (!dq.empty()) {
        auto [r, c] = dq.front(); dq.pop_front();
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C || g[nr][nc] == '#') continue;
            int w = (g[r][c] == '>' && k == 0) ? 0 : 1;              // conveyor carries east for free
            if (d[r][c] + w < d[nr][nc]) { d[nr][nc] = d[r][c] + w; w ? dq.push_back({nr, nc}) : dq.push_front({nr, nc}); }
        }
    }
    cout << "fastest route to T: " << d[tr][tc] << " seconds\n";
    // the same grid with every move costing 1 (plain BFS)
    vector<vector<int>> b(R, vector<int>(C, -1)); queue<pair<int, int>> q; b[sr][sc] = 0; q.push({sr, sc});
    while (!q.empty()) { auto [r, c] = q.front(); q.pop(); 
…

fastest route to T: 8 seconds
plain BFS (ignoring the conveyors) would report 12 moves

Quiz

? A story says “some moves are free, others take one unit of time.” Which algorithm fits best?
+ 0–1 BFS :: Linear time for weights 0 and 1.
- Plain BFS :: Treats every move as cost 1.
- Floyd–Warshall :: All pairs, O(V³).
- DFS :: Does not give shortest paths.

? What should you write down before coding? (select all that apply)
+ Exact inputs, outputs and constraints :: They determine the algorithm.
+ Edge cases :: Empty, single, duplicates, extremes.
+ The objects and relations (array, graph, intervals, states) :: The model.
- The final code's line count :: Irrelevant.

? Why read the constraints early?
+ They indicate the complexity the solution must meet :: Module 58.
- They are always generous :: No.
- To choose a programming language :: Not mainly.
- They never matter in interviews :: They do.