Šį mėnesį dalelę laiko praleidau skaitinėdamas perldoc.perl.org . Tekstas jame sunkus, ir patys dalykai vietomis sunkiai įkandami, tačiau dalį įsisavinu į atmintį. Kartais mėginu minimaliai pasirašyti - taip geriau įsimena. Pasimokiau hash'ų pradmenis ir išsprendžiau kelis Codeforces uždavinukus su hash'ais. Dar pasiskaičiau apie Perl operatorius (perlop), kintamuosius (perlvar). Dar pamėginau pasirašyti elementarų "dvimatį masyvą", kuris Perl'e gaunamas tik per nuorodų sukūrimą. Taigi - pasimokiau kažko naujo.
Codeforces šį mėnesį sprendėsi prastai. Dariau klaidų, neapgalvojau visų atvejų. Kartą tik trumpam laikui prisijungiau į kontestą, ir kartą - mėginau rašyti mobiliuoju telefonu, kurį pasiskolinau iš draugo: buvo labai sunku rinkti kodo tekstą - daugiausia laiko tai ir užtruko.
Mėginimai crackint'i kitų dalyvių kodus - dažniau nesėkmingi.
2014 m. rugsėjo 2 d., antradienis
2014 m. rugpjūčio 5 d., antradienis
Codeforces 2014 birželis-liepa
Šiais dviem mėnesiais, pagrinde leidau su programavimu susijusį laiką Codeforces svetainėje, turnyrėliuose.
Būta nesėkmingų pasirodymų. Neretai iškeisdavau mėginimą spręsti sekančius uždavinius mėginimais nulaužti kambariokų programas. Kai kuriuose kontestuose iš mėginimų nulaužti gaudavau neigiamą taškų skaičių, nes buvo ganėtinai daugiau nesėkmingų bandymų.
Tarp lengviausių uždavinių pasitaiko eilutinių uždavinių. Juos iškart norisi spręsti Perl programavimo kalba.
Viename tokiame apsižioplinau.
Sąlyga buvo tokia: yra vardų sąrašas (iš mažųjų lot. raidžių), ir yra šablonas (iš mažųjų lot. raidžių arba taškiukų). Šablonas visada tinka tik vienam iš vardų. Reik išvesti vardą.
Kadangi šablonas nesiskyrė nuo Perl šablonų sintaksės, tai paėmiau ir tiesiog į paieškos regexp'ą įrašiau duotą šabloną, ir nusiuntęs sprendimą gavau OK. Tačiau nepraėjo finalinio testo: "......", nes jis tinka tik vienam vardui, o pagal Perl regexp'o paiešką, išmetė visus rezultatus, kur vardai buvo sudaryti iš 6 ar daugiau raidžių. Tereikėjo šablone įrašyti eilutės pradžios ir pabaigos inkarėlius (^ ir $)
Dar vienam konteste pasisekė tai, kad išsprendęs A uždavinį, ieškojau ir laužiau varžovų programas. Surinkau 4 teisingus hack'us (+400-0). Ir dar, kai išsprendžiau B uždavinį, ieškojau tenai klaidų, jaučiau, kad yra, bet buvo velniškai sunkūs kodai ir sunkus būtų buvęs testų galvojimas.
Kažkaip gavosi, kad nors turnyrėlis yra abiem divizionams (geri programuotojai, ir blogi programuotojai (aš)), tačiau tarp visų turnyrėlio dalyvių, surinkau daugiausiai hack-taškų. Tai labai pradžiugino.
Uždavinys buvo daugmaž toks: Akshat ir Malvika žaidžia žaidimą. Turi vertikalių ir horizontalių pagaliukų. Eina paeiliui. Pradeda Akshat. Vienu ėjimu reik pasiimti horizontalų ir vertikalų pagaliuką. Kai negali paimti bent kurio nors pagaliuko, pralaimi. Išvesti, kas laimės.
Neteisingi kodai, kuriuos laužiau:
Būta nesėkmingų pasirodymų. Neretai iškeisdavau mėginimą spręsti sekančius uždavinius mėginimais nulaužti kambariokų programas. Kai kuriuose kontestuose iš mėginimų nulaužti gaudavau neigiamą taškų skaičių, nes buvo ganėtinai daugiau nesėkmingų bandymų.
Tarp lengviausių uždavinių pasitaiko eilutinių uždavinių. Juos iškart norisi spręsti Perl programavimo kalba.
Viename tokiame apsižioplinau.
Sąlyga buvo tokia: yra vardų sąrašas (iš mažųjų lot. raidžių), ir yra šablonas (iš mažųjų lot. raidžių arba taškiukų). Šablonas visada tinka tik vienam iš vardų. Reik išvesti vardą.
Kadangi šablonas nesiskyrė nuo Perl šablonų sintaksės, tai paėmiau ir tiesiog į paieškos regexp'ą įrašiau duotą šabloną, ir nusiuntęs sprendimą gavau OK. Tačiau nepraėjo finalinio testo: "......", nes jis tinka tik vienam vardui, o pagal Perl regexp'o paiešką, išmetė visus rezultatus, kur vardai buvo sudaryti iš 6 ar daugiau raidžių. Tereikėjo šablone įrašyti eilutės pradžios ir pabaigos inkarėlius (^ ir $)
Dar vienam konteste pasisekė tai, kad išsprendęs A uždavinį, ieškojau ir laužiau varžovų programas. Surinkau 4 teisingus hack'us (+400-0). Ir dar, kai išsprendžiau B uždavinį, ieškojau tenai klaidų, jaučiau, kad yra, bet buvo velniškai sunkūs kodai ir sunkus būtų buvęs testų galvojimas.
Kažkaip gavosi, kad nors turnyrėlis yra abiem divizionams (geri programuotojai, ir blogi programuotojai (aš)), tačiau tarp visų turnyrėlio dalyvių, surinkau daugiausiai hack-taškų. Tai labai pradžiugino.
Uždavinys buvo daugmaž toks: Akshat ir Malvika žaidžia žaidimą. Turi vertikalių ir horizontalių pagaliukų. Eina paeiliui. Pradeda Akshat. Vienu ėjimu reik pasiimti horizontalų ir vertikalų pagaliuką. Kai negali paimti bent kurio nors pagaliuko, pralaimi. Išvesti, kas laimės.
Neteisingi kodai, kuriuos laužiau:
cin >> a >> b; if (a == 1 || b == 1){ cout << "Akshat"; return 0; } if (a % 2 == 0 || b % 2 == 0) cout << "Malvika"; else cout << "Akshat";
cin>>n>>m;
if (n==1 || m==1)
{cout<<"Akshat";return 0;}
if (n%2==0|| m%2==0)
cout<<"Malvika";
else
cout<<"Akshat";
scanf("%d%d",&n,&m);
if(((n & 1) && (m & 1)) || n == 1 || m == 1) printf("Akshat\n");
else printf("Malvika\n");
cin>>a>>b;
if(a*b%2==0&&a>1&&b>1)
cout<<"Malvika"<<endl;
else
cout<<"Akshat"<<endl;
Tereikėjo paimt mažesnį iš skaičių ir pažiūrėti ar lyginis, ar nelyginis.
Tiek šiam kartui.
2014 m. birželio 4 d., trečiadienis
Codeforces turnyrų sėkmės ir nesėkmės
Pastarųjų pusantro mėnesio dažniausiai su programinimu siejau savo gyvenimą dalyvaudamas turnyrėliuose.
Ir dar turėjau apie savaitę laiko užsiėmimą susijusį su duomenų bazėmis ir paieška jose klaidų, kurių neturėtų būti, ir jas reikėtų suradus mokėti pataisyti. Įdomu.
Taip pat kartą teko pasimokyti su žmogum, kuris ruošiasi informatikos egzaminui, pasimokyti C++ kalbos ir atlikti užduočių su struct(), kurio šiaip niekad nenaudodavau, o kitose kalbose irgi nenaudoju, nes neužsiimu dalykais, kur jų prireikia (struct'ų, record'ų).
Ketinu toliau įraše dalintis tik rezultatais ir mintim apie Codeforces.
Paskutinius kelis kartus dalyvaudamas turnyrėliuose šiek tiek nukritau reitinge. Tai buvo dėl įvairių priežasčių: 1) nuovargio, kurį turėjau vieną sprendimo dieną, 2) dėl laiko ribotumo, kai sprendžiau ne visą duotą laiką, 3) kai pasirinkau nulaužinėti kitų programas vietoj tolimesnio užduočių sprendimo.
Paskutiniuosiuose keliuose turnyrėliuose buvau kaip "siautėjantis nulaužinėtojas". Savo kambaryje dažniau būdavau su didžiausiu sėkmingu nulaužimų skaičiumi, ir neblogu bendru nulaužimų rezultatu.
Kadangi ieškoti klaidų svetimose programose yra velniškai įdomu, tai net išsprendęs kurį uždavinį, dažniau einu pasižiūrėti tiek kambario rezultatų, tiek lyderių rezultatų, ir stebiu ar dalyvių tarpe nėra sėkmingai nulaužinėjaučių. Nes jeigu jų būtų, tai reikštų kad yra kažkokia detalė, kuri nebūna aptinkama pretestų ir lieka nenulaužta.
OBUOLIAI
Vienas uždavinys (paprasčiausias, A) - apie obuolius, jame 5 kart sėkmingai laužiau, ir 5 - nesėkmingai (kai kambary dažniausiai ~30 aktyvių žmonių), viso sukaupiau +500-250 taškų.
Jo sąlyga tokia: duotas obuolių sveriančių arba 100 arba 200 g masyvas, reikia pasakyt, ar įmanoma masyvą padalint į du masyvus taip, kad juose esantys obuoliai svertų po vienodai.
Štai vieno iš dalyvių neteisingas kodas:
Čia pateiktas per daug paprastas sprendimas: tikrinama, ar visų obuolių suma dali iš dviejų šimtų, ir kad obuolių turi būti bent 2.
Deja programa nesusidoroja su tokiais testiniais atvejais, kuriuos sudaro nelyginis (n>1) obuolių, turinčių 200 g masę, skaičius, pvz. 200 200 200. Ji išveda atsakymą YES, o turi būti NO.
Tapati kito dalyvio klaida, kurią laužiau:
Kito dalyvio kode radau tokią neteisingą eilutę (paryškinu):
Čia dalyvis įvertina teisingais testus 200 100 100, 200 100 100 100 100 100 100, tačiau neįvertina teisingu 200 100 100 100 100, ir jo nepagauna sekanti eilutė, dėl to klaidingai išspausdinamas NO. Šią klaidą aptikti buvo sunkiau, ir testą sukurti taip pat.
Taip pat 5 kartus prašoviau lauždamas programas, dažnai tai būna neįsigilinus į programos kodą, nes nujaučiant, kad tenai kažkas netaip. Kartais pasiseka, kartais ne.
NAMŲ DARBAI
Kitame konteste pirmas uždavinys buvo toks:
Mokinukas sprendžia testą, jam pateikti 4 atsakymo variantai. Jeigu varianto ilgis yra bent dvigubai didesnis už likusius variantus, tai jis mokinukui patinka. Taip pat, jeigu varianto ilgis bent 2 kartus trumpesnis už kitus variantus, jis mokinukui patinka. Jeigu mokinukas turi vieną patinkantį variantą, tai pasirenka būtent jį, antraip pasirenka variantą C.
Išsprendžiau šį uždavinį, ir kiek laiko luktelėjęs užrakinau. Mano kambary nemačiau nė vieno laužimo. Nuėjau į bendrą statistiką, tenai irgi nebuvo laužančių, kiek pažiūrėjau. Praėjus valandai, pirmąjam (lyderių) puslapy pamačiau, kad du dalyviai turi po ~10 hack'ų, o likę neturi nė vieno.
Man kilo įtarimas, kaip taip gali būti? Ir iškart atsirado konspiracinė mintis: gal šie du dalyviai yra kambariuose, kur yra kokie nors feik akauntai, kuriuose specialiai daromos klaidos, kad būtų galima nulaužti.
Tačiau nuėjau dar kartą paskaityt sąlygos ir atidžiau skaitydamas, supratau, kad pats išsprendžiau neteisingai, ir jau nebegalėsiu pasitaisyt, nes užrakinau užduotį. O neteisingumas tame, kad mano kodas blogai apdoroja tokį testą, kur mokinukui patinka du skirtingi atsakymai (pvz. A ir D), nes tuomet jis pasirenka atsakymą C, o ne pirmą pasitaikiusį patinkantį variantą.
Klaidingas mano kodas:
Pasirodo, analogiški buvo ir kitų dalyvių daug kodų.
Tiesiog susirašiau daugmaž tokį testą:
A.a B.aa C.aa. D.aaaa, ir ėmiau mėgint laužti daugumą kambariokų programas. Pirmi trys bandymai sėkmingi, dėl to atsirado mintis, kad jeigu delsiu ir nelaužysiu toliau, tai kažkas kambary gali atsirast ir pradėt taipogi laužti bei pasisavinti potencialius mano taškus. Dėl to, kodus, kuriuose mačiau klaidą - laužiau, o kurie buvo nesuprantami - atsidėdavau, ir tik kartais lauždavau. Kartais jie būdavo teisingi, ir prarasdavau taškus. Tik kai liko nedaug nelaužtų dalyvių, kurių tarpe stipresni, jų programas skaičiau atidžiau ir ieškojau pagrindo mėginimui laužti, o supratęs, kad jie supragramavę teisingai, veltui nebelauždavau.
Iš viso gavosi, kad mėginau 27 kartus (!!), iš kurių 16 sėkmingų, ir 11 nesėkmingų, arba +1600-550 taškų.
Antros užduoties, deja, niekaip nesugalvojau kaip išspręst, o mano pirmoji buvo neteisinga. Ją kontestui einant į pabaigą nulaužė kambario lyderis, tapdamas antruoju laužėjų mūsų kambaryje, ir atlikdamas pirmąjį istorinį manęs nulaužimą Codeforces.
Gavosi, kad neturėdamas nė vieno išspręsto uždavinio ir visą masę laužimų, pasikėliau reitingą. Pralinksmino.
Mane nulaužusio dalyvio kodo fragmentas:
Šioje sąlygoje jis patikrina, ar mokinukui patinka lygiai vienas atsakymas ir taip nepadaro klaidos.
Kito dalyvio klaida (analogiška mano klaidai):
DAR 2 UŽDAVINIAI
Paskutiniam dalyvautam konteste teko išspręst 2 uždavinius. Pirmą išsprendęs, persitikrinau ir užsirakinau. Tada ėmiau ieškoti klaidų kituose, bet užėmė nemažai laiko, ir vienintelė klaida, kurią aptikau dviejose vietose, tai > panaudojimas vietoje >=. Šiems atvejams pritaikiau testą ir gavau 200 taškų.
Tačiau antras uždavinys, pasirodo, buvo ir nesunkus, ir su galimybe laužt, nes daug kas laužė. Pasirodo, kad uždaviny duoti skaičiai iki 1e+5, o atsakyme atlikus visus sumavimus gali gautis skaičius iki 1e+15, kuris išeina iš už longint'o ribų. Tie, kas naudojo juos, buvo laužiami.
Išsprendžiau uždavinį su Perl'u. Tačiau rodė 170 ms, ir pamaniau, kad ant stipresnio testo nulūš, be to pamėginus išvesti su Perlu skaičiu su 15 nulių, jis išveda 1e+15, tokia išraiška būtų klaida. O su "use bignum" programa time-limit'ina, dėl ko nusprendžiau perrašyti žemesne kalba. Su Pascal'iu neperrašiau, nes reikėjo skaičių sorto. Kažkodėl baidausi rašyti sortą pats, tai pasirinkau C++0x, ir jame suprogramavau ir sėkmingai nusiunčiau. Tada užrakinau. Ir ieškojau klaidų.
Pavyko surasti vieną: dalyvis vietoje tiesinio sudėtingumo naudojo kvadratinį šimtui tūkstančių duomenų apdoroti. tam, kad nulaužčiau turėjau parašyti testą, kurį sudarytų du skaičiai pirmoje eilutėje (100000 ir 100000), ir šimtas tūkstančių skaičių "100000" - antroje. Pamėginau pasirašyti 10, tada tekstą kopijavau, ir klonavau vėl dešimt kartų, daug rankų darbo... kas buvo nepatogu, dėl ko nustojau. Tada pirmą kart nusprendžiau pamėgint pasinaudot testo sukūrimu programa, nes Codeforces leidžia jam nusiųsti programos generuojančios testą kodą, ir po kelių bandymų nusiųsti teisingą testą generuojančią (Perl kalba) pavyko. Džiaugiausi, kad nulaužiau.
Atrodė taip:
Dar trys bandymai laužti buvo nesėkmingi. Viso +300-150.
Du kartus mėginau nulaužti Pascal'iu rašytą programą, kuriame parašytas sort'as su rekursija. Man pasivaideno, kad jis galėtų būti lėtas, tai panaudojau du šūvius (pirmą neprotingai). Kai baigėsi kontestas, pasirodė, kad ta programa visgi mirė ant sisteminių testų, ir būtent ant time-limit'o, kurio ir aš toje programoje ieškojau kaip silpnybės... bet deja neradau.
Tikiuos, ateity pavyks ir geriau spręsti ir geriau laužti.
Ir dar turėjau apie savaitę laiko užsiėmimą susijusį su duomenų bazėmis ir paieška jose klaidų, kurių neturėtų būti, ir jas reikėtų suradus mokėti pataisyti. Įdomu.
Taip pat kartą teko pasimokyti su žmogum, kuris ruošiasi informatikos egzaminui, pasimokyti C++ kalbos ir atlikti užduočių su struct(), kurio šiaip niekad nenaudodavau, o kitose kalbose irgi nenaudoju, nes neužsiimu dalykais, kur jų prireikia (struct'ų, record'ų).
Ketinu toliau įraše dalintis tik rezultatais ir mintim apie Codeforces.
Paskutinius kelis kartus dalyvaudamas turnyrėliuose šiek tiek nukritau reitinge. Tai buvo dėl įvairių priežasčių: 1) nuovargio, kurį turėjau vieną sprendimo dieną, 2) dėl laiko ribotumo, kai sprendžiau ne visą duotą laiką, 3) kai pasirinkau nulaužinėti kitų programas vietoj tolimesnio užduočių sprendimo.
Paskutiniuosiuose keliuose turnyrėliuose buvau kaip "siautėjantis nulaužinėtojas". Savo kambaryje dažniau būdavau su didžiausiu sėkmingu nulaužimų skaičiumi, ir neblogu bendru nulaužimų rezultatu.
Kadangi ieškoti klaidų svetimose programose yra velniškai įdomu, tai net išsprendęs kurį uždavinį, dažniau einu pasižiūrėti tiek kambario rezultatų, tiek lyderių rezultatų, ir stebiu ar dalyvių tarpe nėra sėkmingai nulaužinėjaučių. Nes jeigu jų būtų, tai reikštų kad yra kažkokia detalė, kuri nebūna aptinkama pretestų ir lieka nenulaužta.
OBUOLIAI
Vienas uždavinys (paprasčiausias, A) - apie obuolius, jame 5 kart sėkmingai laužiau, ir 5 - nesėkmingai (kai kambary dažniausiai ~30 aktyvių žmonių), viso sukaupiau +500-250 taškų.
Jo sąlyga tokia: duotas obuolių sveriančių arba 100 arba 200 g masyvas, reikia pasakyt, ar įmanoma masyvą padalint į du masyvus taip, kad juose esantys obuoliai svertų po vienodai.
Štai vieno iš dalyvių neteisingas kodas:
int main()
{
int n,w[100],s=0,a=0,b=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>w[i];
s+=w[i];
}
a=s/100;
if ((a%2==0)&&(n>1))
{ cout<<"YES"; }
else
{ cout<<"NO"; }
return 0;
}
Čia pateiktas per daug paprastas sprendimas: tikrinama, ar visų obuolių suma dali iš dviejų šimtų, ir kad obuolių turi būti bent 2.
Deja programa nesusidoroja su tokiais testiniais atvejais, kuriuos sudaro nelyginis (n>1) obuolių, turinčių 200 g masę, skaičius, pvz. 200 200 200. Ji išveda atsakymą YES, o turi būti NO.
Tapati kito dalyvio klaida, kurią laužiau:
if((sum/2)%100==50) printf("NO\n"); else printf("YES\n");
Kito dalyvio kode radau tokią neteisingą eilutę (paryškinu):
int main() { int n, tmp, c200 = 0, c100 = 0; cin >> n; while(n--) { cin >> tmp; if(tmp == 200) c200++; else c100++; } if(c200 % 2 && c100 % 4 == 2) cout << "YES"; else if(c200 % 2 == 0 && c100 % 2 == 0) cout << "YES"; else cout << "NO"; return 0; }
Čia dalyvis įvertina teisingais testus 200 100 100, 200 100 100 100 100 100 100, tačiau neįvertina teisingu 200 100 100 100 100, ir jo nepagauna sekanti eilutė, dėl to klaidingai išspausdinamas NO. Šią klaidą aptikti buvo sunkiau, ir testą sukurti taip pat.
Taip pat 5 kartus prašoviau lauždamas programas, dažnai tai būna neįsigilinus į programos kodą, nes nujaučiant, kad tenai kažkas netaip. Kartais pasiseka, kartais ne.
NAMŲ DARBAI
Kitame konteste pirmas uždavinys buvo toks:
Mokinukas sprendžia testą, jam pateikti 4 atsakymo variantai. Jeigu varianto ilgis yra bent dvigubai didesnis už likusius variantus, tai jis mokinukui patinka. Taip pat, jeigu varianto ilgis bent 2 kartus trumpesnis už kitus variantus, jis mokinukui patinka. Jeigu mokinukas turi vieną patinkantį variantą, tai pasirenka būtent jį, antraip pasirenka variantą C.
Išsprendžiau šį uždavinį, ir kiek laiko luktelėjęs užrakinau. Mano kambary nemačiau nė vieno laužimo. Nuėjau į bendrą statistiką, tenai irgi nebuvo laužančių, kiek pažiūrėjau. Praėjus valandai, pirmąjam (lyderių) puslapy pamačiau, kad du dalyviai turi po ~10 hack'ų, o likę neturi nė vieno.
Man kilo įtarimas, kaip taip gali būti? Ir iškart atsirado konspiracinė mintis: gal šie du dalyviai yra kambariuose, kur yra kokie nors feik akauntai, kuriuose specialiai daromos klaidos, kad būtų galima nulaužti.
Tačiau nuėjau dar kartą paskaityt sąlygos ir atidžiau skaitydamas, supratau, kad pats išsprendžiau neteisingai, ir jau nebegalėsiu pasitaisyt, nes užrakinau užduotį. O neteisingumas tame, kad mano kodas blogai apdoroja tokį testą, kur mokinukui patinka du skirtingi atsakymai (pvz. A ir D), nes tuomet jis pasirenka atsakymą C, o ne pirmą pasitaikiusį patinkantį variantą.
Klaidingas mano kodas:
if ($A>=$B*2 and $A>=$C*2 and $A>=$D*2 or $B>=$A*2 and $C>=$A*2 and $D>=$A*2){print "A\n"; next} if ($B>=$A*2 and $B>=$C*2 and $B>=$D*2 or $A>=$B*2 and $C>=$B*2 and $D>=$B*2){print "B\n"; next} if ($C>=$A*2 and $C>=$B*2 and $C>=$D*2 or $A>=$C*2 and $B>=$C*2 and $D>=$C*2){print "C\n"; next} if ($D>=$A*2 and $D>=$B*2 and $D>=$C*2 or $A>=$D*2 and $B>=$D*2 and $C>=$D*2){print "D\n"; next} print "C\n";
Pasirodo, analogiški buvo ir kitų dalyvių daug kodų.
Tiesiog susirašiau daugmaž tokį testą:
A.a B.aa C.aa. D.aaaa, ir ėmiau mėgint laužti daugumą kambariokų programas. Pirmi trys bandymai sėkmingi, dėl to atsirado mintis, kad jeigu delsiu ir nelaužysiu toliau, tai kažkas kambary gali atsirast ir pradėt taipogi laužti bei pasisavinti potencialius mano taškus. Dėl to, kodus, kuriuose mačiau klaidą - laužiau, o kurie buvo nesuprantami - atsidėdavau, ir tik kartais lauždavau. Kartais jie būdavo teisingi, ir prarasdavau taškus. Tik kai liko nedaug nelaužtų dalyvių, kurių tarpe stipresni, jų programas skaičiau atidžiau ir ieškojau pagrindo mėginimui laužti, o supratęs, kad jie supragramavę teisingai, veltui nebelauždavau.
Iš viso gavosi, kad mėginau 27 kartus (!!), iš kurių 16 sėkmingų, ir 11 nesėkmingų, arba +1600-550 taškų.
Antros užduoties, deja, niekaip nesugalvojau kaip išspręst, o mano pirmoji buvo neteisinga. Ją kontestui einant į pabaigą nulaužė kambario lyderis, tapdamas antruoju laužėjų mūsų kambaryje, ir atlikdamas pirmąjį istorinį manęs nulaužimą Codeforces.
Gavosi, kad neturėdamas nė vieno išspręsto uždavinio ir visą masę laužimų, pasikėliau reitingą. Pralinksmino.
Mane nulaužusio dalyvio kodo fragmentas:
if (goodCount==1) { int curr=0; while (!isGood[curr]) curr++; putchar('A'+curr); } else { putchar('C'); }
Šioje sąlygoje jis patikrina, ar mokinukui patinka lygiai vienas atsakymas ir taip nepadaro klaidos.
Kito dalyvio klaida (analogiška mano klaidai):
if((a1>=2*a2&&a1>=2*a3&&a1>=2*a4)||(a1*2<=a2&&a1*2<=a3&&a1*2<=a4)) { printf("A\n"); } else if((a2>=2*a1&&a2>=2*a3&&a2>=2*a4)||(a2*2<=a1&&a2*2<=a3&&a2*2<=a4)) { printf("B\n"); } else if((a3>=2*a2&&a3>=2*a1&&a3>=2*a4)||(a3*2<=a2&&a3*2<=a1&&a3*2<=a4)) printf("C\n"); else if((a4>=2*a2&&a4>=2*a3&&a4>=2*a1)||(a4*2<=a2&&a4*2<=a3&&a4*2<=a1)) printf("D\n"); else printf("C\n");
DAR 2 UŽDAVINIAI
Paskutiniam dalyvautam konteste teko išspręst 2 uždavinius. Pirmą išsprendęs, persitikrinau ir užsirakinau. Tada ėmiau ieškoti klaidų kituose, bet užėmė nemažai laiko, ir vienintelė klaida, kurią aptikau dviejose vietose, tai > panaudojimas vietoje >=. Šiems atvejams pritaikiau testą ir gavau 200 taškų.
Tačiau antras uždavinys, pasirodo, buvo ir nesunkus, ir su galimybe laužt, nes daug kas laužė. Pasirodo, kad uždaviny duoti skaičiai iki 1e+5, o atsakyme atlikus visus sumavimus gali gautis skaičius iki 1e+15, kuris išeina iš už longint'o ribų. Tie, kas naudojo juos, buvo laužiami.
Išsprendžiau uždavinį su Perl'u. Tačiau rodė 170 ms, ir pamaniau, kad ant stipresnio testo nulūš, be to pamėginus išvesti su Perlu skaičiu su 15 nulių, jis išveda 1e+15, tokia išraiška būtų klaida. O su "use bignum" programa time-limit'ina, dėl ko nusprendžiau perrašyti žemesne kalba. Su Pascal'iu neperrašiau, nes reikėjo skaičių sorto. Kažkodėl baidausi rašyti sortą pats, tai pasirinkau C++0x, ir jame suprogramavau ir sėkmingai nusiunčiau. Tada užrakinau. Ir ieškojau klaidų.
Pavyko surasti vieną: dalyvis vietoje tiesinio sudėtingumo naudojo kvadratinį šimtui tūkstančių duomenų apdoroti. tam, kad nulaužčiau turėjau parašyti testą, kurį sudarytų du skaičiai pirmoje eilutėje (100000 ir 100000), ir šimtas tūkstančių skaičių "100000" - antroje. Pamėginau pasirašyti 10, tada tekstą kopijavau, ir klonavau vėl dešimt kartų, daug rankų darbo... kas buvo nepatogu, dėl ko nustojau. Tada pirmą kart nusprendžiau pamėgint pasinaudot testo sukūrimu programa, nes Codeforces leidžia jam nusiųsti programos generuojančios testą kodą, ir po kelių bandymų nusiųsti teisingą testą generuojančią (Perl kalba) pavyko. Džiaugiausi, kad nulaužiau.
Atrodė taip:
**********************************
*** Взлом использует генератор ***
**********************************
** Аргументы командной строки **
нет аргументов
** Сгенерированный тест **
100000 100000
100000 100000 100000 100000...
** Исходный код генератора **
print "100000 100000\n100000";
print (" 100000"x 99999);
print "\n";
Dar trys bandymai laužti buvo nesėkmingi. Viso +300-150.
Du kartus mėginau nulaužti Pascal'iu rašytą programą, kuriame parašytas sort'as su rekursija. Man pasivaideno, kad jis galėtų būti lėtas, tai panaudojau du šūvius (pirmą neprotingai). Kai baigėsi kontestas, pasirodė, kad ta programa visgi mirė ant sisteminių testų, ir būtent ant time-limit'o, kurio ir aš toje programoje ieškojau kaip silpnybės... bet deja neradau.
Tikiuos, ateity pavyks ir geriau spręsti ir geriau laužti.
2014 m. balandžio 20 d., sekmadienis
2014 balandžio I-oji pusė
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.
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. 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.
Užsisakykite:
Pranešimai (Atom)