In romana ii zice ucenic 

Doar 18 rosii .... Cam reflecta realitatea!
Poate ar merita si cei cu rating peste 1000 o culoare separata.

Tocmai revenisem la rosu si acuma iar is galben. Uff!

La swaps am obtinut o recurenta de genu f (p) = a * f (p-1) + b, care se rezolva asa:

f (p) = f (0) * a^n + b * ((a^n) - 1) / (a - 1)

si care se poate calcula cu exponentiere in timp logaritmic fara matrice  

Mie mi-au placut problemele, chiar daca am busit controlor (cum sa calculezi gresit memoria? In loc de vreo 5-6 mega cum calculasem aveam vreo 20 si ceva).
Bravo, tuturor!

[caracted]

Pe fiecare linie, primul caracter de pe linie trebuie sa fie prima litera a unui cuvant, iar ultimul caracted de pe linie trebuia sa fie ultima litera a unui cuvant (presupunand ca pe un rand incap mai mult de doua cuvinte).

Nu ar fi mai corect, cel putin doua cuvinte (sau mai mult de un cuvant)?

Poate te ajuta daca te uiti la cazuri in care trebuie sa pui si egal in loc de mai mare sau mai mic strict.

Pe care varianta mi-o recomanzi sa o folosesc pe la concursuri?

Depinde de ce ai nevoie. In general, pe infoarena, se foloseste clasa vector pentru a stoca listele de adiacenta (desi cuvantul "liste" ne duce cu gandul sa folosim chiar o lista - care este si ea implementata in STL).

Am incercat sa stochez graful prin liste de adiacenta numai ca nu reusesc - vreau sa le tin ca o multime sa le gasesc mai usor.

De ce ai nevoie sa "gasesti" un nod? Eu nu am avut niciodata nevoie sa folosesc set pentru a memora grafuri, dar cine stie?

Cum memorezi grafurile, decizi in functie de problema. Dar in general e ok daca folosesti vector.

Am implementat eu cu iterator, un dfs ce ia O(n+m) (am folosit codul tau): http://infoarena.ro/job_detail/686376

Varianta cu set, cum ai scris-o tu are complexitatea de O(n^2 log n). La fel ca si la dfs cu matrice de adiacenta, atata doar ca la set iti ia O(log n) pe accesarea elementului a de i si j fata de O(1) la matrice. Incearca sa o scrii cu un iterator pe set.

Si apropo, daca scrii asa nu declari o lista:

Cod:

vector<int> v;

Lista nu permite accesarea celui de-al k-lea element in O (1). In schimb lista permite adaugare/stergerea unui element in O (1) (aici nu intra si cautarea elementului).
Clasa Vector permite accesarea unui element in O (1). Dureaza O (n) sa stergi sau sa adaugi un element dintr-o sau intr-o pozitie oarecare.
Asa ca clasa Vector seamana mai mult cu un array (un sir obisnuit) decat cu o lista. Ce are in plus fata de un sir obisnuit e faptul ca dimensiunea lui e dinamica (se poate schimba in timp), mentinand complexitatile pentru inserare, stergere si random access la fel ca la sir. Dezavantajul la vector e ca pot exista elemente care desi sunt alocate nu sunt folosite. Adica, in orice clipa, un vector e un sir care are alocata memorie pentru capacity () elemente; ceea ce va da size () e numarul de elemente folosite din vector. In momentul in care size ()== capacity () si inserati un nou element, se aloca o noua zona continua de memorie, care poate fi de 2*capacity (), si se copiaza toate elementele vectorului in noua zona, si se adauga noul element inserat la sfarsit. Apoi se elibereaza vechea zona de memorie. Inserarea ia astfel, pentru un numar mare de elemente O (1) si din cand in cand ia O (n), dar per total, pentru a insera n elemente ia O (n), astfel se zice ca inserarea ia O (1)/element. Ceva de genu e si cu stergerea.


http://en.wikipedia.org/wiki/Sequence_container_(C%2B%2B)#Vector

Poti vedea si codul stl aici. Ca sa vezi inserarea trebuie sa te uiti in stl_vector.h la

Cod:

void push_back(const _Tp& __x) {
    if (_M_finish != _M_end_of_storage) {
      construct(_M_finish, __x);
      ++_M_finish;
    }
    else
      _M_insert_aux(end(), __x);
  }

si

Cod:

template <class _Tp, class _Alloc>
void 
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x) {
//codul il iei de pe dowload stl
}

Dintre cei care ati citit/v-ati uitat peste Programming Pearls de Jon Bentley, care credeti ca e mai buna, prima sau a doua editie?

Eu am cautat a doua editie pe net si am gasit doua variante (link mai jos). A doua pare publicata mai recent (dec. 2006). Este vreo diferenta intre cele doua de mai jos (in afara de data publicarii - diferente de continut)?

http://www.amazon.com/Programming-Pearls-Joe-Bentley/dp/8177588583

http://www.amazon.com/Programming-Pearls-2nd-Jon-Bentley/dp/0201657880

P.S.: Se mai gaseste cartea Programarea in limbajul C/C++ pentru liceu. Volumul al III-lea pe undeva? Am cautat-o pe net si nu am gasit-o. Daca stiti ceva librarii sau magazine unde se gaseste va rog sa imi spuneti.

Multumesc

Super super!

Duminica dimineata e mai ok, in 26 e mai ok. Dimineata e mai fresh lumea.

P.S.: Corectati poll-ul.

[de ce]

In solutia mea, r este 2^(1/65536), iar p este logaritm in baza r din x. Adica r^p=x adica logaritm in baza 2 din x e p/65536.

P.S.: Precizia e de 4 zecimale pt ca 65536 > 10000. Ca sa ajung la solutia mea de la faptul ca raspunsul poate fi scris ca fractie zecimala cu 4 cifre sau ca p/10000, unde p e intreg. am folosit 65536 pentru ca 2^(1/65536) e mai usor de calculat decat 2^(1/10000) (faci radical de radical de radical ... din 2).

Edit:

Mie imi  place solutia cu ln(x)=2ln(sqrt(x)) si ln(x)=x-1 pt x apropiat de 1 - e geniala. Din pacate am auzit destul de multi oameni care ziceau chestii de genu': daca ii problema de mate eu nu o stiu face. De-aia imi place solutia asta. Omul care foloseste solutia asta nu se teme de mate si cred ca ar trebui promovata mai mult gandirea matematica la info. Tin minte ca la noi la liceu se preda algoritmul cu planificarea spectacolelor (ala din capitolul greedy din Cormen) fara demonstratie. Adica profesorul le zicea ca solutia e asa: sortati intervalele de timp in care se pot tine spectacolele dupa terminare si apoi luati greedy intervalele. Fara sa se explice de ce merge (ca de-aia se fac demonstratii, nu? ca sa se observe ca ii adevarata o teorema - in cazul nostru ca algoritmul functioneaza sau ca are timpul de executie nu stiu cat si nu stiu cate altele). Si alti algoritmi erau tratati la fel (imi vin in minte acuma aia de grafuri: Kruskal, Dijkstra, ...).

Cred ca se intelege ca vreau sa zic ca matematica nu promoveaza invatarea algoritmilor pe de rost ci intelegerea lor, nu?

96 caractere; din pacate nu merge decat pentru x > 1.

Cod:

double log(double x){double p,r=1.0000105766425498,t;for(p=0,t=r;t<x;p+=1,t*=r);return p/65536;}

Ceea ce ai tu acolo nu e eroare, e doar un avertisment! Functia fscanf returneaza numarul de obiecte citite daca citirea s-a executat cu succes. De aici:http://www.cplusplus.com/reference/clibrary/cstdio/scanf/

On success, the function returns the number of items successfully read. This count can match the expected number of readings or fewer, even zero, if a matching failure happens.
In the case of an input failure before any data could be successfully read, EOF is returned.

Probabil ca tu nu folosesti valoarea returnata de fscanf si atunci iti atrage atentia asupra acestui lucru. Programele ruleaza chiar daca au primit avertismente la compilare, spre deosebire de erori.

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

E intr-adevar nevoie de main? Stiu ca daca nu avem main, vom primi o eroare de genul "entry point must be defined". Dar pare ca nu e nevoie de aceasta functie intotdeauna.

Si daca avem urmatorul cod:

Cod:

int glob = 2;
int glob2 (3);
class A {
public:
  A () {
      glob = 4;
      glob2 = 5;
  }
};
class B {
public:
  B () {
      glob = 6;
      glob2 = 7;
  }
};
A a;
B b;
int main () {
  cout << glob << " " << glob2 << endl;
  return 0;
}

Ce va afisa? Intotdeauna? Adica constructorii se executa secvential, pe rand, de sus in jos? E garantat asta de standard? Ar fi greu de transformat C++ ul intr-un limbaj concurent sau paralel cu bucati care se executa garantat secvential? Ca si sintaxa, eu cred ca ar putea ramane la fel, atata doar ca Definirea  variabilelor sa se execute concurent - la fel si instructiunile din main. Voi ce credeti?

Dragute problemele - si parca putin mai usoare decat la runda precedenta. Felicitari tuturor!
Cateva observatii as vrea sa fac totusi:
Ar putea sa se strecoare in enunturile problemelor, la fel cum se facea mai demult, si unele definitii:
De exemplu la problemele de azi se putea introduce definitia pentru subsecventa, subsir, lant ...
Am gasit definitii ale lantului care ziceau ca ordinea muchiilor nu conteaza si atunci cred ca era alt raspuns pe exemplu la problema kgraf.
Definitia era asa: un lant e o secventa de muchii u1, u2, ..., uk cu proprietatea ca ui si u(i+1) sunt arce incidente (orientarea nu conteaza).

Cateva observatii/sfaturi legate de codare:
1.Daca avem:
set <int> s;
s.upper_bound(2) e O (logn), pe cand upper_bound (s.begin(), s.end (), 2) e O (n)
2.Nu schimbati niciodata chestii in ultimele minute si resubmitati - eu asa am pierdut 85 de puncte la SecvMin

Edit:
Am gasit de ce erau 85 si nu 100 de puncte. In loc sa iau lungimea minima dintre toate lungimile subsecventelor "stranse" care contineau sirul respectiv ca subsir, luam lungimea ultimei subsecvente. Ceea ce inseamna ca pe 17 din 20 de teste raspunsul era dat chiar de ultima potrivire a lui b in a si daca porneai cu potrivirea de la sfarsit la inceput luai 85 chiar daca faceai destul de prost. Poate ar trebui revizuite testele. Sau macar pe viitor sa incercati sa nu puneti ultima solutie gasita cu back din spatiul de solutii, chiar daca vreti sa scoateti cu TLE solutiile slabe.(ci penultima )

The most beautiful quicksort I've never written:

Cod:

quicksort  []           =  []
quicksort (x:xs)        =  quicksort [y | y <- xs, y<x ]
                        ++ [x]
                        ++ quicksort [y | y <- xs, y>=x]

Incearca sa comanzi aici: http://www.byblos.ro/search/?next=1&pg=book&isbn=9739753477
Daca iti vor raspunde cum ca nu mai au, poti sa mai cauti alte magazine online sau poti sa iei una folosita de la colegi, prieteni sau chiar membri ai comunitatii infoarena care nu mai doresc acea carte.

Oare acest articol mai are sens? Acum ca nu se mai foloseste Borland C++ 3.1 la judeteana, nu cred ca mai are rost.

[(metoda? pentru ce)]

Sunt persoane care chiar vreau sa te ajute. Ajuta-le si tu pe ele! Scrie clar ce ai de intrebat, ca sa nu trebuiasca sa se chinuie sa inteleaga ce vrei sa spui. Desigur ca majoritatea au inteles ce ai vrut sa spui (pentru ca au ghicit - nu pentru ca ai scris tu), dar sunt cazuri in care exista mai multe variante la "intrebarile" tale. E frustrant sa vrei sa ajuti o persoana si sa trebuiasca sa te chinui sa intelegi ce a vrut sa zica.

Am vazut de ceva timp (mai precis de cand s-a schimbat evaluatorul), ca pe compilatorul nou, daca citesc cu scanf, deschid fisiere cu freopen, citesc cu fread sau multe altele, imi da un warning cum ca valoarea returnata de functii nu este folosita (gen scanf returneaza nr. de elemente citite, freopen returneaza un pointer s.a.m.d). Eu am gasit o metoda (metoda? pentru ce), cu assert, dar alta nu vad. As dori sa-mi spuneti voi daca ati gasit alta

Eu cred ca tu vrei sa ai un vector cu trei valori intregi. Poti face asa:

Cod:

struct type1 {
  int a,b,c;
};
vector<type1> v;
type1 x;
x.a=2;
x.b=8;
x.c=1;
v.push_back(x);
cout << v [0].a << v [0].b << v [0].c << endl;
for (vector<type1> :: iterator it = v.begin (); it != v.end (); ++ it) {
  cout << it->a << it->b << it->c << endl;
}

Sau daca vrei sa le grupezi, dupa cum am dedus din scrierea ta:

Cod:

struct type2 {
  int a, b;
};
struct type3 {
  int a;
  type2 y;
};
vector<type3> v;
type3 x;
x.a=2;
x.y.a=8;
x.y.b=1;
v.push_back(x);
cout << v [0].a << v [0].y.b << v [0].y.c << endl;
for (vector<type3> :: iterator it = v.begin (); it != v.end (); ++ it) {
  cout << it->a << (it->y).b << (it->y).c << endl;
}

Sau cu structura pair din stl:

Cod:

vector<pair<int, pair<int, int> > > v;
pair <int, pair <int, int> > x;
x.first = 2;
x.second.first=3;
x.second.second=4;
v.push_back (x);
v.push_back(make_pair(5, make_pair(6, 7)));
cout << v [0].first << v [0].second.first << v [0].second.second << endl;
for (vector<pair<int, pair <int, int> > > :: iterator it = v.begin (); it != v.end (); ++ it) {
  cout << it->first << (it->second).first << (it->second).second << endl;
}

Sau poti sa-ti faci ceva similar structurii pair din stl:

Cod:

template<class C1, class C2>	struct pereche {
  C1 first;
  C2 second;
}
vector<pereche<int, pereche<int, int> > > v;
pereche <int, pereche <int, int> > x;
x.first = 2;
x.second.first=3;
x.second.second=4;
v.push_back (x);
cout << v [0].first << v [0].second.first << v [0].second.second << endl;
for (vector<pereche<int, pereche <int, int> > > :: iterator it = v.begin (); it != v.end (); ++ it) {
  cout << it->first << (it->second).first << (it->second).second << endl;
}

Daca ti se par prea lungi tipurile poti sa pui oricand un typedef:

Cod:

typedef vector <pair <int, pair <int, int> > > :: iterator vit;
for (vit it = v.begin (); it != v.end (); ++ it) {
  cout << it->first << (it->second).first << (it->second).second << endl;
}

Sau pe rand:

Cod:

typedef pair <int, int> pii;
typedef pair<int, pii> pip;
typedef vector <pip> vp;
typedef vp::iterator vit;
vp v;
pip x;
x.first = 2;
x.second.first=3;
x.second.second=4;
v.push_back (x);
v.push_back(make_pair(5, make_pair(6, 7)));
cout << v [0].first << v [0].second.first << v [0].second.second << endl;
for (vit it = v.begin (); it != v.end (); ++ it) {
  cout << it->first << (it->second).first << (it->second).second << endl;
}

Cod:

bitset<maxn> uz;
struct graf
{
	short int nod [2];
	graf *next;
};
graf *a[maxn];
short int cost[maxn],h[maxn];

Codul asta ia Accepted pe una dintre problemele de pe timus 

Cod:

#include <iostream>

using namespace std;

int main () {
    int a, b, c;
    cin >> a >> b;
    c = a + b;
    cout << c << endl;
    return 0;
}

Fisierele de intrare, respectiv de iesire sunt secv3.in, respectiv secv3.out si nu secv3.in.txt si nu secv3.out.txt

Nu ai voie sa deschizi alte fisiere decat cele indicate in problema si de aceea primesti SIGSEGV.