USACO 2025 US Open Contest Bronze Division - More Cow Photos

Problem link: TBA

Video link: here

Solution Author: Stefan Dascalescu

Problem Solution

Given that the array must be symmetric, we have to count the number of values which show up at least twice. This can be done using frequency arrays.

If we fix the value in the middle, we can surround it by pairs of smaller values.

Source code

The source code in C++ can be seen below.

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n;
    cin >> n;

    vector<int> frq(n+1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        frq[x]++;
    }

    int cnt = 0;
    int ans = 1;
    for (int i = 1; i <= n; i++) { // all possible maximum values
        if (frq[i] > 0) {
            ans = max(ans, cnt*2+1);
        }
        cnt += (frq[i] >= 2); // if frq is at least 2, we increment the cnt
    }
    cout << ans << '\n';
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }
    return 0;
}