infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: ditzone din Octombrie 15, 2006, 21:26:31

Titlul: 279 Int
Scris de: ditzone din Octombrie 15, 2006, 21:26:31

Aici puteÅ£i discuta despre problema Int (http://infoarena.ro/problema/int).

Titlul: RÄƒspuns: 279 Int
Scris de: Andrei-Bogdan Antonescu din Martie 06, 2008, 10:31:17

Am rezolvat int de 100pt folosind si qsort si shell sort
Si in cazu shell sort am scos un timp(maxim) mult mai mic 128ms in loc de 208ms

Imi poate spune si mie cnv dc ca stiam ca qsort e mult mai rapid

Titlul: RÄƒspuns: 279 Int
Scris de: Andrei Grigorean din Martie 06, 2008, 10:54:30

Depinde si de sirul pe care trebuie sa il sortezi. De exemplu pe un sir gata sortat bubble sort merge in O(N).

Titlul: RÄƒspuns: 279 Int
Scris de: gaboru corupt din Mai 02, 2008, 15:48:40

Citat

Determinati o submultime de intervale cu numar maxim de elemente, cu proprietatea ca intersectia oricaror 2 intervale din submultime este vida.

in exemplul dat, daca ne luam dupa ce spune enuntul problemei, trebuie sa cautam intervalele cu un numar de exemente maxim... deci nu trebuia selectate intervalele:

Citat

-11 -7
0 30

poate nu am inteles eu bine problema...va rog o explicatie mai detaliata

Titlul: RÄƒspuns: 279 Int
Scris de: Stefan Istrate din Mai 02, 2008, 16:01:26

Submultimea trebuie sa aiba numar maxim de elemente, nu intervalele.

Titlul: RÄƒspuns: 279 Int
Scris de: gaboru corupt din Mai 02, 2008, 16:16:21

deci vrei sa spui ca trebuie sa aflu nr maxim de intervale disjuncte, si nu intervalele disjuncte cu numarul maxim de elemente ???

Titlul: RÄƒspuns: 279 Int
Scris de: Stefan Istrate din Mai 02, 2008, 17:21:37

Titlul: RÄƒspuns: 279 Int
Scris de: gaboru corupt din Mai 02, 2008, 18:05:38

deci ideea mea e in felul urmator: am un vector v[] care la inceput e initializat cu 0. parcurg intervalele de la sfarsit la inceput. si pentru fiecare interval verific toate intervalele din dreapta lui daca sunt disjuncte cu el. cand am ajuns la primu interval disjunct, atribui la v[interval_curent]=v[interval disjunct]+1...iar daka nu exista interval disjuct cu el atunci v[interval_curent]=1. si caut maximul din v[] si il afisez... daca ati putea sa imi dati un contra exemplu la aceasta rezolvare :thumbup:

Titlul: RÄƒspuns: 279 Int
Scris de: Andrei Misarca din Mai 02, 2008, 19:35:56

Un hint pentru O(N*logN) pls :) K N^2 sigur nu intra in timp

Titlul: RÄƒspuns: 279 Int
Scris de: gaboru corupt din Mai 03, 2008, 11:00:02

gata, am scos 100. :yahoo: mishu, poti incerca si ideea mea de mai sus... scoti timpi faini, 70 ms cel mai mare :D suuces! :ok:

Titlul: RÄƒspuns: 279 Int
Scris de: Andrei Misarca din Mai 03, 2008, 11:35:09

Pai ideea asta e in O(N^2), si am incercat-o si scot 40 de puncte :?

Titlul: RÄƒspuns: 279 Int
Scris de: Bondane Cosmin din Mai 03, 2008, 11:48:20

Poti rafina putin ideea, v(i) = numarul maxim de intervale care nu se intersecteaza, folosind si intervalul i.

Sortezi intervalele in functie de capatul drept. Daca la un moment dat ai ajuns la intervalul i, poti sa cauti binar primul interval care nu intersecteaza intervalul i. Sa zicem ca ii al k-lea. Atunci v(i) = maximul de pe intervalul 1..k + 1. Pentru a afla maximul de pe intervalul 1..k poti sa ti un arbore de intervale.

Complexitate (N*logN*logN), care ar trebui sa intre in timp.

Titlul: RÄƒspuns: 279 Int
Scris de: Serban Andrei Stan din Mai 03, 2008, 12:10:18

Este o solutie si O (n log n), destul de usor de inteles si de implementat. Consta in a sorta intervalele dupa limita din stanga, iar cele care o au egala, dupa limita din dreapta. Dupa aia se alege pur si simplu primul interval, si trebuie sa vezi care este intervalul cu limita din stanga mai mare decat limita din dreapta a celui ales. Il alegi pe primul care il intalnesti, si tot asa. Asta o sa-ti iasa in timp liniar. N log N vine de la sortare... Spor!

Titlul: RÄƒspuns: 279 Int
Scris de: gaboru corupt din Mai 03, 2008, 12:10:36

Citat

Pai ideea asta e in O(N^2), si am incercat-o si scot 40 de puncte

ideea mea de mai sus a survenit niste modificari, fiindca si eu tot 40 de puncte luam. mai ai o conditie inainte sa cauti primul interval disjunct in dreapta. daca intervalul curent este disjunct cu intervalul maximului din v[].daca da atunci v[curent]=max+1, ("max" care e prima valoare maxima din v), iar daca intervalul curent nu e disjunct cu intervalul maximului din v[], atunci cauta la dreapta primul interval disjunt.

PS: nu prea le am in a calcula complexitatea algoritmului, dar cu un quicksort scoti timpi de maxim 80 ms

Titlul: RÄƒspuns: 279 Int
Scris de: gaboru corupt din Mai 03, 2008, 12:16:06

Citat

daca am inteles eu bine explicatie, pentru exemplul:

Citat

6 ---nr de intervale
-2 5
1 2
2 3
3 4
4 5
7 10

acesta imi ia intervalul -2 5 si cauta primu interval disjunct, adica 7 10. si afiseaza 2. rapunsul este gresit pt ca trebuie afisat 5, intervalele disjuncte incepand de pe pozitia a 2-a pana la final.

Titlul: Răspuns: 279 Int
Scris de: Serban Andrei Stan din Mai 03, 2008, 12:28:19

Mda, ai dreptate, scuzele mele. Sortezi dupa al doilea cap, si daca ai mai multe intervale egale cu al doilea, sortezi si dupa primul...In rest e la fel.

Titlul: RÄƒspuns: 279 Int
Scris de: Andrei Misarca din Mai 03, 2008, 12:49:36

Multzam fain la amandoi... am scos suta :yahoo:

Citat

PS: nu prea le am in a calcula complexitatea algoritmului, dar cu un quicksort scoti timpi de maxim 80 ms

Cu introsort din STL am scos timpu maxim de 60 ms

Titlul: RÄƒspuns: 279 Int
Scris de: Iancu David Traian din Februarie 06, 2009, 15:25:55

Imi puteti da si mie vreun indiciu, macar pentru O(n*n) deoarece nu prea am inteles ce am de facut.

Titlul: RÄƒspuns: 279 Int
Scris de: Dragos-Alin Rotaru din Mai 30, 2009, 11:02:51

Incearca sa sortezi cu sort-ul din STL si sa gasesti o modalitate de a compara capetele intervalelor in O(N). :ok:

Titlul: RÄƒspuns: 279 Int
Scris de: Guianu Leon din Noiembrie 07, 2012, 10:26:02

E ceva in neregula cu problema aceasta sau sunt eu fraier? Am trimis un O(N^2) in care compar pe fiecare cu fiecare si sunt teste pe care da Incorect in loc de TLE. Initial am folosit exact metoda de rezolvare de la problema spectacolelor, care mi se pare rezolvarea imediata, fiind cea mai simpla si rapida, si mi-a dat Incorect pe 9 teste :'(

Titlul: RÄƒspuns: 279 Int
Scris de: Radu-Andrei Szasz din Noiembrie 07, 2012, 18:12:13

E ceva in neregula cu algoritmul tau. Am scris acum o sursa cu greedy-ul de la problema spectacolelor si am luat 100.

Poti scoate problema in complexitate O(N log N)(datorita sortarii e N log N, in rest ai nevoie de o singura parcurgere).

Daca ai nevoie de ajutor, da-mi PM.

Titlul: RÄƒspuns: 279 Int
Scris de: Bratie Fanut din Februarie 04, 2013, 17:27:30

deci am programul urmator:

Cod:

#include <stdio.h>
#define NMAX 50001
using namespace std;

struct interval{int st, dr;};
interval v[NMAX],x,k;
int n,i,j,p,s=0;

int main()
{
    FILE *f,*g;
    f=fopen("int.in","rt");
    g=fopen("int.out","wt");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    fscanf(f,"%d%d",&v[i].st,&v[i].dr);

    for(i=1;i<=n-1;i++)
    for(j=i+1;j<=n;j++)
    if(v[i].st>=v[j].st)
    {
        x=v[i];
        v[i]=v[j];
        v[j]=x;
    }

    k=v[1];
    for(p=2;p<=n;p++)
    {
        if(k.dr<=v[p].st)
        s++;
        k=v[p];
    }
    fprintf(g,"%d",s);
    return 0;
}

aceasta este ideea pe care m-am bazat. pt fiecare test pe care il fac imi scrie in fisierul de iesire numarul corect -1. de exemplu pt

Cod:

imi afiseaza 2, etc. nu cred ca am inteles inca ce trebuie sa fac, acum invat greedy. imi poate spune cineva ce gresesc si sa imi ofere un idiciu in rezolvarea acestei probleme. va multumesc!

Titlul: RÄƒspuns: 279 Int
Scris de: Pirtoaca George Sebastian din Februarie 04, 2013, 17:56:35

Problema este o reformulare la "Problema spectacolelor", pe care o gasesti in orice manual.
Sortezi dupa y, iar daca ai mai multe intervale care au acelasi y, le sortezi dupa x. Acum faci greedy (e clar ca intervalul care are y cel mai mic este favorabil sa il alegi, nu are rost sa alegi altul care se termina mai tarziu).
Succes! :ok:

Titlul: RÄƒspuns: 279 Int
Scris de: Bratie Fanut din Februarie 04, 2013, 18:39:24

bun, am sortat dupa y, si in caz ca sunt egali am sortat dupa x, folosind sort din <algorithm>. pe testele mele imi da corect dar pe infoarena 0 puncte..

Cod:

#include <stdio.h>
#include <algorithm>
#include <iostream>
#define NMAX 50001
using namespace std;
 
struct interval{int st, dr;};
interval v[NMAX],x,k;
int n,i,j,p,s=0;
 
bool cmp(interval p, interval p1)
{
    return p.dr<p1.dr?true:p.dr==p1.dr?p.st<p1.st?true:false:false;
}
 
int main()
{
    FILE *f,*g;
    f=fopen("int.in","rt");
    g=fopen("int.out","wt");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    fscanf(f,"%d%d",&v[i].st,&v[i].dr);
 
sort(v+1,v+n+1,cmp);
 
for(i=1;i<=n;i++)
cout<<v[i].st<<" "<<v[i].dr<<endl;
 
    k=v[1];
    s=1;
    for(p=2;p<=n;p++)
    {
        if(k.dr<=v[p].st)
        s++;
        k=v[p];
    }
    fprintf(g,"%d",s);
    return 0;
}

Titlul: RÄƒspuns: 279 Int
Scris de: Pirtoaca George Sebastian din Februarie 05, 2013, 10:18:53

Nu e bine asa. Uite o secventa corecta :

Cod:

  ultim=1;     
  s=1;     
  for(i=2;i<=n;i++)         
         if(v[i].a>=v[ultim].b) {            
                  ultim=i;             
                  s++;         
          }     
  g<<s;

Titlul: RÄƒspuns: 279 Int
Scris de: Bratie Fanut din Februarie 05, 2013, 15:06:23

In sfarsit am luat 100 :shock: Multumesc mult SebiSebi :D mi-am dat seama unde am gresit #-o multumesc din nou :thumbup: :thumbup: