DA

Aici puteti pune intrebari la problema Prietene

Aici puteti pune intrebari la problema Game4

Aici puteti pune intrebari la problema Suma6

Aici puteti pune intrebari la problema Mostenire2

Aici puteti pune intrebari la problema Lift

Aici puteti pune intrebari la problema Electoral

S-a reparat in final problema: acum are restrictiile initiale, testele input initiale si output-urile corecte. Problema e in arhiva.

Le-am adaugat acum..

Problema Colors a avut din pacate o gresela in sursa oficiala care a afectat teste in valoare de 20 puncte (testele 16-19 cu N peste 666013). Momentan testele respective au fost eliminate si problema reevaluata, iar limita N scazuta si in enunt la 500000 < (666013) fata de 1000000 cat era initial. Scuze celor care au avut batai de cap cu asta duminica (probabil 2 elevi, din fericire asta nu a afectat rezultatele de la concursul onsite).

E pus pe pagina principala de pe 2 martie 2017 20:06:49. Pagina concursului am adaugat-o insa de-abia ieri. Pe clubul de info am anuntat tot de joi, oricum, imi dau seama ca nu e foarte eficient dar alta metoda nu am avut.

Aici puteti pune intrebari la problema Escape

Aici puteti pune intrebari la problema Colors

Aici puteti pune intrebari la problema Reactor

Aici puteti pune intrebari la problema Hanoi2

Aici puteti pune intrebari la problema Palindrom4

Aici puteti pune intrebari la problema March

Solutia mea este urmatoarea:
Pentru fiecare pozitie x din matrice, putem precalcula maximul de deasupra (pe o linie cu indice strict mai mic) ce e la distana manhattan maxim orice putere a lui 2. Se formeaza o ‘piramida’ de genul:
000000000000
000010000000
000111000000  -> ‘1’ - casute la distanta maxim 4 fata de ‘x’
001111100000
011111110000
0000x0000000
O ‘piramida’ cu 2^k linii este reuniunea a alte 6 piramide cu 2^(k-1) linii. (stanga, dreapta, sus, una care are aceeasi baza si posibil mai raman doua zone dar care se poate deduce usor ca pot fi acoperite de alte doua 'piramide'.

Putem retine doar ‘piramidele’ cu numar de linii egal cu cea mai mare putere a lui 2 <= D, pentru fiecare casuta, apoi rezultatul se poate calcula in O(N * M * 6).
Complexitate O(N * M * log D).
Pentru elemente de pe aceeasi linie, se poate roti matricea si repeta tot algoritmul.


Din pacate au intrat solutii care nu trebuiau sa intre cu sortare sau altele, si unele din cele care aveau implementare cu RMQ / log luau TLE, desi am dublat timpul de executile al sursei mele.

Da. Asta se intampla si in exemplu.

1) Da
2) Da
3) Nu

Am sa completez si enuntul.

Trebuie afisat cu 4 zecimale ca in exemplu, am modificat enuntul.

Aici se pot pune întrebări legate de problema Fifty

Aici se pot pune întrebări legate de problema Permking

Aici se pot pune întrebări legate de problema Sokoban

Aici se pot pune întrebări legate de problema Trineq