Uždavinių sprendimas codeforces

Pastaruoju metu gana dažnai užsiimdavau Codeforces uždavinių lėtu sprendimu. Ir kai tik pavykdavo - dalyvaudavau virtualiuose contest'uose.
Patiko paskutinieji keli turai, kurių metu sekėsi (pavykdavo) kiek geriau.

Turų santykinis sudėtingumas priklauso ir nuo to, kokio tipo uždaviniai jame būna. Nes vienus sprendžiu geriau negu kitus.

Ne kontestų metu spręsdamas, dažnai "cheatin'u" - žiūriu nepraėjusius test case'us, ir bandau programą adaptuoti prie jų. Tuomet mąstyti reikia mažiau. Sunkiau būtų - pačiam kuo įmanoma daugiau ir įvairesnių, kraštutinių bei sudėtingų test case'ų sugalvoti.

Iš archyvo uždavinių, iš tų, kuriuos išsprendę mažiau kitų dalyvių, o aš - išsprendžiau, dominuoja - uždaviniai su eilučių apdorojimu. Mat, įvaldžius Perl'o reguliariąsias išraiškas, tampa lengviau spręsti. Kodas paprastesnis, trumpesnis. Taip pavyksta išspręsti kai kuriuos ne pernelyg didelių įeities duomenų uždavinius, nes sprendžiant didelių įeities duomenų uždavinius, Perl'as nesusidoroja su laiku, arba mano algoritmas būna per neefektyvus.

Blogiausiai sprendžiu uždavinius turbūt: su grafais, duomenų struktūrom, kombinatorika, dinaminiu programavimu (jo reikšmės dar nesuprantu), hash'ais (jų nemoku), binarine paieška (nesinaudoju, nemoku). Patogu, kad archyve prie uždavinių pateikti tag'ai. Tokiu būdu yra netgi užvedama ant to, kokiu būdu reikėtų spręsti uždavinį.

*****
Vieni iš mėgstamiausių arba įdomiausių uždavinių būna, kai reikia kažką padaryti ar surasti dvimačiame masyve.
Štai šis uždavinys labai patiko, ir pavyko jį per nemažai valandų išspręst. 
Sprendimas - Pascal'iu. Kai kurie C++ vartotojai skundėsi, kad uždavinyje labai didelė įvestis (matrica iki 5k x 5k = 25M) ir jie nespėja nuskaitydami su "cin", sutilpti į time-limitus;
Ant lapo teisingas idėjas sugalvoti pavyksta greičiau, ir pati idėjų realizacija kodo rašymu užtrunka apie 5 kartus ilgiau, deja. Mano algoritmas čia atrodo kvadratinis - du "for" ciklai. Du kartus. Tai pavyko tilpti, bet vistiek laikas 780ms - nemažas (geriausias sprendimas 265ms GNU C++)

Kitas patikęs uždavinys, kurį iš principo norėjau išspręsti ir sugaišau daugybę laiko, yra "dinaminis" - žaidimas su skliausteliais. Turėjau įjungti stack'inę mąstyseną. Sprendimas Pascal'iu. Apie stack'o sukūrimą rodyklėmis nesivarginau pradėt galvoti, tačiau mąsčiau kaip juo spręsti. Nes kitaip sugalvoti - ilgai nepavyko. Savo "stack'ą" pasidariau iš masyvo, kuriame šokinėja stack'o "dangčio" koordinatė. Nuo dangčio mažyn indeksai reiškia stack'o turinį, o nuo stack'o aukštyn indeksai reiškia nereikšmingus duomenis, šiukšles. Kadangi įėjimo eilutės ilgis iki 1E6, ir tikrojo stack'o, maksimalus gylis turėtų siekti 1E6, tai mano stack'o-masyvo "plotis" nuo pradinės koordinatės turi į dvi puses siekti +-1E6 pozicijas, todėl masyvą teko kurti iš 2E6 elementų, ir suteikti pradinį stack'o dangčio indeksą - 1E6. Parašyta programa su užduotim susidorojo.

*****
Uždaviniuose, kur reikia daug skaičiavimų, priskyrimų, rikiavimų atlikti, Perl'u būna labai sunku tilpti į laiko limitus. Jis parašytas apdoroti eilutėms ir yra tragiškas artimetikai. Man tas nepatinka. Suprantu, jeigu jis atliktų operacijas tik kelis arba dešimt kartų lėčiau, bet jeigu tai trunka keliasdešimt - šimtus kartų, tai jau labai ne kas.
Žinoma, ieškojimas artimetikos galimybių Perl'e, būtų tas pats kaip kad vienam forume perskaičiau, ieškoti kaip su benzo-pjūklu nukirsti ir sukapoti medį.

Nusivyliau Perl'o netikslumu, netgi naudojant bignum'ą. Štai vieno uždavinio nepavyko įveikti su labai ilgo skaičiaus testu: http://codeforces.com/contest/219/submission/5491687

Patiko su Perl'u, neefektyviai, bet atrodo, teisingai, išspręsti nemažą kiekį eilutinių uždavinių, šis - klasikinis.
Nors vieno tokio, taipogi klasikinio, skambančio labai paprastai, eilutinio, - nepavyko niekaip, įdėjus daug pastangų.

*****
Dar kol kas man neteko niekam kitam nulaužti programos kontesto metu, bet norėčiau. Keletą kart mėginau spėliot, bet tik praradau taškus.