Troll

[•eudanip]

Aici se pot pune întrebări legate de problema Troll de la Runda 2 a concursului .com 2012

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

[•informatician28]

"sa ia un interval de valoare maxima si sa vada cate intervale mai poate adauga astfel incat acestea sa nu se suprapuna in nici-un punct", in sens ca toate celelalte intervale sa fie cuprinse in acest interval cu z maxim, dar intre ele(cele ramase, fara z maxim) sa nu se suprapuna?

[•andreifirst]

Eununtul e putin ciudat. Trebuie sa aflam numarul maxim de intervale si apoi valoarea maxima din ele sau trebuie sa alegem valoarea maxima si apoi nr maxim de intervale ce mai poate fi adaugat?

[•darren]

Ce valori poate avea Z?

[•andreifirst]

intervalele [1, 2] si [2, 3] se considera ca se suprapun?

[•eudanip]

"sa ia un interval de valoare maxima si sa vada cate intervale mai poate adauga astfel incat acestea sa nu se suprapuna in nici-un punct", in sens ca toate celelalte intervale sa fie cuprinse in acest interval cu z maxim, dar intre ele(cele ramase, fara z maxim) sa nu se suprapuna?

Nu. Nici un interval nu trebuie sa se suprapuna cu nici un interval. Inclusiv cel cu valoarea maxima.

Eununtul e putin ciudat. Trebuie sa aflam numarul maxim de intervale si apoi valoarea maxima din ele sau trebuie sa alegem valoarea maxima si apoi nr maxim de intervale ce mai poate fi adaugat?

Scrie in enunt ordinea corecta.

[•S7012MY]

Problema cere:
Sa se afle suma maxima obtinuta din intervale disjuncte incluse in intervalul de valoare maxima care poate fi inclusa in acest interval ?

[•darren]

Cred ca testul 6 (de la rezultate partiale) nu respecta conditia 1 ≤ X, Y ≤ 100000.

[•roots]

Pentru testul :

Cod:

3
1 1 1
1 3 2
2 4 2

raspunsul este :

Cod:

2 2

?

[•vendetta]

1) Ce se stie despre Z?
2) Practic tu tot timpul alegi intervalul de valoare maxima ?

[•Challenge]

Se garanteaza ca Z-urile sunt distincte?

[•tzipleatud]

Pentru cerinta a 2-a, daca exista mai multe intervale cu Z maxim, care nu se suprapun, se pot lua toate? Adica pentru testul

Cod:

2 
1 5 10
7 11 10

raspunsul este

Cod:

 10 2 

?

[•edp100]

@Buhai
Limita a fost modificata, era asa de la o versiune anterioara a problemei, imi cer scuze pentru inconvenientele cauzate.

@andreifirst

astfel incat acestea sa nu se suprapuna in nici-un punct

intervalele fiind inchise  ( [x, y] ),  se considera ca se suprapun.

@vendetta & Challenge
Z incape in int, de asemenea pot exista mai multe intervale cu acelasi z.

@tzipleatud

Pentru cerinta a 2-a, daca exista mai multe intervale cu Z maxim, care nu se suprapun, se pot lua toate?

DA

[•darren]

Z este >= 0?

[•edp100]

NU,
Am adaugat:

-1337 ≤ Z ≤ 2000800000

@roots
Vezi :

@tzipleatud
Citat
Pentru cerinta a 2-a, daca exista mai multe intervale cu Z maxim, care nu se suprapun, se pot lua toate?
DA

@S7012MY
NU

[•repp4radu]

Dupa modificarea limitei cu X, Y, cred ca ati facut multa lumea sa piarda destul de mult timp...

[•valentin.harsan]

nu uitati de restrictia:

Pentru a obtine punctele la testul 10 trebuie sa afisati 1337 inainte de celelalte 2 numere.

[•dariusdarius]

Se poate ca 2 interval sa fie identice?

[•eudanip]

Nu mai trolla.

nu uitati de restrictia:

Pentru a obtine punctele la testul 10 trebuie sa afisati 1337 inainte de celelalte 2 numere.

[•edp100]

@Darius
DA

[•andreifirst]

Se mai pot pune intrebari? Doar pentru clarificare: problema imi cere sa aflu numarul maxim de intervale astfel incat printre ele sa existe si intervalul (unul din intervalele) de lungime maxima din lista?

[•valentin.harsan]

cred ca limita de timp la problema asta e cam mica....
de la citirea cu cin iau 90 

[•Mihai22e]

Eu am reusit sa obtin 80p la problema aceasta cu un algoritm destul de slab, dupa parerea mea: sortez intervalele dupa capatul din dreapta, si apoi cu un algoritm greedy verific cate intervale pot lua maxim astfel incat sa nu se intersecteze (fie K numarul maxim de intervale pe care le pot lua astfel incat sa nu se intersecteze); apoi am 2 cazuri:
1.in cele K intervale luate, am cel putin un interval cu valoarea maxima, deci afisez Z-ul cel mai mare si K
2.nu am niciun interval cu valoarea maxima si procedez in felul urmator: iau pe rand fiecare interval dintre cele cu valoare maxima si verific cate intervale trebuie sa scot din cele K astfel incat sa-l pot introduce pe cel ales acum, iar apoi compar cu maximul; deci afisez Z-ul cel mai mare si maximul.
Ceea ce e si mai ciudat e faptul ca in prima sursa pe care am trimis-o am facut o eroare destul de grava, care ar fi trebuit sa dea peste cap tot algoritmul: cand sunt in cazul al 2lea si aleg un interval cu valoare maxima, in loc sa-l compar cu cele K intervale deja luate, il compar cu toate intervalele (N) si verific cate ar trebui sa scot pentru a-l introduce pe acesta..ceea ce e evident gresit. De aici deduc ca majoritatea testelor nu au intervale care sa se intersecteze, sau au prea putine.