Fibonacci, mátrix power, aranymetszés

derégvoltam

Na de, láttam ezt a postot nemrég:

http://tristan-interview.blogspot.hu/2012/03/calculate-number-of-different-ways-to.html

be is nekróztam egy kommentet, most pedig megoldjuk rendesen :) közben megmutatom az egyik kedvenc ágyúmat.

A kérdés egyébként ez volt: egy n fokos lépcsőn akarunk felmenni, hányféleképp tehetjük ezt meg, ha egyszerre egy, két vagy három fokot tudunk lépni?

Oldjuk meg ezt a feladat-sablont.

Amit mindenki tud remélhetőleg: ha erre rekurziót írunk, akkor

f(1) = 1, f(2) = 2, f(3) = 4 (ezeket akár kézzel) és f(n+3) = f(n) + f(n+1) + f(n+2).

Persze ezt nem implementáljuk így, mivel mindig több kisebb argumentummal hívjuk újra, ez így n-ben exponenciális időt igényelne, ehelyett rekurzió-memorizálunk, vagy eleve bottom-up dinamikus programozunk:

T[1] = 1; T[2] = 2; T[3] = 4;

for( int i = 4; i <= n; i++ ) T[i] = T[i-1] + T[i-2] + T[i-3];

return T[n];

Mondjuk szerintem memoizationt spec itt használni hülyeség, hiszen pontosan tudjuk, melyik cellákra van szükség a számításhoz: mindre. Tehát kiszámítjuk mindet, nem ifezünk, hogy volt-e már egy hívás vagy sem.
Mivel mindig csak az utolsó három cellát használjuk, elég csak azt a hármat észben tartani és ciklikusan tölteni a 3-elemű tömböt modulo 3:

T[1] = 1; T[2] = 2; T[0] = 4;

for( int i = 4; i <= n; i++ ) T[ i%3 ] += T[ (i-1)%3 ] + T[ (i-2) % 3 ];

return T[ n % 3 ];

észre is vehetjük persze, hogy mindenképp a tömbösszeget rakjuk bele, kevesebb if:

T[1] = 1; T[2] = 2; T[0] = 4;

for( int i = 4; i <= n; i++ ) T[ i%3 ] = T[ 0 ] + T[ 1 ] + T[ 2 ];

return T[ n % 3 ];

Lineáris idő, konstans tár, örülünk, így a fenti post. Örülünk?

frászt.

nincs ez még kész.

Egyrészt ha a tömb típusa int, akkor ez a három lépésig visszamenő rekurzió kábé 1.83ⁿ-nel arányos (lásd pl itt: http:://mathworld.wolfram.com/TribonacciNumber.html ), ami n=37-nél kicsúszik a 32 bitből, n=75-nél pedig a 64 bitből is, szóval akkor már inkább használjunk precomputed táblát, és ne zavarjon már az a néhány byte tárterület... (ok, nyilván azt dinamikusan számoljuk ki, de ne hülyéskedjünk ezzel a száz helyett csak négy inttel, tegyük el mindet tömbbe és ha jön a query, konstans idő visszaadni, kezét csonkolom.)

A kis n-ek kérdését lezongoráztuk. De mi van, ha n=100-ra kéne az érték? Akkor már akármekkora egészekkel kéne aritmetikát csinálni, ahol meg nem lehet azt mondani, hogy konstans idő alatt végzünk az összeadással pl. Versenyeken általában nem ilyen formában történik a kérdés, hanem kicsit komolyabban:

"Határozzuk meg a fenti T[n] értékét n~1.000.000.000.000 -re, modulo 1.000.007!"

értem? az eredmény befér intbe, a lineáris idő meg nem jó nekünk, ha n 64-bites. Ha látsz egy ilyet, el kéne kezdeni gondolkodni :D

úgyhogy ennél általánosabban fogjuk megoldani a kérdést, O(logn) idő és konstans tár mellett bármi hasonlót, modulóval vagy anélkül (anélkül persze nem feltétlen lesz O(logn), inkább O(log²n)).

k-lépéses lineáris rekurzió egy olyan f függvény, aminek megadjuk az f(1), ..., f(k) értékét, és a1,...,ak együtthatókat, ezek mondjuk valami valós számok; továbbá, minden n>=0-ra

f(n+k+1) = a1*f(n+1) + a2*f(n+2) + ... + ak*f(n+k).

Ilyen a fenti is, háromlépéses, f(1)=1, f(2)=2, f(3)=4 és a1=a2=a3=1 választásával, de a Fibonacci is, f(1)=f(2)=1, a1=a2=1 választással kétlépéses.

Kérdés az n. tag értéke modulo something, gyorsan, tegnapra, nagy n-re.
Írjunk fel egy k*k-s (ha a sorozat adott, ez konstans méretű) A mátrixot, mégpedig: az utolsó oszlopba fentről lefelé írjuk az a1,...,ak együtthatókat, a főátló ALÁ közvetlenül egyeseket, minden máshova 0 kerül.

Ez ennél a feladatnál pl.

(0 0 1)

(1 0 1)

(0 1 1)

lesz, a Fibonacci esetében pedig

(0 1)

(1 1).

de miért? Mondjuk van egy (n1, n2, n3, ..., nk) vektorunk. Mit kapunk, ha beszorozzuk a fenti A mátrixszal? az első elem helyére kerül a második (ld mátrix első oszlop), a második helyére a harmadik stb; az utolsó oszlopot kivéve a mátrix egy shift left mátrix. Az utolsó elem helyére mi kerül?

a1*n1 + a2*n2 + ... + ak*nk.

Tehát ha a vektorunkban megvan az utolsó k eleme a sorozatnak, akkor a mátrixszal való szorzás eggyel tovább húzza az ablakot. Emiatt ha inicializáljuk a kezdővektort a v = (f(1), f(2), ..., f(k)) értékekkel és az n+k. elemet kell kiszámolnunk, akkor csak a vAⁿ szorzat (ez egy vektor ugye, n-szer kell rászorozzunk A-val a v vektorra, hogy bekerüljön az f(n+k) az utsó pozícióba) utolsó koordinátáját kell visszaadjuk.

Ha modulo kell számolni, akkor úgy.

Elsőre ez nem jár előnnyel, sőt, hiszen most nem O(n) darab számot kell összeadni, hanem O(n) vektor-mátrix szorzatot kiszámolni, kinek jó ez?

nekünk!

mert tudunk iterált mátrixhatványozni: Aⁿ kiszámításához kiszámoljuk négyzetreemelgetéssel A, A², A⁴, A⁸, ..., A^2logn mátrixokat és ami kell belőlük (hatványozás-azonosság: ahol n-ben 1-es van, azoknak megfelelőt szorozzuk), azokat szorozzuk össze:

T pow( T a, unsigned n ){

  T ret; //inicializáljuk a szorzás egységelemére, mátrix esetében tehát egységmátrixra

  while( n ){

    if( n % 2 ) ret *= a;

    n /= 2;

    a *= a;

  }

  return ret;

}

kész is. ha modulo kell, akkor persze a mátrix osztályban úgy csináljuk a szorzás implementációját, hogy minden alapműveletet eleve modulo csináljon. Ez mennyi? O(logn) mátrixszorzás, konstans (k³) művelet per mátrixszorzás.

és akkor

Matrix A; //ezt a mátrixot inicializáljuk az aktuális sorozat együtthatóitól függően;

Vector init; //ezt a vektort inicializáljuk az aktuális sorozat kezdő k tagjától függően;

scanf("%d",&n); 

return (init * pow( A, n))[k-1]; //értelmes overridingokat feltételezve

Ha tehát az n nagy lehet, ezt inkább így csináljuk.

A "mekkora számít nagynak" kérdésre: pl k=3 esetén két mátrix szorzása 45 művelet, az akkor cca 90logn lépés, plusz az apró, szemben az eredeti 2n művelettel. Ha pl n úgy kábé 300, akkor már a  mátrixozás gyorsabb (főleg ha inkább egy konkrét 3x3-as memóriaterületen megy a számolás és nem pl új objektumokat hozogatunk létre nyakló nélkül, legyen bármi is az a nyakló. Párhuzamosítani is lehet.)
Ha meg kisebb, mint 300, én precomputed tábláznék. Nyilván kombinálnám a kettőt: kiszámolnám előre egy tömbbe az első mondjuk száz elemet, a többit mátrixokkal, ha kérdezik.

(Amúgy van komplikált hatványozós zárt képlet is a wolframos linken, azzal csak egy a baj: nincs az a lebegőpontosság, ami jó lenne ehhez a feladathoz, túl sok értékes jegyet kell megtartsunk..)

most már ki tudjuk bármilyen lineáris rekurzió általános, sokadik tagját gyorsan számolni.
örülünk, Vincent?

Pitagorasz

Ma ezt a feladatot dolgozzuk fel:

http://www.spoj.com/problems/EQBOX/

Bejön négy szám: A, B, C, D. Egészek. 1 és 50.000 közt.

Kérdés: befér-e egy A*B-s téglalapba egy C*D-s téglalap a határai érintése nélkül?

Ilyen tesztesetből jön be kb 10.000.

Első érzésből az ember azt hiszi, hogy megvan a könnyű feladat, adja a kódernek, hasonlítsa össze a kisebbet a kisebbel, a nagyobbat a nagyobbal és ha a C*D-snek a rövidebb oldala rövidebb, mint az A*B-sek, és a hosszabb is, akkor true, egyébként false.

WA

OK, akkor olvassuk el még egyszer. LEHET FORGATNI.

Így már egész más a leányzó fekvése.. egy 8x8-as boxba pl befér egy 10x2-es, ha 45 fokban elforgatva rakjuk bele.

A forgatással kapcsolatban: ha tetszőleges szögű forgatással kell dolgoznunk, akkor rossz esetben szögfüggvényezni, kevésbé rossz esetben gyököt vonni kell. Mindkét esetben át kell menni lebegőpontba, amivel az a baj, hogy a számítások pontossága is elronthatja a napunkat, nullára sose tesztelhetünk (helyette mindig azt kell nézni, hogy egy érték +- epszilon közt van-e, ahol epszilon valami pici konstans. Meg persze a float kulcsszót felejtsük el, sose ismertük, minden double.

És még az is hozzájön, hogy a sqrt, sin, stb függvények (az egész aritmetikához képest) nagyon lassúak. Emiatt minél kevesebb olyan esetet kellene hagyjunk, amikor ténylegesen átmegyünk lebegőpontba, és amit egész aritmetikával meg lehet oldani (mivel az input egész, erre van esélyünk), azt egésszel oldjuk meg, még ha több is lesz benne az if.

Először is rendezzük le az oldalakat A <= B, C <= D sorrendbe, úgy könnyebb lesz kezelni a továbbiakat, és kevesebb lesz az if, nem spagettit készítünk, hanem kódot.

Aztán, nyilván ha C < A és D < B, akkor nyilván befér, ezt az esetet gyorsan lekezeljük. (ezt amúgy is megcsináltuk az előző WA-s beküldésnél, akkor meg miért töröljük ki :D )

Lássuk a forgatást: ha a C*D-s téglalapot forgatjuk, akkor közben C-nél rövidebb nem lesz egyik tengelyirányba se. (Már négyzetre se lehet kisebb, és mivel D legalább C, ettől alacsonyabbá nem válhat.)

Emiatt ha A <= C, nem fog beférni.

Aztán az is tiszta, hogy ha befér, akkor az átlója is befér. Az A*B-s téglalap két legtávolabbi pontja szintén az átlója. Vagyis ha a C*D-s téglalap átlója hosszabb, nem fog beférni. Pitagorasz. Gyököt nyilván nem vonunk:

Ha A*A + B*B <= C*C + D*D, nem fog beférni.

Na most már (szerintem) viszont kell legalább gyökvonás is. 

Kép:

Gondolatban megdupláztam az a,b,c,d értékeket. A fekete téglalap az A*B téglalap bal felső negyede. Ha befér, szimmetriai okokból befér úgy is, ha a két téglalap középpontja egybeesik. Annyit kell kiszámolnunk, hogy a C*D téglalap átlója (a képen a piros vonalak) hol "ütközne bele" a bal oldali ill. felső oldalba. Ha a két ütközési pont közé legalább a C*D téglalap rövidebb oldala befér (kék vonal > C), akkor befér: csak megfelelően összébb kell csukni az átlókat, a hosszabb oldal szimmetria és konvexitás miatt  be fog férni automatikusan.

Pitagorasz: a piros hossza gyök(c*c+d*d), akkor x=gyök(c*c+d*d-a*a) és y=gyök(c*c+d*d-b*b). A kék vonal egy átfogó, a befogók a-x és b-y, ezekből számítva kék=gyök((a-x)*(a-x)+(b-y)*(b-y)). Ha kék > C, befér, különben nem.

Kód: http://pastebin.com/HYAH2cvs, 0:04, jó ez így. Lehet, hogy még ki lehet belőle küszöbölni a gyökvonásokat pár iffel, vagy benéztem valamit és egész aritmetikával is megoldható? Vagy már megint a scanf tart sokba? :-)

Bottom line: tartsunk egész aritmetikát, amíg csak lehet, ha meg nem lehet, double, és minél kevesebb bonyolult lebegőpontos művelet, az se a pontosságnak, se a futásidőnek nem tesz jót.

Ismétléses permutációk

Ma ezt a feladatot dolgozzuk fel:

http://www.spoj.com/problems/YODA/

Input egy string, hányféle palindroma rakható ki belőle.

Ez is egy olyan feladat, amit nyugodtan oda lehet adni a kódernek az első negyedórában :)

A feladat szövegében egy string egy sorban jön be, lehet benne szóköz is. Ezért a gets lesz a barátunk, aki egy sort benyel (scanf("%s") szóköznél megáll). Ha null jön be, vége az inputnak.

Továbbá, a sor tele lehet szeméttel, csak az angol kis- és nagybetűkkel kell foglalkozzunk, azokat viszont kezeljük egyben. Csinálhatnánk azt, hogy létrehozunk még egy stringet a filterezett stringgel, de tök fölösleges, hiszen csak a betűk darabszáma fog számítani, ezért egy count kb 26-elemű tömbbe beszámoljuk őket.

Észrevesszük, hogy a szó első fele meghatározza a másodikat, és azt, hogy

• ha több betű is van páratlan sokszor, akkor a válasz 0,
• ha pontosan 1, akkor az kell legyen középen,

és ha a válasz nem nulla, akkor annyi, ahányféleképp a betűk felét el lehet rendezni a szó első felébe. Tehát végigosztjuk kettővel a count tartalmát, ha közben már másodjára látunk alapból páratlan számot, akkor printf("0\n") és jöhet a következő sor (ezt egy borzasztó ronda gotoval oldottam meg :D ), egyébként pedig vissza kell adnunk, hogy a count tömb szerint megadott darabszámú különböző elemek (aka betűk) hányféleképp rakhatók sorrendbe.

Ha valaki nem emlékezne, ezt ismétléses permutációnak hívják és N!/(a!b!c!..z!) az értéke, ahol a, b, c, ..., z rendre az a, b, c, ..., z betűk darabszáma, N pedig az a+b+...+z összeg.

Ezzel persze nem vagyunk kész, hiszen N! nagyon nagy lehet (2^NlogN nagyságrendű), tehát a számláló, majd a nevező kiszámolásához és végül egy osztáshoz nem ártana ~10.000 bites számokkal számolni képes modult írni (ha nincs limit a sor hosszára, általában 1024-re becslem a felső korlátot, aztán ha nem annyi, majd kiderül). Ezt nem csináljuk.
Ehelyett vegyük észre, hogy ha z == 0, akkor ez az érték N!/(a!b!...y!), ha meg z > 0, akkor (N-1)!/(a!b!...(z-1)!) * N / z, és ami nagyon fontos most nekünk: az első tényező az szintén egy ismétléses permutáció, tehát egy egész szám. Amit aztán felszorozva N-nel még mindig egészet kapunk, majd leosztva z-vel pedig az eredményt, ami szintén egész kell legyen...

Ezt a rekurziót feloldva kapjuk, hogy a P(k1,...,km) ismétléses permutáció kiszámítására egy idő- és tárhatékony módszer:

long long unsigned result = 1;
long long unsigned n = 1;
for( int i = 1; i <= m; i++ ){
  for( int j = 1; j <= k[i]; j++ ){
    result *= n++;
    result /= j;
  }
}
return result;

Ezt még megfejelhetjük azzal, hogy az első elemmel nem is foglalkozunk, n=k[1]+1-gyel inicializálunk és i=2-ről futtatjuk a ciklust, vagy azzal, hogy megkeressük azt a t indexet, amire k[t] maximális, n=k[t]+1-gyel kezdünk, i=1..m futtatjuk a ciklust és az i==t esetet kihagyjuk. Nagyságrendileg ezekkel csak nagyon extrém esetben lesz gyorsabb a kód.. :)

Ja, kód: http://pastebin.com/BxaiNugT
Mivel 0:00, nem csináltam meg utána az optimalizálást az utolsó bekezdésből. Az eredmény 64-bites a szöveg szerint (a közenincs e ezt mondja, bár az e-nek van némi köze a faktoriálishoz, de most épp nem túl sokat használunk ezek közül) és persze nemnegatív, ezért long long unsigned a típus, emiatt ne legyen WA.

Jó vs jobb

Még mielőtt elfelejtem: a következő post arról szól, hogy hiába tanulunk algából egy problémára egy algoritmust, ami az Új Algoritmusokban is benne van, ATTÓL MÉG NEM AZ A LEGJOBB.
Kulcsszavak pl: SCC, Kosaraju, Tarjan, Gabow, párosítás, magyarmódszer, Hopcroft-Karp lesznek.

Erősen összefüggő komponensek

Ma ezt a feladatot dolgozzuk fel:
http://www.spoj.com/problems/TOUR/

Adott tehát egy irányított gráf, csúcsai a versenyzők, i-ből akkor megy él j-be, ha j garantáltan legyőzi i-t, ha egymás ellen játszanak. (Nem feltétlen tranzitív reláció, irreflexív, antiszimmetrikus).

A bírák döntik el, hogy ki kivel mérkőzzön meg először, a vesztes végleg kiesik, ezután a bírák megint döntenek stb. (bárkit választhatnak: az is lehet, hogy végig ugyanazt a játékost játszatják, míg valaki "végre" le nem győzi, meg az is, hogy egy bináris fát alkotnak, akárhogy). Nyilván a sorrend befolyásolhatja, hogy ki nyer, pl. ha kő-papír-ollót játszatunk, akkor egy kő-papír meccsel kezdve a végén olló nyer (miután papír legyőzi követ, olló és papír marad), de bárki más is kihozható győztesnek. Kő-papír-olló-gyík-Spockban is.

Mondjuk azt, hogy a bírák tudnak fújni az A játékosnak, ha tudják úgy rendezni az összecsapások sorrendjét, hogy a végén mindenképp A jöjjön ki győztesre. (Abban az esetben, ha olyan i és j játszik, akik közt vezet él, akkor garantáltan az győz, akibe vezet az él; ha nincs köztük él, akkor bárki győzhet -- ekkor mindkét lehetőség esetén kell tudják a bírák folytatni úgy a meccsek beosztását, hogy a végén A győzzön.)

A feladat: adott a gráf, hány játékos van, akiknek a bírák tudnak fújni?

Oldjuk meg ezt a feladatot.

Kis gondolkodás után rájöhetünk, hogy ha egy x játékos mindenhonnan elérhető, akkor a bírák tudnak neki fújni: ekkor vegyünk egy részfát a gráfban (x gyökerű, x felé irányított részfát), és ennek bottom-up módon játszassunk mindenkit a közvetlen rákövetkezőjével. (Tehát először a leveleket a rákövetkezőjükkel, akik legyőzik őket, majd a rákövetkezőket -- akik levelekké váltak ezalatt -- azok rákövetkezőjével stb, míg eljutunk x-hez, aki nyer.)

Még egy kis gondolkodás után rájöhetünk, hogy ha nem így van, akkor a bírák nem feltétlen tudnak neki fújni: legyen C a csúcsoknak az a halmaza, melyből x elérhető és D ennek komplementere. Nyilván D-ből nem vezet él C-be, hisz akkor egy ilyen él forrásából, egy D-beli csúcsból mégis elérhető lenne x. Másfelől x maga C-beli. Feltételezhetjük tehát akár azt is, hogy minden D-beli legyőzi az összes C-beli játékost (minden él C-ből vezet D-be a két pontosztály közt). Ekkor pedig világos, hogy a végén csak D-beli maradhat, ekkor x nem győzhet.

Mit kaptunk? Azt, hogy a bírák pontosan akkor tudnak fújni egy x játékosnak, ha a gráf minden csúcsa elérhető belőle. Csak azt kell megmondjuk, hogy hány ilyen csúcs van.

Namost triviális módszer minden csúcsból indítani egy dfs-t és megnézni, elérünk-e mindenkit.. ennek megfelelően TLE (gondolom. Sose próbáltam ki, hogy őszinte legyek :D ), hiszen négyzetes algoritmus.

Csináljunk belőle lineárist.

Azt tudjuk, hogy minden irányított gráfhoz hozzá lehet rendelni a komponensgráfját: a csúcsok az erősen összefüggő komponensek (SCC-k), C-ből akkor megy él D-be, ha van olyan él az eredeti gráfban, aki egy C-beli csúcsból egy D-beli csúcsba megy. (Két csúcs akkor tartozik egy SCC-be, ha elérhetőek egymásból.) Ez a komponensgráf megkonstruálható lineáris időben a következőképpen:

• csinálunk egy mélységi bejárást, tetszőleges sorrendben a csúcsokon (kapunk egy mélységi erdőt);
• aztán az eszerinti bejárás szerinti elhagyási idő szerint csökkenőbe rendezve csinálunk egy mélységi bejárást a csúcsokon, a gráf transzponáltján. (azon a gráfon, amiben az élek visszafele vannak irányítva.)

A második lépésben kapott mélységi erdő fái adják a komponenseket. Köztük az éleket pedig értelemszerűen fel lehet venni a gráf még egy bejárásával. Praktice a csökkenő sorrendet úgy varázsoljuk, hogy egy verembe dobjuk a csúcsokat, amint a dfs kijött belőlük.

Miért segít ez nekünk? Egyrészt x-ből y pontosan akkor elérhető, ha x komponenséből y komponense az a komponensgráfban (ezt alapul véve is lehet egyébként tranzitív lezárást készíteni egy input gráfon). A fújható csúcsok nyilván egy-egy nyelő komponensben kell legyenek: ha egy komponensből megy kifele él, akkor az egy olyan komponensből vezet, ahonnan nem lehet visszajönni, hisz a komponensgráf körmentes. Namost ha több nyelő van, ezekből egymásba átmenni megintcsak nem lehet, tehát ekkor senkinek nem tudunk fújni. Ha viszont egy nyelő van, akkor oda minden komponensből el lehet jutni: csak lépegetni kell mindig egy másik komponensbe az aktuálisból, előbb-utóbb egy nyelőbe kell érjünk a körmentesség miatt. Ekkor pedig a nyelő összes csúcsa fújható.

Összegezve:

• meghatározzuk a komponensgráfot
• ha abban csak egy nyelő van, akkor annak az elemszáma a válasz
• egyébként pedig nulla.

Kód itt. 0:24, lassú a többihez képest, de i) komponensgráfot lehet talán gyorsabban is csinálni más algoritmusokkal, amiben nem kell transzponálni és az eredeti gráfot is tárolni, ii) I/O, ennyi scanf :D

Easy fabejárás

Ma ezt a feladatot dolgozzuk fel:
http://www.spoj.com/problems/PYRA/

Miután elolvastuk a feladatot, próbáljuk kiszámolni, mit is kell kiírnunk? Egy elem szélessége a rajta levő elemeknek ( = a gyerekeinek) a szélességeinek az összege, plusz a gyerekeinek a száma plusz egy (a kihagyott üres helyek, mind egység széles, összesen ennyi van).
Ez a képlet kijön a levelekre is, ott nulla gyerek össz nulla szélesen, plusz egy az épp egy.

Fantasztikus, akkor csak felépítjük a gráfot, ami jön az inputon, irányítatlan gráfot fogunk építeni, mert mint ahogy a példából is látszik (van (0,1) és (2,0) is, 0 a gyökérelem), az élek irányát nem mondja meg az input.
Aztán ezt a fát a 0 csúcsból indulva egy bfs-sel felcímkézzük, rekurzívan, mert az időlimit azt mondja, hogy nagyon-nagyon ráérünk (lineáris futásidejű algoritmus, legfeljebb 25 darab egyenként legfeljebb tízezer csúcsú fán, ez pite). Közben szummázzuk is az értéket.

Sample megoldás itt. 0:25, ez bőven javítható, a C++ beépített konténerosztályok adnak egy kis overheadet, de nem arra játszunk versenyen, hogy a leggyorsabb kódot írjuk, hanem arra, hogy a leggyorsabban írjunk egy ACCEPT kódot, úgyhogy using namespace std, davaj.
Pár szó a kódról:

• mivel a gráfunk irányítatlan, fel kell címkézzük a csúcsokat -- visited tömb
• vizsgálhatnánk a bfs-be belépéskor is, hogy visited-e a node vagy sem, meg minden hívás előtt is. Általában azt javasolnám, hogy belépéskor első sorban tegyük ezt, de most azért nem, mert a bfs visszaad egy számot, amihez hozzáadunk egyet. Mondjuk persze akkor visszaadhatna -1-et is, és 0 lesz az összeg, de ez csak most jutott eszembe :D 
• emiatt a 0 csúcs visited értékét alapból 1-re kell állítsuk, a többiét meg 0-ra, mielőtt hívnánk a bfs-t a 0 gyökércsúcsra. (this costed me a WA :P :D ) Meghívjuk és az akkumulált totalSize értéket kiírjuk.

Minden versenyen van egy olyan feladat, amit csak oda kell adni a kódernek, hogy tessék, kódold le, míg a többiek megoldanak még egyet, a jobb lengyelek rendszerint tíz percen belül ezt azonosítják is és meg is oldják. Ennek a feladatnak a tanulsága maximum az, hogy ismerjük és használjuk az STL osztályokat: gráfot pl éllistával érdemes egy vector< deque< int > >-be rakni, ha a csúcsai 0-tól N-ig a számok, úgy a szomszédsági listákat konstans időben elérjük, a listákon a deque-eken az iterátor léptetése konstans, és az új él beszúrása is konstans idő, mást meg nem kell csinálnunk, tehát az adatszerkezet nagyon jó időigényt biztosít nekünk.
Hülyeség szomszédsági mátrixba rakni a dolgokat (általában egyébként az; egy kivétel talán, mikor iterált mátrixhatványozással oldunk meg tranzitív lezárást. Meg a Floyd-Warshall. Talán.)

Amikor a scanf is lassú

Ma ezt a feladatot dolgozzuk fel:
http://www.spoj.com/problems/HPYNOSII/

Röviden a feladat a következő: kapunk egy rakás 32-bites számot. Legyen f az a függvény, ami egy számhoz a számjegyei négyzetösszegét rendeli, pl. f(145) = 1*1 + 4*4 + 5*5 = 42. Ezt a függvényt iteráljuk, pl. f²(145) =  f(f(145)) = f(42) = 4*4 + 2*2 = 20, f³(145) = 4, stb.
Induljunk ki egy n számból. Elképzelhető, hogy van olyan k, amire fk(n)=1. Ebben az esetben írassuk ki a legkisebb ilyen k értéket.
Meg az is elképzelhető, hogy máshol kezd ciklizálásba az iteráció, pl. a fenti példát folytatva f(4) = 16, f(16) = 37, f(37) = 58, f(58) = 89, f(89) = 145, amit meg már láttunk. Ebben az esetben írjunk ki -1-et.

Általában az is elképzelhető lenne, hogy a függvény divergál (pl. az n -> n + 1 nyilván ilyen függvény) és se nem fut le 1-re, se nem esik ciklusba, de a feladat szövege egyértelművé teszi, hogy ez az f nem csinál ilyet. Tehát ezt tesztelnünk se kell. (jobb is, mert általánosan eldönthetetlen :P )

Oldjuk meg ezt a problémát.

Első nekifutásban az ember ha ilyet lát, mit tesz? Ha az f-fel nem foglalkozunk, akkor "csak" annyi a feladatunk, hogy iteráljuk f-et, számoljuk, hogy hányszor tettük ezt, ha 1 az eredmény, akkor print, egyébként ha olyan számot látunk, aki már volt az aktuális sorozatunkban, akkor print -1.

Oké, a vastag betűs részt még kicsit ki kéne dolgozni. Az első megközelítés, hogy dobáljuk bele egy konténerbe a sorozat képzése közben a számokat. A std::set pont erre való: lehet beletenni (és kivenni) dolgokat, és ellenőrizni, hogy amit betettünk, volt-e már. Csak annyi kell, hogy az operator< definiálva legyen, vagy legalább paraméterezzük fel egy comparatorral, ami értelmez a bedobált objektumok halmazán egy < teljes rendezést.

Tehát gyártunk egy ilyen kódot:
unsigned iterate( unsigned n ){
  set< unsigned > theSet;
  theSet.insert( n );
  unsigned result = 0;
  while( n ) {
    if( n == 1 ) return result;
    n = f(n);
    if( theSet.find( n ) != theSet.end() ) return -1;
    theSet.insert( n );
    result++;
  }
}
ahol persze f az iterálandó függvényünk, most éppen pl.
unsigned f( unsigned n ){
  unsigned result = 0;
  while( n ){
    unsigned d = n % 10;
    n /= 10;
    result += d*d;
  }
  return result;
}
persze ha valaki nem szereti a szorzást, kinézheti lookup táblából is azt a d*d értéket.

Persze TLE (Time Limit Exceeded), mi más történt volna.

Sok ötletünk lehet gyorsítani ezt a kódot. Egyelőre itt egy bottleneck az iterálás futásideje lehet (minden f-re, nem csak a mostani konkrétra). Miért? A std::set underlying adatszerkezete egy kiegyensúlyozott bináris keresőfa (mondjuk piros-fekete). Ez egy n-méretű halmazban a fenti műveleteket (beszúrás, check) O(logn) lépésben oldja meg. Tehát ha megcsináljuk az iterációt, akkor d lépés megtételéhez log1 + log2 + ... + logd ~ dlogd időre van szükségünk. Ha tehát olyan f-fel van dolgunk, ahol nagyon hosszú (milliós) láncon kell tesztelnünk, hogy beáll-e a vége egy fixpontra (jelen esetben: lefut-e 1-re) vagy máson kezd ciklizálni, akkor ennél gyorsabb módszerre van szükségünk.
Két lehetséges megoldás:

• Ha van olyan szerencsénk, hogy a bíró fordítója támogatja a C++11-et (CERC'13-on van: a GCC 4.7.3 részlegesen támogatja), akkor használjunk std::unordered_set-et. Ezt ugyan nem lehet sorrend szerint bejárni, hiszen underlying adatszerkezete egy hashset, viszont cserébe a beszúrás, keresés időigénye amortizált konstans. Elméletileg. Mondjuk továbbra is megy némi idő a dinamikus memóriakezeléssel, ha egy milliós lánc minden elemét belerámoljuk...
• Használhatjuk a következő trükköt: KÉT intet futtatunk. Alapból mindkettőt beállítjuk n-re, az egyiken f-et, a másikon ff-et iteráljuk (tehát a másodikat kettővel léptetjük egyszerre). Ha a második lefut 1-re, kész vagyunk, közben számoltuk a lépéseket. Ha nem, mert ciklusba esik máson, akkor előbb-utóbb a lassabb iterátor is beér a ciklusba és mivel lassabb, a második előbb-utóbb utoléri (méghozzá legfeljebb újabb d iterálásban, hiszen ez felső korlát a ciklus hosszára is), és ekkor egyenlőek lesznek. Abból pedig rájövünk, hogy ciklusban vagyunk és adhatjuk a mínuszegyet vissza.

Utóbbihoz kód:
unsigned runningPointers( unsigned n ){
  unsigned n1 = n, n2 = n, result = 0;
  do{
    if( n2 == 1 ) return result;
    n1 = f( n );
    n2 = f( n );
    result++;
    if( n2 == 1 ) return result;
    n2 = f( n );
    result++;
  }while( n1 != n2 );
  return -1;
}
Hurrá, van egy O(d) időigényű algoritmusunk, fut mint a szél, submit, TLE.

Mit rontottunk el?

Ha egyetlen inputot kapnánk, vagy legalábbis nem sok számot és a láncok várható hossza nagy lenne, ez egy elfogadható megoldás lenne (általános f-re, amiről nem tudunk megállípítani semmit). DE MOST NEM EZ A HELYZET.

Hanem: kapunk EGYMILLIÓ számot, 32-bitest. Ez már bőven az a mennyiség, amikor komoly költsége van annak, ha mindig újra kiszámítunk korábban már meglevő értékeket. Adja magát az ötlet, hogy tegyük le egy std:map<int,int>-be, az pont erre való: számhoz rendelünk értéket, mégpedig egy adott számhoz azt, hogy hány lépésben fut le 1-re (inkább eggyel többet szúrunk be: lépésszám helyett lépésszám+1), vagy -1 jelzi, ha nem fut le. Ezt a tömböt szépen töltögetjük (a -1 azt is jelzi, hogy az az elem épp töltés alatt áll -- így ha a rekurzió -1 értékű elemre fut, tudjuk, hogy körbeért), miközben dolgozzuk fel az inputot és ha már ismert érték jön, kiírjuk:

std::map<unsigned, int> cache;
cache[1] = 1;
int computeAndStoreInMap( unsigned n ){
  if( cache[ n ] != 0 ) return cache[ n ];
  cache[ n ] = -1;
  int d = computeAndStoreInMap( f( n ) );
  if( d == -1 ) return -1;
  return d + 1;
}
Érdemes tudni, hogy az első sorban az operator[] hívással be is szúrjuk az elemet a default allokátorral, tehát 0-val. Azaz az első sor a "ha már benne volt" if, különben nullával belekerül. Lehet persze rekurzió-mentesíteni is, aki akarja, most csak a cachelés a lényeg. Hadd menjen.

TLE.

Megint mit csináltunk? Mi lehet a baj, hát letároltunk mindent, amit korábban számoltunk, tuti nem számoltunk ki semmit többször...

...de azzal, hogy mindent bedobunk a cache-be, használhatatlanná tesszük azt: egymillió inputról beszélünk, még ha mindnél csak egy elemet is szúrunk be (ami egy alsó korlát), akkor is egy milliós mapot managelünk a maga kis logn-es insert, find etc. műveleteivel -- mert a map is kiegyensúlyozott keresőfa alapú. Kicsit jobban állunk megint, ha van C++11 és std::unordered_map-et használunk, az megint egy hashmap, de a milliós méretű dinamikus memória most nem nyerő.

Nem kéne mindent cachelni. Csak amit tényleg lehet, hogy újra felhasználunk többször is.

Eljött az a pont, ahol rá is nézünk magára az f függvényre: a számjegyek négyzetösszegét kell képezni, az input egy 32-bites egész... akkor egy lépésben legfeljebb az 1,999,999,999 által elérhető 9*9*9+1 = 730-ra futunk rá. AZ f FÜGGVÉNY ÉRTÉKKÉSZLETE AZ 1..730 HALMAZ.
Tehát nincs más dolgunk, mint

• kiszámoljuk előre az 1..730 számokra a megfelelő értékeket,
• beolvassuk az inputot (ami a specifikáció szerint legalább n = 2 lesz), hívjuk rá a számjegynégyzetösszeget, aztán kilessük a táblából, hogy még hány lépés, kiírjuk.

Nyilván mivel egy 730 elemű, 1..730 közt folytonosan indexelt precomputed táblát építünk fel, ezt tényleg tömbbe rakjuk. Kód:
int fillTable( n ){
  if( table[ n ] ) return table[ n ];
  table[ n ] = 0;
  int d = fillTable( f( n ) );
  if( d != -1 ) d++;
  table[ n ] = d;
  return d;
}
for( int i = 0; i <= 730; i++ ) table[ i ] = 0;
table[ 1 ] = 1;
for( int i = 2; i <= 730; i++ ) fillTable( i );

int compute730( unsigned n ){
  return table[ f( n ) ];
}
Figyeljük meg, összeérnek a dolgok: a precomputed táblába eleve eggyel nagyobb számokat rakunk be, így feldolgozáskor nem kell növelni.
Minden kész, van egy tankönyvi precomputed táblánk, párezer műveletben felépül (a korlát ugye rendszerint kb egymilliárd műveletet tesz lehetővé input file-onként, tehát a tábla felépítése elhanyagolható), a négyzetösszeg függvényt hova gyorsítsuk, inputonként egyetlen négyzetösszeg-számítás és egyetlen táblaelemnézés, mi baj lehet.

TLE.

(sigh) (mi más)

Egyébként erről a kódról beszélünk. Mikor kitűztem a feladatot, úgy gondoltam, hogy ez lesz a megoldás, aztán a versenyen mikor kódolgattam a megoldásokat, néztem egyet, hogy ezt ennél gyorsabban nem lehet megoldani, nincs rá jobb algoritmus, kizárt.

és mivel algoritmus nincs rá jobb...

...csak az I/O-val lehet gond. Ránéztem még egyszer frissebb szemmel a kiírásra: egymillió tízjegyű számot kapunk meg inputként, ez cca enterekkel tizenkét megabyte-os input file.

Amit mindig elmondok:

• SOSE HASZNÁLJUK a cin és cout streameket. Egyszerűen túl lassúak minden feladatra.
• Amit használunk: scanf (formázott inputra), gets (soronként stringet), printf (kiírásra).

na ez az elmélet esett részlegesen pofára. Itt bizony az a gond, hogy azzal a tizenkét megabyte-al a scanfelés nem bír el...

úgyhogy a megoldás, hogy a számokat stringként olvasom be gets-sel. Aztán persze nem csinálok belőle számot (arra való egyébként az atoi függvény), mi a fenének? Eleve a stringből a digit négyzetösszeget számolom és azt kinézem a táblából... lásd itt. 

ACCEPT.

1:40, a 2 másodpercbe épp belefér :D

Egyébként ezután átírtam a beolvasást fread_unlocked-re, ami jó dolog, mert nem egymillió gets hívásunk van, hanem egyetlen IO hívásunk, az egész file bemegy memóriába és toljuk, mint stringet. 1.02. Lehet még alakítok rajta kicsit később, mert a nyolcadik-kilencedik lapon művészkedni nem menő :D