infoarena

http://infoarena.ro/blog/buguri-frecvente

Uit sa sortez elementele deoarece toate testele date aveau deja elementele sortate :) !

Uit sa returnez rezultatul modulo X si uit sa sortez elementele daca toate exemplele date aveau deja elementele sortate  :aha:

Am declarat vectorul prea mare si am primit MLE. Am pierdut 100 pct pt asta la OJI 2012.

+1... stupid de des mi s-a intamplat :)

Foarte frecvent la mine, mai ales pe topcoder.


Int in loc de short. -100 la oji 2011. Am avut mare noroc ca am trecut.
Cred ca toata lumea a patit.

Tu macar te-ai calificat.Eu am ramas acasa pentru un micut "bugestain" de asta... :'(.Ehh, poate la anul  :winner1:.

Later Edit: trebuia specificat mai sus daca nu e prea stupid,"evitarea" lasarii altor variabile in fisierul de iesire,gen matrice pentru debug...stuff like that  :P!

Uit sa lucrez pe parcursul anului si nu ajung la ONI. E tot un fel de bug :-'

Eu am avut un bug in mingw, deoarece cand faceam debug, imi afisa ca sqrt (4)=0, la fel si cu sqrt (4.0), iar expresia pe care o trimiteam ca argument era 1.0*(...). Foloseam functia sqrt pentru ca aveam nevoie de radicalul unor patrate perfecte, asa ca am inlocuit-o (temporar, ca sa vad daca imi merge pe testele mele) cu un vector de 1 milion de elemente, int, in care aveam radicalii precalculati. Din pacate, la final, am uitat sa sterg acest vector din variabilele declarate, si am luat MLE pe toate testele si astfel, anul acesta, am pierdut 91 de puncte la OJI  :D.

@ Heidelbacher Andrei: Dar,te-ai calificat =D> .Asta e important. :)

Anul trecut cand am fost la Grigore Moisil am folosit variabila j1 si nu am verificat daca CodeBlocks-ul e configurat pe compilatorul care trebuie. A rezultat -100 de puncte si de la Premiul 1 la ultimul loc   ](*,) . - foarte stupid

Anul acesta la info am uitat sa nu mai citesc steletutele sa ma ajute in algorithm
si Tot asa de la primul la ultimul loc

La marimea arrayurilor: un bug specific un pic mai subtil a fost la dimensionarea arrayului pentru arbori de intervale: l-am facut 2*N, dar trebuia sa fie 2*<o putere de 2 cel putin N>. (N era 100000 si trebuia dimensiunea > 262144, eu am pus 200002).

Greseli pe care le-am facut eu pe parcursul olimpiadelor:

- pentru cei de clasa a 5-a: vedeti ca ceasul are 24 de ore  :shock:. Nu uitati sa faceti % 24.

- pentru cei de clasa a 6-a: vedeti ca viata uneori e nasoala. Se poate intampla ca nu stiu cate concursuri la rand sa te prinzi de  probleme si totusi sa nu se lipeasca cifra 100 de ele  :fool:. Singura modalitate este sa lucrati cat mai mult  :weightlift:.

- pentru cei de clasa a 7-a: cititi foarte atent enuntul  :readthis:. sa nu va treziti dupa concurs sa ziceti: "A stai  :aha:!!!! Da ce credeam eu ca trebuie sa fac nu are absolut NICI o legatura cu cerinta problemei  ](*,). Oare din acest motiv am luat 0  ????"

-pentru cei de clasa a 8-a:
1. vedeti cand cititi cu char ca cititi si spatiile (eu inca nu ma prind cum de imi dadea pe exemplu :rotfl:)
2. vedeti sa faceti cast la long long cand inmultiti 2 inturi.(daca e nevoie  :wink:)
3. aveti grija cu indicii pe acolo (i seamana cu j dar nu sunt acelasi caracter  :o)
4. vedeti daca puteti sa folositi AIB in loc de Aint atunci ar fi de preferat AIB  :roll:(mai mult pentru JBOI)
5. daca nu ati luat maxim pe o problema sfatul meu este totusi sa verificati testele si sa le raportati  :evil:. E posibil sa mai fie gresite.
6. Nu uitati sa tratati cazul de imposibilitate  #-o
7. Asigurativa ca faceti MODULO peste tot. Un singur loc daca ratati, ati pierdut suta   :bye:.
 
-pentru cei de clasa a 9-a:
1. declarati memoria la numere mari cat trebuie  :-'
2. de preferat sa folositu priority_queue si nu set-uri  [-X daca se poate
3. aveti grija deoarece sunteti obisnuiti sa declarati v[NMAX] si s-ar putea sa trebuiasca v[2*NMAX] :?
4. dati nume la vectori si variabile cat mai sugestive  :-k(sa nu va treziti ca un vector auxiliar se numeste A, exact ca si arborele de intervale)
5. cititi toate restrictiile problemei  :-'
6. aveti grija la initializari la dinamici  :indifferent:
7. rucsac cu baza 10^18 si long long merge mai prost decat rucsac cu baza 10^9 si int. de retinut  :thumbup:

-pentru cei de clasa a 10-a:
1. daca cumva ati terminat in 2 ore din 5 sa nu stai cum am stat eu(like a boss  8)). Testeaza nene  :readthis: !!!!!!!!!
2. aveti grija la declaratii. sa puneti double daca e nevoie deoarece e nasol sa pierzi 70 pct pe o prostie ca asta  :sad:
3. sau si mai rau. dupa ce scrii 3 kilo de cod la un dijkstra mai ciudat sa gresesti un if  :x la saturarea muchiilor si sa iei 0
4. eu la OJI am avut 2 surse. una cu baza 10 si una cu baza 10^9. am trimis sursa proasta desigur :fighting:,  cea cu baza 10. Va rog sa nu faceti asta.   :'(

Cred ca am mai avut multe greseli dar momentan cam asta imi amintesc eu acum  :P.
Sa invatati :read:, sa va distrati  :dance:, sa va relaxati :walkman: si sigur o sa faceti macel  :guns:.

MEGA-Like pentru postul lui Dani  :D

Pot sa mai adaug si eu la lista ceva ce am patit anul asta la un concurs judetean (pe post de olimpiada locala a Vasluiului) : la o dinamica pe trei vectori am vrut sa folosesc o matrice M[3][] , iar in for-urile de dinamica bineinteles fiecare din cele 3 linii avea formula ei,dar eu in cele 3 if-uri de dinamica in loc sa am if(M[0]...) if(M[1]...) if(M[2]...) am facut if(M[0]...) if(M[1]...) if(M[1]...)  :-' Ciudat e ca pe testele date mergea bine,iar pe altele cateva probabil mi-a fost lene sa le verific de mana  :oops: Interesant ca a mers de 30pct asa, diferenta pana la 100 fiind de un singur caracter  :roll:

Sfatul meu : cand aveti timp ca mine (da,terminasem dupa o ora si mai aveam doua ore  :-' ) faceti-va la fiecare problema (daca este posibil) un program brute (un back sau altceva) pentru a verifica corectitudinea implementarilor voastre  :)

3 sfaturi care mi-ar fi fost utile daca le-as fi aplicat:
1) Cititi cu atentie problemele a.i. cerinta sa fie clara. Puneti intrebari daca sunteti nesiguri
2) Cel mai important e sa salvati problemele unde/cum trebuie. Degeaba munciti la probleme,daca le salvati prost. O greseala aparent nesemnificativa cum ar fi confundarea unui "o" cu un "0", dupa cum am experimentat si eu, va conduce cu siguranta la un punctaj rotund de 0 puncte.
3) Verificati tot timpul memoria folosita. Chiar daca memoria disponibila pare arhisuficienta, este de preferat sa verificati. Eu am reusit sa busesc memoria la o problema de la oni anul trecut la care erau 128 mb disponibili.
Succes!  :)

Ma bag si eu, ce eu n-am talent? :pimp:

Problema interactiva. Scriu problema cu citire si scriere pentru modulul de interactie. Trebuie sa fac debug. Pun la comentarii cele pentru interactie (habar nu am de ce..) si imi scriu citire si scriere din fisier. Intre timp restructurez un pic codul si am un iterator folosit la afisare pe care trebuia sa-l tin permanent modulo 7.


Ok, si verific problema pe vreo 30 de teste, merge pe toate. In enunt scria ca inputul are n constant si numerele implicate in testare sunt random. Deci eram multumit, sigur merge.
Siiii sterg scrierea de la debug si o decomentez pe aia interactiva. Guess.. what..
Ca sa fie totul mai frumos, exemplul avea o anumita valoare 0 , astfel incat v[current][7] == v[current][0] == 0  8) deci am primit feedback pozitiv pe exemplu. Am luat 0.
Nu fiti noobi cu debugul. Folositi cerr , folositi orice, dar nu lasati tampenii prin cod dupa ce ati terminat cu el.

wow! seriously, wow :shock: daca citeam postul asta acum cativa ani... :fighting:
ce frumos era daca nu aflam majoritatea acestor greseli pe pielea mea
apropo de cerr, si eu il folosesc mereu, problema e sa nu il uitati in cod, deoarece sigur iei TLE
De asemenea, sa aveti grija la dimensiunea fisierului sursa, eu am depasit la OJI 2011
Si long long cred ca e cea mai frecventa greseala, cateodata nu e atat de evident ca trebuie folosit, cateodata pur si simplu scrii int din obisnuinta, desi gandesti long long... De exemplu, la problema swaps (http://infoarena.ro/problema/swaps) de la Algoritmiada 2012, runda 3, unde N era 1.000.000, dar in cod foloseam undeva N*N ce depaseste int.  :aha:

Eroare ce mi s-a intamplat des. Nu uitati sa scoateti afisari in standard error (fprintf(stderr,  sau cerr << ). Desi aparent aveti tot aceeasi complexitate puteti sa luati foarte usor TLE. (100.000 de valori va costa pe putin cateva secunde)

Alta chestie care mi s-a intamplat la ONI ,am uitat sa pun  '\n' dupa ce am afisat tot ce era de afisat, prin urmare nu am luat niciun punct pe testele respective. 

Se pare ca anul asta la a 9-a la campion trebuia sa afisezi cu '\n'
Inca un bug pe care l-am avut: trebuia sa calculez totul long long dar din obisnuinta functia mea primea ca si parametru un int.

Chiar daca sunteti presati de timp nu dati copy/paste la unele secvente de cod care se repeta(for-uri, if-uri, apelari de funnctii) :readthis:. De exemplu, mie mi s-a intamplat sa copiez cateva for-uri de vreo 3-4 ori intr-un program si am constat dupa un timp foarte lung de depanare ca al doilea for mergea pana la n in loc de m sau in alt caz sa scriu incorect (Ex: for (j=1;j<=m;i++) ) si astfel toata problema s-a dus de la un cap la altu' pe apa sambetei :x.

Aceste doua lucruri m-au costat anul trecut la OJI :sad:, deci fiti foarte atenti.

Oricum omul cat traieste invata :thumbup: si este aproape imposibil sa nu dai peste vreun bug.

@Radu pare un bug frecvent asta la arbori de intervale. Cred ca tre sa dai cu capul o data ca sa il inveti :).
@Daniel buna lista.
@Alex good one, nu stiu cum am uitat de greseli de copy paste

Initiliazati minime/maxime cu valori suficient de mari/mici , aveti grija la prioritatea operatorilor mai ales cand folositi operatii pe biti (Exemplul ar fi arborii de intervale unde poate vreti sa alocati mai mult 1 + 2 ^ n , 1 + 1<<n e echivalent cu 2 ^ n + 1 nu cu 1 + 2 ^ n. Acesta e mai mult pentru incepatori dar am patit si eu la problema Nums unde aveam alocat un arbore de 2 ^ 23 in loc de  2^15 + 8  ) . De asemenea as mai aduce aminte ca modulo din c++ poate da si negativ asa ca aveti grija la recurente cu scaderi in care trebuie afisat modulo x rezultatul.

4 bug-uri care mi-au ramas mie in minte :

- inversarea indicilor
- La finalul concursului nu deschideti cpp-ul cu notepad (sfatul meu) . Din simpla dorinta de a mai verifica o data , am deschis cu notepad si din instinct am dat un ctrl+s , insa nu am observat ca de fapt apasasem s + ctrl + s , si astfel am salvat sursa cu un s in plus. Asta a facut diferenta de la 80 la  0 puncte :)).
- initiliaziarea
- La un ONI am rezolvat o problema . Aceasta presupunea generarea unui vector la final . Din inversarea conditiei din if , vectorul meu arata exact invers. Din pacate, testul din foaie era chiar palindrom si neavand timp , nu mi-am dat teste . Foarte curios a fost ca in testele oficiale s-au gasit 3 teste palindroame :)))

Un ultim sfat : Cititi atent problema . Pe langa bug-urile de mai sus care mi s-au intamplat foarte rar, neatentia in timpul citirii enuntului m-a costat de multe ori foarte mult.

Am avut si eu probleme la OJI 2011 tot cu int in loc de short si -100 de puncte.

Cel mai enervant bug: for(i = N; i >= 1; i++)  #-o.

De asta nu m-am calificat eu anul trecut la ONI. Am zis că nu mai apăs ctrl+s în veci la concursuri. :))

Aveti grija cu numele constantelor, eu am pierdut 80 de puncte la o problema chiar acum la ONI pentru ca in loc sa declar un arbore de intervale AInt[3*XMax] l-am declarat AInt[3*NMax], unde XMax era 100005 si NMax era 805   ](*,)
In acest fel, in loc sa fiu pe locul 6, am ajuns pe 14, asa ca fiti foarte atenti la lucruri de genul acesta, pot costa foarte scump.

Int in loc de long long. Depasirea poate fi mare iar numarul sa fie pozitiv iar rezultatul sa para bun :))

Grija mare tot la long long cand faceti descompuneri. Codul urmator cicleaza cand incerc sa descompun un numar prim foarte mare:
http://community.topcoder.com/stat?c=problem_solution&rm=312577&rd=14732&pm=11135&cr=22895893

Am pierdut niste bani din cauza asta  ](*,)

Tot int in loc de long long  :D La variabila i

N-ar fi afectat daca faceam descompunerea cum trebuie :)

Ce nu inteleg e de ce te zgarcesti la o variabila? Crezi ca faci economie? De regula, intr-o problema in care e necesar sa am o variabila long long, le fac toate long long, ca sa ma asigur ca nu am probleme legate de domeniul de valori al variabilei. Exceptie fac sirurile care pot duce la "Limita de memorie depasita". Acolo, intai fac un calcul sa vad daca imi ajunge memoria, si daca nu imi ajunge sau daca cred ca daca folosesc mai putina memorie imi va imbunatati sesizabil viteza de executie a programului (adica daca imi cresc sansele sa prind teste in plus), atunci folosesc int (bineinteles doar daca valorile incap pe int), iar mai apoi urmaresc cu atentie toate locurile in care folosesc sirul respectiv ca sa nu am probleme. In general, cu cat e mai simplu codul, cu atat mai bine. Nu are rost sa te complici pentru cativa bytes in plus sau in minus.

P.S.: Cum faceai descompunerea "ca sa fie bine"?

Deseori te omoara timpul rau de tot daca faci toate operatiile pe long long  :).

O alta greseala comuna si inrudita e la ciurului lui Eratostene:


Daca nu pui acolo long long pentru n = 65 000 deja programul cicleaza. Ma rog, mai exista si alte moduri elegante de a evita asta (gen i*i <= n), dar am vazut ca lumea tinde sa faca asa. Fiti atenti.

Multumesc de sfat. E foarte tare ca il dau si eu, dar nu il aplic. O sa incerc sa tin cont de el

Descompunerea clasica pana la radical din numar

Intr-adevar, dureaza cu pana la 150% mai mult la inmultire si cu 100% mai mult la adunare daca faci asa:


fata de asa:


Dar dureaza cu 83% mai mult la adunare si 24% mai mult la inmultire daca faci asa:


fata de asa:


Daca programul tau e la limita, intr-adevar conteaza optimizarile astea, dar daca nu consuma nici macar jumatate sau o treime din limita de timp, de ce sa te complici?
(Pe topcoder limita e de 2 secunde cam la toate problemele, desi 0.1 secunde ar fi arhisuficient la majoritatea).