Uvod u TopCoder

TopCoder

Siguran sam da je i ranije bilo price o TopCoderu na ovom forumu,
ali nisam primetio da su se ljudi odazvali. Pa eto, pokusacu jos
jednom da zainteresujem ljude. Na pocetku vam mogu reci da je to
jedna veoma zarazna vrsta takmicenja iz programiranja (barem meni i
ljudima koje ja poznajem).
A o detaljnom objasnjenju citajte dalje.

TopCoder organizuje takmicenja iz raznih oblasti, ali za sada cu samo
opisati algoritamska takmicenja, gde se resavaju problemi slicni ovima
na z-treningu.

Jedna NAPOMENA na pocetku : prog. jezici koje mozete koristiti su :
C++, Java, VB, C#, Python.

Dakle, (uglavnom) jednom nedeljno se organizuje po jedno takmicenje.
Postoje 2 divizije : Div1(jaca) i Div2(slabija).
U kojoj ste diviziji zavisi od vaseg ratinga(pomenucu ga kasnije).

U svakoj diviziji se rade po 3 zadataka (easy, medium, hard).

Tezina zadataka je otprilike sledeca :
easy - vise od ~90% takmicara bi trebalo da ga uradi (uglavnom vuce 250 poena).
medium - recimo, ~30-40% takmicara bi trebalo da ga uradi (uglavnom vuce 500 poena).
hard - 5-10% takmicara bi trebalo da ga uradi (uglavnom vuce 1000 poena).

Naravno, tezine zadataka u Div1 i Div2 se razlikuju. Div1 easy je uglavnom isti kao
i Div2 medium. Dakle, tezina zadataka se "pomera za jedan".

Kao prvo, za takmicenje se morate registrovati iz TC Arene (koja je dostupna na
www.topcoder.com/tc u gornjem levom uglu) u periodu od 3h pre pocetka takmicenja
do 5min pred pocetak.
Kada se faza registrovanja zavrsi, posle par minuta takmicari ce biti rasporedjeni
u sobe. U svakoj sobi ima ~20 takmicara. U sobu ulazite iz "Active Contests->enter".

Faza kodiranja traje 1h 15min. U njoj radite zadatke i shaljete.
Veoma bitne stvari oko ove faze je da posle otvaranja nekog problema,
startuje se tajmer. I u svakoj jedinici vremena se skida odredjen broj
poena. Dakle, poslati problem posle 10min i posle 1h nije isto (tacnije, nije ni blizu).
Recimo, da poshaljete zad. od 500 poena posle 10min dobijete ~420, a posle 1h ~200.
Jos jedna bitna stvar je da ponovno slanje zadatka skida 10% ukupnih poena od zadatka.
Dakle, trebate biti sto brzi i efikasniji.

Po zavrsetku te faze nastupa 5 minuta odmora.

Zatim krece tzv. "challenge" faza. U njoj mozete gledati tudje kodove takmicara iz VASE SOBE
i ukoliko pronadjete neku gresku u njima sastaviti test primer i pokusati
da "oborite" to resenje. Ako je pokusaj uspesan dobijate 50 poena, a ako nije gubite 25.
Ova faza traje 15min (sem na turnirima).

Posle toga je sve prepusteno TCu. Sledi tzv. "System Test".
U njemu se vase resenje testira sa odredjenim brojem test primera.
Da bi resenje bilo uspesno, mora proci SVE test primere.
Posle relativno kratkog vremena videcete konacne rezultate testiranja.

Sledece je update-ovanje ratinga. Vasa pozicija na ukupnoj rank listi (ne onoj iz vase sobe)
ce najvise uticati na vas novi rating. Po udpate-ovanju cete biti obavesteni.

I to bi trebao biti kompletan opis jednog takmicenja.

Jedina stvar koja je ostala nerazjashnjena je "Gde i kako mi tamo kodiramo?".

Format u kome se rade TC zadaci je sledeci :

class ImeProblema {
 public :
  tip_rezultata glavnaFunkcija(parametri) {
   // radi zadatak
   return rezultat;
  }
};

Dakle, rezultat glavne funkcije treba biti i resenje problema.
No, vi niste obavezni da sav kood pisete u ovoj funkciji, pa cak
ni u ovoj klasi. Mozete sasvim slobodno imati globale promenljive i funkcije.

Postoji nekoliko plug-inova koji olaksavaju kodiranje. Mislim da je
za pocetnike najbolji tzv. KawigiEdit (sto ne znaci da je nesto slabiji od
ostalih plug-inova).
Njega mozete preuzeti odavde :
http://www.topcoder.com/tc?module=Static&d1=applet&d2=plugins
Na istoj stranici je prisutan i link ka uputsvu za instaliranje i koriscenje.

Savetujem vam da pre nekog "pravog" takmicenja odradite i neka prosla. Njih mozete
naci u appletu iz "Practice Rooms->...". Verujem da cete se snaci dalje.

I, to bi bilo to.. Mozda sam nesto propustio, ali sam sasvim siguran da je
ovo sasvim dovoljno svakom da pocne sa takmicenjima (meni niko nista nije pokazao :)).

Nadam se da nece ispasti da sam ovo dzaba kucao :)
Toplo vam savetujem da probate. Videcete koliko je zanimljivo..
Ocekujem vas vec na sledecem takmicenju :)

Ako imate jos nekih pitanja, samo recite.

Pozdrav, i SRECNO !

Ja sam kratko vreme na topcoderu i nije mi bilo jasno sta je to "Powered by kawigiedit" i takve stvari :D sad si mi stvarno pomogao . Hvala

A sta koristim za pretvaranje od string u int i obratno (u c++)
Ima li neka ednostavna STl funkcija?

Ono sto ja znam
int a;
istringstream iss(string);
iss >> a;

To je da iz stringa uzmes int

int a = 5;
string ret;
ostringstream oss(ret);
oss << a;
cout << oss.str(); // ispisuje 5, ali stavio ti je u string i mozes da mu pristupis sa oss.str()

fala mnogu, tekstot e odlicen !

@darkspirit: ja koristim sscanf i sprintf.

Oni rade normalno kao i scanf i printf, samo sto prije ostalih parametara primaju jos jedan dodatni, polje charova.

npr:

char unos[ 20 ];
scanf( "%s", unos );
// unesemo "5 3"
int a, b;
sscanf( unos, "%d %d", &a, &b );
// ucitati ce dva integera u varijable a i b, no umjesto sa standarnog ulaza, to ce uciniti iz polja charova "unos"
char ispis[ 20 ];
sprintf( ispis, "%d", a + b );
// ispisati ce jedan integer ( u ovom primjer, 8 ) u polje charova "ispis"

@tgudlek:

Da li sa sscanf i spintf treba da se ukljuci sstream datoteka?

Ne, to su ti funkcije iz cistog C jezika. sstream je biblioteka (ispravite ako gresim) iz STL-a, koji je deo C++ jezika. sstream ukljucujes samo kada koristis stringstream.

@Al3kSaNdaR: dobro ti kaze iggy91. Takodjer, na TopCoderu ti zna doci neki string kojeg trebas parseati( naprimjer, daju ti podatke o nekom igracu u obliku "IME REZULTAT BROJ_POKUSAJA" ). Mogao bi naci gdje pocinje i zavrsava koji od ovih dijelova, pa onda pretvarat samo taj dio u broj, a mozes i jednostavno sscanf( podaci[ i ], "%s %d %d", unos[ i ], rez[ i ], pok[ i] );, pri cemu je "podaci" polje polja charova ( matrica, jelte ), a "rez" i "pok" polja integera.

( Ako nije jasno, reci, pa da probam malo polakse i u vise koraka objasniti ) :)

Ok, nisam jos poceo da se takmicim na TC ( ima vremena ) , ali je dobro znati sscanf. Hvala na pojasnjenju. :)

Hm... kod tog sscanf... Moram li stavljati space za razdvajanje u stringu koji oznacava format unosa? Dakle, moze li "%s%d%d" umesto "%s %d %d"?

I ako je unos, recimo, razlomak oblika "12/5", ucitavam ga sa sscanf(ulazni_string, "%d/%d", &a, &b);

Kako bi recimo ako je unos vreme u obliku "12:30"? Mislim, na koje sve nacine moze?

I postoji li neka funkcija kojoj se kao parametar moze dodati stdin pa da se parsira direktno sa ulaza a ne da se prvo ulaz smesta u string pa iz stringa da se parsira?

Ne znam tocno, probaj. Mislim da ne radi ako ucitavas

xxx-xxx

sa scanf( "%s-%s", unos, unos1 );

( dva stringa izmedju kojih je neki znak ( ne razmak ) ). A mozda to samo moj Dev Cpp :D

Nije samo tvoj Dev... Ako u %s u formatu po defaultu oznacava citanje niza znakova, sve dok se ne pojavi razmak, novi red ili EOF... Ali u formatu za ucitavanje niza znakova se moze manualno zadati koji znakovi ce oznacavati kraj citanja...
Recimo ako zelis da scanf ("%s", unos); cita sve do kraja reda ( zanemaruje razmak ) koristis:
scanf ("%[^\n]", unos );
- u ovom slucaju je ce citati sve osim znaka \n (novi red )

Ako recimo zelis ucitati vrijeme ( minute i sate u poseban string ) :
char sati[5], minute[5];
scanf ("%[^:]:%s", sati, minute);

ili jednostavno direktno u int:
int h, m ;
scanf ("%d:%d", &h, &m);

Moželi mi itko naći neki lagan zadatak na TOPCoder-u??

http://www.topcoder.com/tc?module=ProblemArchive&sr=&er=&sc=&sd=&class=&cat=&div1l=&div2l=1&mind1s=&mind2s=&maxd1s=&maxd2s=&wr=