Classical BFS Problem – UVa 10400 – Game Show Math

Problem Statement

You can find the official problem statement here.

Given a list of no more than 100 numbers and a target number. You need to insert signs (addition, subtraction, multiplication, and division) in between the numbers, to get the final result.

Note that the problem states that ” The expression should be read from left to right, without regard for order of operations, to calculate the target number. ” So that, when you are calculating the result, you can disregard the orders of operations.

Algorithm

This is a kind of problem that asks you to try all the possibilities. These problems can generally be solved using one of the searching methods (DFS, BFS), and pruning (returning false on invalid cases) is usually used to reduce the running time.

For this problem specifically, I find BFS especially suitable for solving.

Each state should contain 2 parameters: The current term in the number sequence, and also the result of the expression up to the current term.

It is also suggested to maintain all the existing signs used up the current term in a string, so the expression can be recovered later.

Things to keep in mind

  • The order of operation does not matter here
  • Only do division if there is no remainder
  • When evaluating the expression, the result up to each term can only be in the bounds of [-32000, 32000]
  • Make sure to output “NO EXPRESSION” when there is no possible solutions

Coding

Additional note: make sure you maintain an array of if the {current term, current result} pair is visited or not. You will not be able to pass (TLE) if you don’t do that.

BFS Function:

bool dfs(int nextTerm, int currentResult, string signs){
    if (nextTerm == N){
        if (currentResult == target) {
            result = signs;
            return true;
        }
        return false;
    }

    if (currentResult > 32000 || currentResult < -32000) return false;
    if (visited[nextTerm][currentResult + 32001]) return false;
    visited[nextTerm][currentResult + 32001] = true;

    bool ans = false;

    if (dfs(nextTerm + 1, currentResult + numbers[nextTerm], signs + "+"))
        return true;

    if (dfs(nextTerm + 1, currentResult - numbers[nextTerm], signs + "-"))
        return true;

    if (dfs(nextTerm + 1, currentResult * numbers[nextTerm], signs + "*"))
        return true;

    if (currentResult % numbers[nextTerm] == 0)
        if (dfs(nextTerm + 1, currentResult / numbers[nextTerm], signs + "/"))
            return true;

    return false;
}

There is another thing that needs attention is that, you need to “pad” the currentResult to currentResult + 32001 to avoid the negative index in the visited array.

if (currentResult > 32000 || currentResult < -32000) return false;
if (visited[nextTerm][currentResult + 32001]) return false;
visited[nextTerm][currentResult + 32001] = true;

You also need to make the size of the visited array 2 times bigger than 32000.

bool visited[101][70000];

You can find the full version of my source code here.

Leave a Reply

Your email address will not be published. Required fields are marked *