# Editorials to STL practice problems

##### caution

Donâ€™t read the editorial, if you have not attempted or read the problem. It would hamper your thinking capability, if you do so.

## Hackerrank

## Editorial

You need to give a O(N) solution. You can see the approach using a deque or queue here :

See the Queue modification (method 1) here## Editorial

See above problemâ€™s editorial , as it is almost the same question, with a slight modification.

## Editorial

We can use a stack to solve such kinds of problems.

Let's define {, (, and [ as opening brackets and }, ), and ] as closing brackets.

Algorithm:- Whenever an opening bracket appears, we push it onto the stack.
- If a closing bracket appears and if it matches the opening bracket at the top of the stack, it means that the brackets are balanced and we pop the opening bracket out of the stack and continue analyzing the string.
- If the closing bracket doesn't match the opening bracket at the top of the stack (or the stack is empty at that stage), we can infer that the string is not balanced, and we print NO.
- After processing the string completely and if the stack is empty, the string is balanced, and we print YES, else, we print NO

## SPOJ

HISTOGRA - Largest Rectangle in a Histogram

## Editorial

You can use a stack, to calculate the largest rectangle area in a histogram, in just O(N) time complexity.

First , think of a naive or brute-force approach, to understand the efficient solution.

For each bar, we can find the rectangle with the height of it and also containing it.

To do this for a bar, let's say bar, we go to left from and stop at the first bar which is smaller than the bar. Say we have stopped at position.

Then, we move to the right of and stop at the bar which is smaller than bar. Say we have stopped at bar.**So, the rectangle containing bar and of its height will have width from position to (exclusive). The width will be**

We can calculate the area of this rectangle for each bar and take the maximum. That will be our answer. But it has a time complexity of in the worst case, which may give TLE here.

Now, to reduce the time complexity, we will use a stack here, in such a way that we maintain the heights of bars in the stack, in an increasing order. And also, we will push the index of bar to the stack, instead of height. Now, think of some approach, using this stack, by your own. Still if you didnâ€™t get it, you can watch this video for explanation. Thus, we can easily solve this problem in time complexity.

## Codeforces

## Editorial

**Pre-requisite**: Set / Map

**Explanation**: Our task is here to check weather a sock of same type is already on the table or not, and note the no of socks on it and output maximum of all our readings of no socks.

Here it is given that the index of sock is â‰¤100000 thus you can also make an zero array and each time check if it zero or not (i.e checking weather a socks is on table or not.)

But if index very large or something else as string ,char etc then it better to use set here.## Editorial

## Editorial

**Prerequisite**: STL queue, map

**Explanation**:Consider a queue e for every application and also a queue Q for the notification bar.

i. When an event of the first type happens, increase the number of unread notifications by 1 and push pair (i,â€‰x) to Q where i is the index of this event among events of the first type, and also push number i to queue e[x].

ii. When a second type event happens, mark all numbers in queue e[x] as visited,clear this queue and decrease the number of unread notifications by the number of elements in this queue before clearing.

iii. When a third type query happens, do the following -

while Q is not empty and Q.front().first<=t:i = Q.front().firstx= Q.front().secondQ.pop()if mark[i] is false:Mark[i] = truee[v].pop()ans = ans - 1## Editorial

**Pre-requisite**: Vector / Map

**Explanation**: Firstly let's count a number of different states that we can have in the game. Cards can be arranged in any one of n! ways. In every of this combination, we must separate first soldier's cards from the second one's. We can separate it in nâ€‰+â€‰1 places .So war has (nâ€‰+â€‰1)! states. If we'd do (nâ€‰+â€‰1)! "fights" and we have not finished the game yes, then we'll be sure that there is a state, that we passed at least twice. That means that we have a cycle, and game won't end. Otherwise , the game would end simply with one soldier having empty set. Since , n is very small one can use the above brute force method , so the time complexity will be O(n*(n+1)!). The other n is used by map to check the repetition of the states.

One can use vectors to represent states of the soldiers. In every fight do as said in the problem and store the states . Also keep the count of no. of fights. If any of the state gets repeated , then the game would end in an infinite loop, hence print -1 and end the game. If at any instant either of the vectors is empty , the other soldier wins .

To keep count of the states, one can use stl::map of a pair of vectors , where the first vector would represent the set of cards of soldier 1 and the second vector for soldier 2. One can map the pair of vector with bool values which represent whether that state is already visited or not.

## Editorial

**Explanation**:

Let the colour of T-shirt which buyer wants be x. So our task is to find the T-shirt having that colour on any of back or front side and remove it from our available collection of T-shirts.Here as our collection of data from which we want to select minimum is dynamic( i.e it is updating after removing each T-shirt) ,so we will use priority_queue that have both update and query(for minimum) in O(log(n)) time complexity;

We can use priority_queue of pair

`<prize_of_t-shirt , index_of_T-shirt>`

, as by default the ordering is on the basis of first element and we can use index of T-shirt to remove it from collection.1353/D - Constructing the Array

## Editorial

**Prerequisite**: Priority queue or Set , Creating your own comparator functions

**Explanation**: Create a priority queue to store segments, such that the segment having the greatest length is always at the top of priority queue. (If 2 segments have same length, the one with leftmost starting point will be at the top, as per given question)

Now, perform the sequence of operations, as given in the problem.

**Time Complexity**: O(N log N), where N = size of array

[ Since, insertion and deletion in priority queue takes only O( log N ) ]

**Code**: https://codeforces.com/contest/1353/submission/80121041## Editorial

**Prerequisite**: Map, Iterators in STL

**Explanation**:

Itâ€Œ â€Œisâ€Œ â€Œclearâ€Œ â€Œthatâ€Œ â€Œradiusâ€Œ â€Œofâ€Œ â€Œsphereâ€Œ â€Œwithâ€Œ â€Œrectangleâ€Œ â€Œofâ€Œ â€Œsidesâ€Œ â€Œ(a,b,c)â€Œ â€Œ willâ€Œ â€Œbeâ€Œ â€Œmin(a,b,c)/2â€Œ â€Œandâ€Œ â€Œifâ€Œ â€Œtwoâ€Œ â€Œparallelepipedsâ€Œ â€Œexistâ€Œ â€Œwithâ€Œ â€Œtwoâ€Œ â€Œsameâ€Œ â€Œsideâ€Œ â€Œ(a,b)â€Œ â€Œthenâ€Œ â€Œafterâ€Œ glueingâ€Œ â€Œtheseâ€Œ â€Œtwoâ€Œ â€Œtogetherâ€Œ â€Œ,â€Œ â€Œradiusâ€Œ â€Œwillâ€Œ â€Œbeâ€Œ â€Œmin(a,b,c1+c2)/2.â€Œ â€Œ

Forâ€Œ â€Œeveryâ€Œ â€Œpairâ€Œ â€Œ(a,b)â€Œ â€Œletâ€Œ â€Œusâ€Œ â€Œfindâ€Œ â€Œmaximalâ€Œ â€Œadjacentâ€Œ â€Œsidesâ€Œ â€Œc1â€Œ â€Œandâ€Œ â€Œc2â€Œ â€Œ ,thenâ€Œ â€Œweâ€Œ â€Œwillâ€Œ â€Œcheckâ€Œ â€Œforâ€Œ â€Œwhichâ€Œ â€Œpair(a,b)â€Œ â€Œmin(a,b,c1+c2)â€Œ â€Œisâ€Œ â€Œ maximum.â€Œ â€Œ

Weâ€Œ â€Œcanâ€Œ â€Œmakeâ€Œ â€Œaâ€Œ â€Œmapâ€Œ â€Œofâ€Œ â€Œpairâ€Œ â€Œtoâ€Œ â€Œ(vectorâ€Œ â€Œofâ€Œ â€Œpair)â€Œ â€Œ.â€Œ â€ŒInâ€Œ â€Œwhichâ€Œ â€Œforâ€Œ â€Œeveryâ€Œ â€Œ distinctâ€Œ â€Œpairâ€Œ â€Œ(a,b)â€Œ â€Œweâ€Œ â€Œstoreâ€Œ â€Œwhatâ€Œ â€Œisâ€Œ â€Œtheâ€Œ â€Œthirdâ€Œ â€Œsideâ€Œ â€Œandâ€Œ â€Œ correspondingâ€Œ â€Œindex.â€Œ

â€Œ Thenâ€Œ â€Œweâ€Œ â€Œiterateâ€Œ â€Œthroughâ€Œ â€Œtheâ€Œ â€Œmapâ€Œ â€Œandâ€Œ â€Œfindâ€Œ â€Œmaximalâ€Œ â€Œc1â€Œ â€Œandâ€Œ â€Œc2â€Œ â€Œforâ€Œ â€Œ everyâ€Œ â€Œpairâ€Œ â€Œ(a,b).â€Œ â€Œ

Thenâ€Œ â€Œweâ€Œ â€Œfindâ€Œ â€Œforâ€Œ â€Œwhichâ€Œ â€Œpairâ€Œ â€Œmin(a,b,c1+c2)â€Œ â€Œisâ€Œ â€Œmaximumâ€Œ â€Œandâ€Œ â€Œ outputâ€Œ â€Œtheâ€Œ â€Œcorrespondingâ€Œ â€Œanswer.â€Œ

â€Œ**NOTE**:â€Œ â€ŒDoâ€Œ â€Œnotâ€Œ â€Œforgetâ€Œ â€Œwhenâ€Œ â€Œthereâ€Œ â€Œisâ€Œ â€Œonlyâ€Œ â€Œoneâ€Œ â€Œmaximalâ€Œ â€Œsideâ€Œ â€Œforâ€Œ â€Œ pairâ€Œ â€Œ(a,b)â€Œ.â€Œ## Editorial

**Pre-requisite**: Map

**Explanation**: We can clearly see than n â‰¤ 10^5, that is a naive approach of O(n^2) will not pass. We need a better solution.

Here using STL map will make our task easy.

We can make a map of string and int where string will contain the name of person while int will contain the count.

We know that by default map are initialized with zero.

So if the count of a string is zero print OK and increase its counter by 1 else print the string and the count of string and increase its counter by 1.