infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: ditzone din Martie 30, 2006, 20:24:29

Titlul: 214 Subsiruri
Scris de: ditzone din Martie 30, 2006, 20:24:29

Aici puteţi discuta despre problema Subsiruri (http://infoarena.ro/problema/subsiruri).

Titlul: Raspuns: 214 Subsiruri
Scris de: Andrei-Lucian Croitoru din Aprilie 02, 2006, 10:22:13

Am si eu o intrebare intrebatoare: ce au testele 8 si 10?
Programul merge perfect pe restul testelor, iar la 8 si 10 primesc "incorect sau fisier de iesire lipsa". :sad: Sunt convins ca algoritmul e corect, toate variabilele sunt long int, vectorii respecta restrictiile etc. Nu stiu ce sa-i fac...
Daca poate cineva sa ma ajute as fi foarte recunoscator...

Titlul: Raspuns: 214 Subsiruri
Scris de: Bogdan-Cristian Tataroiu din Aprilie 02, 2006, 10:23:39

Ai uitat sa faci modulo 9901 pe parcursul programului probabil... Nu ti s-a mai raspuns odata pe forumu vechi? :)

Titlul: Raspuns: 214 Subsiruri
Scris de: nivan din Mai 11, 2006, 20:51:32

Hmm... cum %&*$%%&^$ :
TEST 1   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 2   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 3   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 4   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 5   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 6   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 7   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 8   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 9   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 10   ...[0.01s]...   RUN ERROR - Invalid memory reference
](*,)

Cand eu o compilez pe linux si merge! ](*,) Destul de ciudat.

Titlul: Raspuns: 214 Subsiruri
Scris de: u-92 din Mai 11, 2006, 21:30:13

o compilezi.. dar de rulat? baga mai multe teste si daca totul e ok si persista mesajul pune undeva codul sa vedem.. mi s-a mai intamplat si mie sa am ceva constante declarate la inceputul programului si sa nu compileze din cauza asta pe infoarena

Titlul: Răspuns: 214 Subsiruri
Scris de: Bondane Cosmin din Februarie 02, 2008, 18:48:19

Cod:

Acest numar se va afisa modulo 9901.

Este restrictie in enuntul pb, nu este o optimizare.

Titlul: Răspuns: 214 Subsiruri
Scris de: Farcasanu Alexandru Ciprian din Februarie 20, 2008, 08:29:50

Sunt incepator si.......nu prea stiu cum sa fac cu problema asta,adica nu stiu cum sa determin subsecventele alea....imi poate explica si mie cineva daca este amabil?

Later Edit: Am aflat ca trebuia facuta cu dinamica, am invatat dinamica, si ma rog, iau pe program doar 80 de pcte , WA la testele 8 si 10.....am vazut ca au mai fost discutii privind aceste 2 teste...este vre-un caz special ?Am pus si %9901

Later later edit: am rezolvat-o pana la urma....eu puneam initial doar la sfarsit %9901, si am corectat punanad peste tot %9901 cand adunam.... erau mai mult de 2 miliarde de posibilitati la un test? ca altfel daca nu iesea din long nu-mi explic de ce ar fi dat WA

Titlul: Răspuns: 214 Subsiruri
Scris de: Adrian Diaconu din Februarie 23, 2008, 12:40:22

Imagineaza-ti un test de genul

Cod:

2 1 4 3 6 5 ... n n-1

Rezultatul pentru acest test este 2^n/2 care depaseste cu mult 2 miliarde.

Titlul: Răspuns: 214 Subsiruri
Scris de: Ionescu Robert Marius din Martie 17, 2008, 18:36:03

se pot repeta 2 subsiruri?? :oops: ca prima oara practic cautam toate posibilitatiile si luam 80 cu 2 TLE si acuma nu le mai formez .. fac ceva in genu c[ i ] = c[j] daca b[ i ]<b[j]+1 si c[ i ]++ daca sunt egale iar numarul de subsiruri maxime le gasesc adunand la fiecare b[ i ] maxim c[ i ] la nr ce e gresit? :sad: :peacefingers:

Editat de admin: Ai grija cand pui chestii de genu [ i ] sa lasi spatii intre i si acolade, deoarce altfel iti face textul italic.

oky ms :D

Titlul: Răspuns: 214 Subsiruri
Scris de: Adrian Diaconu din Martie 18, 2008, 21:27:39

Acolo nu trebuie sa faci c[ i ] ++, trebuie sa ai c[ i ] += c[ j ](in cazul in care sunt egale) deoarece poti sa iei toate subsirurile care se termina in j nu doar unu din ele.

Titlul: Răspuns: 214 Subsiruri
Scris de: Ionescu Robert Marius din Martie 18, 2008, 21:53:25

](*,) uneori ma uimesc cu ce greseli pot sa fac .ms :yahoo: :ok:

Titlul: Răspuns: 214 Subsiruri
Scris de: Andrici Cezar din Noiembrie 21, 2008, 21:12:19

nu inteleg deci incerc sa fac problema dar nu imi gaseste toate subsirurile imi gaseste doar trei cum ar trebuii sa le iau pe toate?

Titlul: Răspuns: 214 Subsiruri
Scris de: Paul-Dan Baltescu din Noiembrie 21, 2008, 23:56:23

Foloseste cu incredere punctuatia. E bine sa scrii corect, daca vrei sa fii ajutat.

Daca inteleg eu bine ce intrebi, pentru a rezolva problema ai nevoie de programare dinamica.

Titlul: Răspuns: 214 Subsiruri
Scris de: Andrici Cezar din Noiembrie 22, 2008, 09:22:24

bine! o sa o caut si o sa invat acesta cautare dinamica! , dar unde o gasesc?

Titlul: Răspuns: 214 Subsiruri
Scris de: Paul-Dan Baltescu din Noiembrie 22, 2008, 14:26:24

Programare dinamica, nu cautare dinamica. Din cate am auzit, un inceput bun ar fi cartea doamnei Cerchez despre programare dinamica. Eu personal am invatat rezolvand cat mai multe probleme de acest gen.

Uite un tutorial (http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg) care s-ar putea sa-ti fie de folos (sau macar sa te lamuresti putin cum sta treaba).

Titlul: Răspuns: 214 Subsiruri
Scris de: Andrici Cezar din Noiembrie 22, 2008, 20:08:28

Dami unul in romana ca eu nu prea inteleg engleza

Titlul: Răspuns: 214 Subsiruri
Scris de: Prigoana Cristian din Martie 23, 2009, 15:20:32

numarul de subsiruri cum se afla ? un hint, ceva, pls :D

Titlul: Răspuns: 214 Subsiruri
Scris de: Dragos Oprica din Martie 23, 2009, 15:42:51

Citat din mesajul lui: Prigoana Cristian din Martie 23, 2009, 15:20:32

numarul de subsiruri cum se afla ? un hint, ceva, pls :D

e tot programare dinamica:
tii un vector v[ i ]=numarul de subsiruri de lungime maxima pana la pozitia i

daca nu iti dai seama de relatie dami un pm :peacefingers:

Titlul: Răspuns: 214 Subsiruri
Scris de: Sergiu-Ioan Ungur din Martie 27, 2009, 11:16:18

Pic testele 8 si 9. Rezolv problema cu dinamica, dar nu'mi dau seama ce gresesc. As fii recunoscator celui ce mi'ar da ceva sugestii :D.

Titlul: Răspuns: 214 Subsiruri
Scris de: UAIC.VlasCatalin din Iulie 11, 2011, 00:06:25

dar care e relatia de recurenta pentru v?

Titlul: Răspuns: 214 Subsiruri
Scris de: Cristian Lambru din Iulie 11, 2011, 11:07:33

Presupunem ca Best[ i ] = 7 si descoperi ca Best[ i ] = 7 se poate forma de pe doua pozitii anterioare cu Best[ i ] = 6, dar acestea doua la randul lor se pot forma din 2 si 3 posibilitati si tot asa in continuare prin recurenta.

Multa bafta :) !

Titlul: Răspuns: 214 Subsiruri
Scris de: UAIC.VlasCatalin din Iulie 11, 2011, 22:38:44

ms pentru hint (Lambru Andrei Cristian) aveam cam aceeasi idee numai ca nu mi se primea s-o implimentez, acum insa am mai analizat si pina la urma am luat 100 :yahoo:

PS: pentru ce care au probleme cu testul 8 si 10, puneti peste tot unde lucrati cu vectorul in care tineti numarul de subsiruri mod 9901 si totul se primeste pe 100p...

Titlul: Răspuns: 214 Subsiruri
Scris de: UAIC Ion Caliman din Iulie 15, 2011, 18:25:12

Spuneti-mi va rog cineva ce nu fac corect in algoritmul meu, primesc WA si nu gasesc greseala

Cod:

#include <fstream>
using namespace std;
ifstream f("subsiruri.in");
ofstream g("subsiruri.out");
int v[2000],n,i,j,best[2000],nr[2000],lmax,num;

int main()
{
    f >> n;
    for (i=1; i<=n; i++) f >> v[i];
    for (i=1; i<=n; i++)
    {
        best[i]=1;
        nr[i]=1;
        for (j=1; j<i; j++)
        if (v[j]<v[i] && best[j]+1>best[i])
        {
            best[i]=best[j]+1;
            if (best[i]>lmax) lmax=best[i];
            nr[i]=nr[j];
        } else if (v[j]<v[i] && best[j]+1==best[i]) nr[i]=(nr[i]+nr[j])%9901;
    }
    for (i=1; i<=n; i++) if (best[i]==lmax) num=(num+nr[i])%9901;
    g << lmax << '\n' << num;
}

Pe testele mele mergi bine

Titlul: Răspuns: 214 Subsiruri
Scris de: George Marcus din Iulie 15, 2011, 20:47:44

Chiar daca ai luat 100, ar fi bine sa initializezi lmax cu 1, in caz ca lungimea maxima e 1.

Titlul: Răspuns: 214 Subsiruri
Scris de: Mihai Visuian din Noiembrie 30, 2011, 19:57:35

nu inteleg... cum imi dau seama daca trebuie %9901? dece tocmai 9901? care e logica?

Titlul: Răspuns: 214 Subsiruri
Scris de: George Marcus din Noiembrie 30, 2011, 20:00:49

Asa ti se cere in enunt. La alte probleme poate fi alt numar.

Titlul: Răspuns: 214 Subsiruri
Scris de: Mihai Visuian din Noiembrie 30, 2011, 20:02:49

am pus modulo si iau 80 pct cu WA pe testele 8 si 10... au ceva special???

un plus la karma nu costa nimic :D:D

Titlul: Răspuns: 214 Subsiruri
Scris de: Paul-Dan Baltescu din Noiembrie 30, 2011, 22:33:22

Nu exista nici o logica pentru care a fost ales exact numarul 9901. Dar cerand rezultatul modulo un numar x, nu trebuie sa implementezi numere mari plecand de la urmatoarele observatii:

(a+b) % x = ((a % x) + (b % x)) % x
(a*b) % x = ((a % x) * (b % x)) % x.

Pe scurt, aceste observatii spun ca e ok sa pastrezi la fiecare pas doar restul modulo x al numarului cautat.

Titlul: Răspuns: 214 Subsiruri
Scris de: Pirtoaca George Sebastian din Septembrie 10, 2013, 13:47:17

Ambele cerinte se pot rezolva in O(n * log N) folosind normalizare si apoi un arbore de intervale, dar nu este necesara complexitatea asta aici. Se poate lua 100 cu O(n^2). :ok:

Titlul: Răspuns: 214 Subsiruri
Scris de: Pirtoaca George Sebastian din Septembrie 10, 2013, 18:30:51

Nu, normalizarea a n numere cuprinse intre 1 si X inseamna sa atribui fiecarui numar o valoare cuprinsa intre 1 si N (de obicei) astfel incat relatiile de ordine sa se pastreze, adica daca numarul i > numarul j inainte de normalizare expresia trebuie sa fie adevarata si dupa. Ex: trebuie sa normalizam numerele 10,5,20,15,13,18 , vom avea : 2,1,6,4,3,5.
Normalizarea se poate face usor sortand numerele si pastrand pozitiile lor in sirul initial. :)