Very hard cheeses do not melt like soft and semi-soft cheeses which is what makes parmesan the best cheese to get exactly the right texture and coating for these potatoes.