995 Matrice3

[•Prostu]

Aici puteţi discuta despre problema Matrice3.

[•ciprianf]

Cod:

putem folosi un RMQ 2D a cărui construcţie prealabilă necesită complexitate timp şi spaţiu O(N^2 log^2 N)
(din articolul cu solutii)

Dar complexitatea nu este defapt N^2 log N?

Later Edit: greseala mea, intr-adevar este N^2 log^2 N

[•DraStiK]

Ma poate ajuta cineva și pe mine cu ceva sugestii sau cu un test mai cu chichiță?

Chiar nu îmi dau seama ce greșesc, rezolv ca si soluția oficiala cu RMQ 2D.

Mulțumesc anticipat.

[•wefgef]

Folosesti unsigned char in loc de char?

[•DraStiK]

Am folosit unsigned char cum mi-ai sugerat si BOOM ... am luat 100p.

Multumesc mult, am omis ca numerele in char intra doar pana la 127.

[•wefgef]

De fapt nu este specificat in standard daca char este signed sau unsigned. Depinde de compilator, asa ca ar trebui sa folositi tot timpul unsigned char pentru valori mai mari de 127.

[•Marker]

Stie cineva unde pot gasi un articol bine explicat despre RMQ 2D?

[•wefgef]

http://infoarena.ro/preoni-2007/runda-2/solutii Problema plantatie.

[•Marker]

mersi wef

[•Addy.]

Ma poate ajuta cineva cu un test mai mare la problema asta? Tot caut greseala, dar nu o gasesc.
Multumesc anticipat.

[•danalex97]

Un O( N*M*min(N,M) + Q * log Q ) intra , sau doar cu RMQ-uri se poate ?

La partea cu RMQ nu inteleg cum ar trebui facut   . Adica la solutii scrie ca RMQ-ul ocupa spatiu si timp de O ( N^2 log^2 N ). De ce si spatiu ? Nu inteleg cum este facut. Multumec anticipat.

[•tzipleatud]

Eu am implementat solutia cu RMQ 2D, si doar cu parsare a mers de 100 puncte. Fara parsare am luat 60 puncte pe ea. Cat despre RMQ, daca ai avea doar patrate in care faci query-uri ai putea tine o matrice RMQ[logN][N][N], dar datorita faptului ca faci query pe dreptunghiuri, ti o matrice RMQ[logN][logN][N][N], deci de aceea ai spatiu si timp O(N^2*log^2 N). RMQ[k][l][x1][y1] reprezinta maximul din dreptunghiul cu coltul stanga sus in (x1,y1), lungime 2^k si latime 2^l. Restul solutiei e explicata aici. Multa bafta!

[•danalex97]

Multumesc mult. 

[•StarGold2]

Daca s-ar putea mari limita de timp, adica nu mi se pare ok ca solutia de 100 puncte de complexitate O(N^2*logN^2 + QlogN) sa ia 60 si sa fie nevoie de parsare sa iei 100.

L.E: Wow, in 30 minute s-a si rezolvat problema 

[•klamathix]

Am dublat limita  .