{x}
blog image

The Score of Students Solving Math Expression

You are given a string s that contains digits 0-9, addition symbols '+', and multiplication symbols '*' only, representing a valid math expression of single digit numbers (e.g., 3+5*2). This expression was given to n elementary school students. The students were instructed to get the answer of the expression by following this order of operations:

  1. Compute multiplication, reading from left to right; Then,
  2. Compute addition, reading from left to right.

You are given an integer array answers of length n, which are the submitted answers of the students in no particular order. You are asked to grade the answers, by following these rules:

  • If an answer equals the correct answer of the expression, this student will be rewarded 5 points;
  • Otherwise, if the answer could be interpreted as if the student applied the operators in the wrong order but had correct arithmetic, this student will be rewarded 2 points;
  • Otherwise, this student will be rewarded 0 points.

Return the sum of the points of the students.

 

Example 1:

Input: s = "7+3*1*2", answers = [20,13,42]
Output: 7
Explanation: As illustrated above, the correct answer of the expression is 13, therefore one student is rewarded 5 points: [20,13,42]
A student might have applied the operators in this wrong order: ((7+3)*1)*2 = 20. Therefore one student is rewarded 2 points: [20,13,42]
The points for the students are: [2,5,0]. The sum of the points is 2+5+0=7.

Example 2:

Input: s = "3+5*2", answers = [13,0,10,13,13,16,16]
Output: 19
Explanation: The correct answer of the expression is 13, therefore three students are rewarded 5 points each: [13,0,10,13,13,16,16]
A student might have applied the operators in this wrong order: ((3+5)*2 = 16. Therefore two students are rewarded 2 points: [13,0,10,13,13,16,16]
The points for the students are: [5,0,0,5,5,2,2]. The sum of the points is 5+0+0+5+5+2+2=19.

Example 3:

Input: s = "6+0*1", answers = [12,9,6,4,8,6]
Output: 10
Explanation: The correct answer of the expression is 6.
If a student had incorrectly done (6+0)*1, the answer would also be 6.
By the rules of grading, the students will still be rewarded 5 points (as they got the correct answer), not 2 points.
The points for the students are: [0,0,5,0,0,5]. The sum of the points is 10.

 

Constraints:

  • 3 <= s.length <= 31
  • s represents a valid expression that contains only digits 0-9, '+', and '*' only.
  • All the integer operands in the expression are in the inclusive range [0, 9].
  • 1 <= The count of all operators ('+' and '*') in the math expression <= 15
  • Test data are generated such that the correct answer of the expression is in the range of [0, 1000].
  • n == answers.length
  • 1 <= n <= 104
  • 0 <= answers[i] <= 1000

Solution Explanation: Dynamic Programming (Interval DP)

This problem asks to calculate the total score of students' answers to a mathematical expression. The expression contains single-digit numbers, addition, and multiplication. Students might make mistakes in the order of operations. The scoring is as follows:

  • Correct answer: 5 points
  • Correct arithmetic with incorrect order of operations: 2 points
  • Incorrect arithmetic: 0 points

The solution uses dynamic programming with an interval DP approach. Let's break down the process:

1. Correct Calculation (cal function):

A helper function cal is defined to compute the correct answer to the given mathematical expression by strictly following the order of operations (multiplication first, then addition, from left to right). This establishes the baseline for comparison.

2. Dynamic Programming (Interval DP):

  • State: f[i][j] represents a set of possible results obtained by evaluating the subexpression from index i to j (inclusive). Indices i and j refer to the digit positions in the expression string. The expression has digits interleaved with operators.
  • Base Case: f[i][i] contains only the single digit at the i-th position.
  • Transition: The key idea is to iterate through all possible splitting points k between i and j. For each k, we consider the results from f[i][k] and f[k+1][j]. We combine these results based on the operator (+ or *) at position k. The union of all possible results across all k forms f[i][j].

3. Counting the Score:

  • A counter cnt stores the frequency of each answer in the answers array.
  • The total score is calculated by iterating through cnt:
    • If an answer matches the correct answer x (calculated using cal), it adds 5 points times the frequency.
    • If an answer is in f[0][m-1] (the set of all possible results for the entire expression) but is not the correct answer, it adds 2 points times the frequency.

Time Complexity: O(n³ * M²)

  • The nested loops for the dynamic programming part have a cubic time complexity (O(n³)). 'n' is approximately half the length of the input string s, representing the number of digits.
  • The set operations (union, add, contains) within the loops can take up to O(M²) time in the worst case, where 'M' is the maximum possible answer value (1000 in this case). This is because set operations might require comparisons between elements in the sets.

Space Complexity: O(n² * M)

  • The f array uses O(n²) space to store the sets of possible results.
  • Each set can potentially contain up to 'M' elements.

Code Explanation (Python):

The provided Python code implements this dynamic programming solution efficiently. It uses Python's set data structure to manage the possible results for each interval. The Counter object simplifies counting answer frequencies. The cal function computes the correct answer based on the order of operations.

The code in other languages (Java, C++, Go, TypeScript) implements the same algorithm with equivalent data structures and logic for their respective languages. The core dynamic programming approach remains consistent across all implementations.