Clasa a VII-a lecția 28 - 12 mar 2020

From Algopedia
Jump to navigationJump to search

Anunțuri

  • Sîmbătă 14 martie ora 10:00AM (ora tentativă) va avea loc un concurs la varena, organizat de Teodor Plop, instructor pregătitor la cercul de informatică de clasa a noua din liceul Vianu. El este destinat elevilor de clasa a noua și va avea probabil 3 probleme ușoare spre medii. Vă încurajez să participați.
  • Duminică 15 martie ora 10:00AM va avea loc concursul FMI No Stress organizat de Infoarena. El este destinat în general studenților începători și va consta din 9-12 probleme ușoare spre medie și va dura 5 ore. Este o bună ocazie să vă testați viteza și cunoștințele de bază (cît de siguri sînteți pe lucrul cu caractere, sau baza doi?) Vă încurajez să participați.

Probleme din care alegem ce discutăm azi

Tema 25 - rezolvări

Optim

Problema optim a fost dată la ONI 2012 clasa a 8a. Ea are o rezolvare fără programare dinamică, ineficientă și nu chiar banal de implementat și o rezolvare cu programare dinamică, eficientă și relativ ușor de implementat.

Joc6

Problema joc6 a fost dată la ONI 2011 baraj gimnaziu. Este o problemă tipică de programare dinamică.

Concurs - rezolvări

Noxa

Problema noxa a fost dată la timus.ru.

Secvență dominată

Problema secvență dominată a fost dată la codeforces.

Steaguri

Problema steaguri a fost dată la timus.ru. Este o problemă tipică de probleme suprapuse.

Rezolvări aici [1]

Tema 27 - rezolvări

Raze

Problema raze a fost dată la ONI 2010 clasa a 8a.

Problema are mai multe variante de abordare.

Suita

Problema suita a fost dată la codechef.

Rezolvări aici [2]

Lecție - discuții probleme OJI

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2020-03-12-clasa-7-lectie-info-28-720p.mp4</html5media>

Foto1

Problema foto1 a fost dată la OJI 2020 clasa a 7a. Este o problemă directă, relativ simplă, poate mai curînd de clasa a 6a.

Soluție forță brută

Vom discuta doar cerința doi, deoarece cerința unu este banală, de introducere în clasa a șasea.

Partea mai grea a problemei este înțelegerea enunțului. Anume:

  • Fulgerele sînt continue și merg de sus în jos.
  • Fulgerele sînt disjuncte. Ele nu se pot atinge nici măcar pe diagonală.
  • Fulgerele nu se pot despărți, ele sînt liniare.

Drept pentru care o soluție forță brută este următoarea:

Parcurgem matricea M pe linii și pe coloane, natural. Pentru fiecare element M[l][c]:

    Dacă M[l][c] este 1 și elementele de deasupra lui sînt 0 (M[l-1][c-1], M[l-1][c], M[l-1][c+1])

        Adaugă 1 la numărul de fulgere.

        Parcurge în jos acel fulger pentru a îi afla lungimea.

Nu detaliez parcurgerea fulgerului, ea se deplasează în jos pe acel element care este 1, adunînd 1 la lungime.

Ce complexitate are această soluție?

Parcurgerea matricei este O(N·M). Parcurgerea unui fulger este O(N) și putem avea O(M) fulgere. Rezultă o complexitate de totală de O(N·M) care este și optimă, deoarece trebuie să citim matricea.

Dar memoria folosită? Ea este evident O(N·M) deoarece vom memora matricea. Mai exact, dacă elementele matricei sînt de tip caracter, memoria necesară este 10000 octeți, adică foarte puțin.

Simplificare

Ca idee de simplificare a implementării forței brute, putem "reseta" elementele unui fulger, pe măsură ce îl parcurgem. Astfel, testul de început de fulger devine mai simplu, dacă elementul curent M[l][c] == 1.

Soluție cu (și) mai puțină memorie

Dacă dimensiunile matricei ar fi ceva mai mari ne-am putea pune problema unei soluții care să nu memoreze matricea. Putem memora doar o linie din matrice. Vom parcurge matricea și, pentru fiecare element 1, ne întrebăm dacă este un început de fulger verificînd elementele din linia de mai sus. Putem, de asemenea, memora lungimile în acea linie, nu doar 0 sau 1.

Iată un algoritm posibil:

Citim matricea M pe linii și pe coloane, natural. Pentru fiecare linie l:

    Citim linia. Pentru fiecare coloană c citim elementul E și:

    Dacă E este 1

        Daca elementele de deasupra lui sînt 0 (L[c-1], L[c], L[c+1] - dar atenție, la L[c-1], ne trebuie valoarea veche)

            Adaugă unu la numărul de fulgere.

            L[c] primește 1 (lungimea actuală a fulgerului.

        Altfel înseamnă că doar un element din cele trei este diferit de zero, un fulger se continuă:

            L[c] primește 1 + L[i] (unde i poate fi c-1, c sau c+1)

        Dacă L[c] depășește lungimea maximă a unui fulger, reține valoarea

     Altfel

        L[c] = 0

Acest algoritm are aceeași complexitate în timp ca cel anterior, dar folosește doar O(M) memorie, adică circa 100 octeti (deoarece elementele matricei pot fi de tip char, lungimile nedepășind 100).

Considerente de implementare

Algoritmul de mai sus se poate implementa mai ușor dacă observăm anumite lucruri:

  • Nu avem nevoie să menținem două linii din matrice. Putem să memorăm valoarea veche din L[c-1].
  • Valoarea de calculat L[c] nu are nevoie de teste (condiții). Ea este suma celor patru valori

(trei deasupra plus elementul citit) înmulțită cu elementul citit.

O implementare bună n-ar trebui să depășească 35 de linii efective de cod.

Wind

Problema wind a fost dată la OJI 2020 clasa a 7a. Este o problemă medie spre ușoară ca dificultate, partea cea mai grea fiind ordinea și disciplina în rezolvare, algoritmul nepunînd probleme (sper).

Comentariu: v-ați gîndit de ce problema se cheamă wind, un titlu în engleză?

Indiciu: gîndiți-vă care ar fi fost alternativa și de ce nu e preferabilă :)

Soluție

Vom discuta doar despre cerința 2, deoarece punctul unu cere găsirea numărului de divizori ai unui număr, problemă banală de clasa a cincea.

Problema cere găsirea unei împărțiri a unui vector de elemente pozitive și negative în subvectori adiacenți de lungime egală, care să minimizeze diferența între cea mai mare sumă a unui subvector și cea mai mică sumă.

Observații:

  • Putem calcula valoarea de minimizat într-o parcurgere a vectorului, deci în O(N).
  • Nu vom lua în calcul decît parcurgeri în care putem crea subvectori egali - deci pentru divizorii lui N.
  • N are maxim 5 cifre.
  • Numărul maxim de de divizori ai unui număr cu 5 cifre este 128, conform numărul maxim de divizori ai numerelor de n cifre.
  • Timpul este 0.3s

De aici rezultă că o forță brută, care pentru fiecare divizor calculează diferența, se va încadra în timp, ea efectuînd circa 128·100000 = 12.8 milioane de operații.

Problema constă, precum spuneam, în implementare, algoritmul fiind forță brută. La ce trebuie să fim atenți?

  • La enunț! Nu este imediat clar că trebuie să afișăm cel mai mare indice al primului element din subvectorul de sumă maximă.
  • Să nu creăm cazuri particulare.
  • Să scriem cît mai clar și mai simplu codul, deoarece avem multe detalii de care trebuie să ținem cont.
  • Să facem parsing! Vom citi 100000 de numere de 9 cifre, plus un separator, deci circa 1MB. Putem cîștiga 0.1s doar din o citire atentă. Atunci cînd avem 0.3s cu totul, devine semnificativ. La olimpiadă aș implementa parsing-ul simplu, cu fgetc(). Nu aș risca parsing-ul cel mai eficient, cu fread(), dar dacă vă simțiți confortabil, de ce nu?

O implementare eficientă, cu parsing simplu, nu ar trebui să depășească 70 de linii de cod efectiv.

Ce complexitate are această soluție?

Precum am discutat, timpul va fi O(d(N)·N), unde d(N) este numărul de divizori ai lui N, în cazul nostru maxim 128.

Memoria folosită este cea necesară pentru a stoca valorile din vector, adică O(N), sau, mai exact, 400KB, mult mai puțină decît cea acordată, de 16MB.

Discuție probleme propuse de voi

În măsura în care vom avea timp vom discuta despre problemele:

  • monede dată la ONI 2014 baraj gimnaziu
  • ssk dată la ONI 2014 baraj gimnaziu

Tema

Tema 28 clasa a 7a

  • foto1 dată la OJI 2020 clasa a 7a
  • wind dată la OJI 2020 clasa a 7a

Rezolvări aici [3]