-1

In reference to the following: 3-PARTITION problem

Could someone please explain why in R. Gurung's cpp solution we are starting our loop of j and k from sum? What if we start our loop from 0?

I modified the given solution a little as follows:

#include <vector>
#include <bits/stdc++.h>
using namespace std;


int partition3(vector<int> &A)
{
  int sum = accumulate(A.begin(), A.end(), 0);
  if (sum % 3 != 0)
  {
    return false;
  }
  int size = A.size();

  vector<vector<int>> dp(sum + 1, vector<int>(sum + 1, 0));
  //bool dp[sum+1][sum+1];
  dp[0][0] = true;

  // process the numbers one by one
  for (int i = 0; i < size; i++)
  {
    for (int j = 0; j <=2*(sum/3); j++)
    {
      for (int k = 0; k <=2*(sum/3); k++)
      {
        if (dp[j][k])
        {
          dp[j + A[i]][k] = true;
          dp[j][k + A[i]] = true;
        }
      }
    }
  }

  for(int i=0;i<=sum;i++)
  {
    for(int j=0;j<=sum;j++)
    {
      cout<<dp[i][j]<<" ";
    }
    cout<<'\n';
  }

  return dp[sum / 3][sum / 3];
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  vector<int> a;

  int n;
  cin>>n;

  for(int i=0;i<n;i++)
  {
    int input;
    cin>>input;
    a.push_back(input);
  }


  cout<<partition3(a);
}

My loop in partition3() works for almost all the solutions and it even passed the test cases of the judge and seemed correct except when i gave a specific test case:

10
20 9 13 27 25 7 2 9 17 15

For the given test case the answer should be 0 This should expect the program to output 0. Since, everyone should get 48, and if anyone take 27, he can not get 48 no matter how he chooses.

But my former algorithm, namely the one who passes the program, outputs 1.

Can someone please explain the flaw? I am not getting it and also why it passes the judge when it is wrong?

EDIT-1

  for (int i = 0; i < size; i++)
  {
    for (int j = sum; j >=0; --j)
    {
      for (int k = sum; k >=0; --k)
      {
        if (dp[j][k])
        {
          dp[j + A[i]][k] = true;
          dp[j][k + A[i]] = true;
        }
      }
    }
  }

The above loops outputs the correct answer (0) to the given test case. Please explain the error in my solution.

Vedansh Jain
  • 1
  • 1

1 Answers1

0

Assuming that the function of R. Gurung's is correct. There is a dependency between dp and A so you cannot fill it from the begin to the end as you suggest.

Bouraoui Al-Moez L.A
  • 679
  • 6
  • 16
  • I thought so aswell but the loop i provided in the edited part works fine and outputs correct answer. Infact when i outputted the complete generated vector dp[][], there were a lot of differences in the two (my revised solution and EDIT-1). Could u please explain why? – Vedansh Jain May 05 '20 at 10:55
  • It looks like you are not filling all elements try that **for (int j = 0; j – Bouraoui Al-Moez L.A May 05 '20 at 11:04
  • I cannot do that since **dp[j + A[i]][k] = true; dp[j][k + A[i]] = true;** would give error if **j+A[i] or k+ A[i]** becomes more than the sum. – Vedansh Jain May 05 '20 at 11:25
  • You can't use your solution as the first items of **A** are filled with the last items of **dp** – Bouraoui Al-Moez L.A May 05 '20 at 11:49