Observations on the number of rotations

After a rotation is performed \(k\) times, Dish \(p_i\) is in front of Person \((i+k) \bmod N\). Here, if \(k\) has the same remainder modulo \(N\), then the values of corresponding \((i+k) \bmod N\) are also equal, so we can limit \(k\) between \(0\) and \(N-1\).

\(\mathrm{O}(N^2)\) solution

Let \(c_k\) be the happy people resulting in performing the operation \(k\) times. Then, the answer is the maximum value of \(c_0,c_1,\ldots\), and \(c_{N-1}\). We can obtain the answer by counting the number of happy people for each case of the number of times of the operation, but checking whether each of \(N\) people is happy or not for each \(k\) costs a total of \(\mathrm{O}(N^2)\) time, which does not fit in the execution time limit.

Improvement to \(\mathrm {O}(N)\)

Suppose that Dish \(i\) is initially in front of Person \(j\). Then, the numbers of operations required to move Dish \(i\) in front of Person \((i-1)\bmod N\), Person \(i\), and Person \((i+1)\bmod N\), are \((i-1-j) \bmod N\) times, \((i-j)\bmod N\) times, and \((i+1-j) \bmod N\) times, respectively. Therefore, for each Person \(i=0,1,\ldots,N-1\), we may increase each of \(c_{(i-1-j) \bmod N}, c_{(i-j) \bmod N}, c_{(i+1-j) \bmod N}\) by one, so that we can find \(c_0,c_1,\ldots,c_{N-1}\) in a total of \(\mathrm{O}(N)\) time.
Note that, while processing Person \(0\), Person \(1\), \(\ldots\), and Person \(N\) in this order requires a precalculation to find the person initially with Dish \(i\), but it can be avoided by processing in the order of Person \(p_0\), Person \(p_1\), \(\ldots\), and Person \(p_{N-1}\). (The sample code is written in this way.)

Sample code

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

int main() {
    
	int N;
	cin>>N;
	
	vector<int> p(N);
	
	for(int i=0;i<N;i++)cin>>p[i];
	
	vector<int> cnt(N,0);
	
	for(int i=0;i<N;i++){
		for(int j=0;j<3;j++){
			cnt[(p[i]-1-i+j+N)%N]++;
		}
	}
	
	int ans = 0;
	for(int i=0;i<N;i++)ans = max(ans,cnt[i]);
	
	cout<<ans<<endl;
	
	return 0;
}