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\$
Difficulty: Advanced
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[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);
}
/*
* 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[0] - arr[1]| = 1
* |arr[0] - arr[2]| = 2
* |arr[1] - arr[2]| = 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
* -1 - not found
*/
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;
}
}
