In this post, we will solve HackerRank Array Construction Problem Solution.
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 8 and the sum of absolute differences between each pair of elements is equal to k. All elements in A must be non-negative integers.
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), 8 (the sum of elements in A), and (the sum of absolute differences between each pair of elements).
Output Format
For each query, print n space-separated integers describing the respective elements of the lexicographically smallest array A satisfying the conditions given above. If no such array exists, print -1 instead.
Sample Input
1
3 3 4
Sample Output
0 1 2
Array Construction C Solution
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 50
#define S 200
#define K 2000
int dp[N+10][S+10][K+10];
int a[N+10];
int main()
{
int t;
scanf("%d",&t);
int n,s,k;
for(int i=0; i<=N; i++)
{
for(int j=0; j<=S; j++)
{
for(int k=0; k<=K; k++)
{
dp[i][j][k]=-1;
}
}
}
dp[0][0][0] = 201;
for(int i=1; i<=N; i++)
{
for(int j=0; j<=S; j++)
{
for(int k=0; k<=K; k++)
{
for(int l=0;l<=S/i; l++)
{
if((k-j+i*l >= 0) && i*l <= j && j-l >=0 && dp[i-1][j-l][k-j+i*l]>=l)
{
dp[i][j][k] = l;
}
}
}
}
}
while(t--)
{
scanf("%d%d%d",&n,&s,&k);
if(dp[n][s][k] == -1)
{
printf("-1\n");
}
else{
int x = 0;
for(int i=n; i>0; i--)
{
int f=0;
for(int j=x; j<=s; j++)
{
if(!f && k-s+i*j>=0 && dp[i-1][s-j][k-s+i*j]>=j)
{
k-=s-i*j;
s-=j;
x=j;
a[n-i+1]=j;
f=1;
}
}
}
for(int i=1; i<=n; i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
}
return 0;
}
Array Construction C++ Solution
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;
int dp[55][222][2222];
int main(){
ios_base::sync_with_stdio(false);
cout<<fixed<<setprecision(0);
fill(dp[0][0],dp[0][0]+55*222*2222,MOD);
dp[0][0][0]=dp[1][0][0]=0;
reps(i,1,51)rep(j,202)rep(k,2004)reps(x,dp[i][j][k],202-j){
const int tmp=k+x*i-j;
assert(tmp>=k);
if(j+x<=202 && tmp<=2002) MN(dp[i+1][j+x][tmp],x);
}
//cout<<"ready"<<endl;
int T;
cin>>T;
while(T--){
int n,s,t;
cin>>n>>s>>t;
//rep(i,n+1){rep(j,s+1){rep(k,t+1)cout<<(dp[i][j][k]==MOD?-1:dp[i][j][k])<<",";cout<<endl;}cout<<endl;}
int o=0;
int ss=s,tt=t;
for(;ss>=0;ss-=n,++o) if(dp[n][ss][tt]<=s) break;
if(ss<0){assert(dp[n][s][t]==MOD);
cout<<-1<<endl;
continue;
}
vector<int> re(n);
rep(i,n){
rep(j,ss+1){
int ns=ss-j*(n-i);
int nt=tt-(ss-j*(n-i));
//cout<<i<<pii(ns,nt)<<endl;
if(nt>=0){
for(int ad=0;ns>=0;ns-=n-i-1,++ad)
if(dp[n-1-i][ns][nt]<MOD){
re[i]=j+o;
o+=ad;
ss=ns; tt=nt;
//cout<<j<<pii(ss,tt)<<endl;
j=MOD; break;
}
}
assert(j!=ss);
}
}
rep(i,n) cout<<re[i]<<" ";cout<<endl;
assert(accumulate(all(re),0)==s);
int sum=0;
rep(i,n)rep(j,i) sum+=re[i]-re[j];
assert(sum==t);
rep(i,n-1) assert(re[i]<=re[i+1]);
assert(re.size()==n);
}
return 0;
}
Array Construction C Sharp Solution
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
class Solution
{
static bool[, ,] cache;
static void Main(String[] args)
{
ProcessQueries();
}
private static void RunSampleTestCase()
{
int[] input = {3, 3, 4 };
arrayLength = input[0];
sumAllElements = input[1];
sumAllDifference = input[2];
cache = new bool[arrayLength, sumAllElements + 1, sumAllDifference + 1];
int[] arr = new int[arrayLength];
IList<string> helper = new List<string>();
Debug.Assert(FindSmallestArray(arr, 0, 0, 0) == 1);
Debug.Assert(string.Join(" ", arr).CompareTo("0 1 2") == 0);
}
private static void ProcessQueries()
{
int queries = int.Parse(Console.ReadLine());
while (queries-- > 0)
{
ArrayConstruction();
}
}
static int arrayLength, sumAllElements, sumAllDifference;
static void ArrayConstruction()
{
var input = Console.ReadLine().Split(' ');
arrayLength = int.Parse(input[0]);
sumAllElements = int.Parse(input[1]);
sumAllDifference = int.Parse(input[2]);
cache = new bool[arrayLength, sumAllElements + 1, sumAllDifference + 1];
int[] array = new int[arrayLength];
if (FindSmallestArray(array, 0, 0, 0) == 1)
Console.WriteLine(string.Join(" ", array));
else
Console.WriteLine(-1);
}
static int FindSmallestArray(
int[] array,
int sum,
int sumDiff,
int index
)
{
if (index == arrayLength)
{
if (sum == sumAllElements && sumDiff == sumAllDifference)
{
return 1;
}
return 0;
}
if (cache[index, sum, sumDiff])
{
return -1;
}
else
{
cache[index, sum, sumDiff] = true;
}
int nextElement = 0;
if (index != 0)
{
nextElement = array[index - 1];
}
for (; nextElement <= sumAllElements; nextElement++)
{
int lowerBound_newSum = sum + nextElement * (arrayLength - index);
int lowerBound_newDiffSum = sumDiff + (nextElement * index - sum) * (arrayLength - index);
if (lowerBound_newSum > sumAllElements ||
lowerBound_newDiffSum > sumAllDifference)
{
return 0;
}
array[index] = nextElement;
var newSum = sum + nextElement;
var newSumDiff = sumDiff + nextElement * index - sum;
var found = FindSmallestArray(array, sum + nextElement, sumDiff + nextElement * index - sum, index + 1);
if (found == 1) return 1;
}
return 0;
}
}
Array Construction Java Solution
import java.util.Arrays;
import java.util.Scanner;
public class Solution {
public static int[][][][] dp;
public static int[] construct(int nums, int sum1, int sum2) {
if (nums == 0) {
if (sum1 != 0 || sum2 != 0) {
return new int[]{-1};
}
return new int[]{};
}
if (dp[nums][sum1][sum2] != null) return dp[nums][sum1][sum2];
for (int place = 0; nums*place <= sum1; place++) {
int nsum1 = sum1 - place * nums;
int nsum2 = sum2 - place * nums - nsum1;
if (nsum2 < 0) continue;
int[] xx = construct(nums-1, nsum1, nsum2);
if (xx.length == 1 && xx[0] == -1) {
continue;
}
int[] actual = new int[nums];
System.arraycopy(xx, 0, actual, 1, xx.length);
for (int i = 0; i < nums; i++) actual[i] += place;
return dp[nums][sum1][sum2] = actual;
}
return dp[nums][sum1][sum2] = new int[]{-1};
}
public static void main (String[] args) {
dp = new int[51][201][5001][];
Scanner in = new Scanner(System.in);
int q = in.nextInt();
while(q-->0) {
int n = in.nextInt(), s = in.nextInt(), k = in.nextInt();
int[] min = null;
for (int start = 0; start*n <= s; start++) {
int[] b = construct(n-1, s-start*n, k);
if (b.length == 1 && b[0] == -1) {
continue;
}
int[] xx = new int[n];
System.arraycopy(b, 0, xx, 1, b.length);
for (int i = 0; i < n; i++) xx[i] += start;
if (min == null) {
min = xx;
continue;
}
boolean less = false;
for (int i = 0; i < n; i++) {
if (min[i] != xx[i]) {
if (xx[i] < min[i]) {
less = true;
}
break;
}
}
if (less) {
min = xx;
}
}
if (min != null) {
for (int i = 0; i < n; i++) {
if (i != 0) System.out.print(" ");
System.out.print(min[i]);
}
System.out.println();
} else {
System.out.println(-1);
}
}
System.exit(0);
}
}
Array Construction JavaScript Solution
function make_array(n, s, k) {
if (k < 0) {
return false;
}
if (s < 0) {
return false;
}
if (n == 1) {
if (k == 0) {
return [s];
} else {
return false;
}
}
let a = 0;
if (s > k) {
a = Math.ceil((s - k) / n);
}
while (((a * n) <= s) && ((a * n * (n - 1)) <= ((s * (n - 1)) - k))) {
let s1 = s - (n * a);
let k1 = k - s1;
let sub = make_array(n - 1, s1, k1);
if (sub) {
return [a].concat(sub.map(x => x + a));
}
a++;
}
return false;
}
function processData(input) {
var lines = input.split('\n');
var q = Number(lines.shift());
for (var i = 0; i < q; i++) {
var [n, s, k] = lines.shift().split(' ').map(Number);
var arr = make_array(n, s, k);
if (arr) {
console.log(arr.join(' '));
} else {
console.log('-1');
}
}
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
Array Construction Python Solution
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)