Vrem sa te ajutam deci nu are rost sa te oftici.
Ideea la rezolvarea problemei e urmatoarea:
  Sortezi dupa z cutiile, acuma daca ai o cutie de indice i si una de indice j cu i < j atunci cutia i se poate cuibari in cutia j daca x < x[j] si y < y[j]. O rezolvare in O(n^2) ar fi simpla cu programare dinamica, astfel best ar fi lungimea celui mai lung sir de cutii cuibarite in care cutia din exterior e cutia i, dar o asemenea rezolvare e clar ca nu ar intra in timp.  best = max(best[j] | j<i , x[j] < x , y[j] < y) + 1 Pentru a rezolva problema ne gandim la dimensiunile cutiilor x si y ca niste puncte in plan iar la best ca si valoarea punctelor respective si asa am ajuns la o  problema de range search (adica o cautare pe intervale). Deci problema noastra se transforma in folosirea unei structuri de date ce contine puncte si valori pentru puncte, in care putem insera puncte si putem raspunde repede la intrebari de genul care este valoarea maxima a unui punct din structura noastra cu proprietatea ca x_punct < x_dat si y_punct < y_dat. Pentru ca dimensiunile cutiilor sunt in intervalul 1 .. N putem folosi pentru asta structura de AIB bidimensional, cu query time de O(log^2 n). Alte structuri care le-am putea folosi ar fi arbori de intervale, quad trees sau kd trees, toate trei structuri de date folosite in rezolvarea problemelor de ortogonal range search (cautare pe domenii ortogonale).

Problema se poate rezolva in O(n) memorie si O(N sqrt(n)) timp daca folositi KD trees.

De ce postezi la Traseu? Nu ai vazut regulile?

Pe topcoder gasesti ceva tutoriale pentru incepatori, si este si unul de geometrie: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=index

Da.

FARA COMENTARII

Tu te referi la algoritmu de gasire a fluxului maxim de cost minim cu cycle canceling sau ce vrei exact sa zici?

Sunt algoritmi de flux mai buni decat Edmons Karp dar ar trebui sa mearga simplu cu Edmonds Karp ... Tu cum gasesti drumurile de marire a fluxului? Cum iti reprezinti graful? O idee de optimizare e ca in cazul maririi dimensiunii muchiei maxime nu trebuie neaparat sa pornesti de la flux 0 ci poti sa pornesti de la fluxul anterior.

O(n) sau O(n log n) fara radix sort.

v-a placut fotbal de la ginfo?

Daca stiti C si nu participati pe topcoder pentru ca acolo aveti nevoie de C++, cititi de aici http://www.topcoder.com/pl/?&module=Static&d1=gicj05&d2=cpp

Faina idee parazite

De ce sortezi cand faci knapsack? Am mai auzit ideea asta da mi se pare aiurea chestia cu sortarea. Daca vrei sa citesti despre 0/1 knapsack e in ambele linkuri ce le-am pus mai sus.

Poti face si cu un arbore de intervale preprocesare si memorie O(n) si query O(log n).

Pai atunci orice problema de pe infoarena e rezolvabila in mai putin de 100^100 operatii, deci orice problema de pe infoarena e rezolvabila in O(1).

Doua tutoriale de pe topcoder:

http://www.topcoder.com/index?t=features&c=feat_040104

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Alta chestie ... Forumu asta are optiunea de a face un thread nou, cand aveti o intrebare noua faceti un thread nou pentru ca cei nou veniti curiosi in o anumita chestie sa dea un search si sa gaseasca threaduri interesante nu sa fie obligati sa citeasca un thread imens.

Cartea "Probleme de combinatorica si teoria grafurilor" de Ioan Tomescu , Bucuresti 1981 e de baza .. destul de multe probleme din cartea respectiva s-au dat nealterate la olimpiada nationala sau la lot deci daca vrei sa te pregatesti in combinatorica ai putea sa o parcurgi ... desi daca o faci nu e garantat ca faci orice problema de combinatorica si mie parcurgerea ei completa mi se pare ca cere multa vointa. Un exemplu de problema ar fi problema Siruri 23 monotone, ea a fost data la baraj in 2001 si la campion si acum e pe infoarena in cartea respectiva e problema 12.21.

Articol despre arbori indexati binar din ginfo: http://www.ginfo.ro/revista/13_1/focus.pdf

Nu e cu abs ...

O panta e reprezentata de abs(x1-x2) / abs(y1-y2) deci de a / b unde a si b sunt numere intregi, daca se foloseau numerereale pentru reprezentarea pantelor apareau erori de precizie deci mai bine se folosea reprezentarea ca fractii si pentru ca o fractie unica sa reprezinte o panta unica, fractia trebuia sa fie ireductibila deci a / b se simplifica cu cmmdc(a,b).

up up

http://www.bitwise.iitkgp.ernet.in/index.php dureaza 12 ore si se participa in echipe de doi, problemele de anu trecut au fost interesante si daca rezistati in fata calculatorului 12 ore e destul de faina experienta, limbajele acceptate erau C si C++.

Hai ca iti dau eu un hint mai serios:

  Fiecare bucata continua pe linie ce trebuie acoperita o transformi intr-un nod, fiecare bucata continua pe coloana o transformi intr-un nod, daca o bucata continua pe linie se intersecteaza cu una pe coloana atunci intre cele doua noduri exista o muchie, deci practic toate patratele ce trebuie sa fie acoperite sunt muchii intre nodurile din graful nostru. Este clar ca acest graf este bipartit. Acum noi daca punem o scandura orizontala pe un patratel nu are rost sa ocupam cu ea mai putin decat toata bucata orizontala din care face parte patratelul respectiv, la fel daca punem scanduri verticale. Pe graful nostru punerea unei scanduri orizontale este echivalenta cu selectarea unui nod dintr-o parte a grafului bipartit si acoperirea tuturor muchiilor ce pleaca din acel nod, la fel o scandura verticala e echivalenta cu selectarea unui nod din cealalta parte a grafului bipartit si acoperirea tuturor muchiilor care au un capat in acel nod. Deci problema noastra s-a transformat in selectarea unui numar minim de noduri intr-un graf bipartit astfel ca pentru fiecare muchie unul din capete e in multimea noastra. Aceasta este o problema clasica, numita suport minim in romana si minimum edge cover in engleza. Este NP completa in graf oarecare dar usor rezolvabila in graf bipartit. La concursul algoritmus s-a dat o asemenea problema numita Paznici (http://algoritmus.org/probleme/Probleme_Runda04.php) si rezolvarea are la baza teorema lui Konig care spune : Cardinalul unui suport minim intr-un graf bipartit este egal cu cardinalul cuplajului maxim. Deci rezolvarea se reducea la determinarea cardinalului unui cuplaj maxim in graful construit mai sus.

Din comunitatea info.devnet s-au calificat la runda urmatoare a turneului si au castigat cate un tricou:  fluffy_, wickedman,  algostorm si Cosmin.ro. Succes si in urmatoarele etape ale concursului.