Android - There is a problem parsing the package

This was a head scratching problem I had. I copied an apk to my phone and tried to install it but immediately got an error

There is a problem parsing the package

So I opened up Android Studio, assembled it again and re-installed it. Same problem. I checked the manifest, checked gradle and a few million other things! Some hours later I tried:

adb install C:/folder/myapp.apk

Then I checked the ADB logcat and finally I had something to go on.

Installation error: INSTALL_PARSE_FAILED_MANIFEST_MALFORMED

How frustrating! Couldn't I have been told that during build? Well at least I had something. It turned out to be a missing provider authority for a specific flavour. Oh well, next time I'll know what to do first!