Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Limite de timp  (Citit de 3666 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« : Septembrie 08, 2005, 11:14:17 »

Am si eu o intrebare... Ce sunt cu limitele de timp asa de stranse la ultimele probleme? De exemplu, la problema prefix am facut ca in rezolvarea oficiala O(N * T), folosind functia prefix KMP. Functia prefix am redactat-o exact ca in Cormen iar parcurgerea pt. sir periodic este un simplu for. Am primit TLE pe 4 teste...
  In plus, la problema "COLOR" am implementat o data in C si citeam cu scanf, iar a doua oara in C++ si citeam cu streamuri. Prima data mi-au dat niste teste teste TLE, a doua oara mi-au dat altele TLE!... foarte instabil... Deci tot programul meu nu facea decat sa citeasca datele, sa calculeze grade ( in timpul citirii ), si apoi mai era inca un for.. SI AM PRIMIT TLE!
  Iar la problema "SISTEM", implementand exact cum scria in explicatia de la ONI2002, aveam 75, restul TLE. A trebuit sa fac cu constante, adica retineam pentru fiecare n de la 1 la 95 (!) valoarea corecta, ca sa nu mai imi iasa din timp... La ONI era 1 sec, aici 0.1...
  _______________
 
  Limitele problemelor noi puse in arhiva ( aproape toate ) sunt mult prea mici... Daca mai e cineva, de acord cu mine, sa posteze pe acest topic... Adica cu algoritmi cu aceeasi complexitate si constanta egala nu ar trebui sa se faca diferente prin faptul ca cineva citeste cu fscanf sau cu fstream..
  DECI, SUNT SAU NU TIMPII DE EXECUTIE PENTRU PROBLEMELE NOI MULT PREA MICI?...

                                                     bubbleSORT
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #1 : Septembrie 08, 2005, 11:35:31 »

Citat din mesajul lui: filipb
Am si eu o intrebare... Ce sunt cu limitele de timp asa de stranse la ultimele probleme? De exemplu, la problema prefix am facut ca in rezolvarea oficiala O(N * T), folosind functia prefix KMP. Functia prefix am redactat-o exact ca in Cormen iar parcurgerea pt. sir periodic este un simplu for. Am primit TLE pe 4 teste...
  In plus, la problema "COLOR" am implementat o data in C si citeam cu scanf, iar a doua oara in C++ si citeam cu streamuri. Prima data mi-au dat niste teste teste TLE, a doua oara mi-au dat altele TLE!... foarte instabil... Deci tot programul meu nu facea decat sa citeasca datele, sa calculeze grade ( in timpul citirii ), si apoi mai era inca un for.. SI AM PRIMIT TLE!
  Iar la problema "SISTEM", implementand exact cum scria in explicatia de la ONI2002, aveam 75, restul TLE. A trebuit sa fac cu constante, adica retineam pentru fiecare n de la 1 la 95 (!) valoarea corecta, ca sa nu mai imi iasa din timp... La ONI era 1 sec, aici 0.1...
  _______________
 
  Limitele problemelor noi puse in arhiva ( aproape toate ) sunt mult prea mici... Daca mai e cineva, de acord cu mine, sa posteze pe acest topic... Adica cu algoritmi cu aceeasi complexitate si constanta egala nu ar trebui sa se faca diferente prin faptul ca cineva citeste cu fscanf sau cu fstream..
  DECI, SUNT SAU NU TIMPII DE EXECUTIE PENTRU PROBLEMELE NOI MULT PREA MICI?...

                                                     bubbleSORT


1. La prefix incearca fgets() la citire
2. La color trebuie optimizata citirea
3. La Sistem se poate implementa solutie O(N^2) care sa intre in timp, dar exista solutie O(N) (fara a lua in calcul operatiile cu numere mari desigur)

Motivul pentru care limitele sunt stranse sunt urmatoarele:
1. Descurajarea "modei" de a trimite solutiile oficiale la problemele puse noi... nu va ajuta cu nimic sa crestesti in clasament... (nu ma refer la tine stai linistit Smile )
2. Aveti timp nelimitat pentru a rezolva niste probleme cunoscute cat de cat, la care se pot gasi solutiile oficiale
3. Pentru ca sa va invatati sa scrieti eficient si sa faceti optimizari

La niciuna din probleme sursa mea nu contine optimizari speciale, doar chestii de bun simt, iar limitele de timp sunt alese astfel incat sa fie cu 50%-100% mai mari decat timpul maxim al sursei mele.

In concluzie, chiar daca exista probleme la care algoritmi de aceeasi complexitate nu primesc 100 din cauza de constanta, este un excercitiu foarte bun si de gandire si de implementare.. ai tot timpul din lume Very Happy... asa ca nu ai de ce sa te plangi, get to work!  Mr. Green
Memorat
cristi8
Vizitator
« Răspunde #2 : Septembrie 08, 2005, 11:40:15 »

ce idee buna cu limitele de timp mici Smile
..serios.. Very Happy
Memorat
andreit1
Vizitator
« Răspunde #3 : Septembrie 08, 2005, 12:42:36 »

Idee este buna, insa daca iau TLE( pe primele 2 teste) cu urmatoarea sursa inseamna ca ceva deja e exagerat!

var fi,fo:text;
    n,x,y:integer;
    m,i:longint;
begin
 assign(fi,'color.in'); reset(fi);
 assign(fo,'color.pas'); rewrite(fo);
 readln(fi,n,m);
 for i:=1 to m do read(fi,x,y);
 close(fo);
end.

Sau se poate face citirea in Pascal mai bine decat atat si nu stiu eu?
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #4 : Septembrie 08, 2005, 15:05:13 »

Citat din mesajul lui: andreit1
Idee este buna, insa daca iau TLE( pe primele 2 teste) cu urmatoarea sursa inseamna ca ceva deja e exagerat!

var fi,fo:text;
    n,x,y:integer;
    m,i:longint;
begin
 assign(fi,'color.in'); reset(fi);
 assign(fo,'color.pas'); rewrite(fo);
 readln(fi,n,m);
 for i:=1 to m do read(fi,x,y);
 close(fo);
end.

Sau se poate face citirea in Pascal mai bine decat atat si nu stiu eu?


Intr-adevar, Pascal s-a dovedit sa citeasca mai incet decat ma asteptam in cazul acesta.. citirea in C optimizata merge mai repede... am marit limita la 0.3 , ar trebui sa mearga acum.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #5 : Septembrie 08, 2005, 18:13:59 »

Ai putea incerca metoda settextbuf in pascal ca sa faci citirea mai rapida.
Memorat
cristi8
Vizitator
« Răspunde #6 : Septembrie 08, 2005, 19:03:02 »

..sau hai cu articolul ala despre assambler, sa putem sa optimizam cat se poate indiferent de limbaj Tongue
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #7 : Septembrie 08, 2005, 19:16:04 »

Chestia cu settextbuf e clasica ... se folosea si la ginfo ... sa folosesti asm pentru optimizari e un pic exagerat.
Memorat
cristi8
Vizitator
« Răspunde #8 : Septembrie 08, 2005, 19:31:49 »

Citat din mesajul lui: Cosmin
sa folosesti asm pentru optimizari e un pic exagerat.


da.. pt concursurile de informatica e cam exagerat sa-ti ceara asa ceva, dar asa "just for fun" mi se pare chiar misto..

..cre ca o sa ma apuc sa fac chestii d-astea dupa ce mai invat assambler, chiar daca nu le cere problema
Memorat
andreit1
Vizitator
« Răspunde #9 : Septembrie 08, 2005, 20:18:18 »

Mersi Cosmin de ideea cu settextbuf. Nu stiam. Doar ca am reusit sa imbunatatesc timpul cu 0.01-0.03 secunde( din 0.4). Se poate si mai bine, folosind valori 'potrivite' pentru buf?( eu am incercat cu 10000 si 1000000).
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #10 : Septembrie 08, 2005, 21:05:40 »

E bine cand sizeof(buf) e putere al lui 2 ca sa fie segment complet de memorie incearca sa vezi pe rand puterile lui 2 <= 1000000 ca nu sunt asa multe si vezi cu care se comporta mai bine Smile, vezi ca in pascal a:array[1..x] of byte; din cate tin minte are sizeof(a) = x + 1.
Memorat
Chris
Vizitator
« Răspunde #11 : Septembrie 08, 2005, 21:14:36 »

In general citirea byte cu byte sau valoare cu valoare e lenta. De preferabil e sa folosesti un buffer mai mare (sa citesti sa zicem 64k o data - cel putin la loaderi de imagini in BP mergea mult mai repede Smile ). De exemplu la problema "Cifra", nu se obtinea punctaj maxim daca numerele se citeau caracter cu caracter, ci era nevoie citirea linie cu linie). De fapt, si pascalul si c-ul folosesc bufferi pentru citire/scriere, dar se pare ca c-ul stie citi mai eficient.

Btw, daca ai folosit deja 100000 bytes pentru buffer, ma indoiesc ca o sa mai scoti un timp cu mult mai bun daca maresti bufferul.

Si inca o chestie : citirea nu prea o poti optimiza in asm (sau daca vrei tu neaparat, poti sa citesti din fisierere binare si sa faci tu o functie echivalenta lui read in asm care sa iti citeasca int-uri, string-uri, etc. din buffer).
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #12 : Septembrie 08, 2005, 21:43:16 »

Citirea in Pascal este cu mult mai rapida decat cea in C in general la fisiere mari... doar ca in cazul asta citirea in C a fost optimizata.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines