Assignment 01 Solution

This problem is an extension of a problem from the recent World finals of the ICPC. The original statement of the problem is available at

https://icpc.kattis.com/problems/circular

The problem is described briefly here.

A nested or balanced bracket sequence is a sequence of n left and right brackets, such that every right bracket has a matching left bracket to its left. A basic property of this sequence is that in any prefix of the sequence, the number of right brackets must not exceed the number of left brackets.

In this problem, we have a circular sequence, and brackets can be of many types. The problem is to cut the circular sequence at some point, to get a linear sequence, such that the number of types of brackets that form a nested sequence is maximized.  Brackets of different types are considered independently. The initial circular sequence is specified by cutting it at an arbitrary point to get a linear sequence. Cutting at other points corresponds to circularly shifting the given linear sequence.

An extension of this problem is to find the minimum number of brackets of any type that must be deleted from the given circular sequence, keeping the order of the remaining elements the same, so that the remaining circular sequence can be cut at some point such that all types of brackets form a nested sequence (possibly empty).

Input Format
The first line of input gives n, the length of the sequence, 1 <= n <= 1000000.
The next line contains n space separated items, each of which is a character 's' or 'e' followed by an integer i, 1 <= i <= 1000000.   Here si represents a left bracket of type i and ei a right bracket of type i.

Output Format
Output 3 space separated integers, the position at which to cut to maximize the number of types that form a nested sequence, the maximum number of types, and the minimum number of elements to be deleted so that all types form a nested sequence. If more than one position gives the same maximum, output the smallest position. The position is identified by the position of the bracket just before which the sequence is cut, with the positions being numbered from 1.

Note: Use only cin and cout for Input/Output

Example
Input                                    Output
9                                        3 1 3
e1 e1 s1 e2 s1 s2 e42 e1 s1

Cutting the sequence just before the 3rd symbol s1, gives the sequence s1 e2 s1 s2 e42 e1 s1 e1 e1. Here brackets of type 1 form a nested sequence but the other types do not. Deleting the symbols e2, s2 and e42 and cutting the sequence just before the first s1 gives the sequence s1 s1 e1 s1 e1 e1, in which all brackets form a nested sequence. An alternative solution would be to delete the first occurrence of e1 and s1 and e42, and cut the sequence just before the second s1. The resulting sequence would be s1 s2 e1 s1 e1 e2.

Time limit: 3 seconds.


Hints for solution
Part 1.
If for any type #si != #ei, such a type cannot form a nested sequence. First identify all types that actually occur and could possibly form a nested sequence. For every type such that #si = #ei, there are always some positions at which the sequence can be cut so that type i forms a nested sequence. Can you identify these quickly? (Hint consider the difference #si - #ei). Now do another pass over the sequence and keep a count of the number of types that form a nested sequence, if the sequence is cut at that position.

Part 2.
Consider the sequence as given. How many symbols need to be deleted to make all types nested? Find the answer for each type i in terms of #si - #ei for the whole sequence, and its minimum value for a prefix. Sum over all types. Now move to the next position and update this sum efficiently, and keep track of the minimum.


Submission
Upload a single file on Moodle named RollNo_1.cpp

Test cases
Test cases for first part are available at

www.cse.iitb.ac.in/~aad/cs293