You are given a sequence S of length at most 100 consisting of integers which represents brackets. A negative integer -x is an opening bracket of type x while x is a closing bracket of type x.
A balanced sequence of brackets is defined as usual (see the full problem statement for clarity).
We call a subsequence s of S valid if and only if s is a balanced sequence of brackets. Your task is to count the number of valid subsequences of S modulo 10^9 + 7.
Define a dp[i][j] table where dp[i][j] := number of valid subsequence of S[i…j]. Notice that you can compute dp[i][j] if you know dp[i + 1][j] and positions of a closing bracket of type x in range from i + 1 to j if S[i] is an opening bracket of type x.
Since input numbers can be quite large (up to 10^9) we want to compress them at the beginning in order to use them as array indices or use a hash table with O(1) lookup and insert time to do this.
Let pos[i][j][x] := list of positions of occurences of closing bracket of type x in S[i…j]
We can compute pos table in O(n^3) time using simple iteration over all 3 dimensions of it.
Let dp[i][j] := number of valid subsequences of S[i…j]
For simplicity, let’s set dp[i][j] := 1 for i > j.
Let’s assume that we have dp[i + 1][j] already computed. We want to extend it to dp[i][j]. There are two cases:
- We don’t take a bracket at the i-th position, so dp[i][j] += dp[i + 1][j]
- If the bracket at the i-th position is an opening bracket of type x, we can try to take it to our subsequence.
While the first case is clear, the second one requires an explanation. If there are k closing brackets of type x in S[i + 1…j] we have k different possibilities to extend shorter subsequences, i.e. dp[i][j] += dp[i + 1][b - 1] * dp[b + 1][j] where b is a single position of a closing bracket of type x in S[i + 1…j]. Since we have pos table computed, we can get values for b using a quick lookup.
The time complexity is O(N^3) because computing pos and dp tables takes this much time and any other computation step doesn’t have greater complexity.
AUTHOR’S AND TESTER’S SOLUTIONS:
To be uploaded soon.
To be uploaded soon.