|
Titlul: 235 The Queen Scris de: Andrei Grigorean din Decembrie 07, 2007, 18:22:55 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? Titlul: Răspuns: 235 The Queen Scris de: Cosmin Negruseri din Decembrie 07, 2007, 18:33:37 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.
Titlul: Răspuns: 235 The Queen Scris de: Andrei Grigorean din Decembrie 07, 2007, 21:18:07 Pai asa fac si eu dar cum scoti O(N^2)?
Titlul: Răspuns: 235 The Queen Scris de: Cosmin Negruseri din Decembrie 07, 2007, 21:36:38 Ca si la car ... Sau daca schimbi masina cu regina nu mai merge treaba e diferita problema? ;)
Titlul: Răspuns: 235 The Queen Scris de: Andrei Grigorean din Decembrie 07, 2007, 22:09:51 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. Titlul: Răspuns: 235 The Queen Scris de: Cosmin Negruseri din Decembrie 08, 2007, 01:54:07 Nu vad care e diferenta ... si de unde iti apare constanta mare
Care e treaba cu ursuletu? Titlul: Răspuns: 235 The Queen Scris de: Andrei Grigorean din Decembrie 14, 2007, 23:58:18 Iti cumperi un ursulet, si inainte sa pui o intrebare stupida pe forum, i-o adresezi ursuletului. Astfel, poti evita multe intrebari inutile.
|