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:

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.