infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva educationala => Subiect creat de: Andrei Grigorean din Februarie 26, 2008, 11:09:39



Titlul: 001 Cel mai lung subsir comun
Scris de: Andrei Grigorean din Februarie 26, 2008, 11:09:39
Aici puteti discuta despre problema Cel mai lung subsir comun (http://infoarena.ro/problema/cmlsc).


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: MciprianM din Februarie 26, 2008, 17:25:44
Ce e o "Eroare in evaluator" ?
Am mai luat SIGSEGV, dar nu aparea eroare in evaluator.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Andrei Grigorean din Februarie 26, 2008, 17:59:19
Este o greseala care nu tine de tine. Se va remedia in curand.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Filip Cristian Buruiana din Februarie 26, 2008, 18:25:33
S-a rezolvat. Un mic bug in evaluator. :oops:


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: floflofloflofloflo din Februarie 26, 2008, 22:49:18
Test     Timp executie     Memorie folosita     Mesaj    Punctaj/test
1   4ms   12kb   Raspuns corect!   10
2   0ms   12kb   Raspuns corect!   10
3   0ms   12kb   Raspuns corect!   10
4   0ms   12kb   Lungime incorecta!   0
5   4ms   12kb   Lungime incorecta!   0
6   0ms   8kb   Lungime incorecta!   0
7   0ms   8kb   Lungime incorecta!   0
8   0ms   12kb   Lungime incorecta!   0
9   0ms   12kb   Lungime incorecta!   0
10   4ms   12kb   Lungime incorecta!   0
Punctaj total   30

Am o problema la lungime,ma poate ajuta cineva, dau sursa prin pm,sa nu fie discutii.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Airinei Adrian din Februarie 26, 2008, 22:54:07
Lungimea maxima a unui sir este 1024, la tine ai declarate sirurile de lungime maxima 100.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: floflofloflofloflo din Februarie 26, 2008, 22:59:06
100 pnc ! ms Adrian !


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Stefan Gheorghe din Martie 12, 2008, 21:58:45
Care ma poate ajuta si pe mine??? La problema asta iau numai 90 pct pe freepascal :
Test     Timp executie     Memorie folosita     Mesaj    Punctaj/test
1   0ms   12kb   Raspuns corect!   10
2   0ms   8kb   Raspuns corect!   10
3   0ms   12kb   Raspuns corect!   10
4   4ms   8kb   Raspuns corect!   10
5   4ms   1136kb   Raspuns corect!   10
6   16ms   2180kb   Lungime incorecta!   0
7   32ms   4120kb   Raspuns corect!   10
8   32ms   3764kb   Raspuns corect!   10
9   32ms   4136kb   Raspuns corect!   10
10   32ms   3368kb   Raspuns corect!   10
Punctaj total   90


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Gabriel Bitis din Martie 12, 2008, 22:01:07
poti sa vezi care e testul 6 (cel pe care iei Lungime incorecta) si sa vezi cat iti da tie si cat ar trebui sa iti dea.. poate gasesti singur ce e gresit :)


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Stefan Gheorghe din Martie 12, 2008, 22:03:12
Si cum vad care e testul 6?pls?


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Gabriel Bitis din Martie 12, 2008, 22:04:52
In coltul din dreapta-sus pe pagina problemei ai un link "Listeaza atasamente"... acolo gasesti si testul si raspunsul.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Maria Stanciu din Martie 12, 2008, 22:05:32
http://infoarena.ro/problema/cmlsc?action=attach-list


L.E.: :)


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Gabriel Bitis din Martie 12, 2008, 22:06:44
http://infoarena.ro/problema/cmlsc?action=attach-list

Merita un + la karma.. eu nu m'am gandit sa'ti dau link'ul.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Florian Marcu din Martie 12, 2008, 22:30:22
http://infoarena.ro/problema/cmlsc?action=attach-list

Merita un + la karma.. eu nu m'am gandit sa'ti dau link'ul.

Si tu meriti. Tu ai explicat la cazul general, pentru a sti ce sa faca si pentru celelalte probleme din arhiva educationala. Deci practic ai dat mai multe linkuri.  :D


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Mari n din Martie 30, 2008, 18:28:29
La unele dintre problemele din arhiva educationala apare si sectiunea: probleme de pe infoarena care folosesc tehnica respectiva. Ma gandesc ca ar fi util ca la toate sa apara asta.
As dori si eu dinamici asemanatoare cu:
1 cel mai lung subsir comin a 2 siruri;
2 dinamica mixta (gen parantezari)
3 distanta minima de trecere intre doua cuvinte
4 alte clasice n2 sau n3

Mumtumesc


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Bogdan-Alexandru Stoica din Martie 31, 2008, 09:46:59
1. cel mai lung subsir comun si cu subsiruri, in general:

Subsir (http://infoarena.ro/problema/subsir)
Iv (http://infoarena.ro/problema/iv)
Subsir2 (http://infoarena.ro/problema/subsir2)
Pscpld (http://infoarena.ro/problema/pscpld)
Password (http://infoarena.ro/problema/password)

2. programare dinamica

Dezastru (http://infoarena.ro/problema/dezastru) (gadeste-te la solutia cu programare dinamica)
Tricouri (http://infoarena.ro/problema/tricouri) (gadeste-te la solutia cu programare dinamica)
Aliens (http://infoarena.ro/problema/aliens)
Carnati (http://infoarena.ro/problema/carnati)
Lista lui Andrei (http://infoarena.ro/problema/nrcuv)
Divk (http://infoarena.ro/problema/divk)
Elimin2 (http://infoarena.ro/problema/elimin2)
Obj (http://infoarena.ro/problema/obj)
Stalpi (http://infoarena.ro/problema/stalpi)
Expresii2 (http://infoarena.ro/problema/expresii2)
Colectie (http://infoarena.ro/problema/colectie)

3. distanta minima intre doua cuvinte

Palind (http://infoarena.ro/problema/palind)
Dist (http://infoarena.ro/problema/dist) (incearca sa o faci intai de 60 de puncte)

Nu le-am pus neaparat intr-o ordine, dar am selectat probleme la care ai si solutii.
Ti-as sugera sa te uiti peste problemele de la OJI si ONI din anii trecuti la clasa a 9a si a 10a (chiar si la 11-12). acolo o sa gasesti multe probleme clasice.
Un alt set de probleme importante este Lista lui Francu (http://voronet.francu.com/probleme/rom/probleme.html). Aproape toate se gasesc pe infoarena.
Mult spor!  :thumbup:


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Berceanu Cristian din Februarie 22, 2009, 17:31:18
De ce nu vrea sa-mi citeasca din fisier text?:|


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Florian Marcu din Februarie 22, 2009, 17:33:57
De ce nu vrea sa-mi citeasca din fisier text?:|

Poti fi mai explicit ? In ce context nu iti citeste din .txt ?


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Berceanu Cristian din Februarie 22, 2009, 17:47:36
Cand vreau sa iau cei 2 vectori din fisier nu ii ia, daca scriu eu fisierul text de mana le ia, altfel nu vrea.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Florian Marcu din Februarie 22, 2009, 18:33:36
In enuntul problemei ai:
Cod:
Fisierul de intrare cmlsc.in contine pe prima linie ...

Deci trebuie sa citesti din fisierul cmlsc.in. Asadar, nu ai treaba cu .txt-urile.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Ureche Silviu Marcel din Martie 01, 2009, 11:21:56
Test Timp executie Memorie folosita Mesaj Punctaj/test
1 0ms 12kb Lungime incorecta! 0
2 0ms 16kb Lungime incorecta! 0
3 0ms 12kb Lungime incorecta! 0
4 0ms 12kb Lungime incorecta! 0
5 0ms 12kb Lungime incorecta! 0
6 4ms 352kb Lungime incorecta! 0
7 8ms 352kb Lungime incorecta! 0
8 12ms 352kb Lungime incorecta! 0
9 4ms 352kb Lungime incorecta! 0
10 4ms 352kb Lungime incorecta! 0
Punctaj total 0

Cod:
#include<fstream.h>
#define max 1026
ifstream f("cmlsc.in");
ofstream g("cmlsc.out");

int main()
{
long m,n,i,j,k=0;
int a[max],b[max];
f>>m>>n;

for(i=1;i<=m;i++)
 {
  f>>a[i];
 }
 for(i=1;i<=n;i++)
 {
  f>>b[i];
 }

 for(i=1;i<=m;i++)
 {
  for(j=1;j<=n;j++)
  {
   if(a[i]==b[j])
    {
     k++;
    }
  }
 }

g<<k<<"\n";

 for(i=1;i<=m;i++)
 {
  for(j=1;j<=n;j++)
  {
   if(a[i]==b[j])
    {
       g<<a[i]<<" ";
    }
  }
 }
 return 0;
}

de ce nu merge?  ](*,)

Editat de admin: Foloseste tagul [ code ] cand postezi surse.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Pripoae Teodor Anton din Martie 01, 2009, 13:44:36
Pentru ca nu e corect :). Tu faci un fel de greedy daca nu ma insel. Problema se face cu programare dinamica. :) Sursa oficiala este  aici (http://infoarena.ro/job_detail/143144?action=view-source)


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Ureche Silviu Marcel din Martie 01, 2009, 19:14:13
Multumesc pentru raspuns..am sa ma uit peste sursa.. sper sa inteleg programarea dinamica..


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Farcasanu Alexandru Ciprian din Martie 02, 2009, 10:22:37
Cum fac daca vreau sa aflu cmlsc a 2 siruri si care sa fie maxim din punct de vedere lexicografic?


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Alexandru-Iancu Caragicu din Martie 29, 2009, 11:44:25
Am trimis o sursa care doar numara corect cate elemente sunt in subsirul comun, si pe urma afisam tot atati de 1 si am luat 90 puncte.  :rotfl:


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Florian Marcu din Martie 29, 2009, 19:08:01
Am trimis o sursa care doar numara corect cate elemente sunt in subsirul comun, si pe urma afisam tot atati de 1 si am luat 90 puncte.  :rotfl:

Si ce-ai castigat?  :D


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Alexandru-Iancu Caragicu din Aprilie 04, 2009, 11:09:33
Nimic.
Am luat pe urma 100 cu o rezolvare adevarata.
Spuneam doar ca 90 de pct e cam mult.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Gutu Pavel din Iunie 27, 2009, 14:31:30
Ce se intimpla daca afisez o alta solutie corecta, in afara de cea oficiala? In fisierele evaluatorului nu sunt alte solutii posibile.

http://infoarena.ro/job_detail/327183


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Florian Marcu din Iunie 27, 2009, 14:52:07
Citat
Daca exista mai multe solutii se poate afisa oricare.
(din enuntul problemei)

Deci orice solutie corecta ai afisa, ea va luat punctaj maxim.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Cristi din Iunie 27, 2009, 14:59:39
am si io o intrebare .....stiu ca ii offtopic......dar inainte la o problema...daca dadeai la solutii trimise...puteai....sa vezi solutia....acuma nu se mai poate....sau nu se mai poate la mine.....ca am vrut sa ma uit la o solutie de la o probl ca sa-mi fie mai clar unele chestii .........da acolo unde scrie: compilator cpp(de ex) mai in dreapta nu mai pot sa dau click ca sa ma duca la solutie......dc?:-/


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Savin Tiberiu din Iunie 27, 2009, 15:14:05
Mie imi merge


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Cristi din Iunie 27, 2009, 15:17:35
Mie imi merge
imi poti trimite o solutie de 100 de pcte(cpp) de la probl cu Zparcurgere: http://infoarena.ro/monitor?task=z ....ms :)


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Savin Tiberiu din Iunie 27, 2009, 15:27:15
Nu poti vedea sursele la toate probleme, doar la cele care sunt open-surse. Acele surse sunt marcate cu un header in enuntul problemei care iti zice ca poti vedea sursele la acea problema. De asemenea in tabelul cu probleme poti vedea ca unele probleme au o iconita langa numele problemei, acele probleme sunt open-surse. Problema Zparcurgere nu e.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Cristi din Iunie 27, 2009, 15:44:06
aha ms.. :wink:


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Mierla Laurentiu Marian din Iulie 12, 2009, 02:37:05
Salut tuturor!

Am sesizat o greseala in sectiunea de Indicatii de Rezolvare ale acestei probleme.
Legatura catre algoritmul de rezolvare de pe wikipedia trimite de fapt la algoritmul de rezolvare al problemei in care subsirul este format din parti consecutive ale sirului initial.

Link-ul catre algoritmul corespunzator de rezolvare, de pe wikipedia, este http://en.wikipedia.org/wiki/Longest_common_subsequence_problem (http://en.wikipedia.org/wiki/Longest_common_subsequence_problem).

Probabil, in enuntul problemei ar fi mai natural sa se foloseasca notiunea de "subsecventa" si nu de "subsir".


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Cezar Mocan din Iulie 12, 2009, 07:35:31
Subsequence din engleza inseamna subsir in romana si substring in engleza inseamna subsecventa in romana...  (cel putin asta am inteles eu) :)


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Mierla Laurentiu Marian din Iulie 12, 2009, 19:59:33
Multumesc, Cezar, am inteles. Si totusi algoritmul de la legatura  catre wikipedia nu este corespunzator acestei probleme.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Cezar Mocan din Iulie 12, 2009, 21:20:23
Da, asta asa e  :-', ar trebui sa-l schimbe un admin.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Bogdan Ionut din Septembrie 28, 2009, 15:42:12
Am o intrebare. Am facut pe pasi vectorii si matricea la sursa de 100 pe hartie, si la un moment-dat la penultimul for din toate ajung la i=1, j=0, a[1]!=b[0] si la iful d[0][0]<d[1][-1]

ii posibil sa fie -1 ? adica valoarea ii tot 0 ? nu am mai intalnit -1 pana acum.
sper ca ati inteles ce-am vrut sa zic :)


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: livica din Mai 15, 2011, 09:34:07
vreau sa remarc o greseala referitor la linkul catre wikipedia. Ala se refera la longest common substring nu subsequence.
De fapt la problema asta este vorba de secventa nu subsir !!!!!!!!!!!!!!!!!!


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: George Marcus din Mai 15, 2011, 09:46:01
Ăăă... mi se pare mie sau problema se numeste "Cel mai lung subsir comun" ?


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Paul-Dan Baltescu din Mai 15, 2011, 10:37:40
vreau sa remarc o greseala referitor la linkul catre wikipedia. Ala se refera la longest common substring nu subsequence.
De fapt la problema asta este vorba de secventa nu subsir !!!!!!!!!!!!!!!!!!

Ai dreptate, am modificat link-ul.

Ăăă... mi se pare mie sau problema se numeste "Cel mai lung subsir comun" ?

Termenii pe care ii utilizam in limba romana (cel putin la olimpiade) nu se potrivesc in acest caz cu cei din limba engleza. Acolo substring = subsecventa si subsequence = subsir.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: George Marcus din Mai 15, 2011, 13:40:37
Aa, da?  :shock: Ce ciudat, chiar nu stiam asta. Si e foarte ilogic.  :eyebrow:


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Mihai Visuian din Decembrie 01, 2011, 12:10:40
Avand in vedere ca problema face parte din arhiva educationala, nu ati putea posta si niste exercitii ce se rezolva pe baza acestui algoritm?


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: George Marcus din Decembrie 01, 2011, 12:34:01
http://infoarena.ro/problema/euro2
http://infoarena.ro/problema/cuburi3
http://infoarena.ro/problema/subsiruri


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Petru Trimbitas din Decembrie 01, 2011, 13:33:15
http://infoarena.ro/problema/euro2
http://infoarena.ro/problema/cuburi3
http://infoarena.ro/problema/subsiruri
Ce ai pus tu sunt pentru cel mai lung subsir crescator


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: George Marcus din Decembrie 01, 2011, 13:38:50
Mda, scuzele mele. Neatentia :)


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Stangaciu Daniela din Noiembrie 12, 2012, 11:00:41
Evaluatorul pentru aceasta sursa s-a blocat.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Dumitru Andrei Georgian din Noiembrie 12, 2012, 14:52:17
Evaluatorul merge. Ai primit eroare de compilare pentru ca nu ai inclus libraria cstring(necesara pentru a putea folosi strlen).


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Mihai Calancea din Noiembrie 12, 2012, 14:57:00
Nu, avea dreptate :). Cazuse evalul, dar l-a reparat Adi.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Salagean Calin din Noiembrie 17, 2012, 22:07:53
Aveti idee care este problema la sursa mea ? http://infoarena.ro/job_detail/818736 (http://infoarena.ro/job_detail/818736)


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Andrei Grigorean din Noiembrie 17, 2012, 22:14:18
Nu faci bine reconstituirea solutiei. Trebuie sa incepi de la (N, M) si sa generezi solutia invers.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Mercea Otniel din August 09, 2013, 10:05:15
cum pot sa afisez toate sirurile care au lungimea comuna maxima?


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Mercea Otniel din August 09, 2013, 10:05:31
cum pot sa afisez toate sirurile care au lungimea comuna maxima?


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: George Marcus din August 10, 2013, 14:30:01
E exact ca si reconstruirea solutiei, doar ca mergi recursiv in toate directiile.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Stancioiu Silviu din Martie 15, 2014, 18:26:51
ce inseamna eraoraea Killed by signal 11(SIGSEGV) ? : http://www.infoarena.ro/job_detail/1143256


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Dragan Andrei Gabriel din Martie 15, 2014, 20:59:13
uite aici: http://www.infoarena.ro/documentatie/evaluator
M-am uitat in sursa ta si ar fi indicat sa declari vectorii de lungime N+5, M+5, pentru ca sunt indexati de la 0. Atunci cand declari lungimea de N, vectorul este indexat de la 0 la N-1, iar tu accesezi pozitia N care nu exista. De acolo se trage eroarea.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Vintur Cristian din Mai 01, 2014, 11:49:54
http://www.infoarena.ro/job_detail/1180896

nu inteleg de ce iau "fisier de iesire corupt" pe testele 1 si 6

la primul test afisez exact ca si in fisierul ok, iar pe testul 6 afisez lungimea corecta, dar difera subsirurile.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: SmileSmile din August 20, 2014, 20:39:52
Ce inseamna "fisier de iesire corupt"?


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: George Marcus din August 20, 2014, 23:38:53
Sirurile pot fi mai lungi decat 30. Se da totul peste cap fiindca depasesti limitele vectorului.


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Soos Marton din Aprilie 04, 2016, 13:07:40
De ce îmi dă "Killed by signal 6(SIGABRT)" la testul nr 3?
http://www.infoarena.ro/job_detail/1674149


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: alehandru69 din Februarie 08, 2017, 22:35:53
http://www.infoarena.ro/job_detail/1873315
imi poate spune cineva ce se intimpla?


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: Bardas Florin din Martie 18, 2017, 13:00:40
Am o nelamurire legata de executarea fisierelor Java.

Primesc "Runtime Error" la orice executie, desi local imi ruleaza corect. Sunt in aceeasi situatie si la Dijsktra unde am incercat mai mult, insa la fel primesc acelasi mesaj de eroare. 


Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: mica bogdan din August 18, 2019, 13:40:04
de ce iau doar 50p ? ](*,)



Titlul: Răspuns: 001 Cel mai lung subsir comun
Scris de: William Damian Balint din August 22, 2019, 14:59:14
Poate sa-mi spuna cineva de ce imi da lungime incorecta si Killed by Signal 11 ? M-am uitat si prin alte surse si chiar nu inteleg care este problema, esuez sa vad vreo diferenta : https://www.infoarena.ro/job_detail/2450281 .