Clasele 9-10 lecția 21 - 4 mar 2015
Contents
Recapitulare pentru OJI
Vom încerca să discutăm probleme de dificultate comparabilă cu OJI și să ne concentrăm pe
- probleme de simulare
- probleme de parsare de text
Dacă ne lovim și de programare dinamică sau de algoritmi pe vectori și matrice, cu atât mai bine
Problema Text (OJI 2010, clasa a 10-a)
Această problemă este interesantă fiindcă combină multe elemente utile pentru clasa a 10-a: parser de text (rudimentar), citirea unui fișier de lungime necunoscută, programare dinamică. Vom discuta soluția detaliată.
Să ne gândim puțin și la aspectele practice:
- Ce fel de teste particulare v-ați da ca să garantați că citiți bine numărul de cuvinte?
- Ce neclarități există în enunț? Eu am găsit două:
- Textul are maxim 20.000 * 20 = 400.000 de caractere. Dar pot fi oricâte linii goale, astfel încât, tehnic vorbind, fișierul de intrare poate fi oricât de lung.
- Ce facem când există mai multe soluții. Probabil oricare dintre ele este acceptabilă, dar este bine să întrebați.
Problema Expresie (OJI 2011, clasa a 10-a)
În această problemă elementele necesare sunt enunțate explicit: parser de expresii, medianul unui vector, subsecvența de sumă maximă.
Vom scrie un parser, pornind de la gramatica acestui limbaj, care este:
E -> E ',' T | T
T -> Numar | '(' E' )' | '[' E ']'
Numar -> '-'? [0-9]+
Alte observații:
- Am putea obține 20% din punctaj în circa 5 minute de codare rezolvând doar prima cerință. Practic am avea de numărat „cuvinte”, unde cifrele și semnul minus fac parte din cuvânt, iar celelalte caractere nu. Desigur, această abordare este sub nivelul nostru, :-) dar este bine întotdeauna să avem un plan B în caz că intrăm în criză de timp.
- În teorie, cele 30% din cazuri care nu conțin paranteze deloc sau nu conțin paranteze imbricate se pot rezolva cu metode mai simple, căci nu necesită recursivitate. Totuși, cred că un parser scris bine și elegant este cea mai rapidă și facilă implementare.
Problema Furnici (ONI 2011, clasa a 9-a)
Eu încadrez problema asta la categoria „noroc”. La origine, enunțul problemei este un puzzle de logică. Dacă „vă prindeți”, problema se rezolvă banal în 10 linii de cod. De aceea, cei care iau 100p nu demonstrează că știu algoritmică (mai mult decât un for și o căutare maxim), iar cei care nu iau 100p nu demonstrează că nu știu algoritmică.
Presupunând că nu v-ați prins de soluția puzzle-ului, cum putem obține cât mai multe puncte? Ca și la alte probleme de simulare, să încercăm să accelerăm simularea naivă. Să spunem că reținem un vector cu coordonatele tuturor furnicilor, de la stânga la dreapta, căci furnicile nu se depășesc una pe alta. Actualizarea acestui vector se face în O(n) și, teoretic, trebuie să facem o actualizare la fiecare ciocnire (câte ciocniri pot fi maxim)? Dar putem reduce numărul de furnici după fiecare una sau două ciocniri, căci o furnică de la un capăt al barei care este orientată cu fața spre capăt va cădea de pe bară fără să se mai ciocnească cu nimeni.
Alte observații:
- Enunțul spune L < 10.000.000 și N < 100.000. Genul acesta de promisiuni sunt suspecte. Într-adevăr, testele oficiale includ un test cu N = 100.000 (În schimb, L nu depășește 1.000.000).
Problema Penal
Aceasta este o problemă numai bună pentru clasa a 9-a. Ea conține elemente de simulare și poate fi accelerată dacă învățăm puțin despre codificări (vezi notele de la clasele 11-12).
Din limitele problemei rezultă că nu ne permitem să iterăm complet matricea pentru fiecare reordonare, căci . De fapt, chiar și este prea mare. Putem găsi o formulă care să reordoneze o bomboană în timp independent de N?
