La recomandarea lui Vlad, voi scrie si aici cate ceva despre concurs. Si ca raspuns la intrebarea de mai sus, o sa incep cu problema circus. Problema aceasta probabil ar fi incuiat pe majoritatea romanilor din lotul de seniori, pentru ca nu prea e pe tiparul nostru. In general, problemele de la loturile noastre au o solutie relativ triviala intr-o complexitate polinomiala, dar prea mare (O(n^3) spre exemplu), iar o mare parte din dificultatea problemei consta in a gasi o optimizate. In problema asta, toate solutiile evidente erau pur si simplu gresite, luau 0-11 puncte. Problema se baza pe o observatie complet contra-intuitiva, fara de care nu puteai progresa deloc inspre vreo solutie. Genul asta de probleme sunt criminale pentru noi, in ideea in care ceva similar creaza haos in lot (@magic). O pot numi noroc ca m-am gandit intamplator la ea din alt unghi pt a lua 40, era la fel de probabil pentru oricare din noi sa se intample asta.
Problema doi din ziua 1 a fost de treap-uri, desi avea o solutie alternativa cu arbori de intervale dinamici in O(log^2), care era suficient. Evident ca eu am fost incapabil sa implementez asta, busind 70 de puncte complet gratis, iar Rochi pur si simplu nu stia treap-uri
.
Problema a treia era strict de implementare. Era un backtracking jegos cu relativ multe cazuri si fara o identitate/idee interesanta in ea. Unii in 30 de minute, unii in 2 ore, dar am facut-o toti.
As vrea sa fiu la fel de obiectiv si legat de ziua 2, dar din pacate nu cred ca pot. In primul rand mi-a fost rau cam toata proba, a trebuit sa merg la baie sa vomit in repetate randuri si am pierdut mult timp asa. Am inceput cu problema "radio", pentru ca mi-am dat seama cum se facea cand k=n, pentru 40 de puncte. Am trimis, dar testele erau grupate si am luat 0, cu primul test din grupa cu Wrong Answer si primul test din grupa urmatoare cu Ok...am trimis o notificare la comisie sa verifice daca testele nu aveau o problema, pentru ca eram destul de sigur de propria implementare, insa mi s-a raspuns ca testele erau corecte. Am trimis mai apoi o sursa cu assert(n==k) si evident a dat crash, chiar era gresit. In cele din urma au admis ca era o problema, ca testele erau decalate cu unul, insa eu pierdusem 45 de minute si aici, iar concursul a fost prelungit cu 10 minute...frustrare, chestii, nu mai zic. Alta problema din ziua aceea dadea o matrice de (n*k)x(m*k) si cerea numarul minim de patrate alese pentru a pune query-uri (interactiv) pentru a face ceva. Imediat mi-a venit in minte problema "bmat" de pe infoarena, si era clar ca raspunsul era n*m, dar asta nu desfiinta complet problema, am luat 75 pe ea, inca nu stiu de ce.
A treia problema era de Suffix Arrays, si m-am simtit super prost dupa concurs cand am vorbit cu Denis despre cum se facea, dar sincer nu am avut timpul fizic sa ma gandesc calumea la ea. Am stat ultima jumatate de ora de concurs sa implementez un kmp cu care, prin intermediul unor optimizari cum numai romanii stiu am luat 40 si ceva de puncte.
Eu sunt putin dezamagit de propria-mi performanta, dar overall a fost foarte ok, iar echipa nu a facut rau. Problemele au fost frumoase, la multe te gandeai cu placere iar atmosfera a fost superba. Comunicare cu comisia era mult mai ok decat prin alte locuri, chiar raspundeau pe larg la intrebarile puse, nu doar "yes", "no", "no comment". Imi cer scuze pentru postul lung, si multumesc celor care chiar ar citi
.
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena