Clasele 9-12 lecția 9 - 12 nov 2014
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
- Media:scc-tarjan.cpp - problema Matroid (algoritmul lui Tarjan)
- Media:scc-kosaraju.cpp - problema Matroid (algoritmul lui Kosaraju)
- Media:tensor.cpp - problema Tensor
- Media:maxxor.cpp - problema MaxXor (divide et impera)
- Media:alpine.cpp - problema Alpine
- Media:magazin.cpp - problema Magazin
- Media:ozn.cpp - problema OZN