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

Tags:
1. Oct 29, 2016

### SlurrerOfSpeech

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>
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();
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. Oct 30, 2016

### 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.

3. Oct 30, 2016

### 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