Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# Where is my logic wrong in this dynamic programming problem?

Tags:
  1. Oct 29, 2016 #1
    I'm trying to solve https://www.hackerrank.com/challenges/summing-pieces and I think I have come up with an O(n) solution although the numbers aren't coming out exactly right. The problem is essentially to find a sum like

    ABCD
    ---> All sets of sets of contiguous subarrays spanning ABCD is
    { {ABCD}, {ABC, D}, {A, BCD}, {AB, CD}, {AB, C, D}, {A, BC, D}, {A, B, CD}, {A, B, C, D} }
    ---> special sum is
    4(A+B+C+D) + 3(A+B+C) + 1(D) + 1(A) + 3(BCD) + 2(AB) + 2(CD) + 2(AB) + 2(C) + 2(D) + 2(A) + 2(BC) + 2(D) + 2(A) + 2(B) + 2(CD) + 2(A) + 2(B) + 2(C) + 2(D)


    Let me know if you see anything wrong with my attempted C# solution, and I would appreciate any general comments on my coding style.

    Code (Text):

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

    /// <summary>
    /// Helper class for finding the sum of elements in a contiguous section
    /// of an array in O(1) time.
    /// </summary>
    public class RangeSummer
    {
        /// <summary>
        /// _s[i] = arr[0] + ... + arr[i]
        /// </summary>
        private long[] _s;

        /// <summary>
        /// Length of _s and arr
        /// </summary>
        public int Length { get; private set; }

        /// <summary>
        /// Initializes using the source aray <param name="arr"></param>
        /// </summary>
        /// <remarks>
        /// Initialization takes O(n) time
        /// </remarks>
        public RangeSummer(long[] arr)
        {
            int n = arr.Length;
            Length = n;
            _s = new long[n];
            for (
                long sum = 0, i = 0;
                i < n;
                sum += arr[i], _s[i] = sum, ++i
            ) ;
        }

        /// <summary>
        /// this[i,j] = the sum of the elements of arr in the range [i, j)
        /// </summary>
        /// <remarks>
        /// Uses the fact that  arr[i] + ... + arr[j - 1] = s[j - 1] - s[i - 1]
        /// </remarks>
        public long this[int i, int j]
        {
            get
            {
                return i == 0 ? _s[i] : _s[j - 1] - _s[i - 1];
            }
        }
    }

    internal class Solver
    {
        /// <remarks>
        /// The problem useslessly makes us mod our answer by 10^7+9
        /// for the final output.
        /// </remarks>
        private long _divisor = (long)Math.Pow(10.0, 9.0) + 7;

        /// <summary>
        /// Utility class for fast lookup of sum of elements
        /// of source array in a given range
        /// </summary>
        private RangeSummer _summer;

        /// <summary>
        /// Single constructor. Since the only purpose of this class
        /// is to solve a single problem, class could be made into
        /// a functor or could use a similar design pattern.
        /// </summary>
        /// <param name="arr">Source array</param>
        public Solver(long[] arr)
        {
            _summer = new RangeSummer(arr);
        }

        /// <summary>
        /// Wrapper function for recursive solution
        /// </summary>
        /// <returns>Final answer</returns>
        public long GetSpecialSum()
        {
            long sum = GetSpecialSum_Recursive(0, _summer.Length);
            return sum % _divisor;
        }

        /// <summary>
        /// Inner function of recursive solution
        /// </summary>
        /// <remarks>
        /// Uses the fact that the solution f({A_0,...,A_n-1})
        /// is equal to
        /// n * (A_0 + ... + A_n-1) + f({A_1, ..., A_n-1}) + A({A_0, ..., A_n-2})
        /// </remarks>
        /// <param name="i">starting index</param>
        /// <param name="j">1 off-the-end of second index</param>
        private long GetSpecialSum_Recursive(int i, int j)
        {
            return i >= j ? 0 :
                (j - i) * _summer[i, j] // (j - i) (arr[i] + ... + arr[j - 1])
                + GetSpecialSum_Recursive(i, j - 1)
                + GetSpecialSum_Recursive(i + 1, j);
        }
    }

    /// <summary>
    /// Solution to the HackerRank problem [PLAIN]https://www.hackerrank.com/challenges/summing-pieces.[/PLAIN] [Broken]
    /// This is for testing and debugging locally. The code pased into the solution box will
    /// be slightly different since it reads the input from the console.
    /// </summary>
    class Solution
    {
        static void Main(String[] args)
        {
            // get test file
            string curdir = Directory.GetCurrentDirectory();
            System.IO.StreamReader file = new System.IO.StreamReader(
                Path.GetFullPath(
                    Path.Combine(curdir, @"..\..\", "TestFiles\\TestTwo.txt")
                ) // second line is 4 2 9 10 1
            );

            // get input and solve
            int.Parse(file.ReadLine()); // don't need this line
            long[] arr = Array.ConvertAll(file.ReadLine().Split(' '), long.Parse);
            Console.WriteLine(new Solver(arr).GetSpecialSum());
        }
    }
     
     
    Last edited by a moderator: May 8, 2017
  2. jcsd
  3. Oct 30, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That is not useless. The actual sum is way too large for any reasonable number format for large n. It also means you have to take it into account in intermediate steps unless you want to store integers with hundreds of thousands of digits.


    I don't follow the logic in GetSpecialSum_Recursive and it looks like an O(2n ) implementation.

    Before you write the first line of code: This is a problem that needs some thought on how to calculate the sum efficiently. O(n) is possible, but not by brute force.
     
  4. Oct 30, 2016 #3

    Mark44

    Staff: Mentor

    Make sure your comments are accurate descriptions of the code. _divisor is actually ##10^9 + 7##, not ##10^7 + 9## as stated in the comment. A comment that is inaccurate is worse than no comment at all.
     
    Last edited: Oct 30, 2016
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Where is my logic wrong in this dynamic programming problem?
Loading...