1
\$\begingroup\$

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\$

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;
  }
}
\$\endgroup\$
  • \$\begingroup\$ I would try to find a way to combine the s and k constraints] \$\endgroup\$ – paparazzo Dec 27 '16 at 17:01
  • \$\begingroup\$ @paparazzi, I will correct a mistake in description, and then make the solution easy to read if need. \$\endgroup\$ – Jianmin Chen Dec 27 '16 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.