dragoon's blog

By dragoon, 13 years ago, In English
Can any one help?
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Well, this can be solved by greedy approach suggested by Nerevar. Let's move from left to right in our sequence. Let's analyse the current symbol. If it's an open bracket, let's increase the balance by 1. If it's a closing bracket, decrease the balance by 2. If it's a question symbol, replace it with a close bracket and decrease the balance by 1 (don't forget to increase the total price by the price of close bracket). Also for each question symbol store it in a priority queue in ascending order according to price transformation Ai-Bi, that is how much it would take to replace this close bracket with an open one.  Now, if at any time the balance becomes negative, find the close bracket with the cheapest cost and replace it with open bracket (don't forget to increase the total price by cost transformation) and increase the balance by 2.
The sequence is impossible to construct, if for a negative balance we do not have any close brackets earlier that can be replaced by open, or if the final balance is not equal to 0 (that means the number of open brackets is greater than the number of close brackets).
The formal proof here can be found by using the standard greedy approaches.