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