First we sort the array in a decreasing order, and calculate the prefix sum. Then, we find the prefix sum with the minimum index that is not less than the target value.
At first, we find the largest integer in the given sequence, denoted as db. Then, we start testing from base db + 1 to 70 (it is sufficiently safe to choose any integer that is larger than 60). If there is no feasible base, the answer is 0. If 70 is also a feasible base, the answer is -1 since there must be infinite bases that satisfy the requirements.
Suppose that all the elements are sorted as a1 < a2 < ... < an.
If n is even, we can divide them into two groups consisting of (a1, a3, ...an - 1) and (a2, a4, ...an), respectively. The proof is that an - |(a2 + a4 + ...) - (a1 + a3 + ...)| = an - 1 - an - 2 + an - 3 - an - 4 + ... + a3 - a2 + a1 ≥ 0.
If n is odd, we can divide them into two groups consisting of (a3, a5, ...an) and (a1, a2, a4, ...an - 1), respectively. The proof is similar if one computes an - |(a3 + a5 + ...) - (a1 + a2 + a4 + ...)|, and thus omitted here.
The main idea is DFS with memorization (I learned from turotials).
We can build a function dfs(l, r, c1, c2), where l, r are the left and right border of the range that we are considering, inculsively, while (c1, c2) are the colors for the brackets at the two borders. Before implementing dfs, we should calculate for each “(”, which “)” matches with it. Note that for the overall sequence, we can divide it into multiple independent subsequences with smaller size. For instance, “(())()()” can be first divided into “(())” and “()()”, and the second part can be further divided into two parts “()” and “()”. This is similar to the idea of divide and conquer, i.e., we divide the original problem into subproblems with smaller size, and solve them seperately, and finally combine their solutions together to obtain the solution to the original problem. This is in fact how our dfs function works. However, trivial dfs leads to TLE due to the huge number of nodes to visit, and thus we should adopt another array dp[l][r][c1][c2] to store the results that we have obtained to reduce the consumed time.
Here are some key issues involved in dfs function.
1) if dp[l][r][c1][c2] already has a value, we immediately return it;
2) if positions l and c correspond to a matched “( )”, we recursively call function dfs(l + 1, r - 1, c3, c4) where c3 and c4 denote the feasible colors for l + 1 and r - 1. Then, by some simple computation, we can obtain the answer. A special case is that l = r - 1 and the answer can be immediately obtained;
3) if brackets at l and r do not match, we find the position at which the bracket matches with that one at l, denoted as m (this implies that m + 1 and r forms another independent subproblem with smaller size), and then recursively call dfs to compute (l, m) and (m + 1, r), respectively.
4) due to the given constraints, some of the combination of colors are infrasible, and thus should not be considered.
This problem can be solved based on the well known KMP algorithm.
For each of the given small strings, we implement KMP algorithm. During this process, for every prefix substring, we store the minimum index at which it is found in the longer string. Furthermore, we reverse both the long and small string and repeat the above process again. Note that the “reversal” version in fact calculates the maximum index at which every suffix string is found in the long string. Thus, we divide the small string at different positions to obtain a prefix and a suffix, and check that if the minimum index of the prefix does not exceed the maximum index of the suffix, then the current small string can be seen.
Comments (0)
