HackerRank university codesprint - Array Construction (advanced algorithm) - score 8 of 80, using DFS, backtracking, pruning etc., O(n^2)->O(n) for sum of Math.abs(Ai - Aj)

ArrayConstruction_10x.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ArrayConstruction_P1
{
    class ArrayConstruction
    {
        /*
         * Array construction:
         * 
         * start time: 11:16pm
         * end time: 11:32pm 
         * finish of writing first version
         * Try to score 1 <= q <= 10 
         * 10% of 80 - 8 points
         * 
         * submit second time:
         * 12:33pm
         * first time, run-time error on sample test case
         * 
         * 
         * 2:31am 
         * do some research on simple mathmatics, and find 
         * some idea to reduce sum of any two elements in the array 
         * from O(nxn) to O(n)
         * http://stackoverflow.com/questions/5855066/finding-sum-of-absolute-difference-of-every-pair-of-integer-from-an-array
         * 
         * using simple formula:
         * For example: Given a[]= {2,3, 5, 7 };
            output would be (3-2) + (5-2) + (7-2) + (5-3) + (7-3) + (7-5) = 17.
            I suppose you could

            Sum the multiplication of each number starting backwards with #count - 1 to get the total
            Sum the multiplication of each number starting up front with #count - 1 to get the total to subtract
            
         *  This would then become (7*3 + 5*2 +3*1) - (2*3 + 3*2 + 5*1) = 17
         * 
         * 3:51am 
         * finish to clean up code
         * make the code as simple as possible
         * Leave the timeout issue for future. 
         * 
         */
        static void Main(string[] args)
        {
             process();

             // testing();            
        }

        private static void testing()
        {
             testCase1(); 
            //testCase3();         

            // test case: "0 1 2 3 4 5 6 7 8 9 10"
            //testcase10();            

            //int sum = sumDiffCal(); 

            
            //int sum2 = sumDiffCal_2(); 

            //testcase50();
        }

        /*
         * 0 1 2 3 4 5 6 7 8 9 10 - construct 11 55 220
         * But the result:
         * 0 0 0 2 6 7 8 8 8 8 8 
         * 
         * The maximum range - is k/n, 
         * k = 220
         * n = 55
         * so, maximumRange = 220/11 = 20
         * 
         * K is at least n * maximumRange 
         * 
         */
        private static void testcase10()
        {
            string[] arr = "11 55 220".Split(' ');

            int n = Convert.ToInt32(arr[0]);
            int s = Convert.ToInt32(arr[1]);
            int k = Convert.ToInt32(arr[2]);

            DateTime startTime = DateTime.Now;
            Console.WriteLine(lexicoSmallest(n, s, k));
            DateTime endTime = DateTime.Now;

            TimeSpan duration = endTime.Subtract(startTime);
            string res = duration.ToString();
        }

        /*
         */
        private static void testcase50()
        {
            string[] arr = "50 89 449".Split(' ');

            //int sumDiff = sumDiffCal_50();
            //int sum = sum50(); 

            int n = Convert.ToInt32(arr[0]);
            int s = Convert.ToInt32(arr[1]);
            int k = Convert.ToInt32(arr[2]);

            DateTime startTime = DateTime.Now;
            Console.WriteLine(lexicoSmallest(n, s, k));
            DateTime endTime = DateTime.Now;

            TimeSpan duration = endTime.Subtract(startTime);
            string res = duration.ToString();

        }

        private static int sum50()
        {
            string test1 = "0 1 1 1 1 1 1 1 1 1 ";
            string test2 = "2 2 2 2 2 2 2 2 2 2 ";
            string test3 = "2 2 2 2 2 2 2 2 2 2 ";
            string test4 = "2 2 2 2 2 2 2 2 2 2 ";
            string test5 = "2 2 2 2 2 2 2 2 2 2";

            string test = test1 + test2 + test3 + test4 + test5;

            int[] arr = toIntArr(test);

            return arr.Sum();
        }

        private static int sumDiffCal_50()
        {
            string test1 = "0 1 1 1 1 1 1 1 1 1 ";
            string test2 = "2 2 2 2 2 2 2 2 2 2 ";
            string test3 = "2 2 2 2 2 2 2 2 2 2 ";
            string test4 = "2 2 2 2 2 2 2 2 2 2 ";
            string test5 = "2 2 2 2 2 2 2 2 2 2";

            string test = test1 + test2 + test3 + test4 + test5;

            int[] arr = toIntArr(test);

            int count = 0;
            for (int i = 0; i < arr.Length; i++)
                for (int j = i + 1; j < arr.Length; j++)
                {
                    count += Math.Abs(arr[i] - arr[j]);
                }

            return count;
        }

        private static void testCase1()
        {
            string[] arr = "3 3 4".Split(' ');

            int n = Convert.ToInt32(arr[0]);
            int s = Convert.ToInt32(arr[1]);
            int k = Convert.ToInt32(arr[2]);

            DateTime startTime = DateTime.Now;
            Console.WriteLine(lexicoSmallest(n, s, k));
            DateTime endTime = DateTime.Now;

            TimeSpan duration = endTime.Subtract(startTime);
            string res = duration.ToString();
        }

        private static void testCase2()
        {
            string[] arr = "6 6 10".Split(' ');

            int n = Convert.ToInt32(arr[0]);
            int s = Convert.ToInt32(arr[1]);
            int k = Convert.ToInt32(arr[2]);

            Console.WriteLine(lexicoSmallest(n, s, k));
        }

        /*
         * "0 1 1 1 1 3"
         * "0 1 1 1 2 2"
         * 
         * the first one is smaller than the second one. 
         * 
         * So, the result is "0 1 1 1 1 3"
         */
        private static void testCase3()
        {
            string[] arr = "6 7 15".Split(' ');

            int n = Convert.ToInt32(arr[0]);
            int s = Convert.ToInt32(arr[1]);
            int k = Convert.ToInt32(arr[2]);

            Console.WriteLine(lexicoSmallest(n, s, k));
        }
        
        private static void process()
        {
            int q = Convert.ToInt32(Console.ReadLine());

            for (int i = 0; i < q; i++)
            {
                string[] arr = Console.ReadLine().Split(' ');

                int n = Convert.ToInt32(arr[0]);
                int s = Convert.ToInt32(arr[1]);
                int k = Convert.ToInt32(arr[2]);

                Console.WriteLine(lexicoSmallest(n, s, k));
            }
        }

        /*
         * Nov. 11, 2016
         * start time: 11:21pm 
         * 
         * brute force solution, try to get 
         * 1<= n <=5
         * 0<= s <=10 
         * 0<= k <=20
         */
        private static string lexicoSmallest(int n, int s, int k)
        {
            int[] arr = new int[n];
            IList<string> list = new List<string>();

            StringBuilder sb = new StringBuilder();                                

            buildResult(list, n, s, k, 0, sb);

            if (list.Count == 0)
                return "-1";

            return list[0].ToString();
        }

        /*
         * use this code as an example
         * https://github.com/jianminchen/Leetcode_C-/blob/master/17LetterCombinationOfAPhoneNUmber_DFS.cs
         * 
         * Nov. 12, 2016
         * DFS
         * 
         * make the array increasing order
         * 
         * Time complexity: 
         * 
         */
        private static void buildResult(                      
           IList<string> list,
           int arraySize,
           int sum,
           int sumDiff,
           int index,
           StringBuilder current
                )
        {
            if (list.Count > 0)
                return;
            string s = current.ToString(); 

            if (s != null &&
                s.Split(' ').Length == arraySize)
            {                
                if (!sumExactly(current, sum) ||
                   !anyTwoSum( current, sumDiff))
                    return;
                
                list.Add(current.ToString());

                return;
            }

            int sumArr = sumSoFar(current);  // partial 

            int min   = getLastOne(current);
            int start = getFirstOne(current);
            string s1 = current.ToString();  // debug purpose 

            int end = sum;

            // narrow down the loop range: end variable
            if (s1 != null    && 
                s1.Length > 0 && 
                arraySize    >= 2)
            {
                int maxRange = Math.Min(sumDiff / (arraySize - 1), sum);
                end = Math.Min(start + maxRange, sum - sumArr);                                                          
            }
            
            for (int i = min; i <= end; i++)
            {
                bool isReady = sumChecking(sum, sumArr, i) &&
                   anyTwoSumCheck(sumDiff, current, i) ;                

                if (!isReady)
                    break;

                string add = (current.ToString().Length == 0) ? i.ToString() : (" " + i.ToString());
                current.Append(add);

                buildResult( list, arraySize, sum, sumDiff, index + 1, current );

                int len = add.Length;
                current.Remove(current.Length - len, len);  // remove last char
            }
        }     
       
        private static bool sumExactly(StringBuilder sb, int sum)
        {
            int sumArr = sumSoFar(sb);

            return (sumArr == sum);
        }
        
        private static bool sumDiffExactly(StringBuilder sb, int sumDiff)
        {
            string s = sb.ToString();

            if (s == null || s.Length == 0)
                return false;

            int[] arr = toIntArr(s);

            int count = 0;
            for (int i = 0; i < arr.Length; i++)
                for (int j = i + 1; j < arr.Length; j++)
                {
                    count += Math.Abs(arr[i] - arr[j]);
                }

            return count == sumDiff;
        }

        /*
         * ?
         */
        private static bool quickCheck(
           int sumDiff,
           int arraySize,
           StringBuilder current,
           int newValue)
        {
            string s = current.ToString();
            if (s == null || s.Length == 0 || newValue == 0)
                return true;

            string[] arr = s.Split(' ');
            int len = arr.Length;

            if (newValue == Convert.ToInt32(arr[len - 1]))
                return true;

            int sum = 0;
            foreach (string item in arr)
            {
                sum += newValue - Convert.ToInt32(item);
            }

            if (sum * (arraySize - len) > sumDiff)
                return false;

            return true;
        }
        
        private static bool anyTwoSum(           
            StringBuilder sb,
            int sumDiff)
        {
            string s = sb.ToString();

            if (s == null || s.Length == 0)
                return false;           

            int[] arr = toIntArr(s);
            int len   = arr.Length;            

            int count = AbsDiff(arr, len);            

            return count == sumDiff;
        }
       
        private static int sumDiffCal()
        {
            string test = "0 1 2 3 4 5 6 7 8 9 10";
            int[] arr = toIntArr(test);

            int count = 0;
            for (int i = 0; i < arr.Length; i++)
                for (int j = i + 1; j < arr.Length; j++)
                {
                    count += Math.Abs(arr[i] - arr[j]);
                }

            return count;
        }

        private static int sumDiffCal_2()
        {
            string test = "3 3 3 3 3 3 3 3 3 3 25";
            int[] arr = toIntArr(test);

            int count = 0;
            for (int i = 0; i < arr.Length; i++)
                for (int j = i + 1; j < arr.Length; j++)
                {
                    count += Math.Abs(arr[i] - arr[j]);
                }

            return count;
        }              
       
        private static int sumSoFar(StringBuilder current)
        {
            string s = current.ToString();
            if (s == null || s.Length == 0)
                return 0;
            
            int[] arr = toIntArr(s);
            return arr.Sum();
        }

        private static int[] toIntArr(string s)
        {
            if (s == null || s.Length == 0)
                return new int[] { };

            string[] arr = s.Split(' ');
            int len = arr.Length;

            int[] res = new int[len];
            for (int i = 0; i < len; i++)
            {
                res[i] = Convert.ToInt32(arr[i]);
            }

            return res;
        }       

        private static bool sumChecking(
            int sum,
            int sumArray,
            int newItem)
        {
            if (newItem + sumArray <= sum)
                return true;
            else
                return false;
        }
     
        private static int getLastOne(StringBuilder sb)
        {
            string s = sb.ToString();
            if (s == null || s.Length == 0)
                return 0;

            string[] arr = sb.ToString().Split(' ');

            return (Convert.ToInt32(arr[arr.Length - 1]));
        }

        private static int getFirstOne(StringBuilder sb)
        {
            string s = sb.ToString();
            if (s == null || s.Length == 0)
                return 0;

            string[] arr = sb.ToString().Split(' ');

            return (Convert.ToInt32(arr[0]));
        }              

        /*
         * 2:29am - Nov. 13, 2016
         * 
         * Julia did some research
         * reduce time complexity from O(n^2) to O(n)
         * from article:
         * 
         * http://stackoverflow.com/questions/5855066/finding-sum-of-absolute-difference-of-every-pair-of-integer-from-an-array
         * 
         * Assuming that array is sorted, 
         * in ascending order
         */
        private static int AbsDiff(int[] a, int n)
        {
            if ( n < 2 ) return 0;
                    
            int sum = 0;
            int i;
            for(i=n-1;i>=0;i--)
            {
                sum += (a[i]*(i) - a[i]*(n-i-1));
            }

            return sum;
        }

        /*
         * start: 2:47pm
         * 
         * think about this way:
         * The code takes time to write, and takes time to debug; 
         * therefore, the idea should not be in the contest. 
         * 
         * Usually, the idea in the contest should be simple, easy to maintain.           
         * 
         */
        private static bool anyTwoSumCheck(            
            int sum,
            StringBuilder current,
            int newItem
            )
        {
            string s = current.ToString();

            if (s == null || s.Length == 0)
                return true;            
            
            int[] arr = toIntArr(current.ToString());
            int len = arr.Length;

            int total = AbsDiff(arr, len);            

            return (total <= sum);
        }        
    }
}