Ti-o vand eu la 250 RON, ca bonus cu autograf si iti arat ce capitole sunt cele mai frumoase din carte

Ce masuri anti plagiere veti adopta pentru runda lunga? 

 

Eu prin "algoritmi elementari" inteleg  niste algoritmi fara de care un programator nu s-ar putea descurca niciodata, ceva indispensabil bagajului de cunostinte necesar. Cred ca te poti descurca foarte bine fara sa stii "c.m.m.d.c", "numar prim", "prelucrarea divizorilor unui nr." sau "conversii intre sisteme de numeratie". Nu mi se pare absolut nimic esential in acesti algoritmi.

Asta ar trebui sa-ti dea o mica idee cat de bine sunt scrise manualele romanesti si de ce ar fi o idee buna sa stai cat mai departe de ele.

Sfatul meu ar fi sa folosesti internetul. Exista o multime de resurse mult mai bune fata de continutul unui manual scris acum 10-15 ani. Poti cauta pe google "C++ introduction", "algorithms introductory course", "how to start programming" si sunt sigur ca resursele vor fi mult mai bune. Anyway, ca programator o mare parte din job este sa cauti pe net lucrurile de care ai nevoie.

Daca vrei sa inveti materia de clasa, poti folosi cu incredere site-ul WellCode, creat de olimpicul national clujean Petru Trimbitas si de a sa mandra. Acesti vizionari ai educatiei informatice folosesc metode moderne pentru a-ti preda materia invechita din scoala.

P.S.: Nu am fost platit sa le fac reclama!

Baga de pe CodeForces probleme div2 C si D. Sa nu uitam nici de cel mai bun online judge din lume, CS Academy. Merita sa arunci un ochi si pe site-ul lor 

Ce zici de problemele de la OJI de clasa a IX a de anii trecuti?

Bitcoin & Altcoins...

[Bossime]

Atentie, contine spoilere. Daca vreti sa rezolvati singuri problemele, nu cititi ce urmeaza dupa linkuri.

• Bossime - Faci o brutana, observi patternul numerelor care nu au solutie, te gandesti de ce se intampla asta, apoi cauti o solutie constructiva pentru numerele care nu se incadreaza in pattern. Fara brutana, mi se pare greu sa gasesti o conditie suficienta ca sa nu existe solutie (primul pas pentru rezolvarea problemei)
• Maestru - Problema trebuia sa se numeasca "Maestrul alcoolic", dupa un film vazut in perioada aia de Teo. Din pacate, conducerea infoarena ne-a cenzurat numele Pe langa faptul ca e misto problema, imi place si ca sunt mentionat.
• Mingiute - Mi se pare o problema de flux destul de originala (nu am mai vazut ceva asemanator). Totodata, l-a popit pe Oncescu in timpul concursului (Oncescu de clasa a 10 a, dar tot se pune). Din pacate pentru mine, protagonistul din enunt participa la concursul onsite si, in timp ce ma plimbam prin sali, mi-a spus "ba Chirica, sa vezi ce te bat dupa ce se termina proba"  
• Copacul Smenar - E a doua problema a mea mentionata, stiu ca deja par narcisist, dar e ultima. Probabil dupa ce te prinzi de solutie, spui "wow, ce tare", ca apoi sa incepi sa injuri pentru cat este de tractorit. Solutia poate fi spusa in 2 propozitii, sursa in 5-7 kb. Anul asta m-a popit Oncescu cu o bulaneala (sa-si ia revansa pentru anul trecut), in schimb am popit si eu conducerea infoarena, care nu au fost pe faza cand am scris enuntul si am putut scrie prostioare.  
• Invsort - Stiu ca e recomandata de 14342432 de ori, dar nu are cum sa nu apara in lista mea. O problema grea pe care as recomanda-o chiar si incepatorilor, o data ce invata despre sortare. Daca intelegi (in loc sa tokesti) algoritmii de sortare, ar trebui sa fie facubila problema.
• Soc - Alta problema grea pe care as recomanda-o indiferent de nivelul cuiva. In afara de a sti sa parcurgi un graf, restul problemei e doar ad-hoc.
• Ciclu5 - Desi foarte frecventi in research, nu prea am vazut algoritmi randomizati la concursuri. Solutia e f misto - colorari random + dinamica pe biti. Desi sansa sa nimeresti la o iterare e extrem de mica, probabilitatile ne spun ca sansa sa nimeresti daca repeti procesul de multe ori e extrem de mare.
• Shgraf - Daca o intelegi pe asta pe bune, poti face cam orice problema care te pune sa numeri grafuri. Prima oara cand am rezolvat problema abia am inteles, a doua oara mi-era totul clar, a treia oara parea totul trivial. E clar genul de problema pe care as rezolva-o de mai multe ori.
• Arbsat2 - Super interesanta solutia. Nu iti vine in minte sa faci Divide et Impera prea usor. Sunt curios daca se poate rezolva fara si care e intuitia care te face sa te gandesti la D&I.
• Comisia - Asemanatoare cu smenul de la Heavy Path. Desi sa faci asta pe arbore a devenit clasic, sa te gandesti sa folosesti o idee asemanatoare pe vector mi se pare smecher.
• Dlog - De obicei dupa ce auzi ca se face in sqrt, devine destul de simpla rezolvarea. Aici nu e deloc clar cum continui. Foarte interesanta solutia (Baby step giant step algorithm).
• Echipe - Aveam 9 ani cand aparea problema asta. Foarte veche, dar sunt sigur ca e grea chiar si pentru concurentii de acum. O data ce reducem problema la intervale ordonate crescator atat dupa x, cat si dupa y, devine ceva mai simplu. Dar e destul de greu sa te gandesti la reducerea asta.

Well, am pus 10 probleme care chiar mi-au placut (excluzandu-le pe cele 2 ale mele) si pe care inca le tin minte, chiar daca unele sunt rezolvate cu mult timp in urma. Cred ca lista poate avea lejer 20-30 de probleme, sunt super multe faine pe IA, dar le-am scris doar pe primele 10 care mi-au venit in minte  

O mentiune, lista lui wef m-a ajutat super mult (tin minte ca a fost printre cele mai productive perioade ale mele cand incercam sa rezolv cat mai mult din ea). Din pacate, contine probleme propuse pana in 2006. Ar fi o idee sa faca comunitatea o lista noua pentru ultimii 10 ani, cred ca am castiga toti de pe urma ei.

NIM

Performanța presupune în primul rând ambiție.

Citatul asta imi aduce aminte de filmuletul interlopului roman Mondialu' Nelson intitulat "Ambitia invinge saracia". Recomand tuturor sa il vizioneze pentru dezvoltarea voastra ca oameni 

https://www.youtube.com/watch?v=XLMUGP2Xp4A

Nu cred ca alegerea asta ar trebui sa fie democratica. Cred ca ar trebui facuta alegerea care e mai buna pentru elevi si asta nu e neaparat alegerea pe care o vor elevii.

Cred ca alegerea cea mai buna pentru fiecare depinde de la persoana la persoana. Deciziile de tip "one size fits all" nu sunt niciodata productive. E posibil ca unii sa ajunga la concluzia ca nu e bine sa te uiti la teste/surse, dar doar dupa ce se lovesc singuri de zid  (gen nu au rezutatele asteptate etc.). Nu cred ca e bine sa ii restrictionezi cuiva posibilitatea de a experimenta, doar pentru ca experienta ta subiectiva spune ca nu e bun modul lor de pregatire. Raspunsul asta reflecta si parerea mea referitoare la subiect. Si da, am scris ceva serios doar ca sa nu imi fie stearsa caterincuta de mai sus. 

Cred ca numarul difera de la persoana la persoana Totusi, dupa un anumit numar, ar trebui sa se vada imbunatatiri seminificative.

Cel mai important e sa rezolvi problemele din placere, ca un hobby. In felul asta, o sa se faca multe mai repede decat iti dai seama. Daca nu iti face placere sa rezolvi probleme, cred ca pur si simplu ar trebui sa cauti altceva sa faci cu timpul tau...

O intrebare mai buna ar fi cate probleme ar trebui sa lucrezi 

Unul dintre motive ar fi ca daca punem 1 s in loc de 0.1 s, evaluarea se face de 10 ori mai incet pe un test in worst case (o solutie care ia TLE). O problema are minim 10 teste, deci worst case se face de 100 de ori mai incet pe un job. Acum imagineaza-ti ca la un concurs se tot trimit multe job-uri de-odata, nu ai timp sa lasi sa se evalueze la limita de 1 s pentru ca ar sta celelalte surse in asteptare si coada de evaluare ar fi tot mai mare. Cu cat limitele sunt puse mai mari, cu atat sansa ca feedbackul sa vina mai tarziu creste. Asadar, de ce am pune limite de timp mai mari unde nu e cazul, la un concurs de tip ACM, unde sa primesti feedback-ul repede e important? Apropo, sper sa mai ai mult timp pana dai BAC-ul la rromana, altfel imi pare cam rau de tine 

http://acm.sgu.ru/problem.php?contest=0&problem=307

    

Ca sa fie concursul ol33333mpik!

23 de ore

Autorii au fost ascunsi pentru a nu stii participantii cui sa trimita *urarile* (precedate de un hashtag, desigur)?

Ce te-a determinat sa scazi 0.5 comisiei?

Nu e frumos Vlad, sa scazi pe nedrept din calificativ, dupa ce #comisia munceste atat de mult in favoarea participantilor.

Zaharel can also be solved with a similar idea

Also, a problem of this type is E div1 from one CF round I proposed.

http://codeforces.com/contest/429/problem/E

Cred ca ideea site-ului este ca dificultatea sa fie in gasirea ideii algoritmice, nu in implementari tricky ca sa scoti 0.000001 sec mai putin.  

Un mic spoiler la Zapezi2:

Incepem prin a numara toate APM-urile grafului complet. O parte din acestea sunt proaste - cele care contin o muchie inzapezita. Iteram cate o muchie inzapezita si numaram APM-urile care contin muchia. Din numarul de APM-uri vom scadea acest numar. Acum, am scazut ceva de mai multe ori - APM-urile care contin exact 2 muchii inzapezite. Adunam deci inapoi toate APM-urile care contin 2 muchii inzapezite. Din nou, ceva este adunat de mai multe ori acum...  Suna a ceva algoritm cunoscut?

Pentru a numara APM-urile grafului complet putem folosi teorema lui Cayley. Acum, avem muchii inzapezite pe care suntem fortati sa le luam in APM - evident, nu vor forma niciun ciclu. Aceste muchii formeaza x componente conexe. Trebuie sa adaugam x - 1 muchii pentru a obtine un APM pentru intregul graf. Putem generaliza cumva teorema de mai devreme? Sper ca nu am spoilat prea mult...



Solutia oficiala se bazeaza pe aceeasi idee?

Wild guess: ca sa nu se oftice cei cu 200 care stau acasa cand vad pe cineva cu 30 de puncte calificat.

Mici critici legate de setul de probleme:
http://www.infoarena.ro/problema/cenzura -> http://www.infoarena.ro/problema/ahocorasick

Cred ca erau o multime de participanti care stiau Aho, si totusi nu au putut rezolva problema Asta inseamna ca mai trebuia ceva pe langa Aho.

La Pinball, de ce era limita de timp asa mare? Se putea face in O(N + M) Also, ati avut o idee buna sa nu dati elemente egale, altfel problema devenea foarte jegoasa si plina de cazulete.

Pentru cine e suficient de masochist sa rezolve problema in cazul cu elemente egale, puteti incerca aici: http://www.spoj.com/problems/HILO/

Au fost dragute problemele, mi-au placut in special cea cu livada si cea cu meciul. Felicitari pentru runda!

Indienii au luat meditatii de la romani, care sunt recunoscuti pe plan mondial, la furat de probleme 

Putem afla motivul pentru care PscPld2D nu a fost propusa nicaieri?