Un dezavantaj fata de Pascal este faptul ca in C nu putem avea expresii de genul {@A[-100]@} unde $A$ este un vector. Dar acest lucru se poate remedia. Spre exemplu, daca vrem sa facem un vector $A$ cu elemente de la $-100$ la $100$ procedam astfel:

p(pre).
{@int A[201];@}

p(pre). {@int A[201];@}

{@#define A (A + 100)@}
h2. Fisiere de intrare si iesire
Folositi {@freopen()@} in loc de {@fopen()@} deoarece este mai comod, in special la concursurile in care intrare si iesirea sunt standard.

p(pre).
{@freopen("in.txt", "r", stdin);@}

p(pre). {@freopen("in.txt", "r", stdin);@}

{@freopen("out.txt", "w", stdout);@}
h2. Cautare binara (ideea originala de la Mihai Patrascu)
Urmatorul cod este de aproximativ $4$ ori mai rapid (am testat cu cautare binara ca in manual) , mai usor de inteles, mai flexibil si mai scurt... ce ati putea dori mai mult?

p(pre).
{@int N, A[N];@}

p(pre). {@int N, A[N];@}

{@int binary_search(int val)@}
{@{@}
{@    int i, step;@}

$H$ se calculeaza inainte sau poate fi constant
$T$ sunt tatii nodului si $N$ numarul de noduri

p(pre).
{@void DF(int n, int t2, int lev)@}

p(pre). {@void DF(int n, int t2, int lev)@}

{@{@}
{@    int i;@}
{@    T2[n] = t2, Lev[n] = lev;@}

Operatia de LCA se va realiza apoi foarte usor, urcand pe tatii din intervale, pana se ajunge la doua noduri in acelasi interval, apoi folosindu-se metoda clasica. Cod:

p(pre).
{@int LCA(int x, int y)@}

p(pre). {@int LCA(int x, int y)@}

{@{@}
{@    while (T2[x] != T2[y])@}
{@        if (Lev[x] > Lev[y])@}

for-ul in C/C++ este foarte flexibil si poate ajuta foarte mult in compactarea codului, deci si a timpului de implementare. In continuare vom prezenta algoritmul merge sort (sortare prin interclasare) scris in cateva linii (putine, zic eu!):

p(pre).
{@int N, A[N], B[N];@}

p(pre). {@int N, A[N], B[N];@}

{@void merge_sort(int l, int r)@}
{@{@}
{@    int m = (l + r) >> 1, i, j, k;@}

Consideram urmatoarea problema: se da un vector $A$ de $N$ elemente pe care se fac $M$ astfel de operatii: {@ADUNA(st, dr, x)@} - toate elementele cu indicii intre $st$ si $dr$ isi cresc valoarea cu {$x$}. La sfarsit trebuie sa se afiseze vectorul rezultat. In continuarea vom descrie o metoda care ne da un timp de rulare de $O(1)$ pentru operatia $ADUNA$ si $O(N)$ pentru a determina un element din vector. Vom construi un al doilea vector $B$ de $N+1$ elemente, cu proprietatea ca {$A{~i~} = B{~0~} + B{~1~} + ... B{~i~}$}. Astfel, o operatie {@ADUNA(st, dr, x)@} devine:

p(pre).
{@B[st] += x;@}

p(pre). {@B[st] += x;@}

{@B[dr + 1] -= x;@}
Da, este chiar asa de simplu! Pentru a determina un element A{~i~} vom aduna pur si simplu {$B{~0~} + B{~1~} + ... B{~i~}$}. Incercati pe foaie sa vedeti cum funtioneaza. Aceasta ideea poate fi extinsa si in doua dimensiuni, construind $B$ astfel incat $A{~i,j~}$ = suma subtabloului din $B$ cu coltul in ({$0, 0$}) si ({$i, j$}), astfel (pt. {@ADUNA(x1,y1,x2,y2,v)@}):

p(pre).
{@B[x1][y1] += v;@}

p(pre). {@B[x1][y1] += v;@}

{@B[x1][y2 + 1] -= v;@}
{@B[x2 + 1][y1] -= v;@}
{@B[x2 + 1][y2 + 1] += v;@}

Se stie (sau ar trebui sa se stie!) ca lucrul cu pointerii este foarte incet... astfel, cand retinem un graf rar (numar mare de noduri, numar mic de muchii) cu pointeri (vezi mai jos) incetinim foarte mult programul.

p(pre).
{@struct list@}

p(pre). {@struct list@}

{@{@}
{@    int n;@}
{@    struct list *next;@}

In contiuare vom prezenta o metoda care este de $3-4$ ori mai rapida (adica parcurgerile DF , BF sau altii algoritmi ruleaza de $3-4$ ori mai rapid cand graful este stocat astfel), dar are ca dezavantaj necesitatea de a citi de doua ori fisierul de intrare.

p(pre).
{@#include <stdlib.h>@}

p(pre). {@#include <stdlib.h>@}

{@#include <stdio.h>@}
{@ @}
{@int N, M, *G[N], Deg[N];@}

Sporul de viteza se datoreaza faptului ca se folosesc vectori in loc de pointeri si struct-uri. Daca ne permite memoria putem evita citirea de doua ori a fisierul prin pastrarea muchiilor intr-o lista de muchii si apoi, dupa calcularea gradelor, inserarea muchiilor in liste. Pentru a demonstra eficienta acestei metode faceti urmatorul test: implementati o sursa cu pointeri si struct si implementati un BF, apoi scrieti codul de mai sus cu urmatoarele modificari:

p(pre).
{@...@}

p(pre). {@...@}

{@for (i = 0; i < N; i++)@}
{@{@}
{@      G[i] = (int *) malloc((Deg[i]+1)*sizeof(int));@}

si implementati BF astfel:

p(pre).
{@void BF@}

p(pre). {@void BF@}

{@{@}
{@      int Q[N], ql, qr, *p;@}
{@      char U[N];@}

h3. Suma a doua numere mari

p(pre).
{@void add(int A[], int B[])@}

p(pre). {@void add(int A[], int B[])@}

{@{@}
{@      int i, t = 0;@}
{@      for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)@}

h3. Inmultirea unui numar mare cu un numar mic

p(pre).
{@void mul(int A[], int B)@}

p(pre). {@void mul(int A[], int B)@}

{@{@}
{@      int i, t = 0;@}
{@      for (i = 1; i <= A[0] || t; i++, t /= 10)@}

h3. Inmultirea unui numar mare cu un numar mare

p(pre).
{@void mul(int A[], int B[])@}

p(pre). {@void mul(int A[], int B[])@}

{@{@}
{@      int i, j, t, C[];@}
{@      memset(C, 0, sizeof(C));@}

h3. Scaderea a doua numere mari

p(pre).
{@void sub(int A[], int B[])@}

p(pre). {@void sub(int A[], int B[])@}

{@{@}
{@      int i, t = 0;@}
{@      for (i = 1; i <= A[0]; i++)@}

h3. Impartirea unui numar mare la un numar mic

p(pre).
{@void div(int A[], int B)@}

p(pre). {@void div(int A[], int B)@}

{@{@}
{@      int i, t = 0;@}
{@      for (i = A[0]; i > 0; i--, t %= B)@}

h3. Restul unui numar mare la un numar mic

p(pre).
{@int mod(int A[], int B)@}

p(pre). {@int mod(int A[], int B)@}

{@{@}
{@      int i, t = 0;@}
{@      for (i = A[0]; i > 0; i--)@}

AVL-urile sunt arbori de cautare echilibrati care au complexitate O(lg n) pe operatiile de inserare, stergere si cautare. Pentru mai multe detalii cautati cartea "Arbori" pe [2]site-ul doamnei profesoare Emanuela Cerchez. In continuare voi prezenta o metoda destul de simpla de a implementa aceastra structura de date in timp de concurs. Enjoy!

p(pre).
{@#define max(a, b) ((a) > (b) ? (a) : (b))@}

p(pre). {@#define max(a, b) ((a) > (b) ? (a) : (b))@}

{@#define geth(n) (n->h = 1 + max(n->l->h, n->r->h))@}
{@ @}
{@struct node@}