236 Biscuiti

[ditzone]

Aici puteţi discuta despre problema Biscuiti.

[•filipb]

Dupa ce se demonteaza o scandura, o mai luam in considerare la pasii urmatori?

[u-92]

NU (totusi cred ca se intelege asta din enunt)

[•filipb]

Numerele x sunt intregi sau reale? Chiar nu pricep unde gresesc... Ce au asa de special testele?

[u-92]

sunt numere naturale.. testele nu au nimic special, au fost generate aletor, atentie la tipul de date folosit poate acolo gresesti

[•lucicanu]

N-am nici o idee cum s-ar putea face problema asta. Datele sunt prea mari, deci trebuie un algoritm de complexitate liniara (sau n*logn). Poate cineva sa-mi dea o idee mica?

[u-92]

trebuie sa folosesti o structura de date cu care sa faci eficient operatiile descrise (de exemplu, un arbore de intervale)

[•lucicanu]

Pai... ar fi o problema. Eu sunt in clasa a 10-a si nu stiu arbori. Altfel nu cred ca se poate rezolva, nu (doar cu cunostinte de a 10-a) ?

[•Stilgar]

ce informatie memorezi in arbori?....ce-i ciudat ca daca timpu ar fi fost un pic ma mare(0.7) mi-ar fi intrat o sol de complexitate 0(n^2) optimizat

[u-92]

o problema de la campion poate te ajuta..
http://campion.edu.ro/problems.php?mode=view_solution&problem_id=302&group_number=3&year=2005

ps: nu intra in 0.7 n^2 oricat de optimizat, in monitor iti apare timpul la care a fost oprit programul din executie

[•wefgef]

rezultatul incape pe 64 de biti?

[•gogu]

Rezultatul sigur incape dar ai grija ca trebuie sa retii si lungimile individuale ale scandurilor pe 64 de biti.

[•pauldb]

Ce alte probleme din arhiva se mai rezolva cu abori de intervale?

[u-92]

ar mai fi: farfurii, delay, hotel, parcele, demolish, order, omizi, sequencequery

[•rmikeweb]

La problema asta cat ii complexitatea. Algoritmul meu merge in N log^2 N se poate si in NlogN???

[•wefgef]

La problema asta cat ii complexitatea. Algoritmul meu merge in N log^2 N se poate si in NlogN???

se poate.

[•rmikeweb]

Da am vazut acum cu algoritmul meu in N log^2 N merge de 30 pe restu iau tle.  Dar nu stiu cum sa-l aduc la N log N. Ideea ii ca folosesc 2 arbori de intervale unul care retine minimul si unul care retine suma. Faza ii ca atunci cand elimin o scandura trebe updatati cei 2 arbori. Ca sa modific in arborele cu minim tre sa fac log^2 N operatii deoarece la ficare nivel in fii care contin nodul eliminat  tre sa vad cat ii minimul rasmas si asta o fac verificand cat ii suma in minimul in stanga si dreapta. Imi puteti spune careva cum sa mai optimizez.

[u-92]

este si un link mai sus.. ideea e ca iti trebuie un arbore care retine minimul si unul cat ai adunat pe tot intervalul (si unul pozitia celui mai din stanga in caz de egalitate).. vezi acum cum faci cand ai informatii despre fii si vrei sa updatezi tatal in O(1)

[•Marius]

Pentru urmatorul test

Cod:

1000
1000
999
998
...
2
1

rezultatul este 4950166666500 ?

[•svalentin]

mie imi da 166666500
si pentru

Cod:

10
10
9
...
2
1

imi da

Cod:

165

.. poate te ajuta

[•Marius]

E usor de observat ca 4950166666500 este o conversie pe 64 de biti a valorii 166666500. 

Am declarat o variabila

Cod:

long long infinit = (long long)6000000000;

iar compilatorul de pe InfoArena imi da eroare, spunand ca valoarea intreaga este prea mare.
Cum pot sa rezolv problema ? 

Am modificat in

Cod:

long long infinit = (long long)60000 * 100000;

Frumos din partea lui.

[•Prostu]

Varianta oficiala ar fi ceva de genul:

Cod:

long long infinit = 6000000000LL;

[•Mishu91]

Am si eu o intrebare... cum se poate updata arborele de minime in logN atunci cand trebe sa adaug la fiecare element din stanga pozitiei X, T? Pentru ca nici cum nu reusesc si iau doar 10 puncte 

[•Florian]

Rog pe cineva cu sursa de 100, sa-mi spuna solutiile la testele urmatoare:

Cod:

15
347
131
983
91
657
118
596
416
949
127
5
559
572
880
493

Cod:

10
347
131
983
91
657
118
596
416
949
127

Cod:

7
347
131
983
91
657
118
596

Multumesc!

[•Mishu91]

Cod:

288
85
30