HackerRank university codesprint 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.

If there is more then one such array, you need to find the lexicographically smallest one. In the case no such array 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 $A[i]< B[i]$ and, for any index $j < i$, $A[j] = B[j]$.

Constraints

$1 <= q <=100$

$1 <= n <= 50$

$0 <= s <= 200$

$0 <= k <= 2000$

My introduction of algorithm: I did spend over 10 hours to work on the algorithm in the contest period, but my design has fatal error, only pass a sample test case, and test cases I designed, and scored 0.

After the contest, I studied one of solutions and then understood the design. Since the cache design is kind of tricky, includes three things: size of array, sum of all element, sum of absolute difference pair of elements. And the pruning idea is much better than mine.

It is a simple recursive function, using some cache to prune the algorithm, avoid the problem of Time Limit Exceed (TLE).

Also, I read the editorial note on HackerRank, I could not understand the dynamic programming solution. Compared to dynamic programming soltuon, I have some thoughts about using recursive/ pruning, time complexity cannot be defined in big O terms as dynamic programming described in editorial note. Pruning is hard to estimate in terms of time complexity. I did some pruning in the contest, but cannot compete the one used in the following code.

The C# solution passes all test case, score maximum score 80. In other words, ready to be reviewed. The algorithm is also a dynamic programming, bottom-up solution in terms of calculation of sum of all elements and sum of absolute difference of each pair.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

/*
* https://www.hackerrank.com/contests/university-codesprint/challenges/array-construction
*
*/
class Solution
{
static bool[, ,] cache;
static void Main(String[] args)
{
ProcessQueries();
//RunSampleTestCase();
}

private static void RunSampleTestCase()
{
int[] input = {3, 3, 4 };

arrayLength = input;
sumAllElements = input;
sumAllDifference = input;

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);
sumAllElements = int.Parse(input);
sumAllDifference  = int.Parse(input);

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

/*
* Design concern:
* time limit exceed - biggest concern
* Time complexity:
* unknown - using recursive solution, add some pruning techniques
*
* Algorithm:
* sample test case:
* 0 1 2
* 3 numbers,
* sum of all elements: 0 + 1 + 2 = 3, sumAllElements
* sum of the absolute differences:
* |arr - arr| = 1
* |arr - arr| = 2
* |arr - arr| = 1
* 1+1+2 = 4, sumDifference
*
* Using recursive, memorization to cut the time.
* Start from lexicographically smallest array first, then first one found should be smallest one.
* Every array is checked against the target sum of all elements and also sum of absolute pairs of difference.
* Because of recursive function is used here, a lot of redundant calls, need to prune the algorithm
* using cache.
* The design of cache includes size of the array, sum and sum of absolute difference of each pair.
* cache size checking:
*   n <= 50, s <= 200, k <= 2000,
*   so the cache size: 50 * 200 * 2000 bit = 20*10^7 bit, around 2.5MB < 3MB, memory limit is 512MB
*
* Find the lexicographically smallest array
* @arr - the output array
* return: 1 - find one
*/
static int FindSmallestArray(
int[] array,
int   sum,
int   sumDiff,
int   index
)
{
if (index == arrayLength)
{
if (sum == sumAllElements && sumDiff == sumAllDifference)
{
return 1;
}

return 0;
}

// this pruning is very important, otherwise timeout!
// cache[index, sum, sumDiff] should only be processed once
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++)
{
// the array is in non-decreasing order, so lower bound of sum of all elements, denoted as newSum
// can be estimated:
//       sum + nextElement * ( n - index ) where n is the length of array
// all elements in the array after index - 1 will be not less than nextElement,
// in other words,
//       array[j] >= nextElement, for any j in the range [index,n-1].
// therefore,
//       newSum >= sum + nextElement * (n - index)
// use this lowver bound of sum of all elements to prune the algorithm.
int lowerBound_newSum = sum + nextElement * (arrayLength - index);

// similar to estimate lower bound of newSum, apply same idea to newDiffSum
//       Sum(array[index - 1] - array[j]) where j >= 0 and j < index-1,
// in other words,
//       newDiffSum = sumDiff + Sum(array[index - 1] - Sum(array[j])
// so,   newDiffSum = sumDiff + (nextElement * index - sum)
int lowerBound_newDiffSum = sumDiff + (nextElement * index - sum) * (arrayLength - index);

if (lowerBound_newSum     > sumAllElements ||
lowerBound_newDiffSum > sumAllDifference)
{
return 0;
}

array[index] = nextElement;

// For example, 0, 1 are the elments in array, index = 2,
// sum = 1, nextElement is 2, then, two new pair of difference,
// 2 - 0, 2 - 1, in other word, newSumDiff = 2 * 2 - (0 + 1)
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;
}
}
• I would try to find a way to combine the s and k constraints] – paparazzo Dec 27 '16 at 17:01
• @paparazzi, I will correct a mistake in description, and then make the solution easy to read if need. – Jianmin Chen Dec 27 '16 at 19:19