MajoritySubarray

2018 TCO 2C · 2018-04-20 · by majk

2018 TCO 2C · 2018-04-20 · by majk · Brute Force, Dynamic Programming

Show categories

Class Name: MajoritySubarray

Return Type: long

Method Name: getCount

Arg Types: (int, int, int)

Problem Statement

A majority element of an array A is an element that occurs in A strictly more than length(A)/2 times. In other words, the number of occurrences of the majority element must be strictly larger than the number of occurrences of all other elements combined. For example, the majority element of the array {1, 2, 1} is 1. On the other hand, the arrays {1, 2, 3} and {1, 2, 1, 3} don't have any majority element.

You are given a int[] A of length n. Each element of A is a small non-negative integer (between 0 and m-1, inclusive). Your task is to count the number of contiguous subarrays of A that have a majority element, and to return that count.

You are given the ints n, seed, and m. Since the array A may be long, it is not given explicitly. Instead, use the following pseudocode to generate its contents:

for i = 0 .. n-1:
    A[i] = (seed div 2^16) modulo m
    seed = (seed * 1103515245 + 12345) modulo 2^31

In the pseudocode shown above, ^ denotes exponentiation and div denotes integer division (e.g., 49 div 10 is 4).

Notes

The reference solution does not depend on any properties of the pseudorandom generator used in the statement. In the given time limit the reference solution can compute the answer for any array of length 10^5.
Watch out for integer overflow. In particular, note that the return value may not fit into a signed 32-bit integer variable.

Constraints

n will be between 1 and 105, inclusive.
seed will be between 0 and 231-1, inclusive.
m will be between 1 and 50, inclusive.

Examples

5
200
5
Returns: 8

For these arguments you should generate the array A = {0, 0, 1, 2, 0}. During the generation, the variable seed should have the following values: {200, 1659729249, 1659156614, 155161927, 1266180468, 598410909}. This array has exactly 8 contiguous subarrays that have a majority element, namely: Each of the five one-element subarrays. (Note that three of these look the same, but we are still counting each of them as a different subarray.) The subarray {0, 0}. The subarray {0, 0, 1}. The subarray {0, 0, 1, 2, 0}.

10
15
3
Returns: 23

The corresponding array is A = {0, 2, 2, 0, 0, 1, 1, 0, 2, 2}.

100000
345
2
Returns: 4984459804

100000
784
2
Returns: 4988932294

100000
0
1
Returns: 5000050000

19)

27
541
50
Returns: 27

The generated input is A = {0, 19, 46, 25, 21, 34, 29, 15, 24, 38, 22, 41, 17, 28, 37, 14, 4, 32, 11, 42, 2, 12, 44, 35, 39, 1, 10}.

Submissions are judged against all 31 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MajoritySubarray with a public method long long getCount(int n, int seed, int m) · 31 test cases · 2 s / 256 MB per case