Iata si ideea de rezolvare a problemei: Intuitia v-a spus probabil intr-o
secunda ceea ce mie mi-a spus la o saptamana dupa ce propusesem problema, si
anume ca daca lungimile celor mai lungi subsiruri crescatoare din A si B sunt
respectiv L1 si L2, atunci interclasand A si B in C putem obtine un subsir
crescator de lungime L3=L1+L2. Acum vom face un lucru neobisnuit pentru un
programator, adica demonstratia matematica:

1) Demnostram ca L3>=L1+L2. In cuvinte, putem intotdeauna obtine un vector
C cu un subsir de lungime L1+L2. Pentru a face aceasta, construim subsirurile
crescatoare maxime in A si B, care au lungime L1 si L2, le interclasam, si
adaugam la ceea ce rezulta celelalte elemente din A si B, respectand pozitiile
initiale in vectori.

2) Demonstram ca L3<=L1+L2, adica nu putem obtine prin interclasare un subsir
crecator mai mare decat L1+L2. Sa presupunem prin absurd ca ar exista totusi
un vector C cu un subsir de lungime L3'>L1+L2. Identificam efectiv elementele
subsirului. O parte din acestea, sa zicem in numar de L1' sunt din A, iar
restul, in numar de L2', sunt din B (desigur, L3'=L1'+L2').

Aceasta inseamna ca L1'+L2'=L3'>L1+L2. De aici deducem ca fie L1'>L1, fie
L2'>L2 (fie amandoua). Sa spunem ca L1'>L1. Aceasta inseamna ca vectorul A are
un subsir crecator de lungime mai mare decat L1, pe care am presupus-o maxima,
contradictie.

Punctul 1 al demonstratiei ne indica o metoda simpla de rezolvare. Punctul 2
al demonstratiei ne asigura ca aceasta metoda gaseste solutia optima si nu e
nevoie sa ne complicam. O schita a algoritmului ar putea fi:

- Identifica subsirurile crescatoare maxime in A si B, si retine indicii
  elementelor acestor subsiruri in doi vectori indA si indB.
- Interclaseaza elementele din multimile A[indA[i]] si B[indB[j]], cu
  1<=i<=L1 si 1<=j<=L2. De asemenea, dupa adaugarea lui A[indA[i]] in vectorul
  C, se vor adauga in C si toate elementele din A cuprinse intre indicii
  indA[i]+1 si indA[i+1]-1 (si similar pentru B)

Cam asta este. Eu nu mai stiu cand incep olimpiadele, am auzit ca se amana din
cauza grevei. Oricum, mult succes tuturor cand o veni momentul!