CF2048B Kevin and Permutation

Kevin is a master of permutation-related problems. You are taking a walk with Kevin in Darkwoods, and during your leisure time, he wants to ask you the following question. Given two positive integers $ n $ and $ k $ , construct a permutation $ ^{\text{∗}} $ $ p $ of length $ n $ to minimize the sum of the minimum values of all subarrays $ ^{\text{†}} $ of length $ k $ . Formally, you need to minimize $ $$$ \sum_{i=1}^{n-k+1}\left( \min_{j=i}^{i+k-1} p_j\right). $ $

$ ^{\\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ \[2,3,1,5,4\] $ is a permutation, but $ \[1,2,2\] $ is not a permutation ( $ 2 $ appears twice in the array), and $ \[1,3,4\] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

$ ^{\\text{†}} $ An array $ a $ is a subarray of an array $ b $ if $ a $ can be obtained from $ b$$$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. Two subarrays are considered different if the sets of positions of the deleted elements are different.

N/A

N/A

In the first test case, with $ k=2 $ , consider all subarrays of length $ 2 $ : the minimum value of $ p_1,p_2 $ is $ 1 $ , the minimum value of $ p_2,p_3 $ is $ 1 $ , and the minimum value of $ p_3,p_4 $ is $ 2 $ . The sum $ 1+1+2=4 $ is the smallest among all possible permutations. In the second test case, all subarrays of length $ 1 $ have minimum values of $ 5, 2, 1, 6, 4, 3 $ , and the sum $ 5+2+1+6+4+3=21 $ is proven to be the smallest.