During review, I found a superior solution. What now?
I didn't get a clear impression of your opinion of the authors' work.  "Solving an important problem" ought to make for an excellent paper, but the rest of your description seems to partially negate that.  (In particular, I don't quite know what a "nonstandard input parameter" is, but it sounds a bit like they are cheating or that the legitimacy of their solution could be a matter of debate.)  

Either way, it seems to follow from what you say that you feel that you have solved an important problem, indeed in a better way than the authors.  Unless you are such a known superstar in your field that this is a commonplace occurrence for you, I would think that you deserve to get more out of this than an anonymous thanks.  To me the options seem to be:

1) If the authors' paper is strong enough to be published, say so.  You should not hide your opinions about their shortcomings, but you don't have to include your new ideas in your referee report.  Then:

1a) If just by responding to your criticism (if they care to) the authors replicate your better solution, then it seems that you did not add critical value, and I would just recommend accepting their modified version and letting the matter end there.  

But

1b) If your conscientious refereeing produces a version that is worth publishing but does not replicate your superior solution, then you should prepare your solution for publication.  The timing of this is something that you should ask for other opinions about.  It would be ideal if the authors had circulated their results in preprint form.  If not, you may need to delay submission until their paper actually appears.

2) If you think the paper is not publishable in its current form in the journal to which it was submitted but that it inspired you to solve the problem in a better way, this may be a case for you to ask permission to contact the authors and add your work to theirs.  

3) If the work is really not valuable and your solution has little or nothing to do with theirs, then you could just recommend the paper for rejection and then submit your own solution elsewhere.  Examine your conscience carefully before doing this though: imagine that the authors found out exactly what you did.  Would they see it your way?