RSS

Cum sa furi puncte la OJI

17 Feb

Incep o serie de articole despre olimpiade care sper sa fie folositoare.

La oji fiind doar doua probleme diferentele de punctaj sunt destul de mici in general, iar deseori unele mici “optimizari” fac departajarea intre  concurenti, diferentele intre calificare si necalificare fiind cateodata mai mici de 10 puncte. Deseori unii concurenti pierd timpul cu probleme peste nivelul lor in loc sa incerce sa-si imbunatateasca punctajul deja obtinut sau sa ia puncte pe solutii proaste sau neoptime. Cateodata acest lucru ii face sa rateze calificarea, iar judetul sa trimita la ONI concurenti mai slab pregatiti care si-au folosit timpul in mod util in timpul probei.

Sa presupunem ca esti la OJI si nu te prinzi de probleme

  1. Nu te nelinisti, cel mai probabil nimeni nu s-a prins de toate problemele
  2. Implementeaza solutii ineficiente din punct de vedere al timpului.
  3. Tratati cazuri particulare: n=1, n=m. La multe probleme se specifica formatul testelor si puteti lua puncte tratand cazurile particulare.
  4. Rezolvati cerintele partiale (pentru afisarea corecta a primului numar se acorda 10% din punctaj)
  5. Citirea fara streamuri merge mai bine la oji din cate stiu eu

Banuiesc ca astea sunt  stiute de multa lume. Totusi mai exista cateva trucuri prin care iti poti mari si mai mult punctajul.

  1. In caz ca algoritmul tau e ineficient din punct de vedere al timpului, nu il lasa la evaluare sa ia tle. Opreste-l dupa 2 000 000 calcule(n=min(n,2 000 000)). Asa nu vei pierde punctajele partiale pentru celelalte cerinte si ai sanse destul de mari sa mai prinzi teste.
  2. Poti sa iei puncte cu greedy-uri gresite. Totusi incearca sa le imbunatatesti. De exemplu pentru siruri poti rula si de la inceput la sfarsit un algoritm si de la sfarsit la inceput pentru a gasi mai bine optimul. Incearca sa combini mai multe strategii, totusi nu pierde timpul cu tratarea multor cazuri particulare pentru ca pierzi mult timp pe care l-ai putea folosi la rezolvarea altor probleme.
  3. Optimizeaza solutiile ineficiente. Cauta liniile care se executa cel mai des si incearca sa optimizezi continutul lor.  Nu uita sa dai break acolo unde programul se executa degeaba. Incearca sa nu faci nici un calcul in plus.
  4. Parseaza citirea(fread citeste TOATE caracterele din fisierul de intrare(inclusiv ‘\n’) de aceea merge mai rapid decat functiile obisnuite de citire):
    //
    FILE* fin=fopen("color4.in","r");
    const unsigned maxb=30000192;
    char buf[maxb];
    unsigned ptr=maxb;
    
    inline unsigned getInt(){
        unsigned nr=0;
        while(buf[ptr]<'0'||'9'<buf[ptr])         if(++ptr>=maxb)
                fread(buf,maxb,1,fin),ptr=0;
        while('0'<=buf[ptr]&&buf[ptr]<='9'){         nr=nr*10+buf[ptr]-'0';         if(++ptr>=maxb)
                fread(buf,maxb,1,fin),ptr=0;
        }
        return nr;
    }
    //

    Pentru a citi

    n=getInt()
  5. In putine cazuri daca programul e ineficient din punct de vedere al memoriei, poti sa citesti fisierul de mai multe ori (fseek pt citire fara streamuri si f.close(), f.open() ) pentru streamuri.
  6. Daca ai o dinamica in n^2 in care scoti minimul de la 0 la i si nu intra in timp, scoate-l de la i-200 pana la i. Deseori se pot obtine 100 puncte asa.
  7. Incearca sa eviti folosirea stl-ului daca esti la limita cu timpul. Chiar daca compexitatea operatiilor pe set e log N, in multe cazuri merge foarte rau.

Sper sa ajute 😀

Advertisements
 
Leave a comment

Posted by on February 17, 2013 in fun

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

 
%d bloggers like this: