I'm not sure if this algorithm (or code perhaps) is correct or not. Any help would be greatly appreciated.
Examples use this test case:
9
1 2 1 3 2 2 2 2 3
The algorithm is:
- Store the values and the sum of them all. For this test case it is:
1: 2
2: 10
3: 6 - Then, sort the list by how much the total sum of the list is reduced by. If any two elements have equal impact on the list, then we take whichever has the largest sum.
1: 2: 10
2: 3: 6
3: 1: 2 - Then proceed to remove the values
Code can be found on the submission: 13754753
You can't solve it with greedy.
Test Case — 11
1 1 2 2 2 3 3 4 4 4 4
Your output = 18
Correct output = 22
Greedy means that at each stage you choose whatever is best for you and move accordingly.
For Example — You at each step are looking at the contribution to reduction and you are moving accordingly. But even if reduction caused by 1 (in above test case) is less than that of 2, 2 contributes much more to the score.
Hence, at each step you will have to check both the possibility of reduction and contribution to score, and you have to remove whichever contributes more to your score.
In other words you will have to consider all possible cases.
A recursion will not work in the given constraints.
So you can either go for Memorization or you can code bottom up to get a Dynamic Programming solution. Both will be able to see all possible cases.
I hope it helps!
I know this is old but I don’t have access to write post yet. Answer to the case should be 12, 10 is given by judge.
9 1 2 1 3 2 2 2 2 3
Remove 3 3 2 2 2 in that order to get 12