**Problem Discussed Today:**

**Editorial**

**Idea:**

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,

4 alex ivan roman ivan

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

**Idea:**

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

**Idea:**

First of all, for each closing bracket in our string let's define 2 values:

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

- 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.

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

- Iterate through the characters of the string.
- If the current character is opening a bracket, put its position into the stack.
- 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**
## Comments

## Post a Comment