CF1672I PermutationForces

You have a permutation $ p $ of integers from $ 1 $ to $ n $ . You have a strength of $ s $ and will perform the following operation some times: - Choose an index $ i $ such that $ 1 \leq i \leq |p| $ and $ |i-p_i| \leq s $ . - For all $ j $ such that $ 1 \leq j \leq |p| $ and $ p_i

N/A

N/A

In the first test case, the minimum $ s $ required is $ 1 $ . Here is how we can transform $ p $ into the empty permutation with $ s=1 $ : - In the first move, you can only choose $ i=2 $ as choosing any other value of $ i $ will result in $ |i-p_i| \leq s $ being false. With $ i=2 $ , $ p $ will be changed to $ [2,1] $ . - In the second move, you choose $ i=1 $ , then $ p $ will be changed to $ [1] $ . - In the third move, you choose $ i=1 $ , then $ p $ will be changed to $ [~] $ . It can be shown that with $ s=0 $ , it is impossible to transform $ p $ into the empty permutation.