|
Titlul: 659 Cuvinte2 Scris de: Adrian Diaconu din Februarie 20, 2008, 20:48:11 Aici puteţi discuta despre problema Cuvinte2 (http://infoarena.ro/problema/cuvinte2).
Titlul: Răspuns: 659 Cuvinte2 Scris de: Farcasanu Alexandru Ciprian din Iulie 16, 2008, 11:04:07 Vreo sugestie cum sa scap de TLE? Iau 85 de pcte
Titlul: Răspuns: 659 Cuvinte2 Scris de: Andrei Grigorean din Iulie 16, 2008, 16:19:25 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 ;) Titlul: Răspuns: 659 Cuvinte2 Scris de: Farcasanu Alexandru Ciprian din Iulie 16, 2008, 18:04:27 :shock: 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; Titlul: Răspuns: 659 Cuvinte2 Scris de: Stefan Istrate din Iulie 16, 2008, 18:39:15 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
Titlul: Răspuns: 659 Cuvinte2 Scris de: Andrei Grigorean din Iulie 16, 2008, 21:33:05 :shock: 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; 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). Titlul: Răspuns: 659 Cuvinte2 Scris de: Sturzu Antonio-Gabriel din Martie 16, 2010, 23:38:37 Un hint pt 100 de puncte?
Titlul: Răspuns: 659 Cuvinte2 Scris de: Vlad Eugen Dornescu din Ianuarie 19, 2011, 22:10:41 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? Titlul: Răspuns: 659 Cuvinte2 Scris de: Vlad Eugen Dornescu din Ianuarie 20, 2011, 22:38:31 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) Titlul: Răspuns: 659 Cuvinte2 Scris de: Simoiu Robert din Ianuarie 21, 2011, 12:07:45 Incearca sa-l inlocuiesti cu for ( ; dp[ i ][ j ] >= MOD ; dp[ i ][ j ] -= MOD ) ; Face minuni.
Titlul: Răspuns: 659 Cuvinte2 Scris de: Vlad Eugen Dornescu din Ianuarie 21, 2011, 16:03:07 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 Titlul: Răspuns: 659 Cuvinte2 Scris de: Simoiu Robert din Octombrie 04, 2011, 17:32:47 DE asemenea, nici aici nu e buna limita, prea mica...
Titlul: Răspuns: 659 Cuvinte2 Scris de: Adrian Budau din Octombrie 04, 2011, 20:46:46 Iei la fel, cred ca ar trebui sa fie ok.
|