# Any Corner Case in CHEFWED?

I have been tried this problem a ton times but i am getting WA in
AND

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.

1 Like

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)]
Note that greedy will not work here. Neither by first partitioning and then merging greedily nor by greedily partitioning the whole array.

2 Likes

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)]

1 Like

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?

1 Like

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)].

2 Likes

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:

1. You actually split the array at that point and add a new table.
2. You do not split and you simply increase the inefficiency of the current table.

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.

1 Like

(20,19,15,19,11,1,12) (19,1,20)
6+4=10

1 Like

@shantanumallik Thank you so much for the genuine explaination!!

1 Like

Thanks!!