CODEWITHSUNDEEP
c++dynamiclarge-data
Quân Trần
Quân Trần

Reputation: 27

I need some advice about dynamic programming

Here is the problem : HaNa is a Math Maker. Initially, he has one number n. Every time he performs an action, he will remove any element x, such that x > 1, and then insert to the same position 3 number in order: floor(x/2), x mod 2, floor(x/2). He must continue this operation until he receives the list full of 0s and 1s.

Given that, the list is 1-indexed (the first index of the list is 1). Implement a function sumOfOnes to calculate the sum of the number of number 1 in the range between l and r in the list.

Note that:

I use bottom_up method (dynamic programming) to solve this problem int limit time. Here is my code :

string hana(long long int n)
{
  string* memoize = new string[n+1];
  memoize[0] = "0";
  memoize[1] = "1";
  for(long long int i = 2; i <= n; ++i)
  {
    if(i%2 == 0) memoize[i] = memoize[i/2] + "0" + memoize[i/2];
    else memoize[i] = memoize[i/2] + "1" + memoize[i/2];
  }

  return memoize[n];
}
//
long long int sumOfOnes (long long int n, long long int l, long long int r){
    string result = hana(n);
    long long int ans = 0;
    for(long long int i = l - 1; i <= r - 1; ++i)
    {
        if(result[i] == '1') ++ans;
    }
    return ans;
}

It works well with small input but it doesnt do the same with large input because of lack of memory! I really need some advice about how to deal with large input. Thanks alot!!!

Upvotes: 0

Views: 193

Answers (1)

Secundi
Secundi

Reputation: 1190

First of all, besides several design flaws, you have a heavy memory leak issue, since you heap allocate a local array without proper deletion.

string* memoize = new string[n+1];

Don't do that locally this way, use an std::vector for this:

auto memoize = std::vector<std::string>(n + 1);

Further on, you are recreating the array again and again for each actual value request. This should be avoided at least for your current solving scheme with a fully initialized array, use a more 'global' storage place of the hana-array (preallocated with a maximum possible N)!

For your actual algorithmic issue, without a deeper mathematical insight here and with a feeling that the original problem was stated with more details/precision...:

You'll never be able to solve this with your current approach for n around 50 in an acceptable way.

The key is: It's a common logarithmical problem class, see binary search for instance. You should try to redesign your array access to a recursive function call access, so access to the nth element is always done via a function call and only the first two elements are actually 'concrete'. Without a deeper analysis here in the first place, complexity should already be reducable to something around O(log(n) * (r - l)). I would try to post you a solution but please ensure first, you provided the full problem description here!

Upvotes: 1

Related Questions