How do I install concrete blocks to support deck stairs?
( Note: I see your comment that this is no longer an issue, but since the question is still opened and unanswered, I'll put something down here to get it off of our list and possibly help someone else with a similar issue. )

First things first, Tester is right, don't pay the contractor until you get the permit, and force them to fix their mistakes at their own cost (regardless of whether you paid them or not).

Next, I'm going to suggest ignoring the premise of the question and you remove the stairs to fix this. Depending on how it's attached (I've only done interior stairs where ground movement wouldn't be an issue) you may be able to detach it from the deck, remove any bolts holding it to the supports, and take it out in one piece. Before removing the stairs, make sure to mark the location for the center of your cement pours using stakes about 4' away in two directions (one to the side, and one straight out to the yard, so that with a couple tape measures you can locate the exact spot).

For the hole, make it deep enough to get below the frost line in your location. Fill the bottom with gravel and pour your cement. I like the idea of metal brackets in the cement that keep the wood out of contact with the ground, rather than embedding the post in the cement itself, but only if you have a vertical load and no shear or twisting forces (e.g. I wouldn't use that for a fence). Make sure the bracket is above ground (my neighbor buried his and has all kinds of moisture issues). If you do place the wood support in the concrete, then at least make sure the concrete comes above ground level and slopes away from the wood on all sides.

Finally, reinstall your stairs. Hopefully you measured twice so that all you need to do is cut your supports to the right height and maybe drill some new holes for the bolts.