126 Lungimi de interval

[ditzone]

Aici puteţi discuta despre problema Lungimi de interval.

[•Sergiu]

Imi poate explica si mie cineva exemplul din enunt? ca daca iau intervalele fara capeti imi da 16 iar daca iau si capetii imi da 21 iar in exemplu la .out este 18

[u-92]

Lungimea intervalului [a,b] este b-a
prin urmare avem:
[-5,5] -> 5-(-5) = 10
[0,3] - este inclus in [-5,5], nu il numaram
[2,8] - [2,5] este inclus in[-5,5], nu il numaram, mai ramane 8-5 = 3
[10,13] - nu e inclus nicaieri, 13-10 = 3
[11,15] - [11,13] este inclus in [10,13], mai ramane 15-13 = 2
[100,100] - are lungimea 0
Adunand obtinem 10+3+3+2 = 18

[•devilkind]

problema parerea mea ca e formulata greshit, deoarece [A,B] nu este A-B ci este A-B+1. Pentru ca lungimea sa fie A-B trebuie ca unul din capete sa fie deschis primul sau al doilea.

Ex: intervalul [0,3] - calculat cu formula 3-0=3; dar intervalul contine 0,1,2,3 shi apeland la nishte cunostinte avansate de numarare mie imi da 4.
ati putea deschide unul dintre capete ptr ca problema sa fie formulata corect.

[u-92]

pai apeland la cunostinte nu chiar asa de avansate de numarare lungimea intervalului [0,3] este 3, cum ti-a dat tie 4?

[ditzone]

Apeland la niste cunostinte matematice un pic mai avansate decat simpla determinare a cardinalului multimii {0,1,2,3} o sa afli ca intr-un interval [a,b], a<b sunt o infinitate de numere reale.
Lungimea intervalului se refera de fapt la lungimea segmentului determinat de intervalul respectiv pe axa numerelor reale.

[•devilkind]

deci sa inteleg ca idea mea de a face un vector de la -1 000 000 la 1 000 000 (adik un a[2 000 000]) shi apoi sa iau un intervalul si sa notez cu unu toate elementele incepand cu x+1 000 000 - y+1 000 000 (pentru a nu ma complica cu indexare negativa, lucru care am vazut ca este posibil intrun articol de pe infoarena) nu functioneaza. Pacat, tre sa gasesc o idee de a uni intervalele care se suprapun se pare . asta e

[•wefgef]

vezi poate te ajuta la ceva o sortare

[•devilkind]

da mi-am dat shi eu seama ca ar trebuie sa fac chestia asta. DUDE you're a genius, chiar in tim ce scriam acest post mi-am dat seama cum se face problema, chiar dak shtiam ca trebuie sa fac sortarea, aveam eu impresia ca ar exista un caz ptr care nu ar merge, caz care este eliminat prin acea sortare de fapt. Thanx dude.

[ag3nt_junior]

Frumoasa problema.. Mie nu mi se incadreaza in timp nici macar citirea. Voi cum cititi in c++?

[•Marius]

Incearca sa folosesti fscanf() !

[•gabitzish1]

imi puteti da niste teste  .. mie imi iese exemplul dat in problema.. imi intra in timp.. dar rezultatul se pare ca e incorect...

[•astronomy]

Te sfatuiesc sa mai faci un program brute-force care determina tot timpul rezultatul corect, apoi sa dai teste si sa compari rezultatele, cred ca asta e cea mai buna metoda sa faci debug

[•gabitzish1]

nu stiu cum se face chestia aia

[•astronomy]

Ai un vector de 2.000.000 in care daca A[ x ] == 1 punctul x a fost "atins" de vreun segment. Acum iti este usor sa calculezi rezultatul (cauti secventele de 1 din vectorul asta). Iar ca sa generezi teste faci pur si simplu un alt program care scrie date in fisierul tau de intrare. (arunca o privire si peste functia rand() din stdlib.h).

[•Florian]

Exista vreo sansa sa pot declara un vector de 2.000.000???

[•devilkind]

dap. Dak e long int :  2 000 000 * 4 = 8 000 000 /1024/1024 = 7 MB

[•Florian]

Aham...multumesc! Nu-mi iesea deoarece il declarasem long long (kiar dak nu e nevoie pt problema asta)....am reusit sa nu mai iau kill by signal 11, insa imi depaseste timpul...incerc sa mai optimizez...dak nu se poate o sa incerc alta metoda...

[•Bluedrop_demon]

Se poate lua 100p intr-un timp de 416ms daca descoperiti o conditie. Hint: Unele intervale A, B deja sunt adaugate la suma. 

[•Florian]

Deci..am abandonat faza cu vectorul de 2000000..k`mi iese din timp....
Insa si akum imi iese.desi am facut in urm fel:
 -ordonez crescator dupa a, iar in caz de egalitate crescator dupa b (a,b capetele intervalelor)
 -apoi iau si compar in 0(n) intervalele..adunand lungimile....
Pe testele mele imi da rezultate corecte...dar imi iese din timp...
Stie careva o metoda de optimizare??pls..help me...

[•Bluedrop_demon]

Rezolvarea pare ok si ar trebui sa se incadreze in timp. Numai sa nu fi gresit ceva la implementare. Depinde si ce sortare ai folosit. Complexitatea ar trebui sa fie maxim n^2 pe 3 sec. Nu cred sa intre n^3. Incearca alta metoda de sortare, poate o scoti la capat 

[•ctes]

si cum speri u sa obtii cu o sortare si o comparare/parcurgere (de parcurs tot treb sa parcurgi tot) O(n^2), in cel mai fericit caz obtii O(n*n*log(n))
LE: acest cel mai fericit se refera la quicksort, care daca ai ghinion poate sa ajunga la O(n*n)

[•Bluedrop_demon]

O(n*n*log n) cred ca intra in timp. Eu nu fac sortare, de aceea am n^2. Si asta pe cel mai defavorabil caz, deci sunt sanse sa mearga chiar mai rapid. Dupa cum am zis mai sus, solutia mea are 416ms. Dar un O(n*n*log n ) cred ca e suficient.

LE: Pentru edit-ul cu quick sort. Poti folosi Interclasare, care merge mereu in O(n log n) pe orice caz. Quick-sort nu e cea mai rapida, doar ca la raportul timp/memorie e cea mai buna. Dar memorie e suficienta si pentru Interclasare.

[•ctes]

da dar rezolvarea ta cu O(n*n), dak e cea la care ma gandesc eu e km neortodoxa

[•Darth_Niculus]

important e sa mearga.....