Official

D - KAIBUNsyo Editorial by en_translator


An important observation for the problem is as follows.

  • For every integer \(i\) (\(1 \le i \le N\)), if \(A_i \neq A_{N+1-i}\), then integers \(A_i\) and \(A_{N+1-i}\) should both be substituted by the same integer at last.

Let us regard this as an edge connecting between the vertices \(A_i,A_{N+1-i}\) in an undirected graph.

Then, we can see the following fact:

  • For every integer pair \((i,j)\), if \(i\) and \(j\) belongs to the same connected component of the graph, then \(i\) and \(j\) should both be substituted by the same integer.

Now, how can we minimize the number of operations to make all the integers in a connected component same?

If a connected component has \(k\) integers, obviously we need \(k-1\) or more operations to make them the same integer. Conversely, the objective can be achieved in \(k-1\) substitutions described as follows:

Fix an integer in the connected component, and change all other integers in the connected component to the fixed integer.

Therefore, the solution of this problem is (the number of distinct integers in \(A\)) - (the number of connected component of the graph).

There are several ways of finding this value; two typical ways are:

  • to perform DFS (Depth-First Search) or BFS (Breadth-First Search) for each connected component.
  • to use disjoint-set data structure (Union-Find).

The time complexity is around \(O(N)\) or \(O(N \log N)\), which is fast enough to solve this problem.

Sample code in C++

#include<bits/stdc++.h>

using namespace std;
using Graph=vector<vector<int>>;

void dfs(int v,vector<bool> &flag,Graph &g){
  if(!flag[v]){return;}
  flag[v]=false;
  for(auto &nx : g[v]){dfs(nx,flag,g);}
}

int main(){
  int n,res=0;
  cin >> n;
  vector<int> a(n);
  vector<bool> flag(200005,false);
  Graph g(200005);
  for(auto &nx : a){
    cin >> nx;
    if(!flag[nx]){flag[nx]=true;res++;}
  }
  int p=0,q=n-1;
  while(p<q){
    g[a[p]].push_back(a[q]);
    g[a[q]].push_back(a[p]);
    p++;q--;
  }
  for(int i=1;i<=200000;i++){
    if(flag[i]){
      res--;
      dfs(i,flag,g);
    }
  }
  cout << res << '\n';
}

posted:
last update: