Reporting back a year later.... yup, you need one of each element. I got this in combination with the smoosh 10 creatures in one turn one (double catastrophe). I used Decoys against an AI who had no chance - Zogal. Also, I used Phantasm on my decoys, even though I could have cast Catastrophe, lapped, then cast the second Catastrophe.
Good times.. Only two medals left - 50 and 100 story mode wins