235 The Queen

[•wefgef]

http://acm.sgu.ru/problem.php?contest=0&problem=235

Ce complexitate aveti?

Eu m-am gandit la un O(N^3), dar se pare ca trebuie optimizat mult. Merge mai bine?

[•Cosmin]

Pare ca merge in O(n^2) daca gasesti 2 chestii pt fiecare celula: nr minim de mutari in care poti ajunge in celula, cu acest numar par si nr minim de mutari pentru a ajunge in celula cu respectivul nr impar. Si dupaia doar compari pt fiecare celula drumul cel mai scurt de paritatea lui m cu m, si daca e mai mic celula respectiva poti sa o atingi in m pasi.

[•wefgef]

Pai asa fac si eu dar cum scoti O(N^2)?

[•Cosmin]

Ca si la car ... Sau daca schimbi masina cu regina nu mai merge treaba e diferita problema?

[•wefgef]

Nu e chiar la fel, e naspa aici.

Asemanator cu rezolvarea de la car faceam si eu, insa din cauza ca nu e la fel aveam un O(N^3). M-am gandit mai bine acum, si cred ca o pot intr-adevar reduce la O(N^2)*o constanta maricica.

Mersi, sa vad maine dimineata poate iese .

P.S.: Ar trebui sa imi iau un ursulet.

[•Cosmin]

Nu vad care e diferenta ... si de unde iti apare constanta mare

Care e treaba cu ursuletu?

[•wefgef]

Iti cumperi un ursulet, si inainte sa pui o intrebare stupida pe forum, i-o adresezi ursuletului. Astfel, poti evita multe intrebari inutile.