infoarena

infoarena - concursuri, probleme, evaluator, articole => SGU => Subiect creat de: Silviu-Ionut Ganceanu din Iulie 15, 2007, 19:55:02



Titlul: 280 Trade centers
Scris de: Silviu-Ionut Ganceanu din Iulie 15, 2007, 19:55:02
http://acm.sgu.ru/problem.php?contest=0&problem=280

Iau WA la testu 14. Stiti vreun caz mai dubios?


Titlul: Răspuns: 280 Trade centers
Scris de: Andrei Grigorean din Iulie 15, 2007, 20:02:37
Singurul caz special e cand ai un singur nod.

Nu ne dai mai multe detalii despre cum ai gandit-o?

Stiu ca eu faceam un df, si trebuia sa am grija la sfarsit daca marchez sau nu nodul de start.


Titlul: Răspuns: 280 Trade centers
Scris de: Mugurel-Ionut Andreica din Septembrie 04, 2007, 23:06:37
asa ca.. fapt divers.. greedy-ul de la problema asta, in varianta generalizata in care muchiile au lungimi >= 1 si fiecare nod are o "raza" diferita in care trebuie sa se afle un 'trade center' este chiar greedy-ul folosit in cautarea binara din cadrul solutiei de la problema "Breweries" pe care am propus-o la concursul de selectie ACM din Poli (http://acm.hdu.edu.cn/showproblem.php?pid=1837).

un pic ciudat ca inca nu a luat nimeni AC la problema aia.. oh, well..


Titlul: Răspuns: 280 Trade centers
Scris de: Andrei Grigorean din Septembrie 05, 2007, 00:45:51
TLE cu O(N log Rezultat) :-"


Titlul: Răspuns: 280 Trade centers
Scris de: Adrian Diaconu din Septembrie 05, 2007, 05:10:44
Nu este exact acelasi greedy, cel putin nu in vairanta in care l-am folosit eu.

Eu puneam in coada frunzele, parcurgeam si cand ajungeam ca pentru un nod sa ii parcurg toti vecinii(mai putin unul) il puneam si pe el in coada. La Breweries trebuie sa fac relaxarea pentru nodul din coada cu cel mai mic B[ i ], unde B[ i ] este distanta minima pana la un centru.

Deci complexitatea mea este O( N log N log Rez), dar si cu varianta O(N log Rez) luam TLE nu WA.

Nu prea stiu ce sa ii mai fac. :)


Titlul: Răspuns: 280 Trade centers
Scris de: Adrian Diaconu din Septembrie 05, 2007, 14:55:56
Dupa cateva explicatii din partea lui Muguel m-am lamurit si eu ca este bun si greedy-ul in O(n) si cu cateva optimizari si reparari de buguri am reusit sa obtin primul AC  :D


Titlul: Răspuns: 280 Trade centers
Scris de: Silviu-Ionut Ganceanu din Septembrie 10, 2007, 22:09:41
asa ca.. fapt divers.. greedy-ul de la problema asta, in varianta generalizata in care muchiile au lungimi >= 1 si fiecare nod are o "raza" diferita in care trebuie sa se afle un 'trade center' este chiar greedy-ul folosit in cautarea binara din cadrul solutiei de la problema "Breweries" pe care am propus-o la concursul de selectie ACM din Poli (http://acm.hdu.edu.cn/showproblem.php?pid=1837).

un pic ciudat ca inca nu a luat nimeni AC la problema aia.. oh, well..


Eu m-am prins ca era la fel, da dupa cum vezi n-am facut-o nici pe asta de pe SGU  :'(