Fa un back care sa iti afiseze toate solutiile pt n de la 1 la 20 de exemplu si gaseste un pattern.

Puteti testa solutiile aici.
Si pe infoarena s-a mai discutat legat de problema asta: link

Merge de 100 de puncte si un algoritm in O(V*sqrt(V)+E) - sursa.

Imi amintesc ca am citit in liceu despre arbori indexati binar intr-un articol din GInfo. Recent am dat de o problema la care vreau sa implementez structura aceasta de date. Astfel am ajuns sa imi pun urmatoarea intrebare: daca structura respectiva se numeste "arbore", atunci care sunt nodurile arborelui si care sunt relatiile de tata fiu; iar daca acest arbore este cu radacina, care este radacina?
Tare sunt curios - daca stiti, va rog, postati. In GInfo nu scrie despre asta. Poate mai facem putina lumina asupra acestei structuri de date si asupra modalitatii de alegere a unui interval.

Pe scurt(am schimbat doar indentarea):

Cod:

#include <stdio.h>
#include <stdbool.h>

int main(void) {

    unsigned long long n, i;
    bool ok = 1;

    (void) scanf("%llu", &n);

    if(n % 2) 
        for(i = 3; i * i <= n && ok; i += 2)
              if(n % i == 0)
                 ok = 0;
              else ok = (n == 2);

    if(ok) printf("DA\n");
    else printf("NU\n");

    return 0;
}

P.S.: Te ajuta sa iti setezi compilatorul sa iti dea toate warning-urile. Cand am compilat codul tau, am primit un warning care imi zicea sa pun braces "{}" ca sa evit un ambiguous else.

Dupa o cautare pe google am gasit destul de multe rezultate. Gandeste-te la o multime de curbe(marcate intr-un sistem de coordonate) si ca aceste curbe reprezinta niste ziduri inalte dupa care nu poti vedea nimic. Apoi gandeste-te ca te plimbi pe axa Ox de la minus infinit la plus infinit si te uiti pe o directie paralela cu Oy, sensul inspre y. Toate punctele pe care le vezi formeaza lower envelope. Pentru upper envelope, faci ceva similar pe o dreapta paralela cu oX, aflata undeva la infinit, doar ca de data asta te uiti in jos.
Putin formal lower envelope L = { (x,y)|x in R && (x,y) e pe o curba din cele date si y minim }
Edit: Si un link: http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Envelope_2/Chapter_main.html

Pentru a afla divizorii unui numar poti face asa:

Cod:

for ( d = 2; d * d <= n; ++ d ){
        if ( n % d == 0 )
                scrie d si n/d
}

Astfel in O(sqrt(n)) putem afla toti divizorii! Totusi atentie la patrate perfecte!(9, 16, ...)
Pentru descompunere in factori primi, putem face similar:

Cod:

k = 0;
for ( d = 2; d * d <= n; ++ d ){
        if ( n%d==0 ){     p [ k ]  = d; e [ k ] = 0; k ++;}
        while ( n % d == 0 ){
                e [ k - 1] ++;
                n/=d;
         }
}
if ( n > 1 ){p[k]=n;e[k ]=1;k++;}

Gandestete ce se intmapla cand n este prim!

Mie mi s-a parut foarte bun articolul de pe Topcoder, pentru RMQ si LCA. Pentru arbori de intervale ar trebui sa ajunga sa intelegi ideea din arhiva educationala.

Apoi mai ramane sa faci multe probleme cu fiecare.

Imi poate explica si mie cineva de ce este necesar ca n sa fie compus?
Daca avem n = 7 nu ar fi raspunsul 3 4?

La problema razboi, daca avem un nod izolat, raspunsul e
0
0 0
sau
0
0
?

Exista numere negative in fisierul de intrare?

Problema asta e intr-un concurs activ 

La problema "Sir" ( Runda a doua, problema a treia ), ce se intampla daca avem k < s? Afisam 0 sau x [ s ] + x [ s - 1 ] + ... + x [ k ] ?

L.E.: Cred ca este gresit putin exemplul la problema Sir. Raspunsul din explicatie difera fata de cel din fisierul de iesire. In explicatie e 10, iar in fisierul de iesire e 16.
L.L.E: Cum se adauga un membru unei echipe?

Noi promitem ca vom scrie solutii la toate rundele pana la Runda Finala.

O sa tin minte asta  
L.e.: Revin. Daca pot ajuta cu ceva sa-mi spuneti. Din pacate inca nu am gasit solutii la problemele care nu au scrisa solutia in articol asa ca nu pot sa le completez.

Am creat articolul pentru solutii aici: http://infoarena.ro/algoritmiada-2011/runda-3/solutii
Din greseala am creat paginile pentru runda 3 la runda 2, astfel ca urmatoarele pagini sunt in plus(imi cer scuze si rog adminii sa le stearga):

L.E.: Aici erau link-urile la paginile scrise aiurea. S-au sters paginile, am sters si linkurile.

Articolul cu solutii trebuie completat. Ii rog pe cei care au rezolvat o problema si au timp/chef sa completeze la solutii.

Din ce am vazut la problema asta sunt doua cazuri de "egal":

Primul:

Cod:

3
3 1
1 2
2 1 1

Si al doilea:

Cod:

9
5 2
2 6
4 2
3 7
9 3
8 3
3 1
1 2
2 1 3 1 2 2 2 2 3

Cu raspunsurile:

Cod:

1 2
1 1
1 1

si

Cod:

2 5
1 2
2 2
1 1
2 1
2 1
2 1
2 1
3 1

De data asta mi-au placut f mult problemele de la open. Mi se par f interesante, in special problema egal si problema subsir1000. Tare sunt curios cum se facea pb egal. Sper ca are o rezolvare "ad-hoc" si nu una cu ceva structura de date dubioasa.

P.S.: Sunt doar trei runde online anul asta? Eu ma asteptam la 4. Din mesajul de mai sus am inteles ca sunt doar 3.

Scuze de intarziere, dar in problema scrie ca numerele biletelor sunt intre 2 si N inclusiv, mai exact "Pe următoarea linie se afla N numere aflate în intervalul [2, N] reprezentând locurile preferate ale persoanelor."
Ce se intampla cand N = 1? La restrictii avem 1<=N<=100000.

Puteti vedea chiar aici pe infoarena la sectiunea articole, probleme cu numere lipsa.

Ai dreptate, am citit eu putin gresit. M-am gandit la o demonstratie a algoritmului. Pe scurt ar fi cam asa:
10^n da restul 1 modulo 9 pentru orice n numar natural. Fie a un numar natural mai mare ca 0. Atunci a=c0+c1*10^1+...+cn*10^n, iar restul lui a la 9 poate fi scris cam asa
a%9=(c0+c1*10^1+...+cn*10^n)%9=(c0+c1+...+cn)%9
De aici putem sa demonstram prin inductie ca cifra de control a lui a da acelasi rest modulo 9 ca si a ( pentru ca suma cifrelor  a unui numar este mai mica decat numarul respectiv ).

Pe site-ul dat de Mardare Rares sunt cateva greseli grosolane. Eu nu m-as lua dupa ce scrie acolo in locul vostru. Postul ala da o noua semnificatie a expresiei "algoritm naiv de implementare" a cifrei de control. Adica nu merge. ( Ma refer la algoritmul in O ( 1 ) ). Un simplu contraexemplu este 28.

L.E.: Scuze pentru dezinformare, m-am grabit si am citit modulo 10 in loc de modulo 9.

Poate cineva sa detalieze cineva solutia la problema asta, va rog, ca eu nu ma prind? ( Sunt foarte slab la capitolul asta )
L.E.: Mai exact m-ar interesa cum aflam cel mai apropiat punct de fiecare dintre cele n^2 drepte. M-am gandit la o sortare a punctelor dupa inaltime, ca mai apoi sa putem cauta binar(si mai apoi cu o optimizare in O(1)) punctul cu inaltimea cea mai mica fata de o dreapta data, dar functia distanta intre o dreapta si un punct nu pastreaza ordinea daca schimbam dreapta.

Declari un tablou pentru frecvente pe care il initializezi cu 0. Tabloul trebuie sa aiba indicii de la 0 la 9, deoarece frecv [ i ]  va fi frecventa cifrei i.
Din n iei pe rand fiecare cifra si ii cresti frecventa cu 1. Cea mai usor de accesat cifra e ultima ( cu n mod 10 ). O data ce ai terminat cu ultima cifra a numarului n, poti sa il imparti pe n la 10(impartire intreaga cu div parca; ceva de genul n = n div 10).  Acum ai penultima cifra a numarului n initial pe ultima pozitie a numarului n curent. Ii cresti frecventa si repeti algoritmul, eliminand pe rand ultima cifra din n. Numarul de cifre ale lui n este numarul de pasi facuti inainte de a ajunge la n 0. Trebuie sa descifrezi singur mesajul asta daca vrei sa intelegi problema. Sper sa te ajute.

P.S. Asta e de clasa a 9-a.

Postul despre numarul prim a fost util din punctul meu de vedere. Eu nu am observat ca e format din "el nombre del diablo" si din numarul ghinionist. Dar acuma ca s-a subliniat asta, am reusit sa retin un numar prim folositor la hashing(pana acuma trebuia sa-mi calculez unul). Concluzia: eu o sa folosesc numarul asta