Travelling Salesman (Bitmask DP)

📋

Problem

Imagine a delivery driver who must visit multiple cities exactly once and return home, trying to minimize the total travel distance.

Given n cities and a distance matrix dist where dist[i][j] represents the cost to travel from city i to city j, find the minimum cost to start from city 0, visit every city exactly once, and return to city 0.

1 ≤ n ≤ 20dist[i][j] ≥ 0 for all 0 ≤ i, j < ndist[i][i] = 0 for all i

Edge cases: n = 1 → output 0 (only one city, no travel needed)All distances zero → output 0 (no cost to travel)Asymmetric distances (dist[i][j] != dist[j][i]) → ensure algorithm handles directed costs

</>

IDE

def tsp_brute_force(dist: list[list[int]]) -> int:public int tspBruteForce(int[][] dist)int tspBruteForce(vector<vector<int>> &dist)function tspBruteForce(dist)

def tsp_brute_force(dist):
    # Write your solution here
    pass

class Solution {
    public int tspBruteForce(int[][] dist) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int tspBruteForce(vector<vector<int>> &dist) {
    // Write your solution here
    return 0;
}

function tspBruteForce(dist) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Infinity or very large numberNot returning to start city after visiting all cities, missing base case.✅ Add base case: if mask == ALL_VISITED, return dist[current][0].

Wrong: Non-zero for single city inputFailing to handle n=1 base case, returning cost instead of zero.✅ If n == 1, return 0 immediately or handle base case in DP.

Wrong: Incorrect cost for asymmetric distancesAssuming dist[i][j] == dist[j][i], ignoring directionality.✅ Use dist[i][j] exactly as given without symmetry assumptions.

Wrong: Greedy path cost instead of optimalUsing greedy nearest neighbor heuristic instead of full DP.✅ Implement full bitmask DP exploring all subsets and transitions.

Wrong: Allowing repeated visits to citiesNot enforcing mask bits to prevent revisiting cities.✅ Use bitmask to track visited cities and disallow revisits.

✓

Test Cases

Focus on handling base cases and small inputs correctly before moving on.

Understand common pitfalls like greedy traps and enforcing 0/1 visit constraints.

Prepare for performance challenges by optimizing your DP implementation.

t1_01basic

Input{"n":4,"dist":[[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]}

Expected80

⏱ Performance - must finish in 2000ms

One optimal path is 0 -> 1 -> 3 -> 2 -> 0 with cost 10 + 25 + 30 + 15 = 80.

💡 Consider all permutations of cities and use bitmasking to track visited cities.

💡 Use bitmask DP to store minimum cost to reach a city with a given visited set.

💡 dp[i][mask] = min over j not in mask of dist[i][j] + dp[j][mask | (1 << j)]

Why it failed: Incorrect output means the DP state or transitions are wrong; ensure you include returning to city 0 after visiting all cities.

✓ Correctly computes minimum cost using bitmask DP.

t1_02basic

Input{"n":3,"dist":[[0,5,9],[5,0,3],[9,3,0]]}

Expected17

⏱ Performance - must finish in 2000ms

Optimal path 0 -> 1 -> 2 -> 0 with cost 5 + 3 + 9 = 17.

💡 Try enumerating all subsets of visited cities with bitmasking.

💡 Use memoization to avoid recomputing states.

💡 Remember to add cost to return to start city after visiting all cities.

Why it failed: If output is wrong, likely missing the cost to return to city 0 or incorrect mask updates.

✓ Correctly handles smaller input with bitmask DP.

t2_01edge

Input{"n":1,"dist":[[0]]}

Expected0

⏱ Performance - must finish in 2000ms

Only one city, no travel needed, cost is 0.

💡 Check base case when only one city exists.

💡 DP should return 0 immediately if all cities are visited at start.

💡 Return dist[i][0] only if mask equals all visited; here it's trivial.

Why it failed: Fails to handle single city case; fix by returning 0 when all cities visited and no travel needed.

✓ Correctly handles single city with zero cost.

t2_02edge

Input{"n":3,"dist":[[0,0,0],[0,0,0],[0,0,0]]}

Expected0

⏱ Performance - must finish in 2000ms

All distances zero, so minimum cost is zero regardless of path.

💡 Test if algorithm handles zero distances correctly.

💡 DP should not add any cost when distances are zero.

💡 Ensure no incorrect initialization to infinity or large values.

Why it failed: Incorrect output means algorithm adds unnecessary costs; fix initialization and transitions to handle zero distances.

✓ Correctly computes zero cost when all distances are zero.

t2_03edge

Input{"n":4,"dist":[[0,1,1000,1000],[1000,0,1,1000],[1000,1000,0,1],[1,1000,1000,0]]}

Expected4

⏱ Performance - must finish in 2000ms

Optimal path 0->1->2->3->0 with cost 1+1+1+1=4, testing asymmetric distances.

💡 Check if algorithm handles asymmetric distances correctly.

💡 DP must consider directed edges, not assume symmetry.

💡 Verify transitions use dist[i][j] as given, not dist[j][i].

Why it failed: Fails due to assuming symmetric distances; fix by using dist[i][j] exactly as input.

✓ Correctly handles asymmetric distance matrix.

t3_01corner

Input{"n":4,"dist":[[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]}

Expected80

⏱ Performance - must finish in 2000ms

Greedy approach fails here; optimal path is 0->1->3->2->0 with cost 80, not greedy choices.

💡 Greedy picking nearest city next may not yield optimal path.

💡 Use DP to consider all subsets and paths, not just local minima.

💡 Check all permutations via bitmask DP rather than greedy heuristics.

Why it failed: Greedy approach returns wrong cost; fix by implementing full bitmask DP instead of greedy.

✓ Correctly avoids greedy trap by exploring all subsets.

t3_02corner

Input{"n":5,"dist":[[0,2,9,10,1],[1,0,6,4,2],[15,7,0,8,3],[6,3,12,0,11],[10,4,8,5,0]]}

Expected21

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded knapsack style; must visit each city exactly once.

💡 Each city must be visited exactly once, no repeats allowed.

💡 DP mask ensures no city is visited twice.

💡 Avoid summing costs multiple times for same city.

Why it failed: Incorrect output due to allowing repeated visits; fix by enforcing mask bit set only once per city.

✓ Correctly enforces 0/1 visit constraint with bitmask.

t3_03corner

Input{"n":3,"dist":[[0,1,100],[1,0,1],[100,1,0]]}

Expected102

⏱ Performance - must finish in 2000ms

Off-by-one error test: path 0->1->2->0 costs 1+100+1=102; check mask and indices carefully.

💡 Verify mask bit indexing matches city indices exactly.

💡 Ensure base case triggers when all cities visited (mask == (1<<n)-1).

💡 Return cost to start city only after all cities visited.

Why it failed: Off-by-one in mask or city indexing causes wrong output; fix bitmask checks and base case condition.

✓ Correctly handles mask indexing and base case.

t4_01performance

Input{"n":20,"dist":[[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19],[1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18],[2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17],[3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],[4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],[5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14],[6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12,13],[7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11,12],[8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10,11],[9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,10],[10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9],[11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8],[12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7],[13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6],[14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5],[15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4],[16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3],[17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2],[18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1],[19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0]]}

Expectednull

⏱ Performance - must finish in 2000ms

n=20, O(n^2 * 2^n) complexity must complete within 2 seconds.

💡 Bitmask DP has exponential complexity; optimize state transitions.

💡 Use memoization or bottom-up DP with pruning if possible.

💡 Avoid recomputing states; store results in dp table.

Why it failed: TLE due to exponential complexity O(n^2 * 2^n); optimize DP or use heuristics for larger n.

✓ Algorithm runs within time limit confirming O(n^2 * 2^n) complexity handled.

Practice

1. You are given a binary tree where each node contains a non-negative integer value representing money. You want to maximize the amount of money you can rob without robbing two directly connected nodes (parent and child). Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming on trees using post-order traversal to consider robbing or skipping each node

B. Greedy algorithm that always robs the node with the highest value first

C. Simple recursion without memoization that tries all combinations

D. Breadth-first search to select nodes level by level

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing sum of node values without robbing adjacent nodes, which is a classic tree DP problem.

2. Step 2: Identify suitable algorithm

   Greedy and BFS fail because they don't consider subtree dependencies; simple recursion is exponential. DP on trees with post-order traversal correctly aggregates rob/not_rob states bottom-up.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP on trees handles adjacency constraints optimally [OK]

Hint: Tree DP with post-order traversal handles adjacency constraints [OK]

Common Mistakes:

• Thinking greedy or BFS can solve adjacency constraints optimally

2. The following code attempts to find the longest chain of pairs but contains a subtle bug. Identify the line causing incorrect results on some inputs.

medium

A. Line 10: Checking if pair[0] > current_end

B. Line 7: Initializing current_end to negative infinity

C. Line 4: Sorting pairs by their start values

D. Line 12: Updating current_end to pair[1]

Solution

1. Step 1: Analyze sorting step

   Sorting by start values does not guarantee optimal chain selection in greedy approach.

2. Step 2: Impact on chain selection

   Greedy selection after sorting by start can miss longer chains that sorting by end would find.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting by end is required for correctness [OK]

Hint: Sort by end, not start, for greedy correctness [OK]

Common Mistakes:

• Sorting by start and expecting greedy to work
• Misunderstanding greedy selection criteria
• Assuming initialization or condition is faulty

3. What is the time complexity of the optimized Fenwick Tree based algorithm for counting the number of longest increasing subsequences in an array of length n with values bounded by W (maximum distinct values)?

medium

A. O(n log n) because sorting the array dominates the complexity

B. O(n²) because each update and query can take O(n) in worst case

C. O(n log W) because each Fenwick tree update and query takes O(log W) and we do n such operations

D. O(n) because Fenwick tree operations are constant time

Solution

1. Step 1: Identify Fenwick tree operations cost

   Fenwick tree update and query each take O(log W), where W is the size of the Fenwick tree (number of distinct values).

2. Step 2: Count total operations

   We perform n updates and n queries, so total time is O(n log W). Sorting takes O(n log n), but W ≤ n, so O(n log W) dominates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Fenwick tree operations are logarithmic in size, repeated n times [OK]

Hint: Fenwick tree operations cost O(log W), not O(n) [OK]

Common Mistakes:

• Assuming Fenwick updates are O(n)
• Confusing n and W in complexity
• Ignoring sorting cost

4. The following code attempts to solve the Russian Doll Envelopes problem. Identify the line that contains a subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: Sorting envelopes by width ascending and height ascending

B. Line 6: Extracting heights from envelopes

C. Line 8: Using bisect_left to find insertion index

D. Line 11: Replacing element in lis at found index

Solution

1. Step 1: Examine sorting order

   Sorting by width ascending and height ascending causes envelopes with same width but increasing height to be counted incorrectly in LIS.

2. Step 2: Understand LIS requirement

   Heights must be sorted descending for equal widths to avoid counting invalid envelopes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting order bug leads to wrong LIS and incorrect nesting count [OK]

Hint: Sort height descending for equal widths to avoid LIS errors [OK]

Common Mistakes:

• Sorting both dimensions ascending instead of height descending
• Misusing bisect functions
• Incorrectly extracting heights

5. Suppose the problem is modified so that the path can reuse nodes multiple times (i.e., cycles allowed), and the tree is now a general graph with possible cycles. Which of the following approaches correctly adapts the maximum path sum solution to handle this variant?

hard

A. Use the same DP on tree approach with memoization, ignoring cycles since the graph is connected

B. Convert the graph to a tree by removing edges to break cycles, then apply the original DP on tree solution

C. Perform a DFS with cycle detection and use dynamic programming with visited states to avoid infinite loops, tracking maximum sums on simple paths

D. Use a greedy approach to select the highest value nodes repeatedly until no improvement

Solution

1. Step 1: Understand the impact of cycles

   Allowing node reuse and cycles means paths can be infinite unless cycles are detected and handled.

2. Step 2: Identify correct approach

   DFS with cycle detection and DP with visited states prevents infinite loops and correctly computes max sums on simple paths in graphs.

3. Step 3: Why other options fail

   Original DP assumes tree structure; greedy ignores path connectivity; converting graph to tree loses valid paths.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Cycle-aware DFS with DP is necessary for graphs with cycles [OK]

Hint: Cycle detection plus DP needed for graphs with cycles [OK]

Common Mistakes:

• Ignoring cycles causes infinite loops
• Greedy fails on path connectivity
• Tree DP invalid on graphs