Problem-Click Here
I have been tried this problem a ton times but i am getting WA in
Subtask 2 Task #2
AND
Subtask 2 Task #3
(Rest All Tasks Are AC)
Solution -Click Here (20 points)
Can Anybody tell any Test case on which my code is Failing?Thank You So much In Advance!!
(I Have Generated Many testcases but couldn’t find one on which my code is failing).
1
10 4
20 19 15 19 11 1 12 19 1 20
Output:11
Expected: 10
I’m not sure if greedy solution would work.
This one -
1
13 3
1 2 2 3 4 5 6 1 2 3 4 5 6
Correct answer - 8 [(1 2 2 3 4 5 6)+(1 2 3 4 5 6)]
Your answer - 9
Note that greedy will not work here. Neither by first partitioning and then merging greedily nor by greedily partitioning the whole array.
Thank You So Much For the Reply, Can You elaborate How Output is Coming out to be 10?
[(20 19 15 19 11) … (1 12 19 1 20)]
Thank You So Much @jay_1048576 For The Test Case I got the Idea where i am wrong.So its A DP Right?
Can You explain the DP approach to this problem?
I don’t Think Output should be 10.
For First Partition-4+2=6
For Second Partition-4+2=6
According to this Partitioning Output will be 6+6=12 and not 10
Thanks!!
How is it 10. This partition is giving 12 = 4×2+2+2.
Oh yes… You’re right.
Acc to this arrangement
[(20 19 15 19 11 1)…(12 19 1 20)].
I got the idea and Conclusion is Greedy will not work.
For every position in the array where there is a conflict (i.e, the frequency count of the element is more than 1), consider two cases:
The crux is to select the minimum value of the two cases.
Repeat the above for every conflict position.
Surely this will be of complexity N^2.
This can be improved by storing the values returned by already computed sections of the array. This is where dynamic programming helps with reducing the compute time.
(20,19,15,19,11,1,12) (19,1,20)
6+4=10
Thanks!!