Editorial for Chat Order, The Festive Evening, Longest Regular Bracket Sequence

Problem Discussed Today: 
  1. Chat Order ( 637B )
  2. The Festive Evening ( 834B )
  3. Longest Regular Bracket Sequence ( 5C )

This is a simple problem that can be solved by assigning some weights to the incoming person's messages. It is given that there n messages that will be coming and the most recent message will be displayed at the top, then the second recent message, etc.

To solve this we will be using Map and Sets. The set will contain a distinct person's name and Map will have the relative weight. For example, we will take a look at the first test case,

Here set will contain { alex, ivan, roman } and by mapping, we will get alex=4, ivan=1, roman=3. Now we will traverse the set and make a vector of pairs that will contain { relative weight from map, name }. Now sort this in increasing order of weight and print the names.

Solution Link: Solution

This problem is solved with two linear sweeps. In the first one, we determine the last position for each letter. In the second one, we just model the process: we mark the letter as active when we stumble upon it for the first time, and as inactive when we reach the last position for this letter. If there are more than k letters active at some specific point of time, we output "YES". Otherwise, we output "NO".

Solution Link: Solution

First of all, for each closing bracket in our string let's define 2 values:
  • d[j] = position of corresponding open bracket, or -1 if closing bracket doesn't belong to any regular bracket sequence.
  •  c[j] = position of earliest opening bracket, such that substring s(c[j], j) (both boundaries are inclusive) is a regular bracket sequence. Let's consider c[j] to be -1 if the closing bracket doesn't belong to any regular bracket sequence.
It can be seen, that c[j] defines the beginning position of the longest regular bracket sequence, which will end in position j. So, having c[j] answer for the problem can be easily calculated.

Both d[j] and c[j] can be found with the following algorithm, which uses the stack.

  1. Iterate through the characters of the string.
  2. If the current character is opening a bracket, put its position into the stack.
  3. If the current character is a closing bracket, there are 2 subcases:
  • The stack is empty - this means that the current closing bracket doesn't have a corresponding open one. Hence, both d[j] and c[j] are equal to -1.
  • The stack is not empty - we will have the position of the corresponding open bracket on the top of the stack - let's put it to d[j] and remove this position from the stack. Now it is obvious, that c[j] is equal at least to d[j]. But probably, there is a better value for c[j]. To find this out, we just need to look at the position d[j] - 1. If there is a closing bracket at this position, and c[d[j] - 1] is not -1, than we have 2 regular bracket sequences s(c[d[j] - 1], d[j] - 1) and s(d[j], j), which can be concatenated into one larger regular bracket sequence. So we put c[j] to be c[d[j] - 1] for this case.

Solution Link: Solution

If there is an error or want to discuss your approach, then please feel free to drop in the comment section.

Thank You for Reading