Aspergillus's blog

By Aspergillus, history, 10 months ago, In English

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:

$$$\text{maximum size} = N - N' + \min\left( \frac{N'}{2}, \frac{\sum A'[i]}{K} \right) $$$

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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good thing I asked for help before setting it as true in my head, I had no Idea! Thank you very much.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lol, i misread JOINSTATE in yesterday's codechef contest which turns out to be exactly this problem

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same.. i also misread and had no idea how so many people solved it felt dumb:(