**Array Construction**

### Problem Statement :

Professor GukiZ has hobby — constructing different arrays. His best student, Nenad, gave him the following task that he just can't manage to solve: Construct an n-element array, A, where the sum of all elements is equal to s and the sum of absolute differences between each pair of elements is equal to k. All elements in A must be non-negative integers. A0+A1+...+An-1 = s ΣΣ |Ai-Aj| = k If there is more then one such array, you need to find the lexicographically smallest one. In the case no such array A exists, print -1. Note: An array, A, is considered to be lexicographically smaller than another array, B, if there is an index i such that Ai<Bi and, for any index j<i, Aj=Bj. Input Format The first line contains an integer, q, denoting the number of queries. Each of the q subsequent lines contains three space-separated integers describing the respective values of n (the number of elements in array A), s (the sum of elements in A), and k (the sum of absolute differences between each pair of elements). Constraints 1 <= q <= 100 1 <= n <= 50 0 <= s <= 200 0 <= k <=2000

### Solution :

` ````
Solution in C :
In C++ :
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
int main(){
int q;
cin >> q;
for(int Q = 0; Q < q; Q++){
int n, s, k;
cin >> n >> s >> k;
int dp[s+1][k+1];
for(int i = 0; i <= s; i++){
for(int j = 0; j <= k; j++){
dp[i][j] = 0;
}
}
dp[0][0] = 1;
int done = 0;
for(int c = 1; c <= n; c++){
int d = c*(n-c);
for(int i = 0; i + c <= s; i++){
for(int j = 0; j + d <= k; j++){
if(dp[i][j] != 0 && dp[i+c][j+d] == 0){
dp[i+c][j+d] = c;
}
}
}
if(dp[s][k]){
int diff[n];
for(int i = 0; i < n; i++) diff[i] = 0;
int cs = s;
int ck = k;
while(cs > 0 || ck > 0){
int a = dp[cs][ck];
int b = a*(n-a);
diff[n-a]++;
cs -= a;
ck -= b;
}
int r = 0;
for(int i = 0; i < n; i++){
r += diff[i];
cout << r << " ";
}
cout << endl;
done = 1;
break;
}
}
if(!done){
cout << -1 << endl;
}
}
}
In Java :
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int q = in.nextInt();
while (q-- > 0){
List<Integer> solution = solve(in.nextInt(), in.nextInt(), in.nextInt());
if (solution == null)
System.out.println(-1);
else{
String s = "";
for (int i : solution)
s = i + " " + s;
System.out.println(s);
}
}
}
private static List<Integer> solve(int n, int s, int k){
if (k < 0)
return null;
else if (n == 1){
if (k > 0)
return null;
else{
List<Integer> l = new ArrayList<Integer>();
l.add(s);
return l;
}
}
else if (k > s * (n - 1) || (s * (n - 1)) % 2 != k % 2)
return null;
else{
for (int x = 0; x <= s / n; x++){
List<Integer> solution = solve(n - 1, s - n * x, k + n * x - s);
if (solution != null){
for (int i = 0; i < n - 1; i++)
solution.set(i, solution.get(i) + x);
solution.add(x);
return solution;
}
}
return null;
}
}
}
In C :
#include <stdio.h>
#include <stdlib.h>
#define maxS 200
#define maxN 50
#define maxK 2000
#define maxNodes (200 + 1) * (2000 + 1)
void printArray(short array[], int size) {
for (int i = 1; i < size; i++) {
printf("%hd ", array[i]);
}
printf("%hd\n", array[size]);
}
struct Node {
short init;
short s, k, val;
struct Node* prevNode;
};
struct Node** _initDP() {
struct Node** output = malloc(sizeof(struct Node*) * maxN);
struct Node* firstDP = malloc(sizeof(struct Node) * maxNodes);
for (int i = 0; i <= maxS; i++) {
firstDP[i].init = 1;
firstDP[i].s = i;
firstDP[i].k = 0;
firstDP[i].val = i;
firstDP[i].prevNode = &firstDP[i];
}
output[0] = firstDP;
return output;
}
struct Node** createDP() {
struct Node** output = _initDP();
struct Node* oldNode;
int newVal, newS, newK;
for (int i = 1; i < maxN; i++) {
struct Node* oldDP = output[i - 1];
struct Node* newDP = malloc(sizeof(struct Node) * maxNodes);
short* hasFound = (short*) calloc(maxNodes, sizeof(short));
int nodeIdx = 0;
for (int j = 0; j < maxNodes; j++) {
oldNode = &(oldDP[j]);
if (oldNode->init == 0) { break; }
newVal = oldNode->val;
while (1) {
newS = oldNode->s + newVal;
if (newS > maxS) { break; }
newK = oldNode->k - oldNode->s + (newVal * i);
if (newK > maxK) { break; }
int newIdx = newK * (maxS + 1) + newS;
if (hasFound[newIdx] == 0 || hasFound[newIdx] > newVal + 1) {
newDP[nodeIdx].init = 1;
newDP[nodeIdx].s = newS;
newDP[nodeIdx].k = newK;
newDP[nodeIdx].val = newVal;
newDP[nodeIdx].prevNode = oldNode;
hasFound[newIdx] = newVal + 1;
nodeIdx += 1;
}
newVal += 1;
}
}
output[i] = newDP;
free(hasFound);
}
return output;
}
void printSolution(int n, int s, int k, struct Node* dp) {
for (int i = 0; i < maxNodes; i++) {
if (dp[i].init == 0) { break; }
//printf(" s = %hd and k = %hd val = %hd\n", dp[i].s, dp[i].k, dp[i].val);
if (dp[i].s == s && dp[i].k == k) {
struct Node thisNode = dp[i];
short* solution = malloc(sizeof(short) * (n + 1));
int count = n;
while (count > 0) {
solution[count] = thisNode.val;
count -= 1;
thisNode = *(thisNode.prevNode);
}
printArray(solution, n);
return;
}
}
printf("-1\n");
}
int main() {
int numQueries, n, s, k;
struct Node** dp = createDP();
scanf("%d", &numQueries);
for (int i = 0; i < numQueries; i++) {
scanf("%d %d %d", &n, &s, &k);
printSolution(n, s, k, dp[n - 1]);
}
return 0;
}
In Python3 :
cumsum = []
res = []
def mn(ceil, beans):
return (beans // ceil) * cumsum[ceil] + cumsum[beans % ceil]
def mx(ceil, beans):
return cumsum[1] * beans
fmemo = set()
def f(ceil, sm, beans):
if not (mn(ceil, beans) <= sm <= mx(ceil, beans)):
return False
if beans == 0 and sm == 0:
return True
if (ceil, sm, beans) in fmemo:
return False
for k in range(1, min(beans, ceil) + 1):
if f(k, sm - cumsum[k], beans - k):
res.append(k)
return True
fmemo.add((ceil, sm, beans))
return False
for _ in range(int(input())):
n, s, k = map(int, input().split())
if n == 1:
if k == 0:
print(s)
else:
print(-1)
continue
if s == 0:
if k == 0:
print(' '.join(map(str,[0 for _ in range(n)])))
else:
print(-1)
continue
cumsum = [0, 2*n - 2]
for i in range(1, n):
cumsum.append(cumsum[-1] + 2*n - 2 - 2*i)
res = []
f(n, k + (n - 1) * s, s)
if res:
r = [0 for _ in range(n)]
for num in res:
for i in range(num):
r[-1-i] += 1
print(' '.join(map(str,r)))
else:
print(-1)
```

## View More Similar Problems

## Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →## Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →## Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

View Solution →## Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

View Solution →## Super Maximum Cost Queries

Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and

View Solution →## Contacts

We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co

View Solution →