This problem has been bugging me since morning today. I have a number K, and an array A with N elements. I can merge any amount of numbers in the array such that each element in the end is at least K. I want to merge minimum number of elements to achieve this, or in other words the final array should have maximum size.
Let's say $$$K = 6$$$ and $$$A = [4, 4, 5, 5, 6, 7, 9]$$$ (here size = $$$N = 7$$$) I have this proposed solution which I have not been able to prove/disprove with several random outputs.
The solution is: consider the subset of A containing all the elements which are less than K, which for this A is $$$A' = [4, 4, 5, 5]$$$, (size = $$$N' = 4$$$), my solution is:
For the given example, max length = 3 + min(2, 3) = 5, which corresponds to 9, 9, 6, 7, 9 after merging the 4s and 5s.
If anyone can help me give a counterexample or help me prove the solution, please do so.
A counterexample: $$$[3,4,5,8]$$$, with $$$K = 10$$$.
But I want to emphasize that this is an NP-hard problem, so an efficient solution cannot be this simple. One can solve the partition problem with a reduction to this, by choosing $$$K = \frac{sum}{2}$$$ (as I did above).
Good thing I asked for help before setting it as true in my head, I had no Idea! Thank you very much.
Lol, i misread JOINSTATE in yesterday's codechef contest which turns out to be exactly this problem
Same.. i also misread and had no idea how so many people solved it felt dumb:(