Zadaci sa takmičenja u Šumenu 2017


#1

Zvanični sajt takmičenja

Nedavno je održano takmičenje u Šumenu, gde je učestvovala ekipa Srbije.
Pre svega bih iskoristio priliku da čestitam svoj četvorici naših takmičara koji su učestvovali, a to su:

  • Aleksa Milisavljević, 4. razred, Matematička gimnazija
  • Pavle Martinović, 3. razred, Matematička gimnazija
  • Ivan Pešić, 3. razred, Matematička gimnazija
  • Filip Ćosović, 4. razred, Prva kragujevačka gimnazija

Posebno bih čestitao Aleksi na osvojenoj srebrnoj medalji i Pavlu na bronzanoj.

U nastavku ću pisati analizu zadataka sa ovog takmičenja. Ako još neko želi da doprinese neka slobodno to učini.

EDIT: Ako sajt ne bude u funkciji, tekstove zadataka na engleskom možete naći ovde:
Prvi dan
Drugi dan
A možete i slati svoja rešenja.


#2

Zadatak Superstition

Prepričani tekst zadatka

Dat je prost neusmeren graf sa N čvorova i M grana. Svaka grana ima težinu koja je prirodan broj, t[i] <= 10. Potrebno je naći broj puteva čija je dužina ne više od K i deljiva je sa D. Dva puta su različita ukoliko im se razlikuje niz čvorova. Jedan put mora sadržati bar dva čvora. Dozvoljeno je ponavljanje čvorova/grana na putu. Put može počinjati ili završavati se u proizvoljnim čvorovima. Broj puteva naći po modulu 10^9 + 7.

Ograničenja:

Ostali podzadaci su olakšane verzije jednog od naredna dva podzadatka.

U jednom podzadatku N <= 80, D, K <= 10000
U drugom podzadatku N <= 30, D, K <= 10^9

Broj grana je jedino ograničen brojem čvorova i uslovom da je graf prost, tj. ne postoji više grana između dva ista čvora i ne postoje grane od jednog čvora do njega samog.

Rešenje 1 - dinamičko programiranje.

Neka je d[l][u][v] broj puteva od čvora u do čvora v čija je dužina tačno l. Rekurentna veza je:

d[l][u][v] = Suma { w : susedi od (v) } d[ l - len[w][v] ][u][w]

d[0][v][v] = 1
d[0][u][v] = 0 za u != v.

Nakon što ove vrednosti izračunamo za sve u, v od 1 do N i za sve l od 1 do K, samo pročitamo zbir svuda gde je l deljivo sa D.

Složenost ovog rešenja je O(n^3 D). Ovo rešava neke podzadatke ali nažalost ne sve.

Rešenje 2 - optimizovano dinamičko.

Kako nam polazni čvor u ne učestvuje u rekurentnoj vezi, možemo da probamo da reformulišemo stanje DP-a i rekurentnu vezu.

Neka je sada dp[l][v] broj puteva dužine l koji se završavaju u čvoru v. Rekurentna veza je:

d[l][v] = Suma { w : susedi od (v) } d[ l - len[w][v] ][w]
d[0][v] = 1

Složenost ovog rešenja je O(n^2 D) što je dovoljno efikasno za podzadatak gde je D relativno mali broj, do 10000.

“2n, n+1” trik

Osvrnimo se na klasičan problem koji je verovatno poznat iskusnijim takmičarima: Naći broj puteva dužine tačno D u grafu, gde sve grane imaju dužinu 1.

Za čitaoce koji barataju jezikom linearne algebre: Ovo se može rešiti stepenovanjem matrice susedstva na D-ti stepen, čije se u polju (A^D)[i][j] dobija broj puteva dužine D od čvora i do čvora j. Stepen matrice može se naći u složenosti O(log D) algoritmom pod nazivom binarno stepenovanje. Ovaj trik se može izvesti i u drugim zadacima dinamičkog programiranja i neformalno se naziva “2n, n+1” trik.

Ideja je sledeća: Ako imamo matricu d[l], mi možemo efikasno naći matricu d[2l], na sledeći način, ukoliko su dužine svih grana 1:

d[2l][u][v] = suma { w : od 1 do n } d[l][u][w] * d[l][w][v]

“Isečemo” put dužine 2l na dva puta dužine l, iteriramo po svim mogućim čvorovima w koji se nalaze na sredini tog puta.

Slično možemo naći i matricu d[l+1] ako znamo matrice d[l] i d[1].

d[l+1][u][v] = suma { w : od 1 do n } d[l][u][w] * d[1][w][v]

Ako želimo da izračunamo K-ti stepen neke matrice, iz binarnog zapisa broja K možemo zaključiti kojim redosledom treba vrštii operacije “2n” i “n+1”.

Vratimo se sada na originalni zadatak. Svaku granu dužine t menjamo sa 2t-2 dodatna čvora i 2t usmerenih grana dužine 1, kao na slici:

graph1

Ovime želimo da eliminišemo problem što je dužina grana veća od 1. Broj čvorova sada može biti ne više od N + 2 * M * (Tmax - 1). Sada pri računanju uzimamo u obzir samo one puteve koji počinju i završavaju se u nekom od originalnih čvorova, a ne nekom od dodatih.

Međutim ovo i dalje ne rešava zadatak. Potrebno je da nađemo sve puteve čija je dužina manja ili jednaka K a deljiva sa D. Uzmimo radi jednostavnosti da D deli K. U suprotnom samo postavimo K = (K div D) * D. Jasno je da ovaj broj možemo naći iz matrice A^D + A^(2D) + A^(3D) + … + A(K/D)D.

Prvo, nađimo D-ti stepen matrice A. Nazovimo tu matricu B. Zatim treba naći B + B^2 + … + B^(K/D). Ovo možemo naći postupkom sličnim binarnom stepenovanju: Pamtimo u svakom trenutku zbir S[x] = B + B^2 + … + B^x i vrednost B^x za neki ceo broj x. Korak “2n” možemo realizovati na sledeći način:

S[2x] = S[x] * B^x + S[x]
B^2x = B^x * B^x

Korak “n+1” možemo realizovati kao:
S[x+1] = S[x] * B + B
B^(x+1) = B^x * B

Ovo rešenje ima složenost O((N + M * Tmax)^3 * log(K)) i radi na podzadacima gde je zbir dužina svih grana mali. (Podzadaci 3 i 4, videti originalni tekst zadatka).

Da bismo rešili zadatak za maksimalan broj poena neophodno je da redefinišemo matricu koju stepenujemo.
Naime, nećemo dodavati nove čvorove. već ćemo dužine grana inkorporirati direktno u matricu (tj. stanje), na sledeći način.

Rešenje za maksimalni broj poena

Vratimo se na polaznu DP jednačinu:

d[l][u][v] = Suma { w : susedi od (v) } d[ l - len[w][v] ][u][w]

Umesto da nam indeksi redova i kolona budu čvorovi, neka to bude par (u, x), gde je u čvor a x broj od 0 do Tmax-1, koliko smo udaljeni od tog čvora duž neke grane, gde pretpostavljamo da se krećemo ka tom čvoru.

Definišemo matricu d[1] na sledeći način:

za svaku usmerenu granu dužine t od čvora u do čvora v dodajemo:

d[1][(u, 0)][(v, t-1)] += 1.
Logika iza ovoga: Ako krenemo ovom granom, ostaće nam još t-1 da pređemo do čvora v.
Za svaku neusmerenu granu samo dodamo odgovarajuće dve usmerene.

Dodatno, za svaki čvor u i svako t od 1 do 9 dodajemo:
d[1][(u, t)][(u, t-1)] += 1.
Ako se trenutno nalazimo unutar neke grane, nakon što pređemo još 1 “metar” bićemo na istoj grani, na razdaljini t-1 ili ćemo biti baš u čvoru u, na razdaljini 0 (slučaj t=1).

Sada ovakvu matricu možemo prethodno opisanim postupkom možemo stepenovati i naći zbir odgovarajućih stepena.
Složenost ovog rešenja je O((n * Tmax)^3 * log K), što je uz manje optimizacije dovoljno da se dobije 100 poena.


#3

Zadatak Colorgraph

Dat je kompletan neusmeren graf gde svaka grana ima plavu ili crvenu boju. Za graf kažemo da je crveno-povezan ukoliko postoji put od svakog čvora do svakog drugog čvora koji se sastoji samo od crvenih grana. Analogno definišemo plavo-povezanost. Dato je željeno krajnje stanje grafa - par brojeva (A, B), gde je A = 1 ako krajnji graf treba da bude crveno povezan, A = 0 ako graf treba da ne bude crveno povezan, B = 1 ako graf treba da bude plavo povezan i B = 0 ako treba da ne bude plavo povezan. Promeniti boju minimalnom broju grana tako da se graf dovede u traženo krajnje stanje.

Ograničenja: 3 <= N <= 250

Rešenje

Analiziraćemo različite slučajeve. Od velike pomoći nam je sledeća teorema:

Teorema 1

Graf zadat na gore opisan način ne može da bude istovremeno i plavo-nepovezan i crveno-nepovezan.

Dokaz teoreme

Pretpostavimo suprotno. Neka je graf G sa N čvorova i neka on nije ni crveno ni plavo povezan. Podelimo skup čvorova ovog grafa na dva neprazna podskupa U i V tako da ne postoji crvena grana koja spaja neki čvor iz U i neki čvor iz V. Ovo možemo uraditi tako što npr. uzmemo da je U proizvoljna crveno-povezana komponenta grafa. Dokazaćemo, suprotno pretpostavci, da je ovaj graf plavo-povezan. Neka su u, v proizvoljni čvorovi grafa. Dokazaćemo da postoji plavi put koji ih povezuje.

Prvi slučaj: u je iz U, v je iz V. Kako oni nisu spojeni crvenom granom, biće spojeni plavom, pa postoji put. Analogno ako je u iz V a v iz U.

Drugi slučaj: Oba čvora su iz U. Uzmimo proizvoljan čvor x iz V. Ovo možemo da uradimo jer je V neprazan. Pošto ne postoje crvene grane (u, x) i (x, v), postojaće plave, pa postoji plavi put. Analogno ako su oba čvora iz V.

Dakle graf je crveno povezan ili plavo povezan (ili oba).

Analiza slučajeva

Slučaj N = 3 može se rešiti primernom grube sile. Zato uzmimo N > 3. za N = 3 nije moguće dostići stanje (1, 1).

Graf treba dovesti u stanje (1, 1)

Ako je graf već u tom stanju ne radimo ništa. U suprotnom on je u stanju (0, 1) ili (1, 0) i jasno je da se ova dva slučaja rešavaju analogno. Dakle, graf je plavo povezan, a nije crveno povezan a treba da ga sa što manje grana crveno-povežemo. Jasno je da je donja granica za broj dodatih grana BrojCrvenihKomponenti - 1. Dokazaćemo da skoro uvek moguće povezati graf sa tačno ovoliko grana.

Neka graf ima 4 ili više crveno-povezanih komponenti. Uzećemo redom iz tih komponenti čvorove v1, v2, …, vk, gde je k broj crvenih komponenti. Promenimo grane (v1, v2), (v2, v3), …, (v[k-1], vk) u crveno. Jasno je da je sada graf crveno povezan. Dokažimo da je on i dalje plavo povezan. Posmatrajmo kompletan graf indukovan čvorovima v1, v2, …, vk. On će imati crvene grane (v1, v2), (v2, v3), …, (v[k-1], vk) a ostale grane će biti plave. Jasno je da je čvor v1 plavo povezan sa čvorovima v3, v4, …, vk, jer je spojen plavom granom sa njima. Slično, pošto je k >= 4, v2 će biti spojen plavom granom sa vk, pa je dakle ovaj podgraf plavo-povezan. Odavde sledi da nismo narušili plavo-povezanost originalnog grafa.

Neka sada graf ima 3 crveno-povezane komponente. Uzmimo isto kao i ranije čvorove v1, v2, v3. Promenimo broju grane (v1, v2) u crveno. Graf ostaje plavo povezan jer postoji plavi put (v1, v3, v2). Sveli smo sada problem na rešavanje grafa sa 2 crveno-povezane komponente.

Neka se te dve komponente sastoje od skupova čvorova U i V. Prvi slučaj: obe komponente imaju bar 2 čvora. Uzmimo neka dva čvora u1 i u2 iz U i v1, v2 iz V. Promenimo boju grane (u1, v1) u crveno. Graf ostaje plavo povezan jer postoji plavi put (u1, v2, u2, v1). Drugi slučaj: jedna od ove dve komponente ima jedan čvor. Neka je to komponenta U sa čvorom u. Sada ponovo posmatramo dva slučaja: Prvi podslučaj: Ona druga komponenta sadrži bar jednu plavu granu (v, w). Menjamo boju grane (u, v) u crveno. Graf ostaje plavo povezan jer postoji plavi put (u, w, v). U drugom podslučaju, nije moguće promenom samo jedne grane postići da graf bude crveno povezan, jer ako promenimo boju grane (u, v) u crveno, ova dva čvora više neće biti plavo povezana. U tom slučaju samo izaberemo proizvoljan čvor w iz V i promenimo i granu (v, w) u plavo, i po prethodnom razmatranju, graf će biti plavo povezan.

Vratimo se sada na slučaj sa 3 crveno-povezane komponente. Biramo čvorove v1 i v2 tako da nam ne ostanu dve komponente veličina 1 i N-1, da bismo eliminisali slučaj kada nam treba jedna grana više. To možemo postići tako što izaberemo da su v1 i v2 redom iz dve najmanje komponente povezanosti.

Graf treba dovesti u stanje (0, 1)

Ako je graf na početku već u ovom stanju onda ne radimo ništa. Inače, on je u stanju (1, 1) ili (1, 0), odnosno, on je crveno povezan. Dakle dovoljno je da promenimo neke crvene grane u plave tako da on ne bude više crveno povezan. Na osnovu teoreme 1, znamo da, ako graf nije crveno povezan, da će biti plavo povezan. Dakle samo treba naći skup crvenih grana koje diskonektuju plavi podgraf. Ovo je u literaturi problem poznat pod nazivom global min-cut i rešava se algoritmom Stoer-Wagner-a složenosti O(n^3).


#4

Zadatak Crypto

Za neku permutaciju A brojeva od 1 … N i neki prirodan broj K <= N, definišemo njenu snagu P kao broj jedinstvenih skupova B koji se mogu dobiti kao rezultat sledećeg postupka: Izaberemo neki podniz uzastopnih elemenata dužine bar K. Izaberimo iz tog podniza najmanjih K elemenata, i oni čine skup B. U zadatku su dati brojevi N, K, P. Potrebno je naći broj permutacija od N elemenata čija snaga iznosi tačno P, po modulu 10^9+7.

Ograničenja:

1 <= K <= N <= 400
1 <= P <= 10^9

DP po permutacijama

Rešenje zadatka se oslanja na “trik” koji se često koristi kod zadataka gde je potrebno naći broj permutacija. Trik se sastoji iz toga da se permutacija ne konstruiše sleva ne desno, dodavanjem brojeva na kraj niza, već se konstruiše umetanjem novih brojeva između postojećih, najčešće u nekom redosledu.

Primetimo da rešenje ne može biti pozitivno ukoliko je P > N(N+1)/2, jer ne postoji više od N(N+1)/2 različitih načina da se izabere podniz niza od N brojeva. Ova granica se može još više spustiti ako se uzme u obzir da ovi nizovi trebaju biti dužine bar K.

Ako je N = K, tada postoji samo jedan odabir za skup B, i to je skup B = {1, 2, … , N}. Dakle u ovom slučaju, za P = 1, rešenje je N!, a u suprotnom je rešenje 0.

Postavimo dp[i][j] = broj permutacija brojeva od 1 do i takvih da je snaga jednaka j. Prelaz sa ovog stanja na neka druga stanja vršimo umetanjem elementa i+1 na neku od raspoloživih i+1 pozicija u permutaciji A. Neka smo ovaj element umetnuli na poziciju x, gde je 0 <= x <= i. Za koliko se povećava snaga ove permutacije, ukoliko je ona pre umetanja bila j?
Primetimo da, ako smo za permutaciju A imali neki odabir skupa B, gde je skup B bio “generisan” indeksima l, r (1 <= l <= r <= i), onda se ovaj skup B neće promeniti umetanjem elementa i+1, eventualno se mogu pomeriti leva ili desna granica, ali ovaj odabir ostaje validan jer dužina tog podniza ili ostaje ista, ili se povećava za 1. Skup B se za ovaj podniz ne menja jer je umetnut element koji je veći od svih do tada prisutnih elemenata. Dakle, jedini novi nizovi B koji se pojavljuju su upravo oni koji su generisani podnizovima veličine tačno K u novoj permutaciji, koji sadrže novoubačeni element. Ovaj broj se može odrediti na osnovu x: Ukoliko je x negde “u sredini” niza, odnosno dovoljno udaljen od leve tj. desne granice, onda se snaga povećava za K. U suprotnom se povećava za broj manji od K. Preciznije: Snaga se povećava za tačno K - min(0, K-x-1) - min(0, K-(i-K)-1). Nazovimo ovo funkcijom f(K, i, x).

Sada imamo DP rešenje. Izvršavamo sledeće prelaze:
dp[i+1][j + f(K, i, x)] += dp[i][j], za svako x iz [0, i]

Imamo O(N^3) stanja, odnosno O(N) vrednosti za i, a O(N^2) vrednosti za j. Prelaze iz jednog stanja računamo u O(N), tako da je složenost O(N^4), što je uz manje optimizacije dovoljno da se dobije 50% poena za ovaj zadatak.

Efikasnije rešenje

Ključno je da pripitomimo funkciju f, koja nam određuje pomeraj pri prelazu iz vektora dp[i] na vektor dp[i+1]. Želimo da nađemo, za svako y = f(K, i, x), za koliko različitih vrednosti x se dostiže baš ovo y. Primetimo da funkcija f, posmatrano po x, prvo raste, počev od vrednosti 1, zatim dostiže neki maksimum (koji može a i ne mora da bude K), zatim se drži neko vreme na ovoj konstantnoj vrednosti a zatim opada za po 1 sve dok ponovo ne dostigne vrednost 1 za x = i. Označimo sa g(y) taj broj, broj različitih vrednosti x za koje f(K, i, x) ima vrednost y. Vratimo se na DP vezu, i označimo sa u = dp[i] i v = dp[i+1]. Imamo:

v[j + f(K, i, x)] += u[j], za svako x iz [0, i]

Razbijanjem leve strane po y tj. f(K, i, x) dobijamo:

v[j + y] = suma { y = 0 … Y } g(y) u[j]

gde je Y najveća dostignuta vrednost za y. Primetimo da je ova jednačina odgovara jednačini konvolucije dva niza, koja se može izračunati relativno efikasno pomoću FFT algoritma u O(M log M), gde je M zbir dužina nizova nad kojima se vrši konvolucija. Pošto je d[i] vektor dužine O(N^2), prelaz sa dp[i] na dp[i+1] bi trajao O(N^2 log N), odnosno ceo algoritam bi se izvršavao u složenosti O(N^3 log N), što je nažalost i dalje previše sporo.

Specijalne konvolucije

Primetimo da niz g(y) nije nasumično zadat. Naime, niz g(y) ima vrednost 2 za sve y od 1 do Y-1, a za y = Y ima neku prirodnu vrednost. Kako je operacija konvolucije distributivna po zbiru nizova, mi možemo da zapišemo niz g(y) kao zbir dva niza h(y) + t(y), gde je h(y) niz čiji su svi elementi 2 od prvog do elementa Y-1 a ostali su 0, i t(y) koji na poziciji Y ima neku nenula vrednost a na svim ostalim pozicijama nula.

Konvoluciju proizvoljnog niza sa nizom oblika kakav ima h(y) možemo izračunati sliding window tehnikom - uzmemo da je v = h * u, postavljamo v[Y] = 2*(u[1] + u[2] + … + u[Y-1]). Zatim posmatrajmo vrednost za v[Y+1], ona treba da bude 2*(u[2] + u[2] + … + u[Y]) međutim mi to možemo da izračunamo kao v[Y] - 2 u[1] + 2 u[Y], i tako nadalje za sve ostale elemente niza v. Konvolucija sa nizom koji je oblika kao niz t se računa trivijalno.

Ukupna vremenska složenost ovog algoritma je O(N^3). Memorijska složenost se dobrom implementacijom (pamćenjem samo poslednja dva vektora) može spustiti na O(N^2).