abhishekg's blog

By abhishekg, 9 years ago, In English

some one please help me how to approach http://www.spoj.com/problems/LPPP problem. I am not getting any idea how to solve this problem. Although i have read about how to divide an array into two sets of equal sum using dynamic programming but not able to get this one.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

It's easy to imagine recursive DP:

bool DP(int a, int b, int c, int coinNumber)
{
   if (coinNumber == n) return a == b && b == c;
   return DP(a + coinValue[coinNumber], b, c, coinNumber + 1) ||
       DP(a, b + coinValue[coinNumber], c, coinNumber + 1) ||
       DP(a, b, c + coinValue[coinNumber], coinNumber + 1) ||
}

Where a, b and c — amount of money for three brothers.
Now you should transform recursive DP into iterative.

dp[0][0][0] = true;
for (int coinNumber = 0; coinNumber < n; ++coinNumber)
{
   dpNew = AddCoinToDPTable(dp, coinValue[coinNumber]);
   dp = dpNew;
}

Note you don't need to store value c, because a+b+c is constant and equals to coinValue[0]+... +coinValue[coinNumber]. So you need DP table dp[50 * 50 / 3][50 * 50 / 3]

  • »
    »
    9 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    @Alias thanks

    Accepted now :)

    but can you tell me how to solve this problem using bottom up approach as i don't get how to solve

    this problem using bottom up approach , i solve this problem using memoizaton...

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it
      mat AddCoinToTable(const mat& d, int coinValue)
      {
          mat res = d;
          FOR(a, N)
              FOR(b, N)
                  if (d[a][b])
                  {
                      if (a + coinValue < N)
                          res[a + coinValue][b] = 1;
                      if (b + coinValue < N)
                          res[a][b + coinValue] = 1;
                  }
          return res;
      }
      
      bool CanDivide(const vi& coinValues)
      {
          mat dp(N, vector<char>(N, 0));
          dp[0][0] = 1;
          FOR(coinNumber, coinValues.size())
          {
             mat dpNew = AddCoinToTable(dp, coinValues[coinNumber]);
             dp = dpNew;
          }
      
          int sum = 0;
          FOR(i, coinValues.size())
              sum += coinValues[i];
      
          return sum % 3 == 0 && dp[sum / 3][sum / 3] != 0;
      }