Tip of the day: permutacija == ciklusi

Jeste li znali da permutacija nije ništa drugo nego skup ciklusa? To je objašnjeno u ovom zadatku, a nešto formalnije ovdje (sekcija Cycle notation).

Rješenja mnogih zadataka temelje se na ovom triku:

Cages (izvorno Zmije s Infokupa 2014. za 6. razred)

Korijen permutacije (Codeforces)

Sort (HIO 2011.)

Cycle sort (EJOI 2018., mnogo teža verzija prethodnog zadatka i motivacija za ovaj post)

Uživajte!

Tip of the day: tablica je bipartitan graf

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.

Tip of the day: upsolving

Upsolving je pojam koji, čini se, potječe od Rusa i/ili Codeforcesa. Riječ je o rješavanju zadataka koje niste riješili na natjecanju (ili na simulaciji natjecanja).

Ovako je glasio Tip of the day Ante Đereka za sudionike IOI priprema 2016.:

Prije dosta vremena sam se ‘pripremao’ na topcoderu na sljedeci nacin: Odabrao bih prethodni contest, brzo bih napravio dva laksa zadatka, razmisljao bih 10ak minuta o tezemu, odustao i vise se na njega nisam vratio. Jedino sto sam tako naucio je bilo kako da malo brze kodiram zadatke koje vec znam 🙂

Bitan dio priprema je rjesavanje zadataka koji su ostali nerijeseni na natjecanju jer jedino tako ucite nove stvari. Nije potrebno da idete glavom kroz zid, ako nema napretka nakon 15ak minuta razmisljanja procitajte rjesenje (potpuno ili djelomicno), pitajte nekoga za hint i onda ponovo probajte rijesiti zadatak.

Nažalost, ljudska psihologija je takva da se mnogi poslije natjecanja ne žele vraćati na zadatke s natjecanja, pogotovo ako na tom natjecanju nisu bili uspješni. Poruka ovog posta je da nadiđete taj osjećaj. Dakle, ako se natječete na Codeforcesu, AtCoderu, CSAcademyju ili TopCoderu, ili možda samo na HONI-ju, Boži Težaku, županijskom, državnom ili HIO-u, napredak ćete postići samo na jedan način:

Pravilo natjecateljskog programiranja #1: Nakon svakog natjecanja ili simulacije natjecanja, bez iznimke, riješite barem jedan zadatak koji niste riješili na tom natjecanju. Čitanje rješenja je dozvoljeno, čak se i preporučuje.

Ono što presuđuje, tj. razdvaja uspješne od onih koji su samo daroviti, ne samo na natjecanjima nego općenito, zove se disciplina.

Tip of the day: logaritamska++

Velik broj srednjoškolskih natjecatelja zna logaritamsku strukturu (binary indexed tree ili Fenwickovo stablo) koje služi da bismo brzo provodili operacije oblika “promijeni K-ti element niza” i “odredi min/max/sumu nekog prefiksa niza”.

Manje ljudi zna da logaritamska može podržati i promjenu na nekom intervalu niza (povećaj elemente od A-tog do B-tog za V). Ovdje možete vidjeti kako to učiniti s logaritamskom. Bilo bi zanimljivo napraviti usporedbu duljine i efikasnosti tog rješenja u odnosu na rješenje s tournament stablom (segment tree).

(Koliko ja znam, logaritamskom nije moguće podržati i efikasno postavljanje cijelog intervala na neki broj. Ispravite me ako griješim.)

Postoji i 2D logaritamska koja opisuje matricu umjesto niza. Ona se također može prilagoditi tako da podržava intervalne promjene; evo odgovarajuće implementacije (Vilim Lendvaj, IOI pripreme 2016.):

struct fenwick
{
	long long data[MAXN][MAXN];

	void update(int i, int j, llint x)
	{
		for (; i <= n; i += i&-i)
			for (int j2 = j; j2 <= n; j2 += j2&-j2)
				data[i][j2] += x;
	}

	long long query(int i, int j)
	{
		long long x = 0;
		for (; 0 < i; i -= i&-i)
			for (int j2 = j; 0 < j2; j2 -= j2&-j2)
				x += data[i][j2];

		return x;
	}
} fen1, fenI, fenJ, fenIJ;

long long query(int i, int j)
{
	return fenIJ.query(i, j) * i * j + fenI.query(i, j) * i + fenJ.query(i, j) * j + fen1.query(i, j);
}

void update(int i1, int j1, int i2, int j2, long long x)
{
	fenIJ.update(i1, j1, x);
	fenIJ.update(i1, j2 + 1, -x);
	fenIJ.update(i2 + 1, j1, -x);
	fenIJ.update(i2 + 1, j2 + 1, x);

	fenI.update(i1, j1, -x * (j1 - 1));
	fenI.update(i1, j2 + 1, x * j2);
	fenI.update(i2 + 1, j1, x * (j1 - 1));
	fenI.update(i2 + 1, j2 + 1, -x * j2);

	fenJ.update(i1, j1, -x * (i1 - 1));
	fenJ.update(i1, j2 + 1, x * (i1 - 1));
	fenJ.update(i2 + 1, j1, x * i2);
	fenJ.update(i2 + 1, j2 + 1, -x * i2);

	fen1.update(i1, j1, x * (i1 - 1) * (j1 - 1));
	fen1.update(i1, j2 + 1, -x * (i1 - 1) * j2);
	fen1.update(i2 + 1, j1, -x * i2 * (j1 - 1));
	fen1.update(i2 + 1, j2 + 1, x * i2 * j2);
}

long long query(int i1, int j1, int i2, int j2)
{
	return query(i2, j2) - query(i2, j1 - 1) - query(i1 - 1, j2) + query(i1 - 1, j1 - 1);
}

Eventualne optimizacije su dobrodošle.

Zadatak: https://www.codechef.com/DCL1501/problems/DCL2015E/

Tip of the day: disjunktne maske

Pretpostavimo da radimo dinamiku gdje je stanje bitmaska – koje smo elemente već iskoristili, a u prijelazu biramo neki podskup neiskorištenih elemenata.

Na prvi pogled složenost je 2N * 2N = 4N, ali ne i ako prijelaz pišemo ovako:

for (int nova = ~mask; nova > 0; nova = (nova - 1) & ~mask) { ... }

To će iterirati po svim podskupovima koji su disjunktni s mask. Može se iterirati i u rastućem poretku:

for (int nova = 0; nova < (1 << N); nova = (nova + mask + 1) & ~mask) { ... }

Ako ovdje ne želimo nulu, treba početi od nova = (mask + 1) & ~mask. Probajte na papiru razumjeti ove petlje i zašto funkcioniraju, inače ih vjerojatno nećete zapamtiti.

Ukupna je složenost O(3N). Ako ne vjerujete, zavrtite ovo:

int cnt = 0;
for (int mask = 0; mask < (1 << N); mask++)
  for (int nova = 0; nova < (1 << N); nova = (nova + mask + 1) & ~mask)
    ++cnt;

…i možete se uvjeriti da će cnt biti točno 3N. Dokaz slobodno ostavite u komentarima.

Primjer zadatka: Z-most.

Tu, međutim, nije kraj optimizaciji — još efikasniji pristup, složenosti O(N * 2N), i mnogo zadataka (uključujući jedan s HONI/COCI) možete pronaći ovdje. Hvala Patriku Paviću na ovim linkovima.

Tip of the day: odaberi srednji

[Osvrt na ovosezonske zadatke – 2. dio]

Zadatak Bitcoin sa Županijskog natjecanja 2018., 1. i 2. razred, imao je zadane cijene bitcoina (izražene u eurima) za svaki od N dana. Trebalo je od tih N dana odabrati tri dana, ne nužno uzastopna, u kojima ćemo najprije kupiti bitcoine za 10 eura (1. dan), potom te bitcoine prodati za eure (2. dan) i na kraju opet kupiti bitcoine za eure koje imamo (3. dan), tako da broj dobivenih bitcoina na kraju bude maksimalan. Zbog ograničenja N ≤ 100 000, provjera svih trojki (ili čak dvojki) bila je prespora.

Zadatak se može riješiti na dva načina. Jedan način koristi se u rješenju teže varijante, zadatka Ethereum na istom natjecanju za 3. i 4. razred, u kojemu je trebalo ispisati traženi maksimum za svaki mogući prvi dan. (Autor zadataka je Marin Tomić.)

Jednostavnije rješenje Bitcoina koristi ideju koju sam prvi put vidio u zadatku Berba sa Državnog 2009., a poslije sam je iskoristio za zadatak Audi na JHIO 2017.

Otkrijte sami koji je trik zajednički rješenjima ovih triju zadataka. Hint se nalazi u naslovu ovog posta. Ako netko zna još neki zadatak čije rješenje koristi sličnu foru, neka napiše u komentarima.

Update — još jedan zadatak na ovu foru: Three displays.