I came up with this approach while solving this problem the first time, it is not as clean as the one mentioned in the tutorial. But I do feel like its much easier to understand.

So the first thing that we need to think about here is, If such an array can even be constructed or not. That is the fundamental issue in this problem.

So we can actually do is find out the max and min beauty possible for a particular set of (n,k,s), this approach also needs the verification of the fact that every single value inclusive of the mid and max value is reachable. We can also proof that quite easily.

So max beauty, when it is possible and what is its value, both empirically and theoretically we can arrive on the fact, if the elements present in the array are a factor of k, we will get the largest possible beauty. So we can simple divide the value g by k and get the maximum beauty. Where G is the factor of k, less than or equal to the sum.

This can easily be done in O(n) time

now for minimum beauty, again we will fill the entire array except any single element with the value (k-1), so the total sum is (k-1)*(n-1), the last element is simple s — (k-1)*(n-1)

The n-1 elements contribute 0 to the beauty, while the special one contributes its value/k.

With some basic distribution we can easily verify the fact that every single element in b/w is reachable.

Now how we will go about constructing the array,

The approach here is, we will use a single element to contribute to beauty and rest all of them will contribute 0 only.

Put the first element as b*k

initialize a variable sum_left = s — b*k

now, distribute k-1 to each of the the position of the array left, if the value of sum_left is exhausted, the rest of the array will be filled with 0's

if not, just end the final value of sum_left to the first element.

It can be shown, if there exist a possible solution, the addition of sum_left would not increment the first element enough so that it reaches the next factor of k.

I apologize of the typos if present

here is the code in java

import java.util.*;

public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); StringBuilder sb = new StringBuilder();

while (t-- > 0) {
        long n = sc.nextLong();
        long k = sc.nextLong();
        long beauty = sc.nextLong();
        long sum = sc.nextLong();

        long remainder = sum - (k - 1) * (n - 1);
        long minBeauty = remainder < 0 ? 0 : remainder / k;
        long maxBeauty = sum / k;

        if (beauty < minBeauty || beauty > maxBeauty) {
            sb.append(-1).append("\n");
            continue;
        }

        long[] ans = new long[(int) n];
        ans[0] = beauty * k;
        long sumLeft = sum - ans[0];

        for (int i = 1; i < n; i++) {
            if (sumLeft >= k - 1) {
                ans[i] = k - 1;
                sumLeft -= (k - 1);
            } else {
                ans[i] = sumLeft;
                sumLeft = 0;
                break;
            }
        }

        ans[0] += sumLeft;

        for (int i = 0; i < n; i++) {
            sb.append(ans[i]);
            if (i < n - 1) sb.append(" ");
        }
        sb.append("\n");
    }

    System.out.print(sb);
}

}

1715B - Beautiful Array