Hints: Chamo and Mocha's Array

What are the possible candidates for the answer. Note that any element of the original array is a possible candidate. Hence, if we can find out the answer for each candidate a[i] in O(n), we can solve the problem in O(n^2).

Since we need to find out the maximum value, we can process all the candidates in decreasing order, and as soon as we find a valid answer, we can print it.

So, let’s start with the maximum element. When can it be an answer?

If the maximum element is indeed the answer, then what can you say about the frequency of the maximum element? Can it be 1? Can it be 2?

Is checking the frequency sufficient? Do their order matter?

The frequency of the maximum element m definitely can’t be 1. If it is 1, then even a subarray of length 2 of type

s m

gets converted to

s s

Hence, we will lose the maximum element. Of course, there’s no point in increasing the subarray length, because the maximum would be pushed to the end of the sorted array, and hence, it can never stand a chance of being the median. All of this happens because of the property of the left-leaning median. If the median was right leaning, can you see that the answer would always be the maximum element?

Ok, now we know that the frequency has to be at least 2. What about their relative positions? Can you figure out when can 2 maximum elements in the array dominate/eat the other elements?

If the both the maximas are adjacent, then they can eat all the elements.

s m m

In one step, you can eat s, because the sorted order is s m m with median m. Hence, we conclude that if 2 maximas are adjacent, the answer is the maxima. But what if they are not? What if the distance between the maximas is 2?

Even if the distance between the maximas is 2, they can still eat all elements.

m s m

You can first apply the operation on m s m to get m m m. Now that we have 2 maximas adjacent, we know they are powerful enough to eat the entire array?

But what if the distance between any 2 maximas is greater than 2?

Now, we can assume that the distance between any 2 maximas is at least 3.

m s s m s s m s s

To eat all the elements, you need to create a situation where at least 2 maximas are adjacent. This can never happen, because for every 2 maximas that you add in your subarray, you need to add atleast 2 s in your subarray. Hence, maximas stops being a possible candidate if the minimum distance between them is > 2.

Now, what is the next candidate? The second maxima. When will the second maxima be the answer?

Let’s call the second maxima as s. The same analysis applies, that is, if the distance between consecutive s is 1 or 2, it can start eating all elements one by one.

s m --> s s
s m s --> s s s

But is that all? This solution is sufficient, but not necessary. Can you think about the case that we are missing? What if there is a single second maxima s. Can it never be a valid answer?

We are overlooking the unused maxima m? In fact, if you think about it, even one s is enough to be duplicated if it’s adjacent to a maxima, because

s m ---> s s

And we know that once duplication happens, it is powerful enough to eat everything.

But what if s is not adjacent to the maxima m? Is it still powerful enough?

s e m

Even if the distance between s and m is 2, we can still duplicate it because, remember, s is second maxima so e has to be smaller than s, therefore, this gets converted to

s e m --> s s s

And once we have consecutive s, we are done. So, what is the final condition for the second maxima being an answer?

When evaluating second maxima, you can convert each maxima m to s. Then, you check if the minimum consecutive distance between each s is equal to 1 or 2. If it is not, then this can never be an answer.

Implementing this is easy, process candidates in decreasing order, and when you are dealing with s, replace all occurrence of the last processed element m to s. Then, find out the minimum adjacent difference.

Now, all you need is a data structure that supports 2 operations:

• Add indices to the data structure.
• Find minimum difference between the current indices.

This is because, instead of replacing all the occurrences of m with s, we can simply reuse the position vector of m and append all the position of s. Hence, we need a data structure that can support addition and query.

Think about set.

I just googled the data structure and the first result was the one that I wanted :)

In retrospect, it wasn’t that difficult. You just maintain a set of sorted elements. Every time you insert an element, you find out the next greater and previous smaller element. The only new difference that can be created is between these elements.

Hence, we can keep updating the positions in O(log(n)) per index.

The stuff that I wrote above are my thought process during the contest. Of course, I missed some easy observations and did an overkill. The data structure would not have been needed if I realized that if the configuration is a b c, then the answer would be min(a, b) or min(b, c) or min(a, c). This is because of the reasons discussed earlier, whenever we find a suitable candidate, the distance between it and the higher element would be 1 or 2.

For example, see tourist solution

Anyway, I do not regret my decision of going the O(n^2) to O(n log(n)) route. But a good learning from the concise solution from tourist as well!