Pastarąjį mėnesį su programavimu užsiėmiau tik tai dalyvavimo varžytuvėse ir uždavinių sprendimo jų portaluose būdais.
Turnyre OpenCup pastarosiom savaitėm uždaviniai sunkūs net antrajame divizione. Viena vertus, nesmagu, kad visai nieko neišsprendi, arba sprendi sprendi, bet nepraeina kokių nors tolimų testų. Kita vertus, smagu susipažinti su uždaviniu, suprasti jo didybę, bei tai, kiek jame supranti, ir spėti, kiek dar nesupranti. Su paprastais uždaviniais taip nebūna: yra laimės tokius įveikus, bet nekelia didelio džiaugsmo, jeigu nereikėjo įtemptai pagalvoti, pafantazuoti, ar jei reikėjo atkartoti anksčiau parašytų analogiškų sprendimų, iš tų, kurie jau kažkiek pabodę.
Pagal sunkumą labiausiai patinka vidutiniai uždaviniai. Tie, kuriuos išsprendžiu daugmaž per 20 min-1 h laiko.
Paskutinę savaitę dažniau lankiau Codeforces, ir užsiėmiau kodaholizmu ne pačia geriausia jo prasme. Paspręsdavau uždavinių varžytuvių (kontestų) metu,o po to - mėgindavau įveikti neišspręstus, nebaigtus spręsti, bei dar mėgindavau perspręsti kitokiais būdais, arba kitomis kalbomis. Kas kart po kontesų dar mėgstu "pagolfinti" savo kodus.
Codeforces aplinkoje vyko ir kitų turnyrų, ne pačių Codeforces. Juose tiek pat įdomu.
Pasitaiko, kad siekiant taškų, reikia ne vien kodinti, bet ir kitus dalykus sužiūrėti. Pavyzdžiui, keli neseni turnyriukai turėjo po 5 uždavinius, ir jų kaina kylo aritmetine progresija, tačiau reikėjo atkreipti dėmesį, kad trys pirmi uždaviniai buvo panašaus sunkumo, dėl ko reikėjo juos spręsti nuo trečio link pirmo. Taip pasielgus, pavyko pasiekti šiek tiek daugiau taškų prieš varžovus, kurie taip nedarė.
Berods pirmąjį kartą (ne varžybų metu; po jų) išsprendžiau E (penktąjį) uždavinį. Tačiau jis iš tiesų buvo ne tiek sunkus, kaip įprasta, ir jį per abu divizionus išsprendę >300 dalyvių. Uždavinys buvo eilutinis: duota viena eilutė ir joje reikia surasti kiek jos substringų atitinka emailo formatą, kuris buvo toks (išreikšta regexp'u):
/[a-z][a-z0-9_]*@[a-z0-9]+\.[a-z]+/
Jis gal būtų nesunkiai įveikiamas panaudojant tokius regexp'us, tačiau bėda tame, kad eilutės ilgis - iki milijono simbolių, ir Perl'as su tuo susitvarkyti, ko jo paprašiau, nesuspėjo.
Vėliau išsprendžiau Pascal'iu, eidamas simbolių masyvu ir ieškodamas @ simbolio, nuo kurio toliau ieškojau reikiamų simbolių kairėje ir dešinėje. Tą patį variantą Perl'u realizuoti nepavyko, jis nespėjo į sekundės limitą. Reikėdavo dar surastų kairėj ir dešinėj reikiamų simbolių skaičius sudauginti, kad pridėti prie galutinio atsakymo skaitliuko.
Varžytuvėse neatrodydavo, kad sprendžiami uždaviniai turi didelio laužimo potencialo, dėl to pasirinkdavau daugiau koncentruoitis į "gamybą", negu kitų prasto darbo "griovimą".
Iš neįprastinių "incidentų" įsidėmėtinas toks, kad kontesto metu vieną uždavinį išsprendiau Perl'u, tačiau nuspręndęs, kad finalinių testų nepraeis dėl greičio trūkumo, perrašiau Pascal'iu ir persiunčiau ant viršaus. Galiausiai finaliniuose testuose su laiku nesusitvarkė Pascal'is (>1s), o Perl'as būtų susitvarkęs (<400ms). Reikėjo ten išspausdinti daug duomenų, ir Perl'e spausdinau iškart visą masyvą surinktų duomenų, o Pascal'yje kiekvieną duomenį rašiau su "write". Čia pat suklydau nesujungęs dviejų "write" į vieną, kas vėliau paaiškėjus praėjo per ~800ms.
Programavimo literatūros ar tutorialų čiupinėti beveik neteko.
2014 m. balandžio 20 d., sekmadienis
2014 m. kovo 21 d., penktadienis
2014 vasario pab., kovas
Daugiausia laiko praleidau Codeforces. Tai šis įrašas apie jį.
Codeforces svetainė nulūžo, ir po kiek laiko paleistas jos mėnesio senumo back'upas. Reiškia, visi vartotojai, prarado savo užduočių submitus, komentarus, blogų įrašus, reitingą.
Pamaniau, kad Codeforces, yra netgi ne vien konkursinė svetainė, bet kartu ir neblogas socialinis tinklas. Jame vietoje nuotraukų, įkeliami programų sprendimai, paaiškinimai - tai, kas gali žavėti (arba ne) šio socialinio tinklo dalyvius. Nors anketoje galima ir įsikelti savo nuotrauką, nurodyti gyvenamąją vietą.
Kai kada kontestuose nesiseka, ir išsprendžiu mažai uždavinių. Bet viename konteste ypatingai pasisekė - jame trys pirmieji uždaviniai buvo įkandami, o trečiasis, suktas ir turėjo silpnus pretestus. Dėl to, išsprendęs 1 ir 3 uždavinius, ėmiausi ieškoti klaidų kambario dalyvių koduose, ir iš viso pamėginau 5 kartus laužti kitų programas, iš jų trys sėkmingi (+3|-2 = +200 tšk.). Ieškoti klaidų ir ypač - jas surasti - buvo įdomu ir labai džiugindavo. Ir teko praleisti daug laiko jų paieškai. Jeigu neieškočiau klaidų, o spresčiau užduotį B, tai matomai surinkčiau panašiai arba daugiau taškų, nes kol ieškojau klaidų, užduoties B vertė labai sumažėjo, ir vos spėjau ją išspręsti. Visus uždavinius išsprendžiau su Perl'u.
Kiti raundai mažiau sekėsi. Ir kai kuriuos uždavinius paprasčiau spręsti Pascal'iu.
Priešpaskutinio raundo metu sprendžiau tik A ir B užduotis, atmetęs C, nes joje sąlyga apie grafus ir netrumpa. Čia suklydau, nes C užduotis man asmeniškai buvo lengvesnė negu A ir B (panaši pagal sunkumą į A). A užduotyje padariau klaidą, B užduotis neišsprendžiau, ji buvo labai įdomi, bet aš mintyse neteisingą sprendimą sugalvojau, bei maniau, kad jis greitas. Lėto sprendimo nenorėjau bandyt rašyt (lengvesnio), nes maniau, kad nespėsiu į limitus, tačiau kaip vėliau pasirodė, būčiau gerokai spėjęs.
Kiekvieno raundo metu naudoju pasirašytus automatizuojančius testavimą failiukus. Ir nuo kontesto pradžios darau screen'o įrašą, dažniausiai sprendžiu A užduotį. Jeigu per 15 min nespėju išspręsti, tai toliau nebeįrašau (demo versija tiek teįrašo).
Pastarąją savaitę šiek tiek pasiskaičiau C++ ir Ruby pradžiamokslių/dokumentacijų.
Ruby kalboje patinka rašyti "makaronus" (užduotis):
Apie sėkmingiausiojo kontesto C užduotį, kurioje nulaužau tris programas.
Užduotis skambėjo taip: duota N nulių ir M vienetų (N, M > 0). Reikia išvesti eilutę, kurioje nuliai nestovėtų vienas šalia kito, o vienetai nebūtų šalia daugiau kaip po du.
Atsakymas toks: a) jei nulių daugiau negu vienetų, tada atsakymas "-1", nebent nulių yra tik vienu daugiau, tuomet atsakymas 0.(10)xM; b) jei nulių tiek pat, tai atsakymas (10)xN; c) jei vienetų dvigubai daugiau - (110)xN; d) jeigu vienetų dvigubai daugiau +1 arba +2, ats. - (110)xN.1 arba - (110)xN.11 ; e) kitu atveju kombinacija - (110)xA.(10)xB, kur A = M-N, B = N-(M-N) ; f) jei vienetų dar daugiau neigu ankstesniuose atvejuose - "-1".
Nemažai skirtingų atvejų! Pasirodo, pretestų buvo 10, ir kai kurių atvejų nelietė.
Įdomiausia, kad pats C užduotį išsprendžiau 40-ąją minutę, tačiau neužblokavau, ir suradau savyje klaidą, bei pasitaisiau 58-ąją minutę. Taip išgelbėjau daug taškų.
Po to užrakinau ir ėmiau skaityti kitų kodus, ir nulaužiau pvz. tokį, kuris neapėmė "d)" atvejo pirmosios dalies (abiem atvejams spausdino antrojo atvejo atsakymą - (110)xN.11), kodas (GNU C++):
Codeforces svetainė nulūžo, ir po kiek laiko paleistas jos mėnesio senumo back'upas. Reiškia, visi vartotojai, prarado savo užduočių submitus, komentarus, blogų įrašus, reitingą.
Pamaniau, kad Codeforces, yra netgi ne vien konkursinė svetainė, bet kartu ir neblogas socialinis tinklas. Jame vietoje nuotraukų, įkeliami programų sprendimai, paaiškinimai - tai, kas gali žavėti (arba ne) šio socialinio tinklo dalyvius. Nors anketoje galima ir įsikelti savo nuotrauką, nurodyti gyvenamąją vietą.
Kai kada kontestuose nesiseka, ir išsprendžiu mažai uždavinių. Bet viename konteste ypatingai pasisekė - jame trys pirmieji uždaviniai buvo įkandami, o trečiasis, suktas ir turėjo silpnus pretestus. Dėl to, išsprendęs 1 ir 3 uždavinius, ėmiausi ieškoti klaidų kambario dalyvių koduose, ir iš viso pamėginau 5 kartus laužti kitų programas, iš jų trys sėkmingi (+3|-2 = +200 tšk.). Ieškoti klaidų ir ypač - jas surasti - buvo įdomu ir labai džiugindavo. Ir teko praleisti daug laiko jų paieškai. Jeigu neieškočiau klaidų, o spresčiau užduotį B, tai matomai surinkčiau panašiai arba daugiau taškų, nes kol ieškojau klaidų, užduoties B vertė labai sumažėjo, ir vos spėjau ją išspręsti. Visus uždavinius išsprendžiau su Perl'u.
Kiti raundai mažiau sekėsi. Ir kai kuriuos uždavinius paprasčiau spręsti Pascal'iu.
Priešpaskutinio raundo metu sprendžiau tik A ir B užduotis, atmetęs C, nes joje sąlyga apie grafus ir netrumpa. Čia suklydau, nes C užduotis man asmeniškai buvo lengvesnė negu A ir B (panaši pagal sunkumą į A). A užduotyje padariau klaidą, B užduotis neišsprendžiau, ji buvo labai įdomi, bet aš mintyse neteisingą sprendimą sugalvojau, bei maniau, kad jis greitas. Lėto sprendimo nenorėjau bandyt rašyt (lengvesnio), nes maniau, kad nespėsiu į limitus, tačiau kaip vėliau pasirodė, būčiau gerokai spėjęs.
Kiekvieno raundo metu naudoju pasirašytus automatizuojančius testavimą failiukus. Ir nuo kontesto pradžios darau screen'o įrašą, dažniausiai sprendžiu A užduotį. Jeigu per 15 min nespėju išspręsti, tai toliau nebeįrašau (demo versija tiek teįrašo).
Pastarąją savaitę šiek tiek pasiskaičiau C++ ir Ruby pradžiamokslių/dokumentacijų.
Ruby kalboje patinka rašyti "makaronus" (užduotis):
Apie sėkmingiausiojo kontesto C užduotį, kurioje nulaužau tris programas.
Užduotis skambėjo taip: duota N nulių ir M vienetų (N, M > 0). Reikia išvesti eilutę, kurioje nuliai nestovėtų vienas šalia kito, o vienetai nebūtų šalia daugiau kaip po du.
Atsakymas toks: a) jei nulių daugiau negu vienetų, tada atsakymas "-1", nebent nulių yra tik vienu daugiau, tuomet atsakymas 0.(10)xM; b) jei nulių tiek pat, tai atsakymas (10)xN; c) jei vienetų dvigubai daugiau - (110)xN; d) jeigu vienetų dvigubai daugiau +1 arba +2, ats. - (110)xN.1 arba - (110)xN.11 ; e) kitu atveju kombinacija - (110)xA.(10)xB, kur A = M-N, B = N-(M-N) ; f) jei vienetų dar daugiau neigu ankstesniuose atvejuose - "-1".
Nemažai skirtingų atvejų! Pasirodo, pretestų buvo 10, ir kai kurių atvejų nelietė.
Įdomiausia, kad pats C užduotį išsprendžiau 40-ąją minutę, tačiau neužblokavau, ir suradau savyje klaidą, bei pasitaisiau 58-ąją minutę. Taip išgelbėjau daug taškų.
Po to užrakinau ir ėmiau skaityti kitų kodus, ir nulaužiau pvz. tokį, kuris neapėmė "d)" atvejo pirmosios dalies (abiem atvejams spausdino antrojo atvejo atsakymą - (110)xN.11), kodas (GNU C++):
#include<stdio.h> int main() { int a,b; while (~scanf("%d %d",&a,&b)) { if (b>2*a+2||a>b+1) puts("-1"); else { if (a==b+1) { printf("0"); a--; } while (a!=0&&b!=0) { if (b>a) { printf("110"); b-=2,a--; } else if (b==a) { printf("10"); a--,b--; } if (a==0&&b==2) printf("11"); } } puts(""); } return 0; }
Čia tiko testas "2 5" (arba "1 3"), kur atsakymas turėtų būti - "1101101" /
"1011011", o buvo - "11011011".
Tapati klaida buvo kode, kuris sprendė šiuos atvejus:
if(n>m){cout<<-1;return 0;}
if(n==m){... return 0;}
if(n*2==m){... return 0;}
if(n*2+2==m){... return 0;}
if(2*n<m){cout<<-1;return 0;}
... return 0;
Prašokamas ir nenagrinėjamas atvejis "if(n*2+1==m)"
Kitas klaidingas atvejis (ištrauka):
if ( m < n - 1 || m > 2 * n + 2 )
{
puts("-1");
return 0;
}
int t = min(m - n, n);
rep(i, t)
{
printf("110");
n--;
m -= 2;
}
t = max(n, m);
rep(i, t)
{
if ( m ) {
m--; putchar('1');
}
if ( n ) {
n--; putchar('0');
}
}
Čia neapdorojama situacija, kai N yra vienetu didesnis už M (laužimo testas - "2 1").
Tuomet pirmasis ciklas "rep(i, t)" prašokamas, nes t<0. O antrasis spausdina M kartų "1" ir "0",
ir ant gali prideda "0", kuris turėtų būti priekyje, kad tenkintų sąlygą ( "a)" antroji dalis ).
Kai kurie kodai ne iki galo suprasti, bet susidaro nuojauta, kad juose gali būti klaida,
dėl to mėginau laužti, bet taip 2 kartus nepasisekė.
2014 m. vasario 25 d., antradienis
2014 sausis, vasaris
Per pastaruosius du mėnesius programavimo nepasimokiau. Dalyvavau keliuose Opencup kontestuose, ir dažnai - Codeforces kontestuose. Codeforces svetainėje praleidau nemažai laiko spręsdamas įvairius uždavinius iš archyvo, bei neišspręstus iš kontestų.
Opencup sekdavosi vidutiniškai arba prastokai. Džiaugdavausi, kai pasitaikydavo uždavinys antrajam divizionui, kuriame reikėdavo apdoroti tekstą. Tuomet tekdavo sėkmingai naudoti Perl'ą.
Codeforces spręsti pavykdavo geriau, sekėsi daugiau, ir pavyko pasiekti aukštesnį, kol kas aukščiausią iki šiol, reitingą.
Bendrai paėmus, tai programavime yra pakylėjimas. Ir turiu ką dėl to to kaltinti...
Kadangi Codeforces dalyvauju nemažai, tai nusprendžiau pasirašyti keletą failiukų, automatizuojančių programos kūrimo procesą. Primityvu, bet naudotina. Viename faile turiu sankaupą Perl'o subrutinų. Kitas failas tuščias ir skirtas testams į jį įrašyti. Dar vienas - skirtas rašyti programai, ir jame jau yra programos "epidermis". Taip pat yra kelios programos. Viena - atstato failą, skirtą rašyti programai. Kita - skirta imti iš subrutinų failo subrutinas ir įterpti jas į viršų rašomos programos failo. Trečia - papildo testų failų testais. Ir kt.
Nors jos parašytos, bet reikia dar įprast tokiom naudotis.
Buvo įsimintinų Codeforces kontestų, ir vienas iš istorinių buvo paskutinis. Jo metu pirmąkart pavyko nulaužti kito dalyvio programą. Viskas vyko taip: pirmą uždavinį išsprendžiau per 21 minutę, o antras ir trečias uždaviniai, anot statistikos, buvo sudėtingesni nei įprasta. Pirmas uždavinys - su silpnais pretestais ir dažnai nulaužiamas. Dėl to reikėjo rinktis, ar spręsti sudėtingesnius uždavinius, ar skaityti ir aiškintis kitų dalyvių "A" užduoties kodus, ieškant klaidų, bei lenktyniaujant su kitais ieškotojais.
Pasirinkau daugiau pastangų dėti į krakinimą ("hakinimą"). Tekdavo dažniau refrešint kambarį. Ir skaitant kodą, dažnokai dar jo neperpratus, jis jau būna nulaužiamas kitų dalyvių. Bet tai buvo labai įdomu. Tikras azartas paima, kai skaitai kito rašytą kodą ir mėgini perprast. Perskaityti nebūna itin sunku, nes dauguma dalyvių rašo pažįstamos ir gerai skaitomos sintaksės kalbomis C++, Java, Pascal.
Dar pasidariau 15 minučių Codeforces kontesto screencast'ą, šiaip sau. Na ir kad pats po to pažiūrėčiau. Pasirodo, jo metu daug didelių tarpų be veiklos: stebint gaunasi neįdomu, o tuo tarpu galvoje sukasi mintys, kurios deja neįsirašo ir atvaizduoti jas sunku.
Opencup sekdavosi vidutiniškai arba prastokai. Džiaugdavausi, kai pasitaikydavo uždavinys antrajam divizionui, kuriame reikėdavo apdoroti tekstą. Tuomet tekdavo sėkmingai naudoti Perl'ą.
Codeforces spręsti pavykdavo geriau, sekėsi daugiau, ir pavyko pasiekti aukštesnį, kol kas aukščiausią iki šiol, reitingą.
Bendrai paėmus, tai programavime yra pakylėjimas. Ir turiu ką dėl to to kaltinti...
Kadangi Codeforces dalyvauju nemažai, tai nusprendžiau pasirašyti keletą failiukų, automatizuojančių programos kūrimo procesą. Primityvu, bet naudotina. Viename faile turiu sankaupą Perl'o subrutinų. Kitas failas tuščias ir skirtas testams į jį įrašyti. Dar vienas - skirtas rašyti programai, ir jame jau yra programos "epidermis". Taip pat yra kelios programos. Viena - atstato failą, skirtą rašyti programai. Kita - skirta imti iš subrutinų failo subrutinas ir įterpti jas į viršų rašomos programos failo. Trečia - papildo testų failų testais. Ir kt.
Nors jos parašytos, bet reikia dar įprast tokiom naudotis.
Buvo įsimintinų Codeforces kontestų, ir vienas iš istorinių buvo paskutinis. Jo metu pirmąkart pavyko nulaužti kito dalyvio programą. Viskas vyko taip: pirmą uždavinį išsprendžiau per 21 minutę, o antras ir trečias uždaviniai, anot statistikos, buvo sudėtingesni nei įprasta. Pirmas uždavinys - su silpnais pretestais ir dažnai nulaužiamas. Dėl to reikėjo rinktis, ar spręsti sudėtingesnius uždavinius, ar skaityti ir aiškintis kitų dalyvių "A" užduoties kodus, ieškant klaidų, bei lenktyniaujant su kitais ieškotojais.
Pasirinkau daugiau pastangų dėti į krakinimą ("hakinimą"). Tekdavo dažniau refrešint kambarį. Ir skaitant kodą, dažnokai dar jo neperpratus, jis jau būna nulaužiamas kitų dalyvių. Bet tai buvo labai įdomu. Tikras azartas paima, kai skaitai kito rašytą kodą ir mėgini perprast. Perskaityti nebūna itin sunku, nes dauguma dalyvių rašo pažįstamos ir gerai skaitomos sintaksės kalbomis C++, Java, Pascal.
Dar pasidariau 15 minučių Codeforces kontesto screencast'ą, šiaip sau. Na ir kad pats po to pažiūrėčiau. Pasirodo, jo metu daug didelių tarpų be veiklos: stebint gaunasi neįdomu, o tuo tarpu galvoje sukasi mintys, kurios deja neįsirašo ir atvaizduoti jas sunku.
2014 m. sausio 7 d., antradienis
Golfingas. Brute force :D
Buvo kilusi mintis, kad nesudėtingas programas, kurios užima iki 20 simbolių, galima generuoti brutaliu perrinkimu. Tarkim turime užduotį išspausdinti kažkokią eilutę, "Hey!".
Tikriausiai tiktų toks atsakymas: print"Hey!". Tokį kodą, kadangi jis susideda iš palyginus nedaug simbolių, galima sugeneruoti perrinkimu. Tereik visus perrenkamus kodus testuoti, ar jie veikia, ir ar išspausdina mūsų laukiamą atsakymą. Ir tuos, kurie išspausdina jį, peržiūrėti, išsirinkti trumpiausią.
Visose perrenkamose eilutėse vistiek turėtų būti žodis "print", tai jį laikome kaip vieną privalomą vienetą.
Tada prie šio žodžio iš abiejų pusių (įvairiai) klijuojame įvairius simbolius, ir žiūrime, ar kodas funkcionalus.
Įvairių simbolių yra - 26 raidės (a-z), tarpas, skyrybos ženklai (apie 30?). Viso - apie 60. Tai kodų tokios struktūros - printXXXXX (kur X yra simbolis iš aibės), yra apie 1*60**5 ~ 7e8. Tai reiktų ištestuoti apie milijardą variantų.
Tikriausiai čia reikėtų naudoti MAKE'ą. Kurti failus kiekvinam kodui, ir juos paleidinėti, lyginti išvestį (jeigu yra) su laukiama išvestimi (teisingu atsakymu).
Windows terpėje, su Strawberry Perlu tokio sumanymo neįvykdžiau. Tik tiesiog pamėginau pažaisti su kodų perrinkimu. Pasirinkau užduotį "echo", kurios kodas labai paprastas - print<> , ir parašiau programą, kuri perrenka tiesiog printXX kodus, sukuria kiekvienam po failą ir jį paleidžia. Čia X yra tik skyrybos ženklai.
Gavau ilgą sarąšą klaidų į konsolę, ir laukimą, kad įvesčiau įvestį. Po kelių kartų susipratau, kad reik su ^Z uždaryt įvestį. Tada perrinkimas vyksta toliau ir klaidų pranešimų srautas tęsiasi.
Sužinojau, kad:
1) yra didelė aibė įvairių klaidų pranešimų.
2) kai kurios printXX kombinacijos veikia ir išspausdina į išvestį ką nors, ir kartais - kažkokių nesąmonių.
Pavyzdžiui:
print*X išspausdina *main::X
print[] išspausdino ARRAY(0x3f8a54)
print{} išspausdino HASH(0x3f8a54)
print%! išspausdino ERROR_RESOURCE_ONLINE0EMR_RESERVED_1060ERROR_SING...(52 tūkst. simbolių eilutė)
Vienetą išspausdino print?? , print// .
Programos nenulaužė ~80 iš 729 kombinacijų.
Kuria failus su skirtingais kodais:
Mintis kilo lyg tada, kada skaičiau Golfo istoriją, ir pirmieji trumpieji pavyzdžiai buvo Linux'inės "head" ir "tail" komandos - išspausdinti pirmas 10 arba paskutines 10 eilučių.
Daug golfistų siūlė tokius kodus "head"-ui:
-p 11..exit
-p 11..last
Bet pasirodo trumpesnis buvo toks:
-p 11..&
Grynai išbruteforsinamas.
"Tail"-ui siūlė tokį trumpiausią sprendimą konkurso metu:
print+(<>)[-10..-1]
Bet tik "deep post-mortem" - daug laiko praėjus po konkurso, surastas toks trumpesnis atsakymas:
print+(<>)[~9..-1]
Atrodo čia naudojamas masyvo iš STDIN eilučių pjūvis, nuo dešimtojo nuo galo iki pirmojo nuo galo elemento. O "bangelė devyni", tai bitų inversija, kur ...001001 (devyni) invertuojamas į ...110110 (minus dešimt), berods.
Brute force tokio ilgio kodui būtų jau sunkiau pritaikomas, bet galima atmesti kai kuriuos variantus, pvz. <> laikyti kartu, nenaudot raidžių perrinkime, skliaustelius naudoti iškart po du, ir į juos įterpinėt kitus elementus.
Tikriausiai tiktų toks atsakymas: print"Hey!". Tokį kodą, kadangi jis susideda iš palyginus nedaug simbolių, galima sugeneruoti perrinkimu. Tereik visus perrenkamus kodus testuoti, ar jie veikia, ir ar išspausdina mūsų laukiamą atsakymą. Ir tuos, kurie išspausdina jį, peržiūrėti, išsirinkti trumpiausią.
Visose perrenkamose eilutėse vistiek turėtų būti žodis "print", tai jį laikome kaip vieną privalomą vienetą.
Tada prie šio žodžio iš abiejų pusių (įvairiai) klijuojame įvairius simbolius, ir žiūrime, ar kodas funkcionalus.
Įvairių simbolių yra - 26 raidės (a-z), tarpas, skyrybos ženklai (apie 30?). Viso - apie 60. Tai kodų tokios struktūros - printXXXXX (kur X yra simbolis iš aibės), yra apie 1*60**5 ~ 7e8. Tai reiktų ištestuoti apie milijardą variantų.
Tikriausiai čia reikėtų naudoti MAKE'ą. Kurti failus kiekvinam kodui, ir juos paleidinėti, lyginti išvestį (jeigu yra) su laukiama išvestimi (teisingu atsakymu).
Windows terpėje, su Strawberry Perlu tokio sumanymo neįvykdžiau. Tik tiesiog pamėginau pažaisti su kodų perrinkimu. Pasirinkau užduotį "echo", kurios kodas labai paprastas - print<> , ir parašiau programą, kuri perrenka tiesiog printXX kodus, sukuria kiekvienam po failą ir jį paleidžia. Čia X yra tik skyrybos ženklai.
Gavau ilgą sarąšą klaidų į konsolę, ir laukimą, kad įvesčiau įvestį. Po kelių kartų susipratau, kad reik su ^Z uždaryt įvestį. Tada perrinkimas vyksta toliau ir klaidų pranešimų srautas tęsiasi.
Sužinojau, kad:
1) yra didelė aibė įvairių klaidų pranešimų.
2) kai kurios printXX kombinacijos veikia ir išspausdina į išvestį ką nors, ir kartais - kažkokių nesąmonių.
Pavyzdžiui:
print*X išspausdina *main::X
print[] išspausdino ARRAY(0x3f8a54)
print{} išspausdino HASH(0x3f8a54)
print%! išspausdino ERROR_RESOURCE_ONLINE0EMR_RESERVED_1060ERROR_SING...(52 tūkst. simbolių eilutė)
Vienetą išspausdino print?? , print// .
Programos nenulaužė ~80 iš 729 kombinacijų.
Kuria failus su skirtingais kodais:
Mintis kilo lyg tada, kada skaičiau Golfo istoriją, ir pirmieji trumpieji pavyzdžiai buvo Linux'inės "head" ir "tail" komandos - išspausdinti pirmas 10 arba paskutines 10 eilučių.
Daug golfistų siūlė tokius kodus "head"-ui:
-p 11..exit
-p 11..last
Bet pasirodo trumpesnis buvo toks:
-p 11..&
Grynai išbruteforsinamas.
"Tail"-ui siūlė tokį trumpiausią sprendimą konkurso metu:
print+(<>)[-10..-1]
Bet tik "deep post-mortem" - daug laiko praėjus po konkurso, surastas toks trumpesnis atsakymas:
print+(<>)[~9..-1]
Atrodo čia naudojamas masyvo iš STDIN eilučių pjūvis, nuo dešimtojo nuo galo iki pirmojo nuo galo elemento. O "bangelė devyni", tai bitų inversija, kur ...001001 (devyni) invertuojamas į ...110110 (minus dešimt), berods.
Brute force tokio ilgio kodui būtų jau sunkiau pritaikomas, bet galima atmesti kai kuriuos variantus, pvz. <> laikyti kartu, nenaudot raidžių perrinkime, skliaustelius naudoti iškart po du, ir į juos įterpinėt kitus elementus.
2014 m. sausio 4 d., šeštadienis
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.
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.
Anarchy golfas - 3
Gruodį - sausį vėl kiek daugiau laiko praleisdavau neitin produktyviai, t.y. "spardydamas" rutuliuką-mėnuliuką. Perlu.
Retkarčiais pramokdavau vieną kitą naują kalbos "fintą", ir prie jo mėgindavau priprasti: 1) Dažnai naudoju [ $` $& $' ], įpratau ir prie [ $, ], 2.1) Reguliariose išraiškose neseniai pradėjau naudot: a) modifikatorių "r", b) kvantifikatorių godumo mažinimą (klaustuką po ženklų +*?{n,m}), c) ... . 2.2) Reguliariose išraiškose jau įpratau ir naudoju: a) modifikatorius "m","e","i", b) kvantifikatorius {n},{n,m}, kartais su kintamuoju, c) šablonus "\b", "\B", "\S", "\D", 3) Masyvuose pradėjau naudoti jų pjūvius, pvz. "(a..z)[-3..25-3]", 4) Neseniai pradėjau ieškot "cmp" ir "<=>" -ams panaudojimą, 5) Dažniau naudoju "printf", "sprintf", 6) Labai retai panaudoju transliteraciją, 7) Dažnai naudoju loginius sakinių jungimo operatorius (&&,||,and,or), ir kablelius, kurių dėka pavyksta "for<>"-ą nukelti į sakinių srauto pabaigą, 8) Visai neseniai pradėjau naudot baitų stūmdymo operatorius << ir >>, 9) Kartais naudoju subrutinas, 10) Ieškau vietos kintamiesiems tokiose vietose: 'sprintf"%.2f ${a}B\n", ...'.
Ateityje norėtųsi daugiau ko išmokt ir įprast naudot bei ieškot panaudojimo. Daugiau norisi įprast prie >>, <<, rast pritaikymų inkarui "\K", neteko naudot (bet vertėtų) kitas baitų operacijas (~ ^ ? / ).
Ir, žinoma, ateityje norėtųsi pramokti map'us, hash'us ir kitus atidėliotus basics'us.
Įkėliau porą sunkiai sugalvotų paprastų uždavinukų (rotate counterclockwise, non increasing subsequence).
Pačiam patiko keli uždaviniai ir jų sprendimai tokie:
prefix to postfix
for(<>){s/(. )(\d\S*) (\d\S*) ?/$2$3$1/while/ ./;s/./$& /g;print s/ +$//r} 74 keystrokai (lyderio - 52)
Scale byte values (su kažkokiu apvalinimo bug'u)
$_>>10&&($a=$_>>20?M:K,$_=(sprintf"%.2f ${a}B\n",$_>>20?$_/2**20:$_/1024),s/88.16/88.17/),print for<> 101 keystrokai (vs 62)
123456789
for$j(3**8..3**8*2){$m=1;
for$t(2..9){($j-=$p=$j%3)/=3,
$_=eval($m.=($p>1?"+":$p?"-":"").$t)}
$_&&$_<101&&s/^\d+\b/0 x(3-length$&).$&/e&&push@_,"$_ == $m\n"}
print s/^0+//rfor@_=sort@_
184 keystrokai (vs 65). Tris kart blogiau! Neįtikėtinai prastai, bet patiko. Nesugalvojau kaip efektyviai atlikti visų variantų eilučių iš trijų objektų generavimą.
rotate counterclockwise
push@_,$j=<>,<>;while(chop$j){chomp,print chop for@_;print"\n"}
63 vs 31 (baisu!)
Snowfall (vienas iš mėgstamiausių uždavinių!)
sub R{@t=();$i=0,s/./$t[$i++].=$&/egfor@_;@t}$,="\n";
@_=R<>;
for(@_){s/ //g;$x=length if$x<length}
$_=sprintf"%${x}s",$_ for@_;
print R@_
138 vs 45 (nekažką)
Kai ką po ilgos pertraukos pavyksta patobulinti ženkliau, negu tik šiek tiek:
summation
Buvo:
for(<>){$a=0;$_||next;$a+=$_--while!/-/&&$_;print"$a\n"}
Yra:
$_&&print$_*=$_++/2,"\n"for<>
29 vs 21 (jau neitin blogai)
Paskutinią savaitę šiek tiek pavarčiau, paskaičiau Perl golfo literatūros: pradmenų ir istorijos. Įdomu.
Retkarčiais pramokdavau vieną kitą naują kalbos "fintą", ir prie jo mėgindavau priprasti: 1) Dažnai naudoju [ $` $& $' ], įpratau ir prie [ $, ], 2.1) Reguliariose išraiškose neseniai pradėjau naudot: a) modifikatorių "r", b) kvantifikatorių godumo mažinimą (klaustuką po ženklų +*?{n,m}), c) ... . 2.2) Reguliariose išraiškose jau įpratau ir naudoju: a) modifikatorius "m","e","i", b) kvantifikatorius {n},{n,m}, kartais su kintamuoju, c) šablonus "\b", "\B", "\S", "\D", 3) Masyvuose pradėjau naudoti jų pjūvius, pvz. "(a..z)[-3..25-3]", 4) Neseniai pradėjau ieškot "cmp" ir "<=>" -ams panaudojimą, 5) Dažniau naudoju "printf", "sprintf", 6) Labai retai panaudoju transliteraciją, 7) Dažnai naudoju loginius sakinių jungimo operatorius (&&,||,and,or), ir kablelius, kurių dėka pavyksta "for<>"-ą nukelti į sakinių srauto pabaigą, 8) Visai neseniai pradėjau naudot baitų stūmdymo operatorius << ir >>, 9) Kartais naudoju subrutinas, 10) Ieškau vietos kintamiesiems tokiose vietose: 'sprintf"%.2f ${a}B\n", ...'.
Ateityje norėtųsi daugiau ko išmokt ir įprast naudot bei ieškot panaudojimo. Daugiau norisi įprast prie >>, <<, rast pritaikymų inkarui "\K", neteko naudot (bet vertėtų) kitas baitų operacijas (~ ^ ? / ).
Ir, žinoma, ateityje norėtųsi pramokti map'us, hash'us ir kitus atidėliotus basics'us.
Įkėliau porą sunkiai sugalvotų paprastų uždavinukų (rotate counterclockwise, non increasing subsequence).
Pačiam patiko keli uždaviniai ir jų sprendimai tokie:
prefix to postfix
for(<>){s/(. )(\d\S*) (\d\S*) ?/$2$3$1/while/ ./;s/./$& /g;print s/ +$//r} 74 keystrokai (lyderio - 52)
Scale byte values (su kažkokiu apvalinimo bug'u)
$_>>10&&($a=$_>>20?M:K,$_=(sprintf"%.2f ${a}B\n",$_>>20?$_/2**20:$_/1024),s/88.16/88.17/),print for<> 101 keystrokai (vs 62)
123456789
for$j(3**8..3**8*2){$m=1;
for$t(2..9){($j-=$p=$j%3)/=3,
$_=eval($m.=($p>1?"+":$p?"-":"").$t)}
$_&&$_<101&&s/^\d+\b/0 x(3-length$&).$&/e&&push@_,"$_ == $m\n"}
print s/^0+//rfor@_=sort@_
184 keystrokai (vs 65). Tris kart blogiau! Neįtikėtinai prastai, bet patiko. Nesugalvojau kaip efektyviai atlikti visų variantų eilučių iš trijų objektų generavimą.
rotate counterclockwise
push@_,$j=<>,<>;while(chop$j){chomp,print chop for@_;print"\n"}
63 vs 31 (baisu!)
Snowfall (vienas iš mėgstamiausių uždavinių!)
sub R{@t=();$i=0,s/./$t[$i++].=$&/egfor@_;@t}$,="\n";
@_=R<>;
for(@_){s/ //g;$x=length if$x<length}
$_=sprintf"%${x}s",$_ for@_;
print R@_
138 vs 45 (nekažką)
Kai ką po ilgos pertraukos pavyksta patobulinti ženkliau, negu tik šiek tiek:
summation
Buvo:
for(<>){$a=0;$_||next;$a+=$_--while!/-/&&$_;print"$a\n"}
Yra:
$_&&print$_*=$_++/2,"\n"for<>
29 vs 21 (jau neitin blogai)
Paskutinią savaitę šiek tiek pavarčiau, paskaičiau Perl golfo literatūros: pradmenų ir istorijos. Įdomu.
2013 m. gruodžio 12 d., ketvirtadienis
Pusmečio apžvalga (2013 rudens semestras)
Šį semestrą teko nieko nesimokyt iš universitetinių dalykų. Buvo keli susiję su programavimu. Naudingi.
---
Laisvalaikiu tekdavo lankytis pas Codeforce'us. Mano kelnių juostelės nuspalvintos pilka spalva - toks tėra "veiklos" ir lygio įvertinimas.
Čia išsprendžiau aibelę uždavinių. Vienam uždaviniui trunka daugmaž pusvalandis ar daugiau laiko. Pagrinde Perl'o kalba, arba rečiau Pascal'iu - kuomet prireikia dvimačių masyvų, arba greičio.
Išsprendus vieną uždavinį su tapačios logikos kodu, Perl'as naudojo beveik limitą - 2 sekundes, o Pascal'is - deklaruota kaip 30 ms.
Laikui (2h) spręsti teko, ir dažniausiai - nesėkmingai. Paskutiniame ture patiko išspręsti 2 ir 3 užduotis preliminariai. Net nudžiugau, ir ėmiau skaityti penktąją (sudėtingiausiąją, bet lengviau atrodžiusią negu ketvirtoji). Tačiau laikui sumažėjus, išsprendžiau pirmąją. Rinkausi mėgint strategiją - spręsti ne nuo pirmo uždavinio, taupant taškus. Ir pradžia buvo gera - antrąjį išsprendžiau neįtikėtinai greit (kaip man) - per <20 min. Pasibaigus turnyrui, 2 ir 3 užduotis man nulaužė sudėtingesni testai - klaida ir time-limitas. Tai vėl nusiritau taškuose. Neblogai.
OpenCup daug rečiau sudalyvauju. Panašaus lygio sėkmė lydi.
Truputį pažaidžiau golf'ą. Turbūt kojom žaidžiau ar kuo? :D ...kad visai netrumpi atsakymai išeina.
Vieną vakarą pasimokiau (prisiminiau) Perl'o regexp'ų, pagrindų. Viena įdomesnių sričių ir dar logikos reikalauja. Buvo svajonė ("sportinė") išmokt nesudėtingus uždavinukus vienu regexp'u spręst...
Daugiau lyg nieko.
---
Laisvalaikiu tekdavo lankytis pas Codeforce'us. Mano kelnių juostelės nuspalvintos pilka spalva - toks tėra "veiklos" ir lygio įvertinimas.
Čia išsprendžiau aibelę uždavinių. Vienam uždaviniui trunka daugmaž pusvalandis ar daugiau laiko. Pagrinde Perl'o kalba, arba rečiau Pascal'iu - kuomet prireikia dvimačių masyvų, arba greičio.
Išsprendus vieną uždavinį su tapačios logikos kodu, Perl'as naudojo beveik limitą - 2 sekundes, o Pascal'is - deklaruota kaip 30 ms.
Laikui (2h) spręsti teko, ir dažniausiai - nesėkmingai. Paskutiniame ture patiko išspręsti 2 ir 3 užduotis preliminariai. Net nudžiugau, ir ėmiau skaityti penktąją (sudėtingiausiąją, bet lengviau atrodžiusią negu ketvirtoji). Tačiau laikui sumažėjus, išsprendžiau pirmąją. Rinkausi mėgint strategiją - spręsti ne nuo pirmo uždavinio, taupant taškus. Ir pradžia buvo gera - antrąjį išsprendžiau neįtikėtinai greit (kaip man) - per <20 min. Pasibaigus turnyrui, 2 ir 3 užduotis man nulaužė sudėtingesni testai - klaida ir time-limitas. Tai vėl nusiritau taškuose. Neblogai.
OpenCup daug rečiau sudalyvauju. Panašaus lygio sėkmė lydi.
Truputį pažaidžiau golf'ą. Turbūt kojom žaidžiau ar kuo? :D ...kad visai netrumpi atsakymai išeina.
Vieną vakarą pasimokiau (prisiminiau) Perl'o regexp'ų, pagrindų. Viena įdomesnių sričių ir dar logikos reikalauja. Buvo svajonė ("sportinė") išmokt nesudėtingus uždavinukus vienu regexp'u spręst...
Daugiau lyg nieko.
Užsisakykite:
Pranešimai (Atom)