844 Motel

[•astronomy]

Aici puteti discuta despre problema Motel.

[•gh09]

Din ce cauza da eroare la fisier de iesire? 

Pot exista valori egale pt cele n zile in care poate canta artistul?

[•Omega91]

raspunsul pt

Cod:

2
1 3
3 8
3
1

este

Cod:

1 2
2 1

sau 0 0?

intreb deoarece teoretic ar trebui sa fie prima varianta, dar sursa mea de 100 mi-o afiseaza pe a 2-a

[•gh09]

Ar trebui sa dea:

1 2
2 1

Deci pot exista pt cele n zile valori egale? 

LE: Ar trebui specificata treaba ca zilele pot fie egale.....

[•mihaionly]

Poate cineva să-mi dea o indicație?Și...ar fi prea mult o complexitate O(n^2) ?

[•Robytzza]

nu

[•lucian666]

AM 70 pct cu 1 Memory limit exceeded  si 2 TLE
Am facut un cuplaj 
Exista ceva mai optim pentru 100 pct?>
Multumesc Anticipat!!!

[•klamathix]

Da.

[•lucian666]

un heap poate?

[•klamathix]

Jucam twenty questions?
Baga si vezi .

[•lucian666]

am o intrebare
pt un set daca il declar in felul urmator:set<pair<int,pair<int,int> > >S;
si iteratorul specific: set<pair<int,pair<int,pair> > >:: iterator I;
daca vreau sa ma refer la elementul al treilea din vf heapului:
I=S.begin();
am incercat
I->s->s dar nu merge
cum as putea face altcumva?
Multumesc Anticipat!!!

[•S7012MY]

Pui sageata si punct (->s.s)

[•lucian666]

La problema asta am incercat 3 variante:
1.Cuplaj :70 pct cu 1 TLE si 2 MLE
2.Greedy(N^2):50 pct cu 3 Incorect si 2 TLE
3.Heap :30 pct cu 7 Incorect.

La varianta cu Heap am facut asa:
Am sortat intervalele in functie de limita din st
Am sortat crescator zilele in care artistul are spectacole.
Pt fiecare zi am bagat in heap intervalele care o cuprind ,apoi am sters din heap toate intervalele care nu mai cuprind ziua i.Daca la un anumit pas heapul devine vid => nu exista solutie,altfel afisez ziua i cu intervalul din vf hepului .
Este ceva gresit in judecata mea?
Multumesc Anticipat!!!!

[Later Edit]

Pt Heap am folosit un set

[/Later Edit]
Editat de admin: Nu mai posta in continuare, editeaza-ti mesajele(folosind butonul modifica din dreapta sus a casutei de mesaj)

[•ion824]

Imi poate spune cineva cat va da cu o sursa de 100p pe urmatorul test:
23
9 20
21 25
7 11
9 27
25 27
6 10
18 28
15 21
9 25
8 14
8 25
2 9
23 28
1 10
4 24
11 23
8 16
13 24
3 26
8 17
9 18
2 12
5 20
25
18
3
19
3
16
18
25
6
16
15
20
17
6
9
4
9
2
24
6
25
11
11

Multumesc Anticipat.

[L.E] Am luat suta.
raspuns (sper ca ajuta cuiva):
12 18
14 3
22 5
15 16
6 14
23 20
19 9
3 17
10 15
17 22
20 23
21 11
1 10
8 6
16 13
18 7
11 2
9 4
4 12
2 19
5 21
7 8
13 1

[•ctlin04]

Mie imi da:  0 0   

[•lucian666]

Imi poate spune cineva cat va da cu o sursa de 100p pe urmatorul test:
23
9 20
21 25
7 11
9 27
25 27
6 10
18 28
15 21
9 25

cum ai facut pt 100 pct>? #039;ai folosit heap?
8 14
8 25
2 9
23 28
1 10
4 24
11 23
8 16
13 24
3 26
8 17
9 18
2 12
5 20
25
18
3
19
3
16
18
25
6
16
15
20
17
6
9
4
9
2
24
6
25
11
11

Multumesc Anticipat.

[L.E] Am luat suta.
raspuns (sper ca ajuta cuiva):
12 18
14 3
22 5
15 16
6 14
23 20
19 9
3 17
10 15
17 22
20 23
21 11
1 10
8 6
16 13
18 7
11 2
9 4
4 12
2 19
5 21
7 8
13 1

[•lucian666]

  Buna seara.
Am facut la problema asta un cuplaj maxim si iau doar 70 pct cu 2 TLE si 1 MLE .TLE cred ca se datoreaza functiei de creare a grafului...in fine, exista o solutie mai optima ? ( am incercat cu un Heap dar mai  mult de 30 pct nu iau )
O seara placuta!!!!

[•vendetta]

Da. Cu cautare binara. Fa primadata solutia in n^2 si apoi incearca sa o reduci la N * log N.

[•lucian666]

Salut . Am incercat si solutia cu cautare binara dar iau doar 20 pct retul WA si TLE. . Am incercat mai multe variante la problema asta : Cuplaj(70 pct ) , Greedy(50 pct -desi ar trebui sa ia 80 pct ) , si inca una cu heapuri ( 30 pct cu WA pe restul ). Exista o rezolvare mai optima decat nlogn ? Si daca exista care ar fi aceasta solutie?

Multumesc Anticipat