SETMJRPRE - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: manasagarwal12, luvkansal29
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Prefix sums

PROBLEM:

An array is called dominating if every prefix and every suffix of it has a majority element.

Given an array A, count the number of its prefixes that are dominating.

EXPLANATION:

Let’s analyze a dominating array alone first.
So, suppose A is dominating.
Then, the condition on the prefix of length N means that A must itself have a majority element - let this be M.

Now, majority elements must be unique (after all, only one element can appear more than half the time).
Further, frequencies can’t really change much from the prefix of length i to the prefix of length i+1.
Together, these things give us a rather strong condition: M, the majority of the array, must also be the majority element of every prefix (and every suffix)!

Proof

Let d_M denote the number of occurrences of M, minus the number of occurrences of any other element in the array.
For example, if M = 3 and the array is [1, 3, 3, 2, 3] then d_M = 3 - 2 = 1.
Note that M will be the majority element of the array if and only if d_M \gt 0.

Note that one way to compute d_M, is to start with it at 0 and then iterate through the array, each time adding either +1 or -1 depending on whether we meet an occurrence of M or not.
In particular, note that this tells us whether M is the majority for each prefix or not - we only need to look at the value of d_M for that prefix.
To take the example above, with array [1, 3, 3, 2, 3] and M = 3, the values of d_M for each prefix are [-1, 0, 1, 0, 1].

We want to claim that in a dominating array, d_M \gt 0 for every non-empty prefix.
Suppose this doesn’t happen - meaning some prefix either has d_M = 0 or negative d_M.

If d_M = 0 it means that the number of occurrences of M is exactly half the length of the prefix, so this prefix definitely can’t have a majority element: no other element can occur more than half the time, after all.

What about when d_M \lt 0 for some prefix?
Here, we use the fact that M is the majority of the array, so that the final value of d_M will surely be positive.
However, d_M can only change by either +1 or -1, so if it’s negative at some point and ends up positive, it must definitely equal 0 somewhere in the middle.
So, if d_M \lt 0 for some prefix, there will always exist another prefix with d_M = 0. This brings us back to the first case, where such a prefix cannot have a majority element.

So, if M is not the majority element for each prefix,we’re always able to find a prefix with no majority element at all, contradicting A being a dominating array.

In particular, this means A must also start and end with M.

Now, we want to count the number of prefixes of A that are dominating.
Since the array starts with A_1, this means that the only candidate prefixes are those that:

  1. End with A_1.
  2. Have A_1 as the majority element in every prefix and suffix.

To count these, we use a trick that applies often when dealing with majority elements.
Consider an array B of length N, where:

  • B_i = 1 if B_i = A_1.
  • B_i = -1 otherwise.

Now, subarray [L, R] of A has A_1 as its majority if and only if the sum B_L + B_{L-1} + \ldots + B_R is \gt 0.
Let’s apply this to check whether some prefix of A is dominating.

Suppose we’re looking at the prefix that ends at index i.
Then,

  1. A_i = A_1 should hold, of course.
  2. A_1 should be the majority on every prefix till i.
    This just means that every prefix sum of B till the i-th should be positive.
  3. A_i should be the majority on every suffix ending at i.
    This means that B_j + B_{j+1} + \ldots + B_i \gt 0 for each j \leq i.

Given that we’re dealing with subarray sums of B, let’s build the prefix sum array of B, so that P_i = B_1 + \ldots + B_i.
Then, the suffix sum condition translates to P_i - P_{j-1} \gt 0 for each j \leq i, or in other words P_i \gt P_{j-1} for each j \leq i.
This is really easy to check: just maintain the maximum value seen in P so far, and then check if P_i is larger than it or not!

So, once the prefix sum array P of B has been built, we have a very easy check for whether A[1, i] is a dominating prefix.

  1. A_i = A_1
  2. P_j \gt 0 for each 1 \leq j \leq i
  3. P_{j-1} \lt P_i for each 1 \leq j \leq i

By storing the running maximum of P, all these checks can be made in constant time, so we have a solution that’s linear overall.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    p = [0]
    for x in a:
        if x == a[0]: p.append(p[-1] + 1)
        else: p.append(p[-1] - 1)
    
    ans, pmx = 0, 0
    for i in range(1, n+1):
        if p[i] <= 0: break
        ans += p[i] > pmx
        pmx = max(pmx, p[i])
    print(ans)
1 Like