305 Triplete

[•DITzoneC]

Aici puteţi discuta despre problema Triplete.

[•anamaria1]

va rog frumos imi puteti spune ce are atat de special ultimul test?e singurul caz care imi da incorect

[•wefgef]

Unele variabile trebuie declarate unsigned int (sunt mai mari de 2 miliarde). Ai grija de asta?

[•peanutz]

Vezi ca e unsigned long int....

[•bogdan2412]

in gcc int = long int...

[•pocaitu]

  Exista vreo functie care returneaza in O(1) nr de biti de 1 ai unui nr ?

[•wefgef]

Eu nu cunosc o astfel de functie sau macar un algoritm care sa faca asta. Poti in schmb sa faci o preprocesare si sa raspunzi in O(1).

Exista totusi posibilitatea sa afli in O(nr_de_biti_de_1) folosindu-te de operatii pe biti.

[•amadaeus]

  Exista vreo functie care returneaza in O(1) nr de biti de 1 ai unui nr ?

Numarul de biti de 1 se numeste Hamming weight. Il poti calcula in O(log N), cu o masca pe biti, sau cu niste formule dubioase in timp (aproape ) O(1). Vezi http://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation

[•devilkind]

la problema asta daca (,) calculezi numarul de biti de 1 al unui nr in log n e prea mult. Iti trebuie o(1). Cel mai bine e cu prepocesare cum a zis si andrei grigorean.

[•peanutz]

Daca numeri bitii de 1 normal ajungi tot la complexitatea intiala.. E chiar absolut necesar sa faci precalculare? Nu mi se pare normal sa faci precalculare la o problema ca sa iti intre in timp. Mai ales ca daca ai lucra pe 16 biti ajungi si pe la numere de 5 cifre..

[•astronomy]

Precalcularea o poti face in 2 linii de cod:

Cod:

for(i = 1; i < N; i++)
    cnt[i] = cnt[i>>1]+(i&1);

unde cnt[ i ] = numarul de biti de 1 a lui i

[•peanutz]

A, precalculare in  program, gata, m-am prins, sorry

Later edit: wow, chestia chiar merge si e tare, merci mult

Nu vad ce gresesc... cat va da pe testele

test1

Cod:

6 10
1 2
2 3
1 3
6 1
6 2
6 5
4 5
4 6
3 4
2 4

test2

Cod:

5 9
1 2
2 3
3 4
4 5
5 1
2 4
2 5
1 4
1 3

test3

Cod:

14 20
1 2
1 3
1 4
3 5
3 4
2 3
9 5
5 6 
9 6
6 7
7 9
10 9
7 10
11 12
12 14
1 13
13 2
14 13
14 12

[•pauldb]

Nu era bun executabilul cu care am rulat:

5
7
6 [Pe testul corectat]

[•peanutz]

si pe testul 1

Cod:

6 10
1 2
2 3
1 3
6 1
6 2
6 5
4 5
4 6
3 4
2 4

ce alte triunghiuri mai sunt inafara de urmatoarele:

2 4 6
1 2 3
2 3 4
4 5 6
1 2 6

Cred ca ti-a dat gresit(sau numeri fiecare triunghi de 3 ori...)


Testul 3 e gresit ca se repeta 12 14, daca stergeti ultima muchie si puneti m 19, ar trebui sa dea 6, nu?

[•vlasceanu]

Daca ati folosit matrice ati reusit  sa aveti memorie pentru ultimul test? daca da imi spuneti si voi cum ati facut ca eu nu reusesc deloc sa intru in ultimu test prin metoda asta.