Por Costel si Livada

[•Impaler_009]

Aici puteti pune intrebari la problema Por Costel si Livada de la concursul ONIS 2015 Runda 1.

[•beer_team]

Ce vrei sa spui prin "Intersectia submultimii cu o linie a matricei este fie multimea vida, fie o secventa “conexa” (aceeasi definitie ca mai sus) de celule" ? 

[•The_Viper_The_Mountain_And_The_Imp]

Am adaugat o explicatie alternativa.

[•corul_barbatesc]

Restrictia numarul 3 nu e redundanta?

[•Impaler_009]

No comment.

[•UVT_CompilationTerror]

Nu era suficient O(N * M^2)?

[•DEFINEtelyEngineers]

Noua ne iesea din timp cu aceasta complexitate. Se pare ca comisia a vrut sa departajeze intre O(N*M^2) si O(N*M^2*log(M)) dar...

[•GG_Facil]

Eu am luat OK cu O(N*M^2) dupa foarte multe optimizari 

[•UVT_CompilationTerror]

 

[•DEFINEtelyEngineers]

Nu ni se pare normal sa se dea probleme în care trebuie sa optimizezi 2h astfel încât sa treci problema chiar daca solutia este cea corecta. Si la alte probleme sa se poata lua 100 cu brut. Este destul de incorect.

[•geniucos]

Ce complexitate ai?Mie mi-a intrat mai mult decat lejer fara nicio eficientizare.

[•DEFINEtelyEngineers]

O(N*M^2) este complexitatea. Pentru fiecare linie faceam 2 rmq.

[•geniucos]

Nu ma prind exact ce vrei sa spui.Dar solutiile normale n-aveau rmq...Totusi rmq inseamna inca un MlogM pe acolo...vezi sa nu fie M^2logM sau ceva

[•DEFINEtelyEngineers]

Nu apare log înmulțit cu M^2 nicaieri. Făceam rmq, ca sa găsesc maximul într-un interval de linii, respectiv de coloane. Preprocesarea se făcea în M*log(M) nu M^2*log(M).