USACO 2024 January Contest Bronze Division - Majority Opinion

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

A brute force idea would be to try every subarray and see what values can become the majority ones and then print every value which works. However, this would be way too slow and we need to optimize the process.

For problems like this, it is often very good to think at easy ideas that can help us check more easily the correct values, so a natural step would be for us to think at small subarrays.

We already know that if we can make a value become the majority in a subarray, we can turn the entire array into it by augmenting the subarrays with one value at a time. Thus, if we can find two consecutive equal values or at least 2 equal values in a subarray of length 3, everything can be turned into that value.

Therefore, all we have to do is to check whether we can achieve this by looking at all subarrays of length 2 and 3, because if a value forms the majority in a larger subarray, it also forms a majority in a subarray of length 2 or 3, something that can be proven easily by contradiction.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;

    for(; t; t--)
    {
        int n;
        cin >> n;

        vector<int> fr(n+1);
        vector<int> v(n+1);

        for(int i = 1; i <= n; i++)
            cin >> v[i];

        bool ok = 0;

        for(int i = 1; i <= n; i++)
        {
            if(i + 1 <= n && v[i] == v[i+1])
                fr[v[i]] = 1, ok = 1;
            if(i + 2 <= n && v[i] == v[i+2])
                fr[v[i]] = 1, ok = 1;
        }

        if(ok == 0)
            cout << -1 << '\n';
        else
        {
            vector<int> oki;
            for(int i = 1; i <= n; i++)
            {
                if(fr[i] == 1)
                    oki.push_back(i);
            }
            for(int i = 0; i < (int) oki.size(); i++)
            {
                cout << oki[i];
                if(i + 1 < (int) oki.size())
                    cout << " ";
            }
            cout << '\n';
        }
    }

    return 0;
}

t = int(input())
for _ in range(t):
    n = int(input())
    fr = [0] * (n + 1)
    v = [0] * (n + 1)
    arr = list(map(int, input().split()))
    for i in range(1, n + 1):
        v[i] = arr[i - 1]
    ok = False
    for i in range(1, n + 1):
        if i + 1 <= n and v[i] == v[i + 1]:
            fr[v[i]] = 1
            ok = True
        if i + 2 <= n and v[i] == v[i + 2]:
            fr[v[i]] = 1
            ok = True
    if not ok:
        print(-1)
    else:
        oki = []
        for i in range(1, n + 1):
            if fr[i] == 1:
                oki.append(i)
        print(" ".join(map(str, oki)))