With regard to staffing levels, you mention that 20% of teachers are on leave on a given working day. Is there a more detailed picture of this figure at the provincial, district, regional and school level? This would give us an idea of which areas are affected the most to devise a solution accordingly.
One approach would be to use a 'locum' model often used in the medical field to dispatch staff to areas with a shortage. For example, temporary teachers provided by a staffing agency working within the national framework. This would need an increase in the supply of teachers at the national level to form the pool of temporary teachers.
Another would be to source teachers from neighbouring schools who can easily travel to where they are needed.
An electronic staff management system to allow such scheduling would be needed.