Codeforces Round 285 (Div.2 E / Div. 1 C) - Misha and Palindrome Degree

Problem Statement:
504C - Misha and Palindrome Degree

Solution:
The official editorial to this problem is pretty much clearly explained. This post is mostly a self-note.

In a palindrome, there must be at most only one element with an odd number of occurrences, i.e. the rest of the elements must occur in even number of time. Next, given an array \(a_i\), we can first match all \(a_i\) with \(a_{N-i-1}\) from leftmost element, and stop when they differ.



Let's say we have elements in a[0..k-1] and a[N-k..N-1] matches exactly (i.e. k first elements matches k last elements), then we are left with a[k..N-k+1] to care about. If we can find prefixes/suffixes in a[k..N-k+1] that allows a[k..N-k+1] to be a palindrome after some rearrangement, then we can combine the prefix/suffix with the first or last k elements accordingly to form all possible pairs [L,R]. This approach brings down the search space from \(O(N^2)\) to \(O(N)\)! Cool stuff.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int N;
int a[100005];
int cnt[100005];
int check[100005];
int main(){
    long long ans = 0;
    scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%d",&a[i]);
        cnt[a[i]]++;
    }
    int odd = 0;
    for(int i=0;i<=100000;++i){
        if(cnt[i]%2)++odd;
    }
    if(odd > 1){
        printf("0\n");
        return 0;
    }
    int start = -1;
    for(int i=0;i<N;++i){
        if(a[i] != a[N-i-1]){
            start = i;
            break;
        }
        cnt[a[i]] -= 2;
    }
    if(start == -1){
        cout << (1LL*N*(N+1)/2LL) << endl;
        return 0;
    }
    for(int i=0;i<=100000;++i)check[i] = 0;
    int ret = 0;
    for(int i=start;i<=N-start-1;++i){
        check[a[i]]++;
        if(check[a[i]]*2 > cnt[a[i]]){
            if(i < N-i-1)break;
            if(cnt[a[i]]%2==0 && i==N-i-1)break;
            if(a[i] != a[N-i-1])break;
        }
        ++ret;
    }
    for(int i=0;i<=100000;++i)check[i] = 0;
    for(int i=N-start-1;i>=0;--i){
        check[a[i]]++;
        if(check[a[i]]*2 > cnt[a[i]]){
            if(i > N-i-1)break;
            if(cnt[a[i]]%2==0 && i==N-i-1)break;
            if(a[i] != a[N-i-1])break;
        }
        ++ret;
    }
    ans += 1LL * ret * (start+1);
    ans += 1LL * (start+1) * (start+1);
    cout << ans << endl;
    return 0;
}