10:55 AM cosmin: nu participi la IOI online?
10:56 AM mihai patrascu: parca e chiar acum, nu?
cosmin: da
acuma am citit 2 probleme
mihai patrascu: nu m-am uitat
cosmin: adica toate 3
si una nu o stiu face
mihai patrascu: trebe sa-l faci fix in timp sau ai mai mult
?
cosmin: si la una s-ar putea sa gresesc
cred ca fix in timp
mihai patrascu: ei, atunci se pare ca nu particip
sunt online prob?
cosmin:
http://infoarena.ro/forum/index.php?topic=2076.msg17350 mihai patrascu: adica e un link sau imi trebe cond
10:57 AM cosmin: rahat
cred ca trebuie cont
hai ca iti trimit problemele
10:59 AM mihai patrascu: care ecea mai grea?
]mi fpcui cont
imi facui cont
8 minutes
11:08 AM cosmin: cred ca aia cu sails
e mai grea
11:10 AM mihai patrascu: flood e triviala
cosmin: pai de ce
11:11 AM io am zis
ca tre sa faci de 2 ori
sweep line
si ai arbori de intervale
si structuri de multimi disjuncte
e ceva de lucru
mihai patrascu: eu cred ca intai as imparti segmentele in puncte de intersectie
sa nu am segmente intersectandu-se la mijloc
apoi ai un graf
gasesti conturul
cosmin: pai nu cred ca ai oricum
mihai patrascu: scosi
scoti
11:12 AM si repeti
e timp liniar
cosmin: chestii care se intersecteaza la mijloc
mihai patrascu: fara nici un line sweep
poti sa ai un T
n cate zice
dar il spargi in 3 segm
si e tot nr liniar de segmente
cosmin: si ce faci
parcurgi tot in drepata
mihai patrascu: apoi e prob pe grafuri
cosmin: la fiecare pas?
mihai patrascu: iei segm minim
11:13 AM cosmin: incerci sa mergi
inspre exterior?
mihai patrascu: parcurgi mergand cat mai in dreapta, da
cosmin: ca la infasuratoare?
mihai patrascu: exact
cosmin: pai scrie pe forum
mihai patrascu:
pai daca lumea participa poate n-ar trebui
cosmin: nush eu am primit o problema
mihai patrascu: oricum vreau sa ma gandesc la restul
cosmin: cand eram pe a 9-a
11:14 AM de genu asta
si nu mi-a placut
asa cu mers
in exterior
era peste puterile mele
si am ramas cu sechele
mihai patrascu: asta in particular e facuta sa nu fie gretoasa
ceea ce e bine
btw, nu trebe sa simulezi orele in ordine
faci toata simularea la cea mai din dreapta componenta
si apoi la urmatoare
11:15 AM recursiv
cosmin: dap
iese ceva similar cu dfs
11:16 AM mihai patrascu: da
cosmin: na oricum e facubila
da trebe sa fi atent
11:18 AM mihai patrascu: aliens nu e binary search?
11:19 AM imi scapa ceva?
cosmin: pai cum gasesti
cat e M
?
mihai patrascu: deci ai o celula rosie, nu
ah
acum citii prob mai bine
11:22 AM ba da, e simplu
determini prin binary search x1 si x2
astfel incat ai o tranzitie white-red la x1
si red-white la x2
11:23 AM nu neaparat prima tranzitie
adica pot sa mai fie si white si red intre x1 si x2
ei, si acuma x2-x1 este fie 5M fie 4M etc
ma rog, calculez prost
dar te prinzi
5 minutes
11:29 AM cosmin: mda
bine zici
eu vorbeam prostii pe forum
9 minutes
11:38 AM mihai patrascu: bai sunt bou
iti dai seama ca ordinea orizontala nu conteaza la sail...
11:39 AM cosmin: da nu prea conteaza
adica nah conteaza un pic
ca daca pui un sail la x
atunci nu mai ai mai tarziu
atatea locuri pt x
mihai patrascu: ordinea orizontala, da?
11:40 AM vreau sa zic ca poti sa incepi prin a rearanja catargele cum ai chef
cosmin: tre sa partitionezi chestia aia
ah da
misto
le sortezi
dupa inaltime
11:41 AM mihai patrascu: ceva de genul... nu sunt 100% sigur ce faci in continuare
11:43 AM fie S[h] = nr de sails la inaltimea h
costul e functie de vectorul S evident
si poti presupune ca S e sortat descrescator
11:47 AM deci costul optim e cam asa
11:48 AM iei h=inaltimea max
daca nr catarge la inaltimea h * h >= nr total de sailuri, problem solved --- bagi media la toate inpltimile
11:49 AM daca nu, bagi nr max de sailuri posibile la inaltimea asta
si continue
11:50 AM ca sa poti sa decrement cu 1 nr de sailuri de la toate catargele de inaltime >=h, folosesti un binary tree deasupra
si faci fiecare pas in lg n
(poti sa sortezi catargele dupa inaltime, cum ziceam)
s-ar putea sa poti face lg n si mai simplu cu mai multe observatii
11:51 AM dar asta merge
cosmin: stai
deci tu zici de inaltimea h * h?
sau de inaltimea h?
11:52 AM ah am inteles
mihai patrascu: deci uite, costul e convex
cosmin: vrei sa pui h chestii
pe fiecare nivel
mihai patrascu: si daca poti pune media peste tot te-ai scos
cosmin: ca atunci se minimizeaza suma aia
si sa umplii nivelele
mihai patrascu: daca nu poti pune media la inaltimea max
cosmin: da cu maxim nu prea inteleg
mihai patrascu: pui cat poti
si repeat
cosmin: ah
ok
am inteles
sigur merge asta?
11:53 AM mihai patrascu: pai lemma: daca poti pune media la inaltimea max, poti pune media peste tot si asta e optim
cosmin: iti trebe un heap
in care tii
cat mai ai de pus
pe fiecare catarg
11:54 AM si nu cred ca iti trebe
arbore binar
doar heapu asta e deajuns
si un delta x
mihai patrascu: mda, doar ca daca update fiecare catarg la fiecare pas e cam naspa
cosmin: cat tre sa scazi din toate
adica
mihai patrascu: pot sa fie 100k^2 sailuri
cosmin: la momentu asta
ai
pe catargu i
cat e in heap
- deltax
care e egal pt toate
11:55 AM care sunt inca in heap
mihai patrascu: vrei sa scazi unul din toate catargele la h>=h curent
si apoi cele care se golesc sa le elimini
cosmin: mda
pai stai
tu nu bagi
mihai patrascu: deci vrei sa scazi 1 din primele n-spe
cosmin: catarge in heap
decat in ordinea
inaltimii
mihai patrascu: (sortate)
cosmin: si pornesti de la ordine mare
la ordine mica
si atunci tot timpu
scazi din toate din heap
mihai patrascu: dar ocazional devin zero unele
si trebe sa le scoti
cosmin: ceva
11:56 AM pai sunt in varfu min heapului
care sunt 0
mihai patrascu: e o problema 2D
cosmin: adica care sunt val - deltax
esti sigur?
mihai patrascu: vrei sa faci -1 la toate catargele cu o anumita inaltime
dar nu au acelasi nr de sailuri
unele vor ajunge la 0 si trebe eliminate
cosmin: pai daca mergi de la inaltime mare
11:57 AM la inaltime mica
hai sa luam un exemplu
cu inaltimi
5 3 1
mihai patrascu: si sails
cosmin: si nevoi 2 3 1
mihai patrascu: 1 2 1
cosmin: ok
mihai patrascu: ok
cosmin: ok
bagi (5, 1) in heap
scazi din heap 1 la pasu curent
11:58 AM mihai patrascu: aaaaa
cosmin: o sa ai (5, 1) si delta x
mihai patrascu: heap dinamic
cosmin: = 1
mihai patrascu: mai si bagi chestii
bingo
cosmin: acuma delta x - topheap = 0
scoti pe 5
mihai patrascu: eu simulam toata chestia cu o structura clasica
cosmin: pai stai ca e clasic
mihai patrascu: si evident una din dimensiunile mele era timpul
cosmin: adica nush
le inserezi
dupa inaltime
mihai patrascu: clasica -> statica
cosmin: deci la pasu x
11:59 AM ai in heap
mihai patrascu: ma prind ce faci
cosmin: chestii de inaltime > x
mihai patrascu: e ok
cosmin: daca lema e buna
mihai patrascu: cum ziceam eu b[gam timpul ca dimensiune in mod inutil
cosmin: atunci e super lejer de implementat
12:00 PM mda
sunt facubile problemele
mihai patrascu: sa zicem ca sunt k sailuri la inaltime max
si media e mai mare ca k
12:01 PM atunci intr-o sol daca pui mai putin de k la inaltime max
atunci poti improve mutand in sus
12:02 PM cosmin: mda
zici bine
12:03 PM baga pe forum
mihai patrascu: toate prob?
hai macar sa scriem amandoi
sau facem copy paste din discutie
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena