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.

Considérant en droit :
1.
1.1. Dans une procédure administrative, l'auteur d'un recours déclaré irrecevable pour défaut de qualité pour agir est habilité à contester l'arrêt d'irrecevabilité par un recours en matière de droit public lorsque l'arrêt au fond aurait pu être déféré au Tribunal fédéral par cette voie (<ref-ruling> consid. 3.2 p. 149; <ref-ruling> consid. 1 p. 500).
1.2. Tel est le cas en l'espèce. Le jugement attaqué est une décision finale (<ref-law>) rendue dans une cause de droit public (<ref-law>) par une autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF). Le litige au fond porte sur le paiement d'une indemnité pour la prime d'assurance-maladie dans des rapports de travail de droit public. Il s'agit d'une contestation pécuniaire, de sorte que le motif d'exclusion de l'art. 83 let. g LTF n'entre pas en considération. En outre, la valeur litigieuse dépasse le seuil de 15'000 fr. (art. 51 al. 1 let. a et 85 al. 1 let. b LTF). En effet, un recourant engagé comme policier au bénéfice de l'indemnité litigieuse toucherait 6999 fr. 60 par an à ce titre (583 fr. 30 x 12), soit près de 140'000 fr. sur vingt ans (<ref-law>). Le seuil de 15'000 fr. serait en outre atteint dès le premier mois de fonction si les quarante-et-un recourants devaient tous être engagés comme policiers au bénéfice de l'indemnité litigieuse (41 x 583 fr. 30 = 23'915 fr. 30) (<ref-law>). Le recours ayant été interjeté dans le délai et les formes utiles, il y a donc lieu d'entrer en matière.
2.
La procédure concerne le droit des recourants à bénéficier de la couverture prévue à l'art. 67 al. 1 let. b LPol. Cette disposition prévoit que, jusqu'à l'entrée en vigueur d'une nouvelle grille salariale ayant fait l'objet d'une négociation avec les organisations représentatives du personnel, l'assurance-maladie, telle que prévue en faveur des policiers par les art. 47 et 52 de la loi sur la police du 26 octobre 1957, est maintenue. Par modification du 25 mai 2018, entrée en vigueur le 28 juillet 2018, l'art. 67 LPol a été complété par un al. 2. Celui-ci dispose que la prise en charge de l'assurance-maladie au sens de l'art. 67 al. 1 let. b LPol est remplacée, dès le 1er janvier 2019, par le paiement d'une indemnité forfaitaire mensuelle de 583.30 fr., pour les collaborateurs qui remplissent l'une des conditions suivantes: (1) policiers au bénéfice d'une lettre d'engagement au 1er janvier 2018; (2) assistants de sécurité publique de niveau 4 au bénéfice d'une lettre d'engagement au 1er janvier 2018; (3) policiers ayant terminé au plus tard le 31 décembre 2018 l'école de police commencée en 2017; (4) officiers supérieurs et policiers brevetés mis au bénéfice d'une lettre d'engagement entre le 1er janvier 2018 et l'entrée en vigueur du présent alinéa (à savoir le 28 juillet 2018). A défaut, les policiers et les assistants de police de niveau 4 ne bénéficient 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. 4 LPol).
3.
Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 2.3 p. 266) - ou en violation du droit au sens de l'<ref-law> (<ref-law>), et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (<ref-law>). Conformément à l'<ref-law>, la partie recourante doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. A défaut, un état de fait qui diverge de celui retenu par l'acte attaqué doit être écarté (<ref-ruling> consid. 5.1 p. 356). Les faits et les critiques invoqués de manière appellatoire sont irrecevables (<ref-ruling> consid. 2.4 p. 367).
Dans leur mémoire de recours, les recourants indiquent se rapporter aux faits constatés par l'autorité cantonale tout en précisant que ceux-ci seront critiqués, complétés voire repris en tant que de besoin. Ils ne soulèvent cependant pas de grief lié à l'établissement inexact des faits ni ne soutiennent que ceux-ci auraient été établis de façon arbitraire ou contraire au droit, se contentant d'exposer leur propre vision de la situation. Il n'y a donc pas lieu de s'écarter de l'état de fait établi par la cour cantonale.
4.
La cour cantonale a constaté que les recourants ne réclamaient pas la prise en charge de leurs primes d'assurance-maladie. En effet, ils admettaient eux-mêmes que la question ne se posait pas pendant leur formation, car leur rémunération excluait cette prise en charge. Ils avaient uniquement requis du DSES des garanties à ce sujet pour le moment où ils auraient terminé et réussi leur formation et pour autant qu'ils eussent été ensuite engagés comme policiers. Ainsi, leur requête ne concernait pas leur situation au moment du refus de rendre une décision ou au moment du recours, mais se rapportait à une situation future et hypothétique dans laquelle ils seraient policiers. Par ailleurs, la cour cantonale a relevé qu'une décision formatrice incluant la question de la rétribution avait été rendue en cours de procédure pour chacun des recourants concernés lors de son engagement en qualité de policière ou de policier. L'intérêt digne de protection des recourants pour déni de justice faisait donc défaut au moment du recours. Le même raisonnement valait dans l'hypothèse où le courrier du 17 décembre 2018, par lequel la commandante de la police refusait d'entrer en matière sur les requêtes des recourants, devait être qualifié de décision. Pour ces motifs, la cour cantonale a déclaré le recours irrecevable.
5.
5.1. Dans un grief d'ordre formel, les recourants invoquent une violation de leur droit d'être entendus (art. 29 Cst. et 6 CEDH). Ils estiment que la cour cantonale a omis de traiter la question du droit à une décision au sens de l'art. 4A de la loi [du canton de Genève] du 12 septembre 1985 sur la procédure administrative (LPA; RS/GE E 5 10). Elle aurait ainsi manqué à son devoir de motivation et à l'interdiction du déni de justice formel.
5.2. Le droit d'être entendu consacré par l'art. 29 al. 2 Cst. impose à l'autorité le devoir de motiver sa décision afin que le justiciable puisse en saisir la portée et, le cas échéant, l'attaquer en connaissance de cause. Pour satisfaire à cette exigence, il suffit que l'autorité mentionne au moins brièvement les motifs qui l'ont guidée et sur lesquels elle a fondé sa décision (<ref-ruling> consid. 5.2 p. 70; <ref-ruling> consid. 4.3.2 p. 436). Elle n'a pas l'obligation d'exposer et de discuter tous les faits, moyens de preuve et griefs invoqués par les parties, mais peut au contraire se limiter à ceux qui, sans arbitraire, peuvent être tenus pour pertinents (<ref-ruling> consid. 4.2 p. 157). L'art. 6 CEDH ne confère pas une protection plus étendue que celle qui découle, sur le plan interne, de l'art. 29 al. 2 Cst. (<ref-ruling> consid. 1b p. 308).
5.3. En l'espèce, les juges cantonaux ont déclaré le recours irrecevable faute d'intérêt actuel à recourir. Ils pouvaient ainsi renoncer à examiner les arguments des recourants en lien avec le droit à une décision selon l'art. 4A LPA et le fond du litige, sans commettre de déni de justice ou manquer à leur devoir de motivation. En outre, comme l'a fait remarquer à juste titre l'intimé, le jugement attaqué expose de façon circonstanciée les motifs pour lesquels il nie un intérêt actuel au recours et déclare le recours irrecevable. Le grief tiré de la violation du droit d'être entendu et du déni de justice se révèle ainsi mal fondé.
6.
6.1. Les recourants font ensuite valoir une violation de l'<ref-law> en tant que la cour cantonale leur dénie un intérêt digne de protection à obtenir une décision et à recourir contre le courrier de la commandante de la police du 17 décembre 2018. Ils estiment que l'engagement qu'ils ont pris de servir durant trois ans au moins dès leur nomination dans la police et, pour le cas où ils contreviendraient à cet engagement, de rembourser les frais de formation conformément à l'art. 31 al. 1 et 2 LPol leur conférerait un intérêt actuel et concret à clarifier les conditions de rémunération à la suite d'un changement de loi. Les recourants disposeraient en toute hypothèse d'un intérêt futur suffisant dès lors que sa réalisation paraît vraisemblable d'après le cours ordinaire des choses. Enfin, les recourants présents à l'audience de comparution personnelle auraient confirmé que la suppression de l'indemnité litigieuse aurait des conséquences directes sur eux.
6.2.
6.2.1. L'<ref-law> dispose que la qualité de partie à la procédure devant toute autorité cantonale précédente doit être reconnue à quiconque a qualité pour recourir devant le Tribunal fédéral. Le droit cantonal doit par conséquent définir la qualité de partie conformément à l'<ref-law>: il peut la concevoir de façon plus large, mais pas de façon plus étroite (<ref-ruling> consid. 5.2.1 p. 236 s.; <ref-ruling> consid. 2.1.1 p.164; <ref-ruling> consid. 5 p.149). Le droit genevois ne conçoit pas la qualité pour recourir de façon plus large que l'<ref-law>, de sorte qu'il convient d'examiner la qualité pour recourir sous l'angle de cette dernière disposition (<ref-ruling> consid. 2.1 p. 46). S'agissant de droit fédéral (<ref-law>), le Tribunal fédéral examine librement cette question.
6.2.2. Selon l'art. 89 al. 1 let. c LTF, qui correspond à l'art. 60 al. 1 let. b LPA (<ref-ruling> consid. 2.2 p. 46), la qualité pour recourir est reconnue à toute personne qui dispose d'un intérêt digne de protection à demander la modification ou l'annulation de la décision attaquée. Cet intérêt doit être actuel et pratique, c'est-à-dire qu'il doit exister non seulement au moment du dépôt du recours, mais encore au moment où l'arrêt est rendu (<ref-ruling> consid. 1.3.1 p.143; <ref-ruling> consid. 1.3.1 p. 24; <ref-ruling> consid. 1.2 p. 157; arrêt 8C_767/2016 du 7 août 2017 consid. 6.2), et ce également lorsque la partie recourante invoque un déni de justice formel (<ref-ruling> consid. 4a p. 287; arrêts 2P.24/1996 du 17 février 1997 consid. 1c; 2P. 352/2005 du 24 avril 2006 consid. 3.4). Il est exceptionnellement possible de faire abstraction de l'exigence d'un intérêt actuel lorsque la contestation peut se reproduire en tout temps dans des circonstances identiques ou analogues, que sa nature ne permet pas de la trancher avant qu'elle perde son actualité et que, en raison de sa portée de principe, il existe un intérêt public suffisamment important à la solution de la question litigieuse (<ref-ruling> consid. 1.3.3 p. 78; <ref-ruling> 74 consid. 1.1 p. 208).
6.2.3. On ajoutera que de manière générale, celui qui requiert une décision de constatation doit démontrer qu'il a un intérêt digne de protection à obtenir la constatation immédiate de son droit, que celui-ci ne s'oppose pas à des intérêts publics ou privés prépondérants et qu'il ne peut pas être préservé au moyen d'une décision formatrice ou en prestation (<ref-ruling> consid. 4.2.2 non publié; <ref-ruling> consid. 2.2. p. 279 s.). A certaines conditions, un tel intérêt peut être reconnu lorsqu'il existe, dans un cas concret, des incertitudes sur l'existence, la non-existence ou l'étendue de droits ou d'obligations de droit public (voir <ref-ruling> consid. 1.1 p. 4; <ref-ruling> consid. 3.5 p. 324 s.).
6.3. Devant l'instance cantonale, les recourants ont conclu que soit constaté le déni de justice que la commandante de la police aurait commis en refusant d'entrer en matière sur leur demande de décision quant à leur droit à bénéficier de la couverture prévue à l'art. 67 al. 1 let. b LPol. Or il ressort du jugement cantonal que les recourants ont été informés du fait que la réussite de la formation de policier ne garantissait pas un engagement en cette qualité au sein de la police. Ils n'étaient donc pas directement touchés par la modification des conditions de rémunération des policiers engagés dans la police. Ils ne sauraient pas davantage se prévaloir de droits acquis dans ce contexte. Au surplus, l'art. 67 LPol dans sa teneur depuis le 28 juillet 2018 ne donne pas lieu à des incertitudes particulières sur la situation juridique des recourants et leur droit à obtenir l'indemnité litigieuse. En effet, le texte légal définit clairement les personnes qui bénéficient de la prise en charge de l'indemnité litigieuse: les aspirants de la volée 2018 ne figurent pas parmi les bénéficiaires de l'indemnité litigieuse et la situation juridique des recourants n'appelle pas de clarification. Enfin, on peut relever que le nouvel art. 67 LPol est entré en vigueur avant les requêtes des aspirants au directeur RH, de sorte que le résultat de la procédure n'aurait pas pu produire d'effets rétroactifs à cet égard. Par conséquent, les recourants n'avaient aucun intérêt actuel et pratique à recourir - étant également précisé que les conditions dans lesquelles il peut être fait exceptionnellement abstraction de l'exigence d'un intérêt actuel ne sont pas remplies en l'espèce - ni ne disposaient d'un droit à obtenir une décision en constatation. Du reste, selon la cour cantonale, ceux des recourants qui ont été engagés entre-temps dans la police ont reçu une décision sur la rétribution à laquelle ils peuvent prétendre en qualité de policier ou de policière.
6.4. Compte tenu de ce qui précède, c'est à bon droit et sans violer l'<ref-law> que la cour cantonale a nié l'existence d'un intérêt digne de protection des recourants.
7.
7.1. Les recourants estiment enfin que leur droit d'accéder à un juge (art. 29a Cst.; art. 6 et 13 CEDH) aurait été bafoué. Ils considèrent que la procédure vise à déterminer s'ils ont été trompés lors de leur engagement et si les principes de la bonne foi et pacta sunt servanda ont été violés (art. 5 al. 3 et 9 Cst.). Cette question devrait pouvoir faire l'objet d'une décision sujette à recours. En outre, la potentielle violation des principes de la bonne foi et pacta sunt servanda suffirait à leur conférer un intérêt digne de protection à l'ouverture d'une procédure administrative.
7.2. Selon l'art. 29a Cst., toute personne a droit à ce que sa cause soit jugée par une autorité judiciaire. L'art. 29a Cst. garantit l'accès à un juge disposant d'un pouvoir d'examen complet en fait et en droit (ATF <ref-ruling>5 consid. 2.5 p. 239). Il ne s'oppose cependant pas aux conditions de recevabilité habituelles du recours ou de l'action (<ref-ruling> consid. 8.2 p. 350 s.). Pour pouvoir invoquer l'art. 29a Cst., le justiciable doit se trouver dans une situation de contestation juridique, c'est-à-dire un litige portant sur un différend juridique qui met en jeu des intérêts individuels dignes de protection (<ref-ruling> consid. 4.4 p. 237; <ref-ruling> consid. 4.1 p. 338; <ref-ruling> consid. 4.4 p. 326). En d'autres termes, l'art. 29a Cst. ne confère pas à quiconque le droit d'obtenir qu'un juge examine la légalité de toute action de l'Etat, indépendamment des règles procédurales applicables. Il est en particulier admissible de faire dépendre le caractère justiciable d'une cause d'un intérêt actuel ou pratique (arrêt 2C_871/2015 du 11 février 2016 consid. 2.5.4 et les références citées). Les art. 6 et 13 CEDH n'offrent en principe pas de protection plus étendue que l'art. 29a Cst. (cf. <ref-ruling> consid. 5.3 p. 403; arrêt 5A_510/2018 du 26 septembre 2018 consid. 3.3).
7.3. En déclarant le recours irrecevable faute d'intérêt digne de protection, la cour cantonale a respecté, comme on l'a vu, les garanties minimales prévues par le droit fédéral (art. 111 et 89 LTF). Dès lors que le droit d'accès au juge ne s'oppose pas aux conditions de recevabilité ordinaires du recours, telles que l'existence d'un intérêt digne de protection, le grief des recourants fondé sur l'art. 29a Cst. et les art. 6 et 13 CEDH tombe à faux. L'obtention d'une décision en constatation requiert également un intérêt digne de protection, qui fait défaut en l'espèce. Les recourants argumentent encore sur la base des principes de la bonne foi et pacta sunt servanda (art. 5 al. 3 et 9 Cst.). Sur ces points, leur recours ne satisfait toutefois pas aux exigences de motivation qualifiées prévues à l'<ref-law>, de sorte qu'il n'y a pas lieu de s'y attarder.
8.
Il ressort de qui précède que le jugement attaqué n'est pas critiquable et que le recours doit être rejeté.
9.
Les recourants, qui succombent, supporteront les frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 4500 fr., sont mis à la charge des recourants.
3.
Le présent arrêt est communiqué aux parties et à la Chambre administrative de la Cour de justice de la République et canton de Genève.
Lucerne, le 2 septembre 2020
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
La Juge présidant : Heine
La Greffière : von Zwehl