Editorial for Nagrade


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: admin

Analiza

Prvo, za svaki broj sa ulaza nađimo sve različite proste brojeve koji ga dele. Ovo se može uraditi efikasno pomoću modifikacije Eratostenovog sita, kojom se svaki broj x < M može faktorizovati u logaritamskoj složenosti, gde je M gornja granica za Eratostenovo sito.

Ovih različitih prostih brojeva ima ne više od 6, jer je proizvod najmanjih 7 prostih brojeva veći od 2 \times 10^5. Sada, za svaki broj nađimo količnik njega i svakog različitog prostog broja koji ga deli. Neka je za i-ti broj P_i lista njegovih različitih prostih delilaca a C_i lista koja se dobija kada se A_i podeli sa svakim elementom liste P_i. Cilj zadatka je da nađemo niz različitih brojeva B tako da je za svako i, B_i = A_i / P_{i, j} = C_{i, j} za neko j. Ovaj problem je poznat i pod nazivom sistem različitih predstavnika familije skupova C. Ovo se može rešiti u polinomijalnom vremenu tako što se predstavi kao bipartitni graf, gde su čvorovi sa leve strane indeksi iz originalnog niza, a sa desne strane količnici. Za svako i dodajemo granu od čvora i sa leve strane do čvorova C_{i, j} sa desne, za svako j. Svaki sistem različitih predstavnika sada odgovara jednom perfektnom sparivanju (mečingu) u ovom grafu, odnosno mečingu gde je svaki čvor sa leve strane sparen. Dakle želimo da ispitamo da li ovako dobijen graf ima mečing sa N grana i koji je to mečing.

Najjednostavniji i najpoznatiji algoritam jeste Ford-Fulkersonov algoritam koji radi u složenosti O(VE), gde je V broj čvorova, a E broj grana u grafu, što u našem slučaju, zbog gore pomenutog ograničenja na broj grana iznosi O(N^2). Primetimo da ne moramo da dodajemo sve čvorove sa desne strane već samo one koji se bar jednom pojavljuju kao količnici.


Comments


  • 0
    turneja  commented on May 14, 2020, 12:49 a.m.

    Ajde popravite grader za ovaj zadatak jer ne radi kako treba rucno sam isprobao prvi test primer iz teksta i ne prihvata datu konfiguraciju ali prihvata neku drugu