Konstruktiv Əyləncə (Həll təhlili)

Note that the expression \sum_{1 \le i < j \le n} |a_i - a_j| does not depend on the order of elements in the array. Therefore, without loss of generality, we can assume that the array is sorted in non-decreasing order:

This assumption allows us to remove absolute values and rewrite the expression more conveniently:

Let us analyze how each element contributes to the total sum:

We can group the terms by indices. Fix some index $i$. The element a_i appears:

• as a subtrahend (with a $-$) in all pairs where i < j . There are n - i such pairs.

• as a minuend (with a $+$) in all pairs where j < i . There are i - 1 such pairs.

Therefore, the total contribution of a_i to the sum is:

Summing over all $i$, we obtain:

This gives us an alternative way to compute the total sum of absolute differences for a sorted array.

Recall that we have assumed the array is sorted in non-decreasing order:

To ensure this property holds, we define the array in terms of non-negative increments. Specifically, we let:

where x_i \ge 0 for all $i$. That is,

This representation guarantees that a_1 \le a_2 \le \dots \le a_n, since each subsequent value is obtained by adding a non-negative quantity.

We now substitute this representation into our earlier expression for the total sum of absolute differences:

Exchanging the order of summation:

This gives us a linear expression in terms of the variables x_j, which we can now manipulate to achieve any desired total value of the sum.

Using the increment-based representation of the array, we obtain the following formula for the total sum of pairwise absolute differences:

where x_1, x_2, \dots, x_n are non-negative integers such that

This formula allows us to construct an array with any desired value of the sum by appropriately choosing the values of x_j.

Let us denote the coefficient of x_j as:

Our goal is to choose non-negative integers x_j such that:

This is equivalent to an unbounded knapsack problem: we are given item weights w_1, w_2, \dots, w_n, and we may take each item any number of times (including zero), with the goal of reaching total weight exactly $k$.

Solving this version of the knapsack problem gives us a valid set of increments x_j, which in turn defines a non-decreasing array a_1, a_2, \dots, a_n satisfying the required condition.

Since our goal is to achieve total weight exactly $k$, we are not interested in any item whose weight exceeds $k$. That is, for any $j$ such that:

we can safely ignore the corresponding variable x_j.

Furthermore, we observe that for a fixed $n$, the number of indices $j$ for which w_j \le k is relatively small. Indeed, solving the inequality:

we find that there are only O(\min(n, k / n)) such values of $j$.

This significantly reduces the number of distinct weights we need to consider, which allows us to solve the unbounded knapsack problem efficiently even when $n$ is large.

This quantity is maximized when n = \sqrt{k}, so we conclude that:

Therefore, the number of item types we need to consider in our unbounded knapsack problem is at most O(\sqrt{k}).

If we implement the standard dynamic programming solution to the unbounded knapsack problem over these weights and target value $k$, it runs in time:

Although the theoretical time complexity of the unbounded knapsack solution is O(k \cdot \sqrt{k}), in practice it performs much faster.

Empirical observations show that for all values of n \le 10^4, it is sufficient to consider only the first $200$ weights w_j = (j - 1)(n - j + 1) to be able to construct any possible target sum $k$ within the allowed range.

Moreover, standard optimizations for the unbounded knapsack problem — such as using early stopping, avoiding redundant updates — already yield significant speed-ups.

Even without using advanced techniques such as bitsets, the algorithm runs much faster than the pessimistic bound of O(k \cdot \sqrt{k}) in real scenarios.

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 6e6 + 11, inf = 1000111222;



const int max_k = 1e6 + 11;

int id[max_k];

void test_case() {
    int n, k;
    cin >> n >> k;
    vector <int> have(k + 1);
    have[0] = 1;


    for (int i = 1; i < n && !have[k]; i++) {
        int c = i * (n - i);
        if (c > k) {
            break;
        }
        if (have[c]) { // no need to update if we can make such sum already
            continue;
        }
        for (int j = c; j <= k; j++) {
            if (have[j - c]) {
                if (!have[j]) {
                    have[j] = true;
                    id[j] = i;
                }
            }
        }
    }
    assert(have[k]);
    vector <int> add(n);
    while (k) {
        int i = id[k];
        int c = i * (n - i);
        k -= c;
        add[i] += 1;
    }
    vector <int> ans(n, 1);
    for (int i = 1; i < n; i++) {
        ans[i] = ans[i - 1] + add[i];
    }
    for (auto &i : ans) {
        cout << i << ' ';
    }
    cout << '\n';
}



int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;

    cin >> t;

    while (t--) test_case();

    return 0;
}

/*
KoRoVa!
*/