279 Int

[ditzone]

Aici puteţi discuta despre problema Int.

[•andrei-alpha]

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 

[•wefgef]

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

[•gabor_oliviu1991]

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:

-11 -7
0 30

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

[•stef2n]

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

[•gabor_oliviu1991]

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

[•stef2n]

Da

[•gabor_oliviu1991]

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 

[•Mishu91]

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

[•gabor_oliviu1991]

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

[•Mishu91]

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

[•cos_min]

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.

[•savim]

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!

[•gabor_oliviu1991]

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

[•gabor_oliviu1991]

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!

daca am inteles eu bine explicatie, pentru exemplul:

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.

[•savim]

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.

[•Mishu91]

Multzam fain la amandoi... am scos suta 

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

[•funkydvd]

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

[•mathboy]

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

[•Detrol2k]

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

[•repp4radu]

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.

[•bratiefanut]

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:

5
 -3 10
 -11 -7
 1 6
 0 1
 0 30

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!

[•SebiSebi]

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!

[•bratiefanut]

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;
}

[•SebiSebi]

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;