Pagini: 1 [2]   În jos
  Imprimă  
Ajutor Subiect: Feedback Runda 3  (Citit de 13633 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
harababurel
Client obisnuit
**

Karma: 23
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #25 : Iunie 08, 2014, 21:20:23 »

Reborn
Putem utiliza o structura de date (de exemplu, arbore de intervale sau set) pentru a determina pentru fiecare casa care e cea mai din dreapta pozitie unde poate fi reinviat Tsuna folosind o singura arma.

Se poate rezolva etapa asta mai simplu dpdv. al implementarii, aplicand o interclasare a intervalelor in sir:
Cod:
sort(v.begin(), v.end(), cmp);

for(x=1, y=0; x<=n; x++) {
        while(y < int(v.size()) && v[y].first <= x) R = max(R, v[y++].second); //R = cel mai mare capat drept de pana acum
        rightmost[x] = (R < x)? 0:R;
}
Memorat
Vman
Echipa infoarena
Vorbaret
*****

Karma: 45
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #26 : Iunie 09, 2014, 21:23:10 »

Sliding Window
Parcurgem numerele si retinem ultimele D + 1 intr-un multiset. Cand inseram o valoare noua, cautam care e cea mai mare valoare mai mica sau egala cu ea si cea mai mica valoare mai mare ca ea. Astfel, putem actualiza raspunsul la fiecare inserare.
Complexitatea este O(N * logD).

De mentionat ca problema admite si o solutie O(N) O(NlogK) teoretic. Dau o bere sau 5GB pe Dropbox cui o scoate  wink
« Ultima modificare: Iunie 10, 2014, 00:46:49 de către Duta Vlad » Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #27 : Iunie 10, 2014, 00:28:21 »

Daca D = N atunci problema se reduce la distanta minima intre doua elemente ale sirului. Problema asta nu se poate rezolva mai rapid de O(N log N), deci faci ceva presupunere gresita Vlad.
Memorat
Vman
Echipa infoarena
Vorbaret
*****

Karma: 45
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #28 : Iunie 10, 2014, 00:35:26 »

Ai dreptate Cosmin, ceea ce vreau eu e de fapt o rezolvare O(N) pentru un K fixat. Deci O(NlogK) per total Smile
« Ultima modificare: Iunie 10, 2014, 00:46:20 de către Duta Vlad » Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #29 : Iunie 10, 2014, 00:59:41 »

Zi enuntul problemei pe care o vrei tu in O(n). Ca pot vedea mai multe interpretari.
Memorat
Vman
Echipa infoarena
Vorbaret
*****

Karma: 45
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #30 : Iunie 10, 2014, 01:32:12 »

pentru K fixat determinati daca exista 2 pozitii i, j (i < j) a.i.

| Ai - Aj | ≤ K
j - i ≤ D
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #31 : Iunie 10, 2014, 01:40:49 »

spoiler alert (selectati textul pentru rezolvare):

se pot asocia elementelor x chei cu valoarea [x / k], dupaia folosim un hash table si rezolvam in O(n):
daca exista mai multe valori cu aceeasi cheie problema e rezolvata,
daca nu putem verifica pt fiecare i cheile [x/k] + 1 si [x/k] - 1. (evident, acestea vor contine cel mult un element)
« Ultima modificare: Iunie 10, 2014, 01:45:44 de către Duta Vlad » Memorat
Vman
Echipa infoarena
Vorbaret
*****

Karma: 45
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #32 : Iunie 10, 2014, 01:43:44 »

Dau berea cu prima ocazie  Applause

O sa iti schimb culoarea textului in alb, poate mai sunt utilizatori care vor sa se gandeasca la solutie.
Memorat
veleandu
De-al casei
***

Karma: 155
Deconectat Deconectat

Mesaje: 132



Vezi Profilul
« Răspunde #33 : Iunie 10, 2014, 19:38:15 »

Andrei, la problema Marsmusic faci practic pt fiecare melodie suma modurilor in care se suprapun in toate cazurile?
Daca da .. faci pe numere mari si imparti la m!
Si in cazul asta, se poate sa fac fara numere mari (aceeasi rezolvare) doar cu double?
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #34 : Iunie 10, 2014, 21:02:34 »

In solutia noastra, nu este nevoie nici de numere mari si nici de calcularea lui M!.
Avand dinamica DP[song][time] = probabilitatea ca melodia song sa inceapa la momentul time, putem calcula suma din DP[song][t1] * DP[song][t2] * Intersection([t1, t1 + Duration[song] - 1], [t2, t2 + Duration[song] - 1]) cu ajutorul unor sume partiale. Rezultatul cumulat al acestor sume pentru fiecare melodie va constitui raspunsul.
Pentru a calcula DP[song][time], putem folosi dinamica auxiliara pe care am descris-o anterior: DP2[n][count][time] = probabilitatea ca melodia n sa inceapa la momentul t, stiind ca au fost difuzate exact count melodii dintre primele n - 1 inaintea ei. Recurenta este DP2[n][count][time] = DP2[n - 1][count][t] * (n - count) / n + DP2[n - 1][count - 1][t - Duration[n]] * count / n.
Memorat
gabriel.badea
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #35 : Iunie 10, 2014, 22:20:02 »

Cand se vor mai putea trimite solutii la probleme ?
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #36 : Iunie 11, 2014, 09:55:55 »

Imediat ce vor fi puse în arhiva de probleme. Nu ar trebui sa mai dureze mult.  Ok
Memorat
Denisache
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #37 : Iunie 13, 2014, 21:25:58 »

Cand faceti update la rating?
Memorat
xtreme77
Client obisnuit
**

Karma: 7
Deconectat Deconectat

Mesaje: 69



Vezi Profilul
« Răspunde #38 : Iunie 13, 2014, 23:31:37 »

Cand faceti update la rating?

Pai cred ca mai dureaza ceva din moment ce nici la ONIS nu s-a facut update.(iar ONIS a fost mai devreme ca Monthly)
Memorat
Pagini: 1 [2]   În sus
  Imprimă  
 
Schimbă forumul:  

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