Doar din curiozitate, cum s-a ales numele problemei?

Poate ar trebui marita un pic limita de timp ...

Pot primi premiu oamenii din div1 ?

int a[5] contine a[0], a[1], a[2], a[3], a[4].
Ai o greseala in sursa, nu e problema in evaluator.

Nu poate fi folosit cel de pe codeforces ? Dacă nu greșesc, este publică implementarea.

Nu, e clar ca soluția cu sortare e greșită. Eu încă n-am implementat chestia cu RMQ, dar încearcă să adaugi mici optimizări, de genul, dacă a[ i ][ j ] + X <= ans_now atunci nu mai controlezi daca gasesti un nou raspuns (Unde X este valoare maxima din matrice).

Daca fixam o celula (i,j), observam celulele la distanta cel mult D formeaza un romb. In O(D^2) putem parcurge acest romb si alege maximul dorit. Pentru a intra in timp este nevoie sa construim cate un RMQ pentru fiecare linie si sa alegem maximul in O(D). Complexitatea finala este O(D * N^2). Dar nu-s sigur daca e solutia dorita.

Mulțumesc.
Acum îmi dau seama că ar trebui să se schimbe prea multe la această problemă, ca să meargă suffix automata, dar oricum, Mulțumesc.

Ar fi frumos sa se mareasca limita de memorie, ca sa putem testa si Suffix Automata, pe problema aceasta.

Stie cineva cum se rezolva problema aceasta folosind Palindromic Tree?

in loc de || ar trebui sa pui &&, insa nu o sa primesti raspuns corect. E gresita conditia din if.

Adauga ios_base::sync_with_stdio(0);
mai jos de deschiderea fișierelor.

Am inteles. Imi retrag comentariile atunci, eu nu m-am prins decat de solutia de care am zis mai sus. Oricum, felicitari pentru runda! 

Iar eu stau aici si ma uit la sursa mea cu heavy path... 

Trimite-o pe arhiva, sau descrie ideea, te rog ^_^

nu e chiar 2^K (unde K == sum)

e (2^K)-2

1) excluzi mulțimea vidă
2) surjectivitatea înseamnă că trebuie să ai valori și de -1 și de 0 și de 1, cu alte cuvinte n-ai voie să ai doar 0 și 1 sau doar 0 și -1

Pai, în primul rând, ați putea sa vedeți ce echipe au copiat. După cum am spus, este destul de uşor. Apoi, nu vad de ce nu se reorganizează runda. Este normal să fie echipe (chiar multe) care nu îşi doresc asta deoarece fie au trişat şi nu vor mai obţine acest punctaj într-un context normal fie sau s-au calificat şi nu le pasă. Cele care s-au calificat şi merită asta, nu cred că ar avea mari probleme în a mai demonstra încă o dată ca îşi merită poziţia. Puteţi să incepeţi cu asta prin a mai remedia ce a mai rămas din această încercare de concurs. Pe viitor, ar fi de recomandat să întrebați anumite persoane dacă au mai întâlnit problemele în alte concursuri (persoane care participă activ sau urmăresc ceea ce se întâmplă şi nu sunt concurenţi la ACM).

Cât ține de un scor pentru fiecare propunere: verificarea plagiatului - 100, reorganizare - 100, verificarea ca problemele să nu mai fi fost propuse pe alte platforme - 80. Sunt nişte cerinţe normale, unele precizate chiar în regulamentul ACM.

În contextul unui spațiu ideal, aș fi de acord cu tine. Dar să vedem ce zic organizatorii, ce putere mai au ei ca să schimbe lucrurile.

Sau ați putea apela la niște profesioniști.

Eu, ca participant, m-aș bucura dacă ați putea colabora, pentru runde cît mai bune : )

In primul rând nu știu de ce mai numiți chestia asta încă un concurs. Articolul cu solutii este foarte ajutator, nici nu gasesti solutiile problemelor in editoriale de pe codeforces sau in primul link de pe google (stiu stiu, o sa ziceti ca daca scriu asta insemna ca am cautat chiar eu solutiile in timpul concursului, dar nu este adevarat ). Daca nu stiati ca anumite probleme au fost propuse pe CF atunci nu sunteti capabili sa propuneti probleme pentru concursuri, mai ales nationala ACM. Sunt mai multe variante pentru a rezolva asta, una din ele contactati anumite persoane din industrie care stiu cu ce se mananca algoritmica si au habar de ce se intampla in prezent. Sa va reamintesc ca au trecut vremurile in care propuneati probleme pentru OJI, la ACM e cu totul alta poveste. Mai mult decat atat, exista multe echipe care au trimis solutii de pe conturile personale si asta nu e corect deloc. Puteti verifica asta foarte usor, sa va spun si cum: contactati un admin infoarena sa va puna la dispozitie toate sursele trimise in timpul concursului dupa care folositi un tool sa va spuna cat de asemanatoare sunt sursele intre ele si e foarte simplu (seamana mai mult de 70, 80% => descalificare). Cititi asta http://theory.stanford.edu/~aiken/moss/ . Cu placere! Nu este in regula sa inchideti ochi si sa va bateti joc de cei care au fost corecti, asa ca luati masuri. Explicatii nu puteti sa dati, am vazut, pentru ca nu exista. Cei mai minunati organizatori de concursuri, va multumim foarte mult pentru timpul acordat organizarii acestui concurs de 2 lei, dar daca nu puteti face asta, va intelegem, nu avem nevoie de voi pentru a departaja niste echipe!

Nu întreb cu rău sau provocator, sunt aproape de aceeași părere ca tine.

Ce propuneri ai? Cum s-ar putea proceda în continuare ?
Aș vrea ca la fiecare propunere(idee) să-i pui un punctaj de la 1 la 100. Punctajul să reflecte „cît de pragmatică este propunerea”.

Eu nu am altă idee, înafară de a face încă o rundă ca să o înlocuiască pe asta, dar în acelaÈ™i timp îmi dau seama că punctajul este de  aproximativ 20%. Adică nu e foarte pragmatică, din simplul motiv că nu sunt destule persoane interesate ca să facă încă o rundă (chiar dacă sunt, pentru tine ei ar fi incomentenÈ›i). Runda aceasta tot a fost „trasă de urechi” (presupun) È™i s-a primit ce s-a primit.

Mai trebuie să treacă ceva timp pînă o să înțeleg structuri persistent, dar mulțumesc pentru explicație)

[online]

3.PQ foarte tare se aseamana cu http://codeforces.com/contest/522/problem/D si daca schimbat un

Hm.. sorry ca seamana atat de mult. Se vede ca nu mai sunt la curent cu ce probleme se dau pe la concursuri - daca stiam problema asta de pe CF, probabil nu mai propuneam PQ. Initial aveam o problema mai complicata, care avea PQ ca subproblema - si pt ca nu am avut timp sa pregatesc serios problema initiala, am decis sa propun doar subproblema (adica PQ). Singura "consolare" este ca problema de pe CF nu are editorial (sau eu, cel putin, nu l-am gasit), asa ca macar solutia nu era explicata in mod direct pe undeva.

Anyway, nu stiu cum au aratat solutiile, in general, la PQ, dar sunt curios daca vi se parea mai potrivita/interesanta daca query-urile erau online (adica parametrii L, R ai unui query depindeau de rezultatul query-ului anterior) - in felul asta solutiile bazate pe sortarea query-urilor nu mai functionau. Solutia mea functioneaza online si klamathix mi-a sugerat sa fac problema online, dar nu l-am ascultat

Ai putea descrie cum se face online problema ?

adaugă

Cod:

ios_base::sync_with_stdio(0);

în funcția main
ar trebui să ei 100.

P==N încă poate fi. Dacă înțeleg bine, cînd faci aborele parțial de cost minim, alegi doar N-1 muchii, adică o să avem doar N-1 valori. Și a N-a valoare nu e clar care să o alegi...
Nu cred că există teste cu P==N, dar oricum...

Cunosc oameni care au luat AC și n-au înțeles enunțul, dar au implementat la ghici/intuitiv soluția...
E chiar trist că se întîmpină probleme mai mari la înțelegerea enunțului decât la rezolvare ei.

p.s. nu exclud faptul că problemă e în mine dacă nu înțeleg enunțul al problemei.

Da, dar unii (Echipa mea) a avut de pierdut din cauza acestei neclarități (bine, nu cotează asta așa mult), de asta zic că ar fi bine să fie schimbat.

Foarte reușită problema PQ.
Problema Tribut a avut enunț greșit (încă are) și anume:
În „Date de ieșire” e scris „valoarea maximă a tributului pe care o va primi de la toate sistemele solare.” pe când sursa care afișa valoarea maximă a tributului pe care o primește doar de la uniuni comerciale lua AC și cea care socotea și sistemele solare WA. (Ar fi bine să corectați, măcar pentru arhivă).

p.s. Nasol că la Națională au fost probleme din alte concursuri. : )

Este corect enuntul. Este valoarea primita de la sisteme solare, uniunile au doar rolul de a regula cat anume da fiecare sistem solar (gandeste-te la uniunii doar ca la niste reguli pe care le respecta sistemele, tot sistemele sunt cele care dau banii in final ).

Foarte frumoase problemele la aceasta runda, felicitari comisiei

Totuși, în enunț scrie „TOATE sisteme solare”, dar cele care nu au uniune, acelea nu plătesc (în soluția de 100)

Foarte reușită problema PQ.
Problema Tribut a avut enunț greșit (încă are) și anume:
În „Date de ieșire” e scris „valoarea maximă a tributului pe care o va primi de la toate sistemele solare.” pe când sursa care afișa valoarea maximă a tributului pe care o primește doar de la uniuni comerciale lua AC și cea care socotea și sistemele solare WA. (Ar fi bine să corectați, măcar pentru arhivă).

p.s. Nasol că la Națională au fost probleme din alte concursuri. : )