Na EJOI 2018. pojavio se zadatak Chemical table. Do njegovog rješenja moguće je doći i bez trika koji ću ovdje pokazati, ali taj trik čini rješenje lakšim i očitijim.

Najprije primijetimo da zadatak nije dinamikast, nego grafast, jer poredak redova i stupaca u tablici nije važan: bilo kojom permutacijom redova i stupaca problem se ne mijenja. Iz perspektive redova i stupaca, važno je samo koji parovi (red, stupac) imaju zadano polje u svom presjeku.

Odatle se prirodno nameće pretvorba u graf: ako postoji element u presjeku reda R i stupca S, onda u grafu bridom povezujemo vrh R (koji predstavlja red) i vrh S (koji predstavlja stupac). Dobiveni graf je bipartitan: s jedne strane su vrhovi koji predstavljaju redove, a s druge strane vrhovi koji prestavljaju stupce. Poredak jednih i drugih ne igra nikakvu ulogu, tj. nije važno kojim redom crtamo vrhove dok god čuvamo informaciju o tome koji su međusobno povezani.

Nacrtajmo u dobivenom grafu situaciju iz zadatka, kada imamo tri elementa koja čine “skoro pravokutnik”: (R1, S1), (R2, S1) i (R2, S2). To znači da u bipartitnom grafu imamo tri brida koji zajedno čine put duljine tri: R1 –> S1 –> R2 –> S2. U tom slučaju možemo dodati i brid (R1, S2). To znači da put duljine tri možemo skratiti na put duljine jedan. Iz toga slijedi da možemo povezati svaka dva nasuprotna vrha u bipartitnom grafu ako među njima postoji ikakav put. Drugim riječima, da bismo mogli izravno povezati proizvoljan red s proizvoljnim stupcem (tj. dobiti traženi element u polju), dovoljno je da se odgovarajući vrhovi nalaze u istoj komponenti povezanosti.

Dakle, graf moramo učiniti povezanim, za što je dovoljno broj_komponenata_povezanosti – 1 novih bridova (polja) jer svaki novi brid povezuje dvije komponente i tako smanjuje broj komponenata za jedan.

Još jedan zadatak koji koristi ovaj trik možete riješiti ovdje. Update: pogledajte i Marinov komentar ispod!

Postoji još jedna, drugačija transformacija tablice u bipartitni graf. Ona se javlja u jednom klasičnom zadatku (online inačica je ovdje kao što mi je ukazao abeker):

Dana je M x N tablica (M, N ≤ 300) koja se sastoji od praznih polja i prepreka. Potrebno je tablicu (tj. samo njezina prazna polja) na bilo koji način potpuno popločati dominama (1 x 2 i 2 x 1) ili odgovoriti da to nije moguće.

Ovdje je trik primijetiti da, obojimo li polja tablice crno i bijelo kao na šahovnici, svaka domina pokriva jedno crno i jedno bijelo polje. Budući da polje smije najviše jednom biti pokriveno, zadatak se svodi na maksimalni matching u bipartitnom grafu koji s jedne strane ima crna, a s druge strane bijela polja tablice, ne uključujući prepreke, a susjedna polja povezana su bridom — potencijalnom dominom.

Primijetite da je ovo potpuno drugačija transformacija tablice u bipartitni graf od one s EJOI zadatka: ondje su vrhovi grafa bili redovi i stupci tablice (specijalno, dobiveni graf može biti gust), dok u ovoj vrhovi grafa odgovaraju poljima tablice (svaki vrh ima najviše četiri brida). Teži zadatak na sličnu foru bio je Alliances sa CEOI 2010., a opis rješenja možete pronaći ovdje.