Limite de timp

[•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

[•domino]

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 )
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 ... asa ca nu ai de ce sa te plangi, get to work!  

[cristi8]

ce idee buna cu limitele de timp mici
..serios..

[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?

[•domino]

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.

[•Cosmin]

Ai putea incerca metoda settextbuf in pascal ca sa faci citirea mai rapida.

[cristi8]

..sau hai cu articolul ala despre assambler, sa putem sa optimizam cat se poate indiferent de limbaj

[•Cosmin]

Chestia cu settextbuf e clasica ... se folosea si la ginfo ... sa folosesti asm pentru optimizari e un pic exagerat.

[cristi8]

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

[andreit1]

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).

[•Cosmin]

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 , vezi ca in pascal a:array[1..x] of byte; din cate tin minte are sizeof(a) = x + 1.

[Chris]

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 ). 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).

[•domino]

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.