Daca am un polinom in care P(-20) > 0, P(20) > 0 si P(0) > 0, de unde stiu in ce directie sa ma duc dup'aia? Am reusit sa fac problema, dar nu-mi dau seama cum merge pe acest caz. 

Cum se poate rezolva aceasta problema folosindu-te de un heap? Eu nu-mi dau seama de alta solutie in afara de greedy 

Nu stiam. Thanks! 

Asa este, am luat 100p daca parcurg linie cu linie. Imi poti explica, te rog, care este diferenta?

Mersi, asa este, alocam prea multa memorie si in plus parcurgeam matricea de 2 ori, in loc de o singura data. Dar la sursa asta ce este gresit: http://www.infoarena.ro/job_detail/965110?action=view-source ? Iau doar 70p desi folosesc doar matricea A si o parcurg o singura data 

Cred ca ar trebui marita un pic limita  . Am luat 100p doar cand am parsat, altfel iau doar 60p cu complexitate O(N+C^2+M).

Cand se va afisa programul rundei finale?

Cand se desfasoara runda finala?

Cred ca este gresit exemplul. In exemplu este data relatia (8, 1), adica clanul 8 nu poate face alianta cu clanul 1. Iar la explicatie scrie "Cele 4 clanuri care pot forma o alianta sunt 1, 3, 6 si 8.", adica 1 si 8 intra in alianta.

Di este intotdeauna mai mic decat 2*Pi*R?

Mersi, Alex! Problema nu mai pare asa grea acum.

Cum se rezolva problema aceasta?

Toate valorile folosite in operatiile de push vor fi numere intregi ≤ 10^6.
Sunt numai numere naturale sau pot fi si negative?

Eu am reusit sa obtin 80p la problema aceasta cu un algoritm destul de slab, dupa parerea mea: sortez intervalele dupa capatul din dreapta, si apoi cu un algoritm greedy verific cate intervale pot lua maxim astfel incat sa nu se intersecteze (fie K numarul maxim de intervale pe care le pot lua astfel incat sa nu se intersecteze); apoi am 2 cazuri:
1.in cele K intervale luate, am cel putin un interval cu valoarea maxima, deci afisez Z-ul cel mai mare si K
2.nu am niciun interval cu valoarea maxima si procedez in felul urmator: iau pe rand fiecare interval dintre cele cu valoare maxima si verific cate intervale trebuie sa scot din cele K astfel incat sa-l pot introduce pe cel ales acum, iar apoi compar cu maximul; deci afisez Z-ul cel mai mare si maximul.
Ceea ce e si mai ciudat e faptul ca in prima sursa pe care am trimis-o am facut o eroare destul de grava, care ar fi trebuit sa dea peste cap tot algoritmul: cand sunt in cazul al 2lea si aleg un interval cu valoare maxima, in loc sa-l compar cu cele K intervale deja luate, il compar cu toate intervalele (N) si verific cate ar trebui sa scot pentru a-l introduce pe acesta..ceea ce e evident gresit. De aici deduc ca majoritatea testelor nu au intervale care sa se intersecteze, sau au prea putine.

"valorile sirului sunt din intervalul [0,2^31]"
Daca la 2^31 adaugi ceva, nu depaseste int?
Dar asa e, se putea face si fara unsigned int.

Eu asa le-am declarat.2^31 + x ( 1 <= x < 300 ) depaseste int

Poate sa-mi explice si mie cineva ideea de la aceasta problema? Am stat tot timpul pe ea si n-am reusit sa-mi dau seama. Multumesc anticipat!

sunt curios care era solutia la subset2...  poate posta cineva ideea de rezolvare?

Eu am facut in felul urmator: un element x al carui rest prin impartirea la K este r nu poate fi pus in acelasi subset cu un element y al carui rest prin impartirea la K este K - r. Cele cu restul 1 nu pot fi puse in acelasi subset cu cele cu rest K-1, cele cu restul 2 nu pot fi puse in subset cu cele de K-2 etc. De aici se deduce urmatoarea idee: dintre toate elementele care au restul 0 prin impartirea la K poti pune intr-un subset doar un singur element (Evident, daca pui 2, suma lor % K = 0);  ai 2 cazuri:
1. daca K este impar, vei adauga in subset toate elementele care prin impartirea la K dau resturile 1, 2, ... K / 2 + un singur element care da restul 0. Pentru fiecare i de la 1 la N % K vei avea (N/K + 1) elemente care dau restul i, iar pentru fiecare i de la N%K + 1 la K/2 vei avea N/K elemente care dau restul i. Rezultatul va fi 1 (elementul cu restul 0) + Min(N%K, K/2) * (N/K + 1) + (K/2 - Min(N%k, K/2)) * (N/K).
2. daca K este par, vei adauga in subset 1 element care da restul 0 si 1 element care da restul K/2 (pentru ca daca adaugi 2, evident, suma lor % K va fi 0) si toate elementele care impartite la K dau resturile 1, 2, ... K/2 - 1. Similar primului caz, pentru fiecare i de la 1 la N%K vei avea (N/K + 1) elemente care dau restul i, iar pentru fiecare i de la N%K + 1 la K-1 vei avea N/K elemente care dau restul i. Rezultatul va fi 1 (elementul cu restul 0) + 1(elementul cu restul K/2) + Min(N%K, K/2 - 1) * (N/K + 1) + (K/2 - 1 - Min(N%K, K/2 - 1)) * (N/K).
Sper ca am fost destul de clar in exprimare

Felicitari pentru aceasta runda!  Toate problemele au fost reusite. Imi explica si mie cineva cum se face Ismquery?

asa este, in functia in care compar a^b cu x, imi depaseste unsinged long long int. mersi drastik

multumesc de ajutor, o sa incerc si aceasta metoda, dar vreau sa stiu ce este gresit in rationamentul meu

asta fac si eu..iau pe rand toti exponentii de la 2 la 60 (pot sa am 2^59 < 10^18) si cu cu ajutorul cautarii binare caut baza. daca am gasit o  baza a, astfel incat a^b = x (numaru' dat pentru acel test), verific daca a este prim; aici am 2 cazuri: a < 100 000 (verific in vectorul creat cu ajutorul ciurului) si a >= 100 000 (caut in vectorul v in care am numai numere prime < 100 000 daca exista vreun numar v astfel incat a % v = 0 => nu este prim, iar in caz contrar, este prim). nu mi-a intrat decat pe un test, restul wa

cum se rezolva aceasta problema?

pai si altfel cum putem afla clasamentul?