Skip to content

2019. The Score of Students Solving Math Expression

  • Time: $O(|\texttt{s}|^5 + n)$
  • Space: $O(|\texttt{s}|^3 + n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
 public:
  int scoreOfStudents(string s, vector<int>& answers) {
    const int n = s.length() / 2 + 1;
    const unordered_map<char, function<int(int, int)>> func{
        {'+', plus<int>()}, {'*', multiplies<int>()}};
    int ans = 0;
    vector<vector<unordered_set<int>>> dp(n, vector<unordered_set<int>>(n));
    unordered_map<int, int> count;

    for (int i = 0; i < n; ++i)
      dp[i][i].insert(s[i * 2] - '0');

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        for (int k = i; k < j; ++k) {
          const char op = s[k * 2 + 1];
          for (const int a : dp[i][k])
            for (const int b : dp[k + 1][j]) {
              const int res = func.at(op)(a, b);
              if (res <= 1000)
                dp[i][j].insert(res);
            }
        }
      }

    const int correctAnswer = eval(s);

    for (const int answer : answers)
      ++count[answer];

    for (const auto& [answer, freq] : count)
      if (answer == correctAnswer)
        ans += 5 * freq;
      else if (dp[0][n - 1].contains(answer))
        ans += 2 * freq;

    return ans;
  }

 private:
  int eval(const string& s) {
    int ans = 0;
    int prevNum = 0;
    int currNum = 0;
    char op = '+';

    for (int i = 0; i < s.length(); ++i) {
      const char c = s[i];
      if (isdigit(c))
        currNum = currNum * 10 + (c - '0');
      if (!isdigit(c) || i == s.length() - 1) {
        if (op == '+') {
          ans += prevNum;
          prevNum = currNum;
        } else if (op == '*') {
          prevNum = prevNum * currNum;
        }
        op = c;
        currNum = 0;
      }
    }

    return ans + prevNum;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
  public int scoreOfStudents(String s, int[] answers) {
    final int n = s.length() / 2 + 1;
    int ans = 0;
    Set<Integer>[][] dp = new Set[n][n];
    Map<Integer, Integer> count = new HashMap<>();

    for (int i = 0; i < n; ++i)
      for (int j = i; j < n; ++j)
        dp[i][j] = new HashSet<>();

    for (int i = 0; i < n; ++i)
      dp[i][i].add(s.charAt(i * 2) - '0');

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        final int j = i + d;
        for (int k = i; k < j; ++k) {
          final char op = s.charAt(k * 2 + 1);
          for (final int a : dp[i][k])
            for (final int b : dp[k + 1][j]) {
              final int res = func(op, a, b);
              if (res <= 1000)
                dp[i][j].add(res);
            }
        }
      }

    final int correctAnswer = eval(s);

    for (final int answer : answers)
      count.merge(answer, 1, Integer::sum);

    for (final int answer : count.keySet())
      if (answer == correctAnswer)
        ans += 5 * count.get(answer);
      else if (dp[0][n - 1].contains(answer))
        ans += 2 * count.get(answer);

    return ans;
  }

  private int eval(final String s) {
    int ans = 0;
    int currNum = 0;
    int prevNum = 0;
    char op = '+';

    for (int i = 0; i < s.length(); ++i) {
      final char c = s.charAt(i);
      if (Character.isDigit(c))
        currNum = currNum * 10 + (c - '0');
      if (!Character.isDigit(c) || i == s.length() - 1) {
        if (op == '+') {
          ans += prevNum;
          prevNum = currNum;
        } else if (op == '*') {
          prevNum = prevNum * currNum;
        }
        op = c;
        currNum = 0;
      }
    }

    return ans + prevNum;
  }

  private int func(char op, int a, int b) {
    if (op == '+')
      return a + b;
    return a * b;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
  def scoreOfStudents(self, s: str, answers: list[int]) -> int:
    n = len(s) // 2 + 1
    ans = 0
    func = {'+': operator.add, '*': operator.mul}
    dp = [[set() for j in range(n)] for _ in range(n)]

    for i in range(n):
      dp[i][i].add(int(s[i * 2]))

    for d in range(1, n):
      for i in range(n - d):
        j = i + d
        for k in range(i, j):
          op = s[k * 2 + 1]
          for a in dp[i][k]:
            for b in dp[k + 1][j]:
              res = func[op](a, b)
              if res <= 1000:
                dp[i][j].add(res)

    correctAnswer = eval(s)

    for answer, freq in collections.Counter(answers).items():
      if answer == correctAnswer:
        ans += 5 * freq
      elif answer in dp[0][n - 1]:
        ans += 2 * freq

    return ans