USACO 2026 Third Contest, Gold
Problem 1. Good Cyclic Shifts
Contest has ended.
Log in to allow submissions in analysis mode
For a permutation $p_1,p_2,\dots,p_N$ of $1\dots N$ ($1\le N\le 2\cdot 10^5$), let $f(p)=\sum_{i=1}^N \frac{|p_i-i|}{2}$. A permutation is good if it can be turned into the identity permutation using at most $f(p)$ swaps of adjacent elements.
Given a permutation, find which cyclic shifts of it are good.
INPUT FORMAT (input arrives from the terminal / stdin):
The input consists of $T$ ($1\le T\le 10^5$) independent tests. Each test is specified as follows:The first line contains $N$.
The second line contains $p_1,p_2,\dots,p_N$ ($1\le p_i\le N$), which is guaranteed to be a permutation of $1\dots N$.
It is guaranteed that the sum of $N$ over all tests does not exceed $10^6$.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test, output two lines:On the first line, output the number of good cyclic shifts $k$.
Then output a line with $k$ space-separated integers $s$ ($0\le s<N$) in increasing order, meaning that $p$ is good when cyclically shifted to the right $s$ times.
SAMPLE INPUT:
3 5 5 4 3 2 1 4 1 2 4 3 5 1 2 3 4 5
SAMPLE OUTPUT:
0 2 0 1 5 0 1 2 3 4
Consider the second test case, where $p = [1, 2, 4, 3]$.
- $f(p) = (|1 - 1| + |2 - 2| + |4 - 3| + |3 - 4|) / 2 = 1$. Since $p$ can be turned into the identity permutation in one move by swapping $p_3$ and $p_4$, $p$ is good.
- Cyclically shifting $p$ to the right $1$ time, we get $q = [3, 1, 2, 4]$. $f(q) = (|3 - 1| + |1 - 2| + |2 - 3| + |4 - 4|) / 2 = 2$. Since $q$ can be turned into the identity permutation in two moves by swapping $q_1$ two steps forward, $q$ is good.
It can be seen that the other two cyclic shifts are not good.
SCORING:
- Input 2: $N\le 10$
- Inputs 3-5: $T\le 10, N\le 2000$
- Inputs 6-11: No additional constraints.
Problem credits: Akshaj Arora