Hey everyone, I submitted this Solution and got WA in only 6th test case. I tried to solve it by many logic , still got judge verdict wrong.
Please help me , why i m getting WA
I feel the test cases for the problem Sereja and Stones in the present Long challenge was quite weak, allowing greedy solutions to pass for 100 points. Below is mine greedy solution for 100 points.
(See for subtask 1 and 2 i call differnt function and for subtask 3, I use greedy function i.e. solve2)
Only Test file 6 in subtask 2, requires a correct application of dynamic programming algorithm for the solution. Rest all of the test files pass with a greedy approach. I also saw that many coders are struck on 70 points for the problem and guess that they are also facing the problem of test file 6 in their code.
Link to dynamic programming solution, using maps
Actually, I generated about 100 random test cases on my system and was convinced that if the DP was written in top down manner, then not all the states would be visited. (In my random case about 30% of the total position*left choices were visited).
A hint about the Dynamic programming solution:
Let us first think about the normal greedy solution. I sort the array in descending order and then try to equally divide the m pieces among the {1}^{st} i pieces, and then try to place the remaining m%i pieces in remaining places. Here, most of us used the greedy approach in the sense that we should place the all the remaining pieces, either in the next location only or if possible divide it equally among the remaining (n - i) places. But actually, this is wrong.
We can easily see the sub-structure property of dynamic programming here when we try to solve for remaining (n - i) positions using m%i pieces left. Thus, I used to calculate the Dynamic programming solution using 2 states : pos, denoting the position in the array and left denoting how many pieces I need to place in the remaining array.
Since this 2-D dp array can’t be declared due to large array size, I used a map. Actually, a more elegant solution existed using \texttt{"unordered\_map"} to remove the O(\log n) factor due to map as well. but their was a glitch here “pair<int,int>” can be used with \texttt{"unordered\_map"} due to they being non-hashable.
Here is my final solution, using \texttt{"unordered\_map"} with a running time of 0.45 sec
Also, I saw some of the codes of big users like \texttt{min\_25} and he had also used recursion as well, but is approach was a bit different due to which he got a very fast execution time as well.
If you have any doubts or feel that I may be wrong somewhere, you can ask in comments below.
Happy Coding 
3 Likes
I think that greedy approach is correct approach to solve the problem only if its implementation covers all the corner cases. If there are any corner cases for which the greedy solution is vulnerable, then kindly mail them to me at [email protected] Here is my implementation of Greedy approach with AC verdict.
2 Likes
Solutions of both of you fails on the following test case:
1
8 11
1 5 5 5 5 5 1000 1000
Your output - 61
Correct output - 57 (When the stones are distributed in order 0,1,1,1,1,1,3,3)
P.S. - I know that my input energies does not fulfill the energy constraints 7<=E[i]<=77, but still this shows that both the dp as well as greedy solutions are flawed.
2 Likes
I think, dp solution is not flawed, just that the test cases are weak. My solution is definitely wrong. Thanks for pointing out the test case.
May be E[i] <= 77 helped our case, but I ran @ceilks solution on your test case and gave output as 57. Thus showing that proper dp solution existed.
1 Like
Thanks Bro