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ė.
Komentarų nėra:
Rašyti komentarą