Funkcinis programavimas?

Kol kas tik palengva įsisavimu funkcinio programavimo sąvoką.
Kiek suprantu, tai programavimas 1) be priskyrimo operatorių, 2) su visokiom anoniminėm f-cijom, lambdom, 3) rekursijom?
Jei reikėtų iš tešlos padaryti didelio raganosio formos sausainį, turint pradžioje tešlos gumulą, tai funkciškai programuojant, tas tešlos gumulas visaip tampomas (visas, ar tik jo dalis), bet visada lieka monolitinis, o programuojant struktūriškai tas gumulas plėšomas, iš jo formuojamos būsimo raganosio dalys, kurios kažkada - suklijuojamos.
Į funkcinį programavimą man panašu: 
* užklausos duomenų bazei;
* komandinės eilutės konvejeriai;

Patinka Ruby kalboje kad galima duomenį (ar jų paketą) keisti paeiliui iš kairės į dešinę parašytomis funkcijomis, primena konvejerio struktūrą. Pvz. gets().chomp.scan().gsub().... Patogu tai, kad duomuo po funkcijos panaudojimo dažniausiai nekeičiamas (nebent yra galimybė po funkcijos vardo prirašyti šauktuką), ko nėra Perl'e. Perl'e yra naujas regex'ų modifikatorius "r" - kaip tik nedestruktyvus - patogus keitimams, nekuriant nereikalingų kintamųjų.

Šiandien kažkiek valandų praleidau Project Euler svetainėje, mėgindamas spręsti matematinius uždavinius, o atsakymus išgauti Perl'u. Tai kai kurie uždavinių sprendimo priėjimas atrodo tinkamas spręsti funkciškai. Pvz. 42-ą užduotį sprendžiau taip:

$a{ $i += $_ } //= 1 for 1 .. 50;
print eval join '+', map { 0 + exists $a{ eval join '+', map /\w/ && -64+ ord $&, split/\B/ } } split /,/, <>

Čia buvau pasidaręs reikšmių hash'ą. O tada, visus nuskaitytus duomenis apdoroju funkcijomis paeiliui, nekurdamas kintamųjų, ir apdorojęs išvedu atsakymą. Neapsieičiau čia be "eval" funkcijos.

Panašiai uždavinys 30:

print eval join '+', map { $_ * ($_ == eval join '+', map $_ ** 5 , split // ) } 1 .. 1e6

Perl. Su laiku prisijaukinama naujų įrankių.

Begyvenant, vis paskaitant dokumentacijas ir vadovėlius apie Perl'ą, tenka susipažint su naujomis funkcijomis ir galimybėmis, (<+ pasibandyt +>), po to pritaikyt, ir galiausiai - prisijaukint ir naudoti kai papuola proga.

Išsivardinsiu tų funkcijų ir jų pažinties etapų apytikslias pradžias.

Prieš tai paminėsiu, kad kai ką pradėjau naudoti praktiškai iškart, po pirmųjų pažinčių su Perlu:
while/for, if (retai unless), valdantieji (and or && ||), <>, print, tr///, s///ig, $1..., \s\d\w, ^.*$, cho(m)p, sort, rand, length, push, pop, unshift, shift, join'', split//, open, close, ord, vėliau s|||igmse, vėliau (last next redo exit), reverse...

sub -- 2012 -- 2012? -- 2012?
references -- 2012, 2013, 2014 -- no -- no
2D array -- 2012?, 2014 rugpj -- 2014 rugpj -- 2014 ruduo
%hash -- 2012?, 2014 rugpj -- 2014-08-12 -- 2014 rugpj

, -- 2013 -- 2013 -- 2013
one-line for/while -- 2013? -- 2013? -- 2013?
scalar -- 2012 -- 2012 -- rarely
undef, defined -- 2014? -- 2014? -- yes
local -- 2014? -- 2014 -- rarely
our -- undef -- undef -- no
? : -- 2012? -- 2012 -- 2012
map -- 2014 lap -- 2014 gru -- undef
grep -- 2014 lap -- undef -- no
splice -- 2012? -- 2013? -- no
each -- 2012?, 2014 ruduo -- 2014-08-12 -- no
eval -- 2013? -- 2013? - rarely
pos -- 2014? -- 2014 ruduo -- 2014 ruduo
substr -- 2012 -- 2012 -- 2013?

$0, $! -- 2012? -- 2013? -- 2013?
$, -- undef -- 2013 -- 2014
$", $/, $\ -- undef -- 2014 ruduo? -- 2014 ruduo
@-, @+ -- 2014? -- 2014? -- 2014 ruduo
$&, $`, $' -- 2012 -- undef -- 2013

<=>/cmp -- 2013? -- 2014? -- 2014 ruduo?
\b, \B -- 2012 -- 2013? -- 2013?
\K -- 2014 spa -- 2015-01-09 -- no
\G -- 2013? -- 2014-12-16 -- no
{n}, {n,m} -- 2012 -- 2012? -- 2013?
/x -- 2012, 2014 rug -- 2014 lap -- 2014 lap
/e -- 2012 -- 2012? -- 2012?
/r -- 2013 gruo -- 2013 gruo -- 2013 gruo
(??{}), (?{}) -- 2014 spa -- 2014 spa -- no
lookaround -- 2014 rugs -- 2014 rugs -- 2014 rugs
possessive and lazy quantifiers -- 2012? -- 2013? -- 2013?

qr -- 2012?, 2014 spa -- 2014 lap -- 2014 lap
q, qq -- undef -- 2014 lap -- 2014 lap
qw -- undef -- 2013? -- 2014

pack -- undef -- undef -- no
unpack -- undef -- undef -- no
split " " -- 2012, 2014 lap -- 2014-12-01 -- undef
split " ", $_, N -- 2014 lap -- 2015-01-13 -- no
rindex -- 2012 -- 2014-12-16 -- undef
cho(m)p -- 2012 -- 2012 -- 2012
study -- 2014 spa -- undef -- no
printf -- 2012? -- 2013? -- 2013
sprintf -- 2013? -- 2013? -- 2013
<<heredoc -- 2014 -- 2014 ruduo -- rarely
__DATA__ -- 2014 ruduo -- 2014 ruduo -- 2014 ruduo
do {} while -- 2012? -- 2015-01-04 -- no
do {}; -- undef -- undef -- no
die, warn -- 2013? -- 2013? -- rarely
defined-or // -- undef -- undef -- 2014?
xor -- undef -- 2014 ruduo -- 2014 ruduo
a..z -- undef -- 2013? - 2013?
( )= -- 2013? -- 2013? -- 2014
scalar .. (flip-flop) -- 2014 lap -- 2014 lap -- no
shift: << >> -- 2013 -- 2013 -- 2013
binary (~, ^, &, |) -- undef -- undef -- no
uc, lc, ucfirst -- 2012? -- 2012? -- 2012?
LABEL -- 2012? -- undef -- 2014?
use POSIX (ceil, floor) -- undef -- undef -- rarely
use integer, bigint, bignum, bigrat -- undef -- undef -- yes

Nenaudoju naujųjų: smartmatch ~~, given-when.

2014 spalis-lapkritis

Dviejų mėnesių bėgyje, tiek kiek leido priežastys, pasiskaitydavau kažko naujo arba seno, ir paspręsdavau uždavinukų.

Skaitymas.
* Wikipedijoje skaitau atskirus straipsnelius programavimo tema, pažindindamasis (dažnai paviršutiniškai) su sąvokomis ir su programų veikimo mechanika. Labiausiai patiko "Optimizing compiler" ir iš jo atsišakojantys įvairių kompiliatoriaus daromų optimizacijų aprašymai. Iš jų labiau suprantami: dead-code elmination, constant folding, loop-invariant motion, strength reduction. Dar skaičiau: Index mapping (trivial hash f-tion), Look-up table (LUT), Minimalism (computing), Segmantation fault, Scripting language, Objective-C, Computer worms... kas papuola and minties.
* Mastering Regular Expressions - pdf'as, pagaliau perskaičiau, iš tiesų perskaičiau 7 iš 9 skyrių, nes >6 skyriai eina atskirai konkrečiãi kalbai, tai 7-ame skyriuje apie Perl'o regex'us. Knyga patiko. Skaityti užtruko ir buvo sunku. Tik galbūt reikėjo paieškot ir skaityt 3rd edition vietoj 2nd.
* Learning Perl - pdf'as, 6th (vėliausias) edition, perskaičiau daugumą skyrių, kelis permečiau akimis. Vienkartinio perskaitymo užteko visiems tiems puslapiams, kur aprašoma jau pažįstama medžiaga. O lėčiau tekdavo paskaityti nežinomus dalykus. Skyriai, į kuriuos mažiau gilinausi, ir/ar kurie man sunkesni, tai viskas apie Encoding'ą, Process management, darbas su failais ir direktorijomis, Perl modules (.pm). O 7, 8, 9 skyriai - greituoju skaitymu, nes apie reguliariasias išraiškas. Uždavinių knygoj neišsprendžiau.

[UPDATE] * Žiūrėjau Youtubėj video (57'), kurį vedė Larry Wall (Perl ir Perl 6 kalbų kūrėjas)). Vidijuje pasakoja jis apie naująją kalbą - Perl 6 (kuri iki šiol oficialiai neišleista), apie jos ideologinius ir konkrečius skirtumus nuo Perl kalbos (kitaip tariant nuo Perl 1..5 kalbos versijų, kurių kiekviena yra suderinama (compatible) su aukštesniąja iš bet kurių tos kalbos versija). Istoriškai gavosi, kad tiek įprastas Perl, tiek Perl 6 vystosi lygiagrečiai, ir nėra taip, kad Perl 6 yra skatintina::naudoti versija => geresnė už paskutiniąsias Perl versijas, t.y. Perl 5.20 su kapeikom. Perl 6 yra net ne atsišakojimas, o perrašyta naujai kalba(?), o jos autorius Larry Wall sako, tai yra ne kalba, o kalbos vienoje.
Man Perl 6 neteko naudotis, tačiau paklausyti šios paskaitos labai labai patiko. Be to buvo smagu paklausyti kalbos, kuria rašinėju, autoriaus kalbą!! Ir džiaugiuosi, kad nemažą dalį supratau apie ką kalbėjo, nes daug to, ką vartojo savo kalboje, perskaičiau Mastering Regular Expressions knygoje. [/U]


Programų rašymas.
* Turnyrėliai, uždavinukai.
Šiek tiek anarchy golf'o.
Kelis kart dalyvavau OpenCup'e. Sekėsi prastokai.
Kelis kart dalyvavau Codeforces. Sekėsi vidutiniškai arba kiek prasčiau.
* Pats sau.
Buvau kadaise nepriklausomai sugalvojęs paprastą klausimą: kaip implementuoti (parašyti) dvimačio fragmento paiešką dvimačiame masyve. Pvz. dvimačiame masyve yra 0- ir 1- ukai. Ar galima jame surasti (ir kiek) "pliusų" sudarytų iš 5 vienetukų. Kitaip tariant, pritempus prie reguliariųjų išraiškų, tai būtų dvimatės reguliarios išraiškos paieška(?).
Vieną dieną prisidėdau ir parašiau primityvią versiją, kurios paieškos greitis nedidelis. O veikimo principas toks: 1) paieškos paveikslėlis yra aprašytas keliomis eilutėmis reguliariųjų išraiškų formatu, tada šios eilutės yra sudedamos į masyvą. 2) duomenyse, kuriuos naršysime, paleidžiame ciklą per eilutes iš viršaus į apačią: 2.1) kiekvienoje toje eilutėje atliekame paprastą paiešką su pirmąja vienmačią reguliaria išraiška iš tų reguliarių išraiškų masyvėlio; 2.1.1) jeigu paieška sėkminga, tada einama laikinai prie sekančios eilutės (stojant į konkrečią jos vietą) ir būtent šioje vietoje atliekama paieška su antrąja masyve esančia reguliaria išraiška. Tam manipuliuoju su eilutės pos() (paieškos starto vieta) ir pririšu paiešką \G inkaru, kad neitų ieškot tolyn į priekį.
Suradus vieną sutapimą, programa veikia toliau ir ieško kitų sutapimų, kuriems leidžiama persidengti (tą suprogramuoti pasirodė kur kas lengviau).

Žemiau:
1) tai, ko ieško programa (4 simboliai, ignoruokim tarpus - jie nėra paieškoje),
2) programos veikimo rezultatas (su parodytomis eilutėmis vėliau naudosimomis reguliariose išraiškose),
3) pavyzdinis programos kodas
3.1) kodo apačioje po užrašo __DATA__ yra duomenų dvimatis laukas, kuriame paieška vykdoma.

1.
 #
#
  #.

2.
(0: .{1}#)
(1: #)
(2: .{2}#\.)
Number of matches: 3;
Upper-left corners match at:
[row: 1|column: 1]
[row: 1|column: 6]
[row: 2|column: 0]

3.

use warnings;
use strict;

sub two_d_search{
    my $amount_of_data = shift;
    my @data = splice @_, 0, $amount_of_data;
    my @pattern = ();
    my ($arg, $indentation, $string);
    my $i = 0;
    
    while (@_){
        $arg = shift;
        if ($arg eq "\n"){
            $i++;
            $arg = shift;
            }
        $indentation = $arg;
        $string = shift;
        $pattern[ $i ] .= ".{$indentation}" if $indentation;
        $pattern[ $i ] .= $string;
        print "($i: $pattern[ $i ])", "\n";
        }
    
    my $pos;
    my $match = 0;
    my @matches = ();
    
    for my $i (0 .. @data - 1){
        undef pos $data[ $i ];
        
        OUT_2:
        while ($data[ $i ] =~ m/$pattern[0]/g){
            ($pos) = @-;
            # matches can overlap, so 'pos' increases only by +1:
            (pos $data[ $i ]) = $pos + 1;
            
            for my $j (1 .. @pattern - 1){
                pos ($data[ $i + $j ]) = $pos;
                if ($data[ $i + $j ] =~ m/\G$pattern[$j]/){
                    # do nothing
                    }
                else {
                    next OUT_2
                    }
                }
            $match ++;
            push @matches, "[row: $i|column: $pos]";
            }
        
        }
    $" = "\n"; # set list output separator to "\n"
    return     "Number of matches: $match;", 
            "Upper-left corners match at:\n@matches"
    }

my @data = <DATA>;
chomp @data;

my @info = &two_d_search(
    scalar @data,
    @data,

#    indentation; string; argument of line separation
    1, '#', "\n",    # two_d_regex first line
    0, '#', "\n",    # two_d_regex second line
    2, '#\.'    # two_d_regex third line
    );

print "@info",$/;

__DATA__
#..#.....#.
..#...##...
.#....#..##
#..#....#..
..#...#..#.
.......#.#.
...........

Mokslo metų pradžia

Pastaruoju metu:
* skaičiausi en.wikipedia straipsnelių, susijusių su programavimu.
* mėginau pasidomėti Haskell kalba, bet nieko nesupratau.
* dalyvaudavau Codeforces turnyrėliuose ir treniruotėse.
* perskaičiau pusę vienos knygos apie programavimą, vienos iš šių - žemiau pateiktų:

 Wikipedijoj susipažįstu su savokom "operator overloading", "arity", "linearithmic (O(n log n)) (complexity)... , permetu akeles per straipsnius pavadinimais "sorting algorithm comparison", "computation complexity", "C++ Standard Library", "Standard Template Library", "ternary operation", "scope", "volatile memory", "random access"... daug straipsnių lieka nesuvirškinti ir per sunkūs, tai apie NFA, DFA ((non-)deterministic finite automata) ir kt.

Codeforces platformoje pastarąjį mėnesį sekėsi gan gerai. Nors išspresdavau nedaug ir pačių lengviausių uždavinių, tačiau gan greitai. Taip pat kartais pavykdavo nulaužti kambariokų programas.Už tai užimdavau neblogas vietas, palyginus, ir kilstelėjo reitingas, kurio adekvatumu galima lengvai paabejoti.

Knygos apie reguliarias išraiškas pirmoje pusėje, kurią įveikiau, radau keletą naujų dalykų, bet daug buvo žinoma ir veikė kaip kartojimas, priminimas. Knygoje daug remiamasi pavyzdžiais, kas man patinka. Ir pavyzdžiai gana praktiški. Pradėjau savo sprendimuose Perl kalba taikyti lookaroundą (lookbehindą ir lookaheadą), ko anksčiau nedariau.

Programose ėmiau naudoti kintamuosius: $/ (input line separator), dažniau teko reguliariosiose išraiškose naudoti modifikatorius "m", reguliariai panaudoju nesenai išmoktuosius Hash'us.

Kartais pagolfinu anarchy golfe.

Apžvalga 2014 rugpjūtis

Šį 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.

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:

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. 

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.