Testele sunt grupate la problema asta?

Cum arata o panza cu N = 1?

Se garanteaza ca raspunsul intra in 64 de biti cu semn?

"Paianjenul porneste la punctul aflat la distanta S de centru de pe segmentul 0,"

Deci segmentul 0 sau segmentul 1?

#1:

Intre fiecare 2 segmente consecutive se afla M punti de lungimi A1 ≤ A2 ≤ ... ≤ AM, in asa fel incat punctul Ai sa uneasca punctele de pe cele doua segmente aflate la distanta i de centru.

punctul Ai sau puntea Ai?

Puntile au mereu lungime mai mare sau egala decat lungimea corzii cercului de raza i determinat de cele doua segmente consecutive? (cu alte cuvinte, aceste "punti" sunt de fapt niste "coarde relaxate" pe cercul respectiv? Un desen ar fi fost util aici

#2:

Paianjenul porneste la punctul aflat la distanta S de centru de pe segmentul 0, culege succesiv (in exact aceasta ordine) un bob cu vitamina 1, apoi 2, apoi 3, ..., iar la final N [...]

Exact un bob sau macar un bob? Poate sa aleaga la un pas sa nu aleaga bobul de pe un punct?

Aceeasi intrebare ca si pepsiM4A1

[3]

Inputul din exemplu nu ar trebui sa fie:

4
2 3 1 4
2 1 4 3
3 2 1 4
4 3 1 2

pentru ca solutia sa fie cea descrisa?

Cand se vor posta solutiile  ? (positive pressure)

Am sa incerc si eu sa intru in dezbaterea aceasta, in speranta de a mai "echilibra fortele" care se exercita pe aici.

Am sa incep prin a-mi pune intrebarea: ce este infoarena?

Mai exact, ce este acum si ce se doreste sa fie. Dupa cum vad eu lucrurile, in momentul acesta infoarena are statut de online judge si de arhiva educationala de probleme de programare competitiva. Organizarea concursurilor regulate nu face parte din activitatile de baza ale infoarenei, deci infoarena NU ESTE codeforces, hackerrank, csacademy, topcoder, etc. Daca ar fi sa compar infoarena cu alte site-uri asemanatoare, as mentiona mai degraba site-uri precum SPOJ, UVa, whatever. Site-urile din prima grupa mentionata atrag utilizatorii prin atmosfera competitiva a concursurilor, pe cand site-urile din a doua grupa prin multitudinea de probleme pusa la dispozitie spre rezolvare.

Consider ca eliberarea surselor de pe aceasta platforma va nulifica orice sentiment de competitie in cadrul platformei si orice ambitie a utilizatorului de a-si iesi din aria de confort pentru a se autodepasi. Punerea la dispozitie a unei modalitati usoare si accesibile de a-si indeplini telul in pofida uneia care ii va ajuta mai mult pe termen lung consider ca va determina dereglarea learning path-ului corect si instaurarea unei impresii superficiale de pseudo-succes. S-a facut si un experiment pe tema asta, pe care il atasez https://en.wikipedia.org/wiki/Stanford_marshmallow_experiment.

In al doilea rand, as dori sa punem intrebarea care este scopul infoarenei?,

pentru ca raspunsul la aceasta intrebare poate fi foarte vast. Este o platforma de invatare/evaluare a elevilor de liceu in cadrul orelor de informatica / pregatirilor pentru olimpiadele scolare? Este o platforma pe care un om de orice varsta poate invata "basics"-urile programarii competitive? Este o platforma pentru oamenii de varf, care aspira la competitiile internationale? Este o comunitate de pasionati a programarii?

In functie de raspunsul pe care il gasiti (voi, cei din conducerea infoarenei, nu noi, end-userii), strategia ar trebui abordata in modalitati diferite si concluziile trase pot astfel deveni foarte variate.

Ca sa inchei (TL; DR), personal, nu gasesc un aspect pozitiv major in a elibera accesul la toate sursele din arhiva de probleme. In acelasi timp, consider ca decizia asta este una pe care trebuie sa o ia echipa infoarena pentru binele platformei pe viitor si sa si-o asume, nu sa isi caute raspunsurile intr-o arie foarte "biased" a utilizatorilor ei.

Exista mereu solutie?

[2]: You can prove that there is maximum one way to solve the problem by induction on N. Basically, if I understood the problem correctly, there is only one move that would toggle the top left cell (i.e. toggling the top left rectangle). So using the top left rectangle or not is uniquely determined by that state. In the same way you can argue that the one to the right of the top left one determines the next rectangle to the left, and so on. So the first line determines the first line of available rectangles, and so on.

[3]: You can observe that choosing whether to toggle the first row or not "forces" the decision on all the columns (based on the cells of the matrix), which, again, determines the choice upon the other rows. So the solution is uniquely determined by choosing whether to toggle the first row or not. So we can compute both cases and just take the minimum. Note that there isn't always a solution. (e.g. [101, 000, 101])

In problema E (Metrou4), din enuntul aferent se intelege construirea unui arbore Steiner pe distante manhattan. (Mai exact, https://en.wikipedia.org/wiki/Rectilinear_Steiner_tree ). Scrollam putin pe articol si aflam ca este o problema NP. Aparent, enuntul a fost ambiguu si presupun ca mai toata lumea l-a inteles gresit. In realitate, era un MST pe distante manhattan (ceea ce nu se intelege din enunt).

Legat de problema Robo nu vreau sa ma pronunt, dar sunt n motive pentru care consider ca nu ar avea ce cauta in acest concurs (unele dintre ele sunt chiar sinistre). Am vorbit despre asta si consider ca nu e deloc in regula ce s-a petrecut. (cautati Automaton Minimization)

Problema Padure2 "a mai fost data la un CF" (Harsan), ceea ce nu e neaparat un lucru rau, dar creeaza dezavantaje pentru unele echipe.

Sunt curios daca a existat o echipa in concurs care sa nu "bulaneasca" solutia de la problema Sate2 (daca da, sunt curios ce solutie aveti )

In rest, problemele au fost ok. De apreciat faptul ca runda aceasta (echipa noastra cel putin) nu am mai intampinat probleme legate de limitele stranse de timp.

Cat de mari sunt valorile de pe bilute?

Excelenta Ta, ne cerem iertare ! Maria Ta, sa stii ca editorialul de anul trecut este pe site-ul oficial, impreuna cu sursele oficiale. Si acum serios, mai usor cu tupeul, ca nu esti buricul pamantului.

De asta imi cer scuze nu am stiut,am cautat pe infoarena dar nu am gasit(nam stiut de site oficial),restu nu pot spune nimic miam exprimat parerea.

Poti sa organizezi tu un concurs cu scopul de a aplica toate sfaturile de buna practica pe care ni le-ai dat. 99%, daca nu ti-a intrat o problema in timp, nu ti-a intrat pentru ca solutia nu era optima. Iar legat de memorie, tind sa cred ca a fost suficienta memorie la problemele la care memoria nu conta.

Eu vorbesc in general de infoarena,nu de concursul asta,aici cu memoria e ok (o observatie buna este ca a fost rational de a mari limita la prima problema deoarece sunt solutii care necesita mai multa memorie),sar putea de marit limita la citeva problema exemplu sa luam problema weeee,cineva poate a facut in O(n log n) atunci el are sansa de a lua tle,dar in stil acm este important nu ca solutia sa fie cea mai optima dar sa fie rapid scrisa si sa fie mai rapida cu mult de brut force,daca puneti 1s limita nu prea cred ca brutul va intra in timp.
O mica observatie este ca va fi mai bine de specificat deodata limita nu doar tipul de date (prob hektor),nu stiu cum altii dar eu am ramas confuz fiindca nu stiam daca adun 2 costuri sa tin in int,unsigned int sau long long.
In general sunteti bravo ca ati putut organiza concursul,am spus despre limite ca mam intilnic cu asa probleme unde teste slabe limita mica si solutia normala ia 50 pe cind brutul 100,deloc nu inteleg de ce se pun limite de gen 0.1,0.3 s in loc de 1s,1.5s.

Domnule gabi, la ce acm ai fost tu si ai vazut ca nu se pune accent pe timpul de executie? Nu de alta, dar la acm nu rareori s.au dat probleme cu input de dimensiuni precum 5 milioane sau care sa permita doar o anumita complexitate. Feedback.ul e apreciat, dar cred ca ti.ai facut o parere profund gresita legata de concursul acm propriu.zis. Nu stiu de unde ai auzit tu barfele ca "la acm se da sa intre bruta" sau "limitele de timp / memorie sunt practic infinite". Mai documenteaza.te.

Vedeti ca are 4 ore si nu se vad problemele.

Mai sunt 4 ore sa le vezi, don't worry

EDIT: Also, if the model we build it on allows us to extract the index of the MSB of some number in O(1), all operations become O(1). That is slick!

@dutzul How about not using hashmaps at all (they are a heck of a complexity to estimate). Why not just use regular lists?

I.e. We keep a list of values for each of the "bins". The values will not be the real values, though. They will be indices. That will allow us for an easy update that could "lazily" delete the value from one of the bins (and, eventually, insert it in some other bin, if the value's MSB has changed). It is clear that the total elements of each bin can be stored this way (be aware, though, they do NOT equal the size of the actual lists, as we are doing deletions in a lazy manner). Now, when extracting a min / max, we look for the MSB / LSB of the mask we keep dynamically as you said, and we take its log. Then we eliminate all indices that should have been deleted and take the last element (think of the lists as "stacks"). All operations should be now O(log b), without the annoying "hashmap" constant. (b is the number of bits of the values), and total memory is O(M + b) (M is the total number of operations). Also, it can never exceed O(N * b), where N is the number of insertions, so that is also nice.

A, bun. Ma gandeam ca daca finala se tine la Cluj, o sa fie separata de infoarena. 

Pana la urma, O(logn sqrtn) per update/query intra? Eu in concurs luam tle pe o gramada de teste cu complexitatea asta.

Am reusit sa o fac de-abia ulterior cu O(sqrtn) / update si O(logn*sqrtn) / query (practic am redus update-ul la liniar / bloc).

E vreo sansa sa se faca si o editie on-site?

That would be correct, but I don't think scanning the people in linear manner would do the job, as moving vertices around may cause earlier-scanned ones to "break" (for example, maybe you have to move vertex no. 5 to the right table, but doing that will make vertex no. 2 have two enemies at his table). What I am thinking now, if the idea works, is keeping all the people in a MAX-heap sorted by the number of enemies at the same table, and solving the problem in a Dijkstra-like manner (XORing the top's table and updating its enemies' status), until the heap top has a priority less than 2.

However, I am not very certain about why it actually works.

Cand se pun problemele in arhiva? Cred ca am gasit o solutie in O(MlogM + N) si sunt curios daca merge 
O(M log M) pentru sortare si dupa O(M + N)

Costul muchiilor este mai mic in modul decat 2³¹-1?

+1

Am o intrebare:

Daca am vizualiza structura ca un arbore, la o operatie de Find(x) cu comprimarea drumului, nu vor fi sterse toate muchiile de pe lantul de la radacina la nod (in afara de cea directa)? In cazul asta, nicio muchie nu va fi vizitata de mai mult de doua ori, deci complexitatea ar trebui sa fie lineara (amortizata cel putin). Imi scapa ceva?

You are right. I was solving some other problem, for sure