659 Cuvinte2

[•DITzoneC]

Aici puteţi discuta despre problema Cuvinte2.

[•ciprianf]

Vreo sugestie cum sa scap de TLE? Iau 85 de pcte

[•wefgef]

Ca sa iei 100 trebuie sunt suficiente urmatoarele modificari:
1. #define N 1024 pe a doua linie (e bine ca atunci cand ai matrice dimensiunile (mai putin prima - nu conteaza) sa fie puteri ale lui 2)
2. Atat in functia combin(), cat si in main ai doi de %MOD in aceeasi intructiune. Lasa-l doar pe ultimul, e suficient. Operatiile modulo sunt foarte costisitoare.
3. Peste tot unde ai (j+k) % d, inlocuieste cu f(j+k) unde f are urmtoarea definitie:

Cod:

inline int f(int a) { return a >= d ? a-d : a; }

Am ramas si eu surprins cand am vazut ca facand aceste mici modificari timpul de rulare devine de 3 ori mai mic

[•ciprianf]

  am luat 100. ms mult wefgef. Tradu-mi si mie mai exact ce face functia f. Din cate inteleg eu e asa:

Cod:

 if(a>=d) return a-d; else return a; 

. Nu cred ca e corect, deoarece pt un exemplu banal nu e echivalent cu modul. ( 7 %3=1 ; f(7)=4 dupa mine) . De cate ori e mai rapida o fctie daca pui inline decat daca nu pui?

[•stef2n]

Impartirea modulara e echivalenta cu scaderea repetata pana ajungi la o valoare intre 0 si MOD - 1. Functia f e folosita cand ai 2 numere deja cuprinse intre 0 si MOD - 1 a caror suma vrei sa o afli. Ideea e ca e necesara maxim o scadere a lui MOD din suma, intrucat aceasta e cuprinsa intre 0 si 2 * MOD - 2

[•wefgef]

am luat 100. ms mult wefgef. Tradu-mi si mie mai exact ce face functia f. Din cate inteleg eu e asa:

Cod:

 if(a>=d) return a-d; else return a; 

. Nu cred ca e corect, deoarece pt un exemplu banal nu e echivalent cu modul. ( 7 %3=1 ; f(7)=4 dupa mine) . De cate ori e mai rapida o fctie daca pui inline decat daca nu pui?

Exact ce ai presupus tu face functia f. Explicatia de ce merge a dat-o stef2n mai sus .

Functiile inline sunt folosite pentru a mari viteza de rulare atunci cand codul functiei este scurt (functioneaza oarecum ca un #define, doar ca au caractersiticile unei functii obisnuite).

[•bent_larsen]

Un hint pt 100 de puncte?

[•dornescuvlad]

Dp[ i ][ j ] - nr.cerute de lungime i, a.i sa dea restul j la impartirea cu D.
Ar merge o dinamica sub forma asta?
Am implementat dar iau 1 OK, 2 TLE si restul WA.Nu e corecta gandirea?

[•dornescuvlad]

Complexitatea mea pentru problema aceasta e O(logN * D ^ 2).Se poate mai bine?
Am dp[ i ][ j ] %= mod; care imi mareste timpul de executie..nu vad cum as putea optimiza.. (iau 85 puncte)

[•SpiderMan]

Incearca sa-l inlocuiesti cu for ( ; dp[ i ][ j ] >= MOD ; dp[ i ][ j ] -= MOD ) ; Face minuni.

[•dornescuvlad]

Editat de moderator:
@ Robert : se pare ca in cazul lui Vlad nu face minuni!
@ Vlad : pastreaza-ti calmul!
Pe viitor daca aveti ceva de impartit (neintelegeri, insulte si alte chestii d'astea), faceti'o in particular, nu in topicul unei probleme

[•SpiderMan]

DE asemenea, nici aici nu e buna limita, prea mica...

[•freak93]

Iei la fel, cred ca ar trebui sa fie ok.