3
$\begingroup$

I've recently come across this problem:

Find all solutions to the equation $a + 2b^2 = 3c^3 + 4d^4$ for which $a, b, c, d$ are all less than $100,000$. Hint: use one min-heap and one max-heap.

I can think of an algorithm involving two min-heaps (one for the LHS and one for the RHS), but can't figure out how a max-heap can be used. It needs to be efficient.

How could a max-heap be incorporated?

$\endgroup$
  • 1
    $\begingroup$ The solution you have in mind could be a variant on the solution the setter had in mind. Don't take the hint as scripture. $\endgroup$ – Yuval Filmus Feb 11 '16 at 10:39
  • 1
    $\begingroup$ If you have created two accounts, I encourage you to merge them: cs.stackexchange.com/help/merging-accounts. Thank you! $\endgroup$ – D.W. Feb 11 '16 at 12:27
1
$\begingroup$

A min-heap with entries $x_i$ is equivalent to a max-heap with entries $-x_i$ (or more generally, $A - Bx_i$ for any $B > 0$, or even more generally, $\phi(x_i)$ for any monotone decreasing $\phi$). So you can convert your solution with two min-heaps to a solution with one min-heap and one max-heap, as well as to a solution with two max-heaps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.