De ce daca fac infasuratoarea convexa si apoi calculez aria imi da gresit pe testele mai mari?

Am patit-o la un concurs cand trebuia sa faci infasuratoarea mai intai, si ma chinui sa aflu care e problema.

Subtil. Foarte subtil  

Da, are legatura si cu asta, dar chiar am patit-o, de asta mi-am adus aminte.  

Problema 2 – Sume

La concursul de programare organizat de Colegiul National de Informatica Piatra Neamt au sosit delegatii din N orase ale lumii. In pliantul  realizat de organizatori este marcata pozita geografica a fiecarei delegatii prin doua numere natural (abscisa si ordonata) corespunzatoare unui sistem de axe matematizat.
La inscrierea in concurs fiecare delegatie transmite organizatorilor o lista cu cinci numere naturale  x, y, a, b, c cu semnificatia urmatoare:
•   x - abscisa orasului de unde vine delegatia;
•   y - ordonata  orasului de unde vine delegatia;
•   a - numarul de elevi ai delegatiei ce participa la concursul grupei mici;
•   b - numarul de elevi ai delegatiei ce participa la concursul grupei mijlocii;
•   c - numarul de elevi ai delegatiei ce participa la concursul grupei mari;
Suma de lei alocata fiecarei grupe de concurs se determina astfel:
•   dublam aria poligonului convex de arie minima  ce contine in interior sau pe frontiera punctele pozitiilor geografice de unde provin participantii la concursul grupei respective obtinand numarul de lei alocat pentru premiile I, II, III si Mentiuni;
•   fiecare participant din concurs primeste 50 de lei pentru transportul local si 100 de lei pentru servirea meselor pe perioada concursului;
Cerinta
Determinati sumele de lei alocate fiecarei grupe de concurs.
Date de Intrare
Pe prima linie a fisierului de intrare sume.in se afla numarul natural N, reprezentand numarul de delegatii  participante la concurs. Pe fiecare din urmatoarele N linii se afla cinci numere naturale separate de spatii. Fiecare dintre aceste N linii caracterizeaza  o delegatie iar ordinea si sensul numerelor pe linnie este prezentata in enunt: x  y  a  b  c
Date de Iesire
In fisierul de iesire sume.out se vor scrie trei numere natural altfel:
•   pe prima linie un numar natural ce reprezinta suma de lei alocata grupei mici;
•   pe a doua linie un numar natural ce reprezinta suma de lei alocata grupei mijlocii;
•   pe a treia linie un numar natural ce reprezinta suma de lei alocata grupei mari;
Restrictii
•   4<= N <=500000;     0<= x, y <=30000;   0<= a, b, c <=9;
•   La fiecare grupa de concurs exista participanti din cel putin trei orase diferite;
•   Nu sunt doua delegatii din acelasi oras;

Exemplu
sume.in   sume.out
5
0 0 0 2 3
3 3 1 2 3
4 4 1 0 3
4 0 1 2 0
0 4 1 2 3   616
1224
1816

Timp maxim de executie/test: 1.0 secunde
Limite de memorie: total memorie disponibila 24 Mb.


Daca te uiti la rezultate la a 12-a ai sa vezi ca ala de pe locu 3(eu) a luat 20p cu greseala asta.

De ce daca fac infasuratoarea convexa si apoi calculez aria imi da gresit pe testele mai mari?

Am patit-o la un concurs cand trebuia sa faci infasuratoarea mai intai, si ma chinui sa aflu care e problema.

n^2 log n dar s-a luat 100 cu n^3

Ciudat, eu am avut O(N^3) si am luat 60p.

Un hint pentru O(N^2 * logN) ?

Care era complexitatea oficiala ?

Un luminis poate avea mai mult de 2 luminisuri alaturate ?

De ce o solutie cu set-uri care cauta la fiecare query pentru muchia curenta (x -> y), o muchie pusa anterior (a -> b) cu a maxim (a < x) nu este corecta?

Unde pot gasi subiectele si rezolvarile date la Lot in 2008(Neamt) ?

Daca le are cineva in posesie si mi le-ar putea transmite ar fi perfect.

Problema turnurilor din Hanoi (varianta generalizata s-a dat la Facebook Challenge - https://facebook.interviewstreet.com/recruit/challenges) - trebuia sa ajungi de la o configuratie initiala la una finala in numar minim de pasi.

There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.

A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.
At anypoint of time, the decreasing radius property of all the pegs must be maintained.

Constraints:
1<= N<=8
3<= K<=5

Eu am rezolvat-o cu un BFS pe configuratii - maxim 5^8 stari (le poti memora pe biti si pune intr-un set). Ca si complexitate ar fi O(K^N * log(K^N))...eventual cu niste hashuri poti scapa de log. Nu stiu daca exista complexitati mai bune, eu cu asta am luat punctaj maxim.

Cum se combina 2 submultimi de noduri ale unei multimi la problema asta? 
Nu imi dau seama cum sa combin solutiile pentru dinamica...

L.E.
Se pare ca avea legatura cu submultimile independente ale grafului.

Testele sunt bune? Pentru ca pe infoarena iau 100p si pe .campion 40p...

Daca vrei sa calculezei Bst[1][nod], nod fiind lca-ul unei perechi din cele M, nu trebuie sa separi nodurile de pe lant de celelalte?
Cum se face asta in timp logaritmic?

Un hint la problema asta?
Eu fac un lca intre nodurile ce trebuie unite, cu determinarea muchiei de cost maxim dintre cele 2 noduri. Apoi, daca hotarasc sa o sterg, refac arborele.

Complexitate : O(N*M)
Iau numai TLE si Killed by Signal

Cu algoritmii de RMQ ma gandesc ca nu ar functiona pentru ca se adauga si se sterg muchii, deci ar trebui un LCA dinamic.