Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 280 Trade centers  (Citit de 12946 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
silviug
Echipa infoarena
Nu mai tace
*****

Karma: 193
Deconectat Deconectat

Mesaje: 485



Vezi Profilul
« : 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?
Memorat

"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #1 : 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.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
mugurelionut
De-al casei
***

Karma: 209
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« Răspunde #2 : 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..
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #3 : Septembrie 05, 2007, 00:45:51 »

TLE cu O(N log Rezultat) :-"
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #4 : 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. Smile
Memorat
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #5 : 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  Very Happy
Memorat
silviug
Echipa infoarena
Nu mai tace
*****

Karma: 193
Deconectat Deconectat

Mesaje: 485



Vezi Profilul
« Răspunde #6 : 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  Cry
Memorat

"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines