|
Titlul: 995 Matrice3 Scris de: Stefan-Alexandru Filip din Martie 21, 2010, 15:31:24 Aici puteţi discuta despre problema Matrice3 (http://infoarena.ro/problema/matrice3).
Titlul: Răspuns: 995 Matrice3 Scris de: Farcasanu Alexandru Ciprian din Martie 23, 2010, 09:24:25 Cod: putem folosi un RMQ 2D a cărui construcţie prealabilă necesită complexitate timp şi spaţiu O(N^2 log^2 N) Later Edit: greseala mea, intr-adevar este N^2 log^2 N Titlul: Răspuns: 995 Matrice3 Scris de: Dragos Oprica din Martie 23, 2010, 15:16:57 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. :) Titlul: Răspuns: 995 Matrice3 Scris de: Andrei Grigorean din Martie 23, 2010, 15:55:15 Folosesti unsigned char in loc de char?
Titlul: Răspuns: 995 Matrice3 Scris de: Dragos Oprica din Martie 23, 2010, 16:38:53 Am folosit unsigned char cum mi-ai sugerat si BOOM ... am luat 100p. :yahoo:
Multumesc mult, am omis ca numerele in char intra doar pana la 127. Titlul: Răspuns: 995 Matrice3 Scris de: Andrei Grigorean din Martie 23, 2010, 16:53:09 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.
Titlul: Răspuns: 995 Matrice3 Scris de: Onicas Mircea din Martie 24, 2010, 09:36:16 Stie cineva unde pot gasi un articol bine explicat despre RMQ 2D?
Titlul: Răspuns: 995 Matrice3 Scris de: Andrei Grigorean din Martie 24, 2010, 11:04:58 http://infoarena.ro/preoni-2007/runda-2/solutii Problema plantatie.
Titlul: Răspuns: 995 Matrice3 Scris de: Onicas Mircea din Martie 24, 2010, 13:29:45 mersi wef :ok:
Titlul: Răspuns: 995 Matrice3 Scris de: Adrian Draghici din Februarie 09, 2011, 17:02:19 Ma poate ajuta cineva cu un test mai mare la problema asta? Tot caut greseala, dar nu o gasesc.
Multumesc anticipat. Titlul: Răspuns: 995 Matrice3 Scris de: Dan H Alexandru din Iunie 03, 2012, 13:18:25 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 :-k . 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. Titlul: Răspuns: 995 Matrice3 Scris de: Tudor Tiplea din Iunie 03, 2012, 23:21:36 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 (http://infoarena.ro/algoritmiada-2010/runda-4/solutii/matrice3). Multa bafta! :)
Titlul: Răspuns: 995 Matrice3 Scris de: Dan H Alexandru din Iunie 04, 2012, 14:01:20 Multumesc mult. :ok:
Titlul: Răspuns: 995 Matrice3 Scris de: Emanuel Nrx din Decembrie 04, 2015, 23:52:00 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. :ok:
L.E: Wow, in 30 minute s-a si rezolvat problema :shock: Titlul: Răspuns: 995 Matrice3 Scris de: Mihai Calancea din Decembrie 05, 2015, 00:15:39 Am dublat limita :).
|