Answer: The Shulchan Aruch (OC 244:1; 247:1; 252:2) writes that one may give work to a non-Jewish person to do even though it entails a melacha that is prohibited on Shabbos, providing that the non-Jewish person can reasonably do the work at other times if they wish. Any such work must not be performed publicly on Shabbos, however.
R’ Mordechai Yaakov Breisch (Chelkas Yaakov 1:66) dismisses another Rabbi’s argument that one may, therefore, advertise in a newspaper over Shabbos as the printers could technically print it beforehand. Anyone reading this paper will know that it was, in-fact, printed on Shabbos. He quotes the Taz (244:5) who writes that one cannot hire a non-Jew to sew a garment or write a book and expect them to complete it by a particular deadline if they know that they can only realistically do so in time by working on Shabbos. The Pri Megadim (Mishbetzos Zahav 245:5) explains that doing so is akin to instructing them to work on Shabbos. So, too, by placing such an advert, it is as if they are asking the non-Jewish printers to print the advert on Shabbos.
Likewise, R’ Moshe Sternbuch (Teshuvos Vehanhagos 1:280) writes that even if the adverts were placed in a supplement that is printed before Shabbos, one still mustn’t advertise if it is distributed with a Saturday paper as people will erroneously suspect that melacha was performed on Shabbos on their behalf.
The Piskei Teshuvos (247:n21) adds that if one were to place a daily advert that included the Saturday edition, that would still be prohibited based on the above.
In conclusion, one must avoid placing adverts in a Saturday edition newspaper.