Author: Felix Halim
We should have noticed the following property. If a bracket begins with a positive sign, then nothing will change. If a bracket begins with a negative sign, then all operators within the bracket will be inverted (plus become minus, and vice versa). It means that only brackets with negative sign could change the value of the expression.
1 - (2 - 3 + 4) = 1 - 2 + 3 - 4 1 + (2 - 3 + 4) = 1 + 2 - 3 + 4 1 + (2 - (3 + 4)) = 1 + 2 - 3 - 4
Any expression with brackets has an equivalent expression that use no bracket. So, we can simulate the process of evaluating the expression in the following way. Start from the left most operand, move to the right and process each operator. At any operator in the expression, we always have three options:
– keep going, evaluate the value normally.
– put an open bracket, only if the operator is a negative sign (minus).
– put a close bracket, only if we have at least one open bracket before the operator.
To do this, I used a recursive structure with three arguments: f(x, p, curr); where x is the current index of operators, p is the number of open brackets before x, and curr is the evaluated value of all numbers before x.
To evaluate the current operator in any position (to find out whether it should be a plus or a minus), we just need to count how many open brackets are there before that operator. Remember, we only put open brackets behind negative signs. If the number of open bracket is odd, then invert the current operator, otherwise don’t change anything.
If we reach the end of the expression, then mark the value (curr) as visited. It means that there is a valid expression which evaluated to the value. Note that the value could be anywhere between -3000 and 3000. As we do the simulation, we might encounter repeating state. To prevent this, just mark the states that have been visited.
The overall time-complexity of this process is O(N3 . L) where N <= 30, and L <= 100.
In this problem, top-down/recursive does run faster than plain bottom-up approach. I have observed the behaviour of the recursive structure with many possible cases, and I never found any case which made the memo-table filled by more than 20%. Kurniady once wrote a plain bottom-up approach and failed the time-limit (it need more than 10s to process all the cases, while mine and Felix’s solution need no more than 1s). Somehow, he was able to prune the search process in his bottom-up solution, and it made his solution became as fast as mine.
This problem was solved by 3 teams: Seed (112), Joy (133) and Far (298).
- Title Page
- Problem A – Anti Brute Force Lock
- Problem B – Bonus Treasure
- Problem C – Panda Land 7: Casino Island
- Problem D – Disjoint Paths
- Problem E – Expert Enough?
- Problem F – Free Parentheses
- Problem G – Greatest K-Palindrome Substring
- Problem H – Hyper-Mod
- Problem I – ICPC Team Strategy
- Problem J – Jollybee Tournament