+1

DA, sunt aceeasi persoana
NU, nu pot aparea amandoua in input

DA

Utilizatorii, DA

Da. Nu va exista un numar negativ de prieteni.

Asigura-te ca intelegi mai intai ce face algoritmul. Primul are complexitate logaritmica, al tau are complexitate liniara.

Gandeste-te la un algoritm echivalent recursiv

[tuple<int,double,string,...>]

Good stuff.

It's nice that we also have a standard container for constant sized, C-like, arrays:

Cod:

array<int, 3> arr = {1, 2, 3};
arr.size(); // it has the benefit that it knows its own size and stuff

Now introducing tuple<int,double,string,...>, which are like std::pair, but they can contain any number of elements. Yay, no more annoying custom structs or pairs of pairs of pairs gibberish.

And then there are hash_map and hash_set, which were previously only available in the ext directory, under __gnu_cxx.

Problema biperm, OJI 2013.

Primul test "totul corect", restul nimic in .out.
Curios, ma uit pe sursa, nimic gresit.

Foloseam stream-uri. Putine numere, complexitate mica, o secunda, nu iese din timp.
Observ ca am pus return 0; imediat dupa afisare, fara sa inchid fisierul.
.close() -> 100 pct
m**e eval!
Diferenta dintre 10 si 100. Diferenta dintre a te califica si a nu te califica la ONI.

Invatati din asta.

E mai usor sa incepi cu metoda top-bottom (memoizare). Vezi sfaturile mele de aici:

http://www.quora.com/Algorithms/I-want-to-learn-memoization-Can-you-give-me-some-links-with-problems-from-spoj-topcoder-codeforces

Fiind timpul atat de scurt, cel mai bine e sa faci, pe rand, probleme de aici: http://community.topcoder.com/tc?module=ProblemArchive&sc=7&sd=desc&maxd2s=&div2l=&cat=Dynamic+Programming&div1l=&class=&wr=&mind2s=&mind1s=&maxd1s=

Sunt ordonate in ordine crescatoare a dificultatii. Rezolva-le in practice room! (applet-ul topcoder il descarci din stanga sus unde e semnul "O(N)")

Am sursa asta pt problema "Copaci":

Cod:

#include <fstream>
#include <stdlib.h>
using namespace std;

struct punct
{
    long long x, y;
};
punct v[100001];

long long n,i,a,b;

long long cmmdc( long long a, long long b )
{
	long long r;
	while( b )
	{
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}


int main()
{
    ifstream f("copaci.in");
    ofstream g("copaci.out");

    f>>n;
    for(i=1;i<=n;i++)
    f>>v[i].x>>v[i].y;

    b=0;
    for(i=1;i<n;i++)
    b+=cmmdc(llabs(v[i].x-v[i+1].x),llabs(v[i].y-v[i+1].y));

     long long x1,x2,y1,y2;
    for(i=1;i+1<n;i++)
    {
        x1=v[i].x-v[0].x;
        y1=v[i].y-v[0].y;
        x2=v[i+1].x-v[0].x;
        y2=v[i+1].y-v[0].y;
        a+=x1*y2-x2*y1;
    }
    a=llabs(a*0.5);

    long long p=a-(b/2)+1;
    g<<p;
    f.close();
    g.close();
    return 0;
}

Obtin doar 60 de puncte, pe primele 4 teste iau WA. imi poate sugera cineva ceva?

trebuie sa iei si perechea (n,1)
adica in for i<=n unde v[ n+1 ] = v[ 1 ]

Cam asa eram eu in timpul rundei, nimic nu a mers.

Recursivitate infinita pe Google

scratch that, oricum nu era bine 

in ultimele 5 minute am incercat sa trimit sursa de cateva ori si nu ma lasa sa selectez concursul. verificati si prelungiti cu un minut va rog sa pot trimite

Thank you,

size() nu este inlocuit de o constanta, si nici nu este o valoare constanta, dar este calculata in timp constant.

Se poate folosi Functia abs() din cmath ? sau da eroare pe infoarena???

DA

Ar fi interesant daca la fiecare problema ar aparea cea mai eficienta sursa trimisa (in principiu ca timp). Adica daca timpul de executie adunat de la toate testele este cel mai mic, sursa respectiva sa fie considerata cea mai eficienta 

Sau mai degraba adaugata sortare dupa timp de executie/dimensiune sursa/memorie... 

poti sa pui conditie sa interschimbe doar daca sunt ambele pare, desi nu cred ca ti se garanteaza nimic.. mi se pare o idee mai buna sa faci altfel, de ex sortezi doar vectorul de numere pare si apoi reconstitui sau cum vrei

mda, pai aici trebuie sa te inveti si tu sa codezi frumos... din indentare parea ca if-urile alea 2 sunt separate

Se vede si din rezultate, problemele au fost dragute, s-au adunat puncte destul de usor, departajarea era de viteza  

Deci/practic good job Monthly staff!

Am incercat sa rezolv problema cu algoritmul lui Bellman-Ford (sursa ia 100 pct ) insa nu stiu de ce nu iau mai mult de 10pct aici ,pe restul testelor e incorect...
Daca aveti putin timp sa dati "o geana" pe cod as fi recunoscator

http://infoarena.ro/job_detail/724636?action=view-source

Aruncand un ochi rapid pe sursa ta, trebuie sa verifici/adaugi in coada vecinu' doar daca are distanta mai mica, pe cand tu ai if-ul ala in afara primului, baga-l inauntru.

S incape pe un intreg de 32 de biti cu semn.

Deci gandeste-te ca O(S) nu incape in timp 

Mai gandeste-te putin, o fac si eu acum si dupa iti spun complexitatea care mi-a iesit 

La finala merg primii 10 ?

Nu cobi!

Made my day  

Au fost minunate problemele... Spirala3 inca ma tine foarte interesat, vad ca nimeni nu a reusit sa gaseasca solutia
Anyway, astept solutia oficiala, felicitari organizatorilor

BTW, sper ca luati mai multi la finala de la clasele 11-12 ca ne-am straduit mai tare