Incorrect algorithm
Opened this issue · 9 comments
Input:
6
2 1 4 4 4 6
Your program outputs 1, although there is now way to partition this array into three subsets with equal sums.
Thanks for the input, @lngsv everywhere I was seeing solutions that have multidimensional arrays for different partitions, but this seemed to use only 2D array for DP. Wasn't able to find a negative test case to prove it wrong. Thanks for the test case.
I have the same issue here. (Time used: 9.98/5.00, memory used: 20656128/536870912.) Same code written here. Will be glad if shown how I could solve this problem.
Which program is this?
6.2 partition souvenirs.py
I don't know the correct solution either.
And another fail test case is:
9
7 2 2 2 2 2 2 2 3
The code's output is 1, but in fact, it should be 0.
What this guy is trying to do is that he is looking for the number of ways total_count//3 is found in the table.
But he didn't take into account the fact that this can actually be formed by 3 different ways and some elements maybe common in the 3. So, that will not actually be the solution since we cannot add same element in two different partitions.
Let's take this example-
6
2 1 4 4 4 6
So, here total sum is 21. We will be looking for 7 in the table.
We will get 7 here in following ways-
6+1, 4+2+1,4+2+1 (since there are multiple 4's). Now these all are using '1' but there is only one '1' in the list. So, these are not actually the three different partitions. The assumption with which the author has written the code is not completely correct.
https://github.com/Yash-099/cp_practise/blob/main/Set2/Q2/Q2.py
I have written something. This passes the above two test cases. Please let me know if this is correct or not.
hello, I have difficulty with the 21 questions game. Can anyone please help me?
hello, I have difficulty with the 21 questions game. Can anyone please help me?
Ahhh, this is quite difficult. I fail too.
What this guy is trying to do is that he is looking for the number of ways total_count//3 is found in the table. But he didn't take into account the fact that this can actually be formed by 3 different ways and some elements maybe common in the 3. So, that will not actually be the solution since we cannot add same element in two different partitions.
Let's take this example- 6 2 1 4 4 4 6
So, here total sum is 21. We will be looking for 7 in the table. We will get 7 here in following ways- 6+1, 4+2+1,4+2+1 (since there are multiple 4's). Now these all are using '1' but there is only one '1' in the list. So, these are not actually the three different partitions. The assumption with which the author has written the code is not completely correct.
Yes, I deem we should delete something from a completed set.