Editorial for Maria Breaks the Self-isolation,Special Elements

Problem Discussed Today:



Let x be the maximum number of grannies that can go out to the yard. Then if Maria Ivanovna calls them all at the same time, then everyone will see x grannies. Since x is the maximum answer, then each granny of them satisfy ai≤x (otherwise there's no way for these grannies to gather in the yard), that is, such call is correct. So it is always enough to call once.

Note that if you order grannies by ai, Maria Ivanovna will have to call x first grannies from this list. She can take x grannies if ax≤x (otherwise, after all x grannies arrived, the last one will leave). To find x ,we can do a linear search.

The overall complexity is O(nlogn)per test.

Solution Link: Solution


The intended solution for this problem uses O(n^2) time and O(n) memory. Firstly, let's calculate cnti for each i from 1 to n, where cnti is the number of occurrences of i in a. This part can be done in O(n).

Then let's iterate over all segments of a of length at least 2 maintaining the sum of the current segment sum. We can notice that we don't need sums greater than n because all elements do not exceed n. So if the current sum does not exceed n then add cntsum to the answer and set cntsum:=0 to prevent counting the same elements several times. This part can be done in O(n^2).

Solution Link: Solution

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