Faits : A. A.a. Le 19 décembre 2017, A._, B._, C._, D._, E._, F._, G._, H._, I._, J._, K._, L._, M._, N._, O._, P._, Q._, R._, S._, T._, U._, V._, W._, X._, Y._, Z._, A1._, B1._, C1._, D1._, E1._, F1._, G1._, H1._, I1._, J1._, K1._, L1._, M1._, N1._ et O1._ (ci-après: les aspirants) ont été engagés en qualité d'aspirants à la police cantonale genevoise (ci-après: la police) pour suivre, dès le 1er avril 2018, une formation de douze mois à l'Académie de police de (...) (ci-après: l'académie). Le même jour, les aspirants ont reçu en mains propres un courrier de la commandante de la police sur les conditions de leur engagement. Il y était indiqué qu'ils recevraient une indemnité mensuelle brute de 4'854 fr. pendant la formation (classe 08, annuité 01). Par ailleurs, ils devaient être affiliés à une caisse-maladie reconnue par la LaMal. Le courrier précisait encore que la fonction de policière ou de policier nécessitait d'avoir réussi une école de police et obtenu le brevet fédéral correspondant. La réussite de ces formations ne garantissait cependant pas un engagement dans la police. Toujours le 19 décembre 2017, les aspirants ont signé une convention de formation. Celle-ci prévoyait notamment que les frais de formation pourraient être mis à leur charge en cas de démission ou de renvoi pour justes motifs durant la phase académique de la formation. Conformément à l'art. 31 al. 1 et 2 de la loi [du canton de Genève] sur la police du 9 septembre 2014 (LPol; RS/GE F 1 05), ils s'engageaient de surcroît à servir dans la police durant trois ans au moins et, pour le cas où ils contreviendraient à cet engagement, à rembourser les frais de formation correspondants. A.b. Par courrier du 24 juillet 2018, le directeur des ressources humaines de la police (ci-après: le directeur RH) a corrigé certaines informations communiquées aux aspirants à l'occasion d'une présentation. Un projet de loi modifiant la LPol prévoyait en effet de remplacer, dès le 1er janvier 2019, la prise en charge de la prime d'assurance-maladie par le paiement d'une indemnité forfaitaire mensuelle de 583 fr. 30 pour les catégories de collaborateurs mentionnés aux alinéas 1 à 4. Les policiers et les assistants de sécurité publique de niveau 4 qui étaient exclus, du champ d'application de cette disposition (cf. consid. 2 infra), ne bénéficiaient d'aucun droit à la prise en charge de l'assurance-maladie ni au versement d'une indemnité dès le 1er janvier 2019 (art. 67 al. 2 à 4 LPol; modifications du 25 mai 2018). A.c. Le 27 août 2018, les aspirants de la volée d'avril 2018 ont demandé au directeur RH de prendre en considération le fait qu'ils avaient signé un contrat avant la modification de la LPol. Le 22 octobre 2018, le directeur RH leur a répondu qu'aucune suite positive ne pouvait être donnée à leur requête. Il fallait distinguer deux contrats: le premier pour la formation à l'académie et le second pour la prise de fonction à la police dès l'obtention du brevet fédéral. Les conditions d'engagement correspondaient aux conditions contractuelles en vigueur au moment de la signature. Au 19 décembre 2017, jour de la signature de la convention de formation, l'employeur prenait encore en charge la prime d'assurance-maladie. La base légale concernée avait été modifiée le 25 mai 2018 à la suite des négociations entre les syndicats de la police et la délégation du conseiller d'Etat en charge de la police. A.d. Le 9 novembre 2018, les aspirants ont demandé à la commandante de la police de confirmer leur droit à la couverture prévue par l'art. 67 al. 1 let. b LPol. Ils souhaitaient par ailleurs savoir si le courrier du 22 octobre 2018 du directeur RH devait être considéré comme une décision et, dans la négative, demandaient qu'une décision fût rendue. Leur conseil a joint un avis de droit à ce sujet. Le 21 novembre 2018, les aspirants ont réitéré leur demande. Le 17 décembre suivant, la commandante de la police a répondu à ces courriers. La lettre du 22 octobre 2018 ne constituait pas une décision et reflétait uniquement la décision prise dans le protocole d'accord entre le Conseil d'Etat et les syndicats de police, signé le 19 décembre 2017, ainsi que la modification de l'art. 67 LPol par le Grand Conseil. Il n'y avait dès lors pas lieu d'entrer en matière sur la demande des aspirants. B. Le 1er février 2019, les aspirants ont saisi la Chambre administrative de la Cour de justice de la République et canton de Genève d'un "recours en déni de justice et au fond". Ils concluaient à titre principal au constat du déni de justice commis par le Département de la sécurité, de l'emploi et de la santé (ci-après: DSES) et au renvoi de la cause à cette autorité pour qu'elle rende une décision qui reconnaisse leur droit à l'indemnité litigieuse. A titre subsidiaire, ils demandaient la réforme de la décision contenue dans le courrier du 17 décembre 2018 de la commandante de la police en ce sens que le droit à l'indemnité litigieuse leur soit reconnu. Après avoir tenu une audience de comparution personnelle au cours de laquelle trois aspirants ont été entendus, la cour cantonale a déclaré le recours irrecevable par jugement du 27 août 2019. C. Les mêmes intéressés interjettent un recours en matière de droit public devant le Tribunal fédéral. Ils concluent à l'annulation du jugement cantonal et au renvoi de la cause à l'instance précédente afin qu'elle entre en matière sur le recours et rende une nouvelle décision. Le DSES conclut au rejet du recours.