HackerRank Array Construction problem solution

In this HackerRank Array Construction problem solution, we need to construct an n-element array A where the sum of all elements is equal to S and the sum of the absolute difference between each pair of elements is equal to k. All elements in A must be nonnegative integers.

Problem solution in Python.

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)

{"mode":"full","isActive":false}

Problem solution in Java.

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);
}
}

{"mode":"full","isActive":false}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int Maxn = 52;
const int Maxs = 205;
const int Maxk = 2005;

bool dp[Maxn][Maxs][Maxk];

int main() {
    dp[0][0][0] = true;
    for (int i = 0; i < Maxn; i++)
        for (int j = 0; j < Maxs; j++)
            for (int k = 0; k < Maxk; k++) if (dp[i][j][k]) {
                if (j + i < Maxs) dp[i][j + i][k] = true;
                if (i + 1 < Maxn && k + j < Maxk) dp[i + 1][j][k + j] = true;
            }
    int q; scanf("%d", &q);
    while (q--) {
        int n, s, k; scanf("%d %d %d", &n, &s, &k);
        if (!dp[n][s][k]) { printf("-1\n"); continue; }
        int el = 0;
        while (n > 0)
            if (k - s >= 0 && dp[n - 1][s][k - s]) {
                printf("%d%c", el, n - 1 > 0? ' ': '\n'); n--; k -= s;
            } else {
                el++;
                s -= n;
            }
    }
    return 0;
}

{"mode":"full","isActive":false}

Problem solution in C.

#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;
}

{"mode":"full","isActive":false}