Yeah it has to be a prize. It doesn't just come out of nowhere.

The chocobo thing sucks and I wasn't able to do it for years. I just finished it for the first time the other day so it is possible! You just need a goood balloon placement and also try to use the trainer as a blocker for some of those birds. That really helped me.