Egyébként
azt sose bánjátok, hogy vannak nehézségek (még akkor sem, ha ebből
fakadnak). Anno nálunk volt olyan versenyünk, ahol azért lettünk
másodikak kb. mert valakik rájöttek, hogy túl jó sebességet várnak el,
ezért a 32000-ig számold ki bemenetet tollal áthúzta a kinyomtatott
versenylapokon és fölé írta, hogy 16000. Na ez szép és jó, de annyira
gyorsan dolgozott, hogy nálunk az első számjegy nagyon erősen négyesnek
látszott, így egy órát elszívóztunk az atomra optimalizálással a TLE
miatt, mire végre lefutott időben és akkor írta ki, hogy "wrong answer" -
persze egyébként csak azért volt wrong, mert hát mi tovább is
kiszámoltuk az eredményeket :D
Az ilyenekből lesznek a sok-sok év múlva is mesélt war-room sztorik, meg
ezektől sokat fejlődik az ember. A lányod meg amúgy ügyesnek néz ki az
elmondottak alapján.
ui.: Anno meg egyetemen volt olyan is, hogy véletlenül valaki feladta
vizsgán a P=NP bizonyítását - pontosabban olyat adott fel, hogy ha
bizonyítja bárki is, akkor ezt is bizonyítja, szóval "nem lett túl sok
helyes megoldás", viszont a vizsga utáni sörözés vicces volt
Elég hamar ellehet jutni hozzá, amennyiben valaki beazonosította a problémát. (lassú beolvasás)
Első találat 'c++ slow io'-ra már tárgyalja is a függvényt és szerepét.
A "valaki" és a "beazonosította" közül kimaradt egy olyasmi rész, hogy "tapasztalt programozó, rendszeresen használt angol tudással és".
Elég hamar ellehet jutni hozzá, amennyiben valaki beazonosította a problémát. (lassú beolvasás)
Első találat 'c++ slow io'-ra már tárgyalja is a függvényt és szerepét.
A másik két hívásra jelen esetben nincs semmi szükséged.
Sőt a cout-os tie tudtommal teljesen fölösleges (alapból a cout nincs másik stream-hez kötve) tie
NotesBy default, the standard streams cin and
cerr are tied to cout. Similarly, their wide counterparts wcin and wcerr
are tied to wcout.
Az valóban elég szomorú, ha nagyjából ennek a funkcionalitásnak az
ismeretéhez kötik a beadandó sikerességét, úgy hogy erre külön nem hívta
fel senki a figyelmüket egy IO heavy beadandó előtt.
Félek annak van igaza, aki szerint a tanár scanf-es megoldásokra számít, sőt azokat várja el :(
Nem
lehet, hogy a tanár scanf-es beolvasásra számít, attól függetlenül,
hogy C++-t oktat? Az megmagyarázná, hogy miért nem zavarja a lassú cin,
és nem igényelné mindenféle fekete mágia bekapcsolását a kód elején.
Valoban jo otlet es legrosszabb esetben is csak 100x hajtodik vegre az extra minp=i.
Regen sokat tudtam huzni a float<->string rutinok lecserelesevel. A
számformátum elôre felderítésével (itt konkretan 5 féle gyakori pattern
van: 0 00 -0 -00) es 2-3 digit lookup segitsegevel, megfeleloen monoton
adatnal 10x speedup is elerheto.
Szerintem a feladatra a 0.1sec, 32MB egy standard bélyegzô segítségével került rá. Egyszerûen csak olyan volt a fiókban.
Sziasztok! A jelek szerint mraron megtalálta a "megoldást": a beolvasás a lassú, és azt a trükkös három utasítást kell kiadni, rögtön 0,208 --> 0.072 mp lett az eredmény!!!
Szóval ez nagyon gáz!!!
A kezdő programozó-tanonc honnan tudna ilyen trükköket, szerintem
közülünk is kevesen ismerik/használják. Ha első órán elmondanák, hogy
"kedves kollégák, a beadandót így tessék kezdeni"... de nem mondtak
semmi ilyet.
Amúgy tevemadar javaslata
kicsit gyorsabb lett, épp annyira, hogy kéttized mp alá került, és a
gép elfogadta (ami egyébként hiba, mert 0.1mp volt az időlimit, de a
videobíró elfogadja 0.2mp-től ). Gratula és köszi!
És mindenki másnak is köszönöm az agyalást!
@VersIon: bár ismerem az ifek helyett kivonás-szorzás trükköt, ezt még FORTRAN-os korban szerettük használni , manapság hajlok rá, hogy tevemadárral értsek egyet, nem lesz gyorsabb. De ki kell próbálni.
@csörnyeföldi: standard inputot kell használni, semmilyen fájl inputra nincs mód.
@senki: ugyanezért nem tudunk többször beolvasni és hasonlók. Csak egy
CPP fájlt lehet beküldeni, ami vagy a kiírás szerint működik, vagy
bukta. Se saját tesztet, se kimenetet, se profilt stb. nem ad ki a
rendszer. Amúgy ötletes gyorsítási javaslatokat írtál, csak ezt nem
kezdő programozónak egyik első beadandóban kellene megvalósítani.
Szerintem. Mindenesetre köszi, én is tanultam belőle!!!
Végül egy kis kiegészítő: lányom előállt saját magától egy kis
gyorsítási javaslattal, ami valóban hasznos. (Büszke vagyok a lányomra,
azt hiszem, tényleg tehetséges).
Az ötlete lényege, hogy a min/max keresésnél megjegyezzük az első
találat pozícióját, és a városjelölést csak onnan kell kezdeni, hiszen
korábban nem lesz minimum. Ezzel valóban akár többszáz vizsgálatot meg
lehet spórolni:
Es
ha egyszerre van NxM es egy MxN matrix kefoglalva es feltolve valami
low leveles feldolgozasra? Ha char belefer a +-50 siman. Es az egyik min
maxra optimizal a masik varosra?
1.)
Ki kellene deríteni, hogy a beolvasás-e a lassú, vagy a kód többi
része. Ehhez küldjetek be olyan kódot, ami csak beolvas (mondjuk
kétszer). Emelhetitek azt a számot, hogy hányszor olvastok, így egy kis
logaritmikus-heurisztikus jellegű próbálgatással hamar kiderül, hogy
mennyi ideig tart a beolvasás. Ha elhanyagolható, akkor lehet menni
tovább. Ha nem, akkor scanf(..)-re kell cserélni (vagy annál
low-levelebbre), vagy panaszkodni, hogy terhelt a szerver.
2.) Tevemadar megoldása szerintem sokkal normálisabb, mint az eredeti
tietek. Abból érdekes kiindulnotok, meg én is rögtön így kezdeném, mint ő
tette...
3.) Úgy látom, hogy mindenképpen fel kell egyszer dolgozni a teljes
imputot, így aszimptotikusan nem tudom gyorsítani az algoritmusaitokat,
csak trükközéseket lehet csinálni, hogy kisebb legyen a konstans.
Bizonyítás: Ugye ha jól értem a kiírást, akkor a városok a sorok, a
napok az oszlopok és ugye így a worst case bemenet az olyan, hogy
mondjuk minden sor tök azonos 42-t tartalmaz egészen az utolsó kettő
sorig, ahol -50 és +50 szerepel. Ezért mindenképp végig kellett olvasni,
mert elvileg ehelyett bármi szerepelhet, ami módosítja az eredményt.
Ezt csak úgy mondom.
No szóval. Extra okosság:
* Lehet egy min[0..1000] és max[0..1000] tömb. Ezt az oszlopok fölé képzeled el.
* Amikor olvasod be a fájlt, ebbe már rögtön minker/maxker megy, így
mire az összes oszlopból megvan az összes sor, felette ott lesz, hogy
mennyi volt a min és a max.
EZ EDDIG 1000*1000*4 mondjuk, de a ciklus magját tök jól tudja
pipeline-osítani a CPU és a cache se lesz problémás, mert csak lineáris
balról-jobbra olvasás van és nincs olyan vad anti-cache megoldás, mint
az első kódotokban.
* Szintén ügyes optimalizálás lehet blokkosítani a nagy mátricot!!!!
Minden ilyen blokkhoz el lehet tárolni egy 100-128elemű bitvektort.
* Ez azért jó, mert ha jól látom integerek a koordináták, így amikor
ezen soroknál járunk, akkor a bitvektorban a (szám+50)-edig pozíciót
true-ra tesszük amint (kezdetben minden legyen false). Ezzel egy adott
blokkra vonatkozó "lekérdezéseket" tudunk majd később intézni. Mivel
ezek blokkokra vonatkozó adatok, így nem tudják elkerülni nekünk, hogy
néha soronként végigmenjünk majd, de például olyanok nagyon könnyen
kiderülnek így, hogy egy egész blokkban nem szerepel a blokk oszlopai
felett lévő min és max értékek egyike sem, így azon a részen xdb sornál
nem kell keresni, hanem csak a szűkebb tartományt!
Ha eddig eljutottunk, akkor tehát van: -Egy nagy tömb tele számokkal.1000x1000 - Két-két 1000-es tömb az oszlopok felett min és max értékekkel -Egy-egy 100-ig indexelhető bitset a blokkokhoz, amelynek az i-edik bitje akkor 1, ha a (i-50) celsius az benne volt
Akkor most már csak ki kellene zárni azokat a városokat, melyekre nem
igaz a szükséges kritérium. Ha nem trükközünk, akkor ez egy újabb
1000x1000-es művelet, de itt is lehet trükközni
* Például észrevehetjük, hogy ez nem 1000x1000 művelet kéne legyen,
hanem (worst case) 1000+998+996+... szóval szépen kettesével csökkenő
sorösszeg.
* Ez azért, mert ha oszloponként nézzük az eddigi részeredményt, akkor
ugye csinálhatjuk úgy, hogy végigmegyünk egy oszlopon és minden olyan
sornál, ahol ebben az oszlopban lévő min, vagy max szerepel egy olyan
sorra bukkantunk, amely "rossz" és nem lehet az eredményben. Viszont a
többi oszlopnál az ilyen sorokat nem kell már vizsgálnunk!
Na de hogyan oldjuk meg, hogy mindig csak a "még játékban lévő" sorokat
vizsgáljuk, ha így szépen vertikálisan haladunk? Hát a következő kis
trükkel:
Legyen egy 1000-elemű tömbünk kezdetben. Ezen tömböt képzeljük el a nagy táblázat legszélén vertikálisan. Kezdetben az elemei:
1, 2, 3, 4, ... 999
Ennek jelentése az, hogy az adott sornak mi legyen a rákövetkezője.
Tehát abban a ciklusban, ami minden oszlopra, megnézi a sorokat, hogy
van-e min-max azon a soron - a soronkénti léptetést nem ++j jellegű
inkrementálás, hanem
j = nextj[i]
fogja csinálni! Ezzel már nagyon egyszerűen skippelhetővé tehetjük az
adott sorokat, mert csak a nextj tömbben kell az őt megelőzőnek
beállítani az őt rákövetkezőt és készen is van a varázslatos skippelés.
Egyébként ez jobb is lehet, mint 1000+998+996+... futás a második
menetre, mert ezzel mindegyik olyan sort örökre ki tudunk lőni, amely
vagy a min, vagy a max értékkel egyezett. Egy best case például, ha az
összes sor a max értékkel egyezett, mert minden városban ugyan annyi fok
volt. Ekkor az egész algoritmus leáll. A worst case mint mondtam a
2db-onkénti csökkenés.
Ez nagyon szép, de sajnos csak elméletben...
Na igen. Amit most itt utoljára leírtam, az sok aranyos ügyeskedést
tartalmaz, de a vertikális keresés miatt valszeg lassú. Az indirekció
miatt is esetleg kicsit rosszabb lehet, mint ha egyszerűbben fognánk
meg. Szóval ki kellene mérni.
Van olyan, ami kevésbé elegáns, de gyakorlatibb?
Hát akkor menjünk soronként a végén a tevemadar szerinti algoritmussal és kész egyébként.
Meg hát a blokkos trükközgetést megcsinálhatjuk, mert az jó lesz...
Ezeket mindenesetre ki érdemes már mérni. Amúgy a scanf és a low levelebb inputok sokkal gyorsabbak...
Szerintem
a memórián bukik el a dolog. Talán az lehet a trükk, hogy nem N*M-es
tömböt foglalsz le, hanem csak M hosszút, persze az algoritmus attól még
O(N*M) marad.
Én úgy csinálnám, hogy megkeresném mely városokon van valamelyik nap
aznapi minimum vagy maximum, és amelyik nem ilyen, azt kell kiírni a
végén.
Azt meg úgy keresed meg, hogy minden sort feldolgozol, a napokat
egyesével. Minden napra letárolod hogy melyik volt az aznapi min/max
hőmérséklet, és hogy melyik városhoz tartozik az. Ezt egy M hosszú
tömbben le lehet tárolni.
A végén kapsz egy M hosszú tömböt, benne azoknak a városoknak az
azonosítóival, amik NEM kellenek. Ezek után már csak két halmaz
különbsége az eredmény.
Standard
inputról kell beolvasni így nem igazán. Nyilván nem copy pastenak
szántam a kódot, a bits/stdc++.h-t pedig megszokásból írom ha gyorsan
kell valamit írni, amint láthatod stdlib-ből csak iostream-et használok.
Egy elsős beadandójában, szerintem nem kell túl bonyolítani, az
std::ifstream in("file.txt");
untig elég, és jó lesz, mert mást még nem nagyon tanulthatak. PolyJoe
korábbi hozzászólásából arra emlékszem, hogy pl <vectort> nem
lehet használni. Akkor a bits/stdc++.h sem nagyon díjjazzák. És
szerintem az
std::istreambuf_iterator
Elég gyorsan beolvassa a max 1000x1000 mátrixot a fájlból. Mert ez messze nem nyöszörgő és belesírok tétel.
Masszívan
párhuzamos architektúrára ez jó ötlet. Jelen esetben viszont
valószínűleg többet ér, ha nem kell szorozni, nem kell túlcsordulástól
tartani és menet közben félbe lehet hagyni az egészet.
2. majd utana vizszintesen minden varosban a (homerseklet -min) *
(homerseklet - max) ertekeket szorozzuk ossze naponkent, ha a
vegeredmeny nulla akkor van szelsoertek valahol, a nem nullas ertekeknel
noveljuk a szamlalot, a varos indexet hozzaadjuk egy listahoz
3. kiiratjuk a szamlalot
4 kiiratjuk a varos listat
Bocsánat, igazad van, fordítva írtam. Soronként egy város, összes nap adata jön.
Épp ez a "gond": min/max keresni egy nap összes város adatát kell. Tehát
beolvasni soronként, keresni oszloponként (vagy persze fordítva).
A standard bemenet első sorában a települések száma (1≤N≤1000) és a napok száma
(1≤M≤1000) van. Az ezt követő N sorban az egyes napokra jósolt M hőmérséklet értéke található ...
Szerintem egy sor, egy település összes hőmérséklete.
gyorsítási
lehetőség: ha van min/max értékkel egyező érték a növelés
utána többi nap hőmérsékleti adat ellenőrzését az adott napon
eldobhatjuk, felesleges számolást nmnem végzünk
Szerintem csak egy 1xM -s vektor kell (a vásosok száma)
illetve soronként (városok bemenete) egy min és egy max int érték.
1.) a min és max érték feltöltése az első értékkel
2.) min és max megénzése a az következő elemmel ha min-nél kisebb cserél, maxnál nagyobb...
ha azonos az érték az VÁROS vektor adot indekszén ++ művelet.
....
mindegyik sor(város feldolgozása)
3.) VAROS vektor végignézése. Ha adott érték 0 az indexének kiírása
-> minimális memoria használat, 1x dolgoz fel mindent, minimális
allokáció ( VAROS 1xMx1 byte, unsigned char esetén. Int esetén több
viszont gyorsabba művelet )
Megpróbálok egyben reagálni az elmúlt időszak ötleteire.
Túlbonyolítod
Lehet
De a kiírást nem én készítettem, van egy trükk benne: soronként egy nap
összes város adata jön. Kiírni viszont város szerinti sorrendben kell.
Vagyis a feldolgozást csak akkor lehet elkezdeni, ha már mindent
beolvastunk. De amúgy mindegy, mert egyszer így is, úgy is végig kell
olvasni, mindegynek tűnik a sorrend. (Leszámítva, hogy a processzor
soronként könnyebben cache-el, mint oszlopban, de e célból már a kezdet
kezdetén elforgattuk a mátrixot.)
A soronkénti qsort nyilván nem lehet gyorsabb, mint a min/max keresés -
hiszen utóbbihoz egyetlen lineáris végignézés elég. Valamint ha rendezem
a tömböt, elveszítem a városok növekvő számsorrendjét is... ez nem
járható út. Állítólag pont azért van az időlimit, hogy akadályozzák a
sortolással szélsőértéket keresőket.
A for helyett while sem segít pont itt, mert a min/max kereséshez az
egész napot, minden várost át kell nézni. Lásd kiírás! A megfelelők
keresésénél viszont már benne van, hogy a már kiesett városokat tovább
nem vizsgáljuk.
Tevemadár ötlete felmerült bennem is, de valamiért végül nem használtuk fel. Megpróbálom!
Bocsi
az előbbi postomért, nem olvastam el a specs-et. Szerintem az egyetlen
szükséges tömb az az eredmények sorszáma. Valahogy így képzeltem el:
intNvaros=...; intNnap=...; std::string filename =...; int min =...; int max =...; std::ifstream ifs(filename); std::string city; int temperature; int*result_cities =newint[Nvaros]; int result_count =0; for(int line =0; line <Nvaros;++line){ ifs >> city; bool match =true; for(int data =0; data <Nnap;++data){ ifs >> temperature; if(temperature == min || temperature == max){ match =false; break; } } if(match){ result_cities[result_count]= line; ++result_count; } } std::cout << result_count << std::endl; for(int i =0; i < result_count;++i){ std::cout << result_cities[i]<<" "; }
Lehet, hogy rosszul, de én másképp csinálnám:
- 1000x1000-es tömb stimmel
- 1000-es tömb min, feltölt valami naggyal
- 1000-es tömb max, feltölt valami kicsivel
- az 1000x1000-es tömb beolvasás közben kitölteném a min-max tömböt is
- vektor híján 1000-es tömb a kiírandó városok tárolásához, meg egy számláló
- végigmegy a városokon (i), és városon belül (j) a napokon addig a
napig, amíg a napi hőmérséklet megegyezik a napi maximummal vagy
minimummal. Ha valamelyik nem stimmel, break.
- ha végigért egy városon (j==napokszáma, szóval ehhez j-t nem a for-ban
deklarálnám), vektorhelyettesítő tömbhöz hozzácsap, számláló növel
- kiírás
intNvaros=...; intNnap=...; std::string filename =...; int min =...; int max =...; std::ifstream ifs(filename); std::stringstream result; std::string city; for(int line =0; line <Nvaros;++line){ ifs >> city; for(int data =0; data <Nnap;++data){ int temperature; ifs >> temperature; if(temperature <= min || temperature >= max){ result << city <<"\n";// itt mehet el tobb ido... break; } } } std::cout << result.str();
Ha ismert Nvaros és Nnap, akkor nem kellene a tömböket fixen 1000*1000 és még 1*1000 méretüre venni.
De eleve nem kellene Nvaros * Nnap méretű tömböt foglalni, egy sor
önmagában feldolgozható, az eredmény tárolható. És így nem is kellene
külön ciklusban beolvasni, majd külön ciklusban feldolgozni.
Mi lenne, ha nem boolean-al mentenétek, hogy melyik város éri el a min-t
vagy max-t, hanem egy int 1000 kezdőértékkel induló változóból vonnátok
le mindig egyet?
Most olvasom, hogy a sorszámokat is fel kell sorolni. Azt pedig lehetne
egy másik tömbben tárolni. Nem tudom listát, vagy dinamikus tömböt
tanultak-e. Ha nem, akkor még lehet mindig gyorsabban jön ki, ha így
csinálja:
int sorszamok[1000]; int talalt_sorszamok =0;
Így ha az 1000ből csak 10 városnak a sorszáma kell, akkor is megspórolta
az fentebb említett két ciklusból az elsőt a másodikat pedig
lerövidítette.