Clasele 9-12 lecția 9 - 12 nov 2014

From Algopedia
Jump to: navigation, search

Barajul pentru Șumen

Aceasta nu a fost propriu-zis un cerc, ci am dat barajul pentru Șumen, seniori, runda a 2-a. Se impune, totuși, o observație interesantă. Lecția trecută am vorbit despre bune obiceiuri în programare și am spus că, prin excepție, la concursuri este permis orice. Hai să vedem dacă chiar așa stau lucrurile. Iată niște statistici despre surse trimise la probleme recente de concurs.

  • Am extras lungimea sursei, timpul maxim de rulare și memoria maximă folosită.
  • Am reținut doar sursele care rezolvă problema, în esență (scoruri maxime sau aproape de maxim).
  • Din propriile mele surse am eliminat comentariile, căci umflă sursa cu 1-2 KB.
  • Pentru alți concurenți nu am stat să fac asta, dar alți concurenți, în general, nu folosesc comentarii.
  • Am eliminat sursele oamenilor din afara cercului.

Ce concluzii tragem din ele?

  • Sursele mele sunt cele mai rapide.
  • Sursele mele consumă cea mai puțină memorie.
  • Sursele mele sunt printre cele mai scurte.

Nu spun asta ca să mă dau mare. Un profesor care se bucură că e mai tare ca elevii lui e un profesor ratat. Spun asta ca să ne punem împreună o întrebare. De ce vă mai aruncați la STL? Scrieți mai mult cod, care se excută mai lent și cere mai multă memorie. Și atunci, ce anume câștigați cu toți vectorii și listele voastre?

Vă reamintesc că sursele mele sunt didactice. Întotdeauna le scriu în ideea că altcineva le-ar putea vedea, chiar și pe cele pe care nu le public. Nu folosesc aiurea variabile de o literă, nu le optimizez la sânge dincolo de complexitatea asimptotică.

Programați mai îngrijit. Este bine pentru creierul vostru și este bine pentru punctajele voastre.

Anexă: rezultate la probleme (mărimea sursei, timpi de execuție, memorie folosită)

Matroid

job ID username nume lungime sursă (B) scor timp de rulare (ms) memorie (KB)
86156 Catalin.Francu Catalin Francu 2019 100 344 3864
87242 Mapa Pandele Maria Smaranda 2794 80 412 8212
87111 elfus Florin Olimpicu 1781 100 424 8264
87132 AlexandruValeanu Alexandru Valeanu 3477 100 424 9008
87126 AlexandruValeanu Alexandru Valeanu 3386 90 440 9016
86342 vmanz Victor Manz 2731 100 444 7700
87259 Mapa Pandele Maria Smaranda 2830 80 448 8212
87138 AlexandruValeanu Alexandru Valeanu 2519 100 448 8692
86154 Catalin.Francu Catalin Francu 2201 100 452 4256
86764 francu Cristian Francu 3771 100 452 9720
87271 Mapa Pandele Maria Smaranda 2843 80 460 8212
87133 ericpts Stavarache Eric 2057 100 464 6192
87237 b0rk4n Gramatovici Paul 2184 90 468 5900
87201 smara Smaranda Dinu 2195 100 480 8512
87123 AlexandruValeanu Alexandru Valeanu 3377 80 508 9792
87119 teoionescu Ionescu Teodor 2041 90 508 10624
87117 teoionescu Ionescu Teodor 2042 80 508 10624
87121 smara Smaranda Dinu 1996 80 520 8508
86233 spatarel Spatarel Dan-Constantin 3023 80 524 8676
87112 teoionescu Ionescu Teodor 2233 80 524 11824
87188 smara Smaranda Dinu 2204 90 528 8528
87109 teoionescu Ionescu Teodor 2046 80 532 10836
87235 b0rk4n Gramatovici Paul 2138 80 540 5904
86763 francu Cristian Francu 3691 80 548 9724
86761 francu Cristian Francu 3538 80 548 10300
86760 francu Cristian Francu 3538 80 552 10296

Notă: La această problemă Cristi a implementat o forță brută oribilă, pentru că l-am rugat eu să implementeze una. Era important să aflăm cât de mult se poate optimiza algoritmul forță brută. De asemenea, și sursele lui sunt didactice și frumos comentate.

MaxXor

job ID username nume lungime sursă (B) scor timp de rulare (ms) memorie (KB)
82952 Catalin.Francu Catalin Francu 1425 100 160 1036
83147 francu Cristian Francu 1967 100 184 1824
84851 elfus Florin Olimpicu 3106 100 228 1840
84984 teoionescu Ionescu Teodor 1743 60 232 17096
84892 teoionescu Ionescu Teodor 1743 60 232 17084
84868 teoionescu Ionescu Teodor 1931 60 236 16876
84957 teoionescu Ionescu Teodor 1923 60 264 16940
84911 ericpts Stavarache Eric 2159 60 292 12536

Notă: Urmează un lung șir de scoruri de 50, timpi de rulare pe la 280 ms și memorie folosită aproape de 16 MB (implementările de trie, probabil).

Tensor

La problema Tensor rezultatele sunt mai puțin relevante, pentru că și punctajele au fost mici. Am filtrat sursele de minim 40 de puncte.

job ID username nume lungime sursă (B) scor timp de rulare (ms) memorie (KB)
87059 Catalin.Francu Catalin Francu 2036 100 12 876
87074 spatarel Spatarel Dan-Constantin 2690 100 44 2236
87141 b0rk4n Gramatovici Paul 1864 100 48 2920
87250 smara Smaranda Dinu 1809 40 88 11252
87241 smara Smaranda Dinu 1809 40 96 11168
87247 teoionescu Ionescu Teodor 2029 55 180 12824
87240 teoionescu Ionescu Teodor 2148 50 208 12832

Anexă: sursele mele