Sportsko programiranje. Olimpijade iz programiranja - pomažu li u stvarnom radu? O zadacima i njihovoj pripremi

Ovo je već vrlo stara holivara: jesu li sportski programeri prikladni za oštri aplikativni razvoj ili su to tako lijepe bijele ptice, koje lebde u matematičko-algoritamskim oblacima i nestaju u prizemnijim uvjetima? Postoji uobičajeni mit koji kaže da svi sportski programeri idu na Google ili, barem, na Yandex, gdje nadahnuto rade na algoritmima pretraživanja i njima sličnim. Jednostavan bjeloruski outsourcing nije za njih. Možda, ako ne kraj, onda barem interpunkcijski znak u ovoj borbi mišljenja mogu staviti činjenice. Prikupili smo podatke o svim sportskim programerima u našoj zemlji i na temelju tri kriterija:

• sudjelovao u finalu ACM ICPC;
• govorio je u ime bjeloruskog sveučilišta;
• već je završio studij na sveučilištu;

napravio odabir. Rezultat je bio popis od dvadeset i jednog finalista ACM ICPC-a iz Bjelorusije. Uspjeli smo kontaktirati većinu njih i postaviti tri jednostavna pitanja:

1. Koje je vaše trenutno mjesto rada i koja je pozicija/suština posla koji obavljate?
2. Zašto ova tvrtka/zanimanje?
3. Kakvi su vam planovi za budućnost, kako je vidite za sebe? Gdje biste željeli otići?

Neki su odabrali menadžersku karijeru, neki su ostali vjerni sportskom programu, a tko zapravo razvija algoritme pretraživanja, saznat ćete iz “izravnog govora”Bjeloruski finalisti ACM ICPC.

Ivan Mikhnevich (ACM ICPC 2000)

1. Wargaming Public Company Limited, direktor.
2. To je rezultat rasta u grupi tvrtki od samog početka moje radne karijere.
3. U stvarnosti sam već umoran od svega ovoga i vrijeme je da započnem novu karijeru, na novom mjestu, u novom polju (najvjerojatnije ne IT).

Sergey Stepantsov (ACM ICPC 2000)

1. Trenutno radim kao potpredsjednik poslovnog razvoja u Intetics Co.
2. Veći dio moje karijere vezan je uz ovu tvrtku, gdje sam se uspio okušati u raznim ulogama: počeo sam kao stručnjak za testiranje, a radio sam i kao programer, voditelj projekta i voditelj proizvodnog odjela. I na kraju sam se specijalizirao za poslovni razvoj.
3. Još uvijek se ne osjećam dovoljno staro da se prestanem razvijati :). Mislim da će me budućnost poslovnog dijela mog života tek oduševiti mnogim uzbudljivim zaokretima.

Vladimir Tankovich (ACM ICPC 2000, 2003)

1. Trenutno u Microsoftu radim na algoritmima računalnog vida za Kinectu. Prije toga bio sam u relevantnosti pretraživanja.
2. U ovoj sam tvrtki od 2005. Doveli su me iz Republike Bjelorusije i još nije bilo smisla seliti. Pridružio sam se ovom timu jer mi omogućuje znanstveni rad, koji ne ide u zbirku članaka, već u gotov proizvod.
3. Konkretnih planova za budućnost nema. U IT-ju novac nije problem, kako u Minsku tako i kod nas. Zasad sam jako zainteresiran za razumijevanje strojnog učenja i umjetne inteligencije. Ispada da gotovo cijelo vrijeme radim što god poželim, a za to sam i dobro plaćen. Odnosno, sljedeće 1-2 godine radit ću isto, a onda ćemo vidjeti. Stječem puno iskustva, a ako budem imao ideju kako to pouzdano primijeniti, okušat ću se u startupu.

Aleksej Kirkovski (ACM ICPC 2002., 2005.)

1. NT LLC "LuxSoft", programski inženjer 2. kategorije.
2. Stvarno sam želio otići u poznatu moskovsku radionicu LuxSoft, jer sam od djetinjstva sanjao o automatizaciji otvora, ali nisam primijetio jedno slovo i završio sam u bjeloruskom LuxSoftu. Tamo sam bez gledanja potpisao neke papire i sada radim pod ugovorom na 20 godina za fiksnu plaću u bjeloruskim rubljima, koja mi je dovoljna samo za benzin.
3. Planiram zadovoljiti normu broja redaka u minuti i postati programski inženjer 1. kategorije. Onda nabavite CMS u programiranju, koji će mi biti dodijeljen ovdje ako ne bude niti jednog kašnjenja na posao za cijelo vrijeme trajanja ugovora.

Aleksej Dančenko (ACM ICPC 2002., 2005.)

1. NT LLC "LuxSoft" Softverski inženjer. U U zadnje vrijeme Razvijam programski jezik specifičan za domenu za naš proizvod.
2. Prilika za suradnju s prijateljima na provedbi zanimljive ideje.
3. Nastavite uživati ​​u životu.

Evgeniy Gonchar (ACM ICPC 2003.)

1. Google Švicarska (Zürich), viši softverski inženjer. Radim na jednom od projekata infrastrukture web pretraživanja.
2. Od djetinjstva sam volio programiranje.
3. Volio bih napredovati u sviranju električne gitare i ponovno otići na Novi Zeland.

Ivan Metelsky (ACM ICPC 2003., 2004.)

1. TopCoder, Inc., koordinator problema maratona/algoritama. Pokretanje maratonskih i algoritamskih natjecanja na TopCoderu.
2. Na neki način, jednostavno se tako dogodilo. Ozbiljnije, dobra zarada, relativno zanimljiv posao, teško je naći bolju alternativu.
3. Planovi za budućnost - nije bitno gdje, ali negdje u smjeru nešto manje zauzetosti i više slobode djelovanja. Možda neki posao, ne nužno u IT-u.

Victoria Lebed (ACM ICPC 2004.)

1. Bio sam i ostao matematičar. Ona je bila jedina osoba u timu koja nije dirala računalo :) Ona je radila sve “sa strane” poslove. Živim i radim u Parizu. Trenutno imam privremenu poziciju na Sveučilištu Paris 7 - znanstvena djelatnost i podučavanje. Nedavno sam doktorirao.
2. Ova aktivnost je zato što pruža rijetku priliku za održavanje osobne i kreativne slobode.
3. Trudim se ne raditi nikakve planove za budućnost. Opet, da se ne ograničite ni na jednuonda unutar okvira i ne izlagati sebe osobno teretu očekivanja, nadanja i ostalog. dobro samZamišljam nastaviti put koji sam započeo u sveučilišnom i znanstvenom okruženju, ali ne zatvaram vrata za druge opcije.

Maxim Osipov (ACM ICPC 2004.)

1. VironIT, direktor. Upravljanje poslovanjem (uglavnom nije operativno, već usmjereno na promjenu procesa prodaje, razvoja, kvalitete rada i sl.)
2. Tvrtka VironIT, jer to je moja tvrtka, ja sam vlasnik. Ovo je tečaj (neoperativno upravljanje) jer mi je najzanimljivije smišljati kako razviti posao.
3. Razvijte svoju tvrtku, prijeđite između ostalog na proizvodni model, osnujte obitelj i djecu. Budućnost vidim kao zanimljivu, tešku, ali svakako pozitivnu.

Pavel Irzhavsky (ACM ICPC 2007., 2008.)

1. Profesor na BSU, matematičar-programer na Orientsoftu, nastavnik na ShAD-u, apsolvent (formalno je to studij, ali zapravo je bliže poslu).
2. Svaka aktivnost ima nešto zanimljivo i korisno (osim što sve donosi prihod :)), one jednostavne koje mi omogućuju da se malo opustim, a one složene koje mi omogućuju razvoj. Mislim da općenito postajem manje učinkovit kada počnem raditi istu stvar, grubo rečeno, 8 sati dnevno, a dnevna promjena aktivnosti omogućuje mi da budem na vrhuncu.
3. Nema značajnijih promjena u planovima za budućnost :)

Vladimir Kerus (ACM ICPC 2007., 2008.)

1. EPAM. Vodeći softverski inženjer odjela za mobilni razvoj. Bavim se razvojem aplikacija za Android.
2. Volim učiti nove stvari, au mom sadašnjem društvu lako mogu promijeniti profil i pronaći prave ljude-predavače.
3. Već sam posadio stablo, štedim za izgradnju kuće, planiram imati djecu (idealno, vlastitu ekipu Barcelone).

Sergey Tikhon (ACM ICPC 2009.)

1. EPAM Systems, vodeći softverski inženjer. Arhitekt/specijalni projektant.
2. Ljubazan, jak tim, zanimljivi zadaci, dobre prilike za profesionalni razvoj.
3. Rad u IT-u, ali na granici sa znanošću, rad na implementaciji Data Science u stvarne aplikacije i usluge (strojno učenje, obrada prirodnog jezika, tehnologije pretraživanja, modeliranje). Propaganda, širenje i implementacija funkcionalnog programiranja (vodim blog na F#).

Alexey Lobanov (ACM ICPC 2010.)

1. Tvrtka Yandex, programer Yandex.Maps. Paralelno s tim studiram na diplomskom studiju BSU i radim kao asistent na Zavodu za DMA FPMI (predajem praktičnu nastavu iz kolegija “Algoritmi i strukture podataka”).
2. Zašto Yandex: postoje zanimljivi zadaci (uključujući složene, intenzivne, algoritamske), udobne radne uvjete i odličan tim. Zašto FPMI BSU: Mislim da je važno prenijeti svoje znanje sljedećim generacijama studenata.
3. Planovi za budućnost: uspješno završiti diplomski studij i pokušati obraniti doktorat.

Aleksej Tolstikov (ACM ICPC 2010.)

1. BSU, asistent na Zavodu za računalnu matematiku, diplomirao diplomski studij, podučavanje tečaja« Paralelno i distribuirano računalstvo» (praksa). Yandex,kustos akademskih programa, voditelj Minske podružnice School of Data Analysis (+ tamošnji nastavnik), programer za pretraživanje.
2. Ne mogu u jednoj rečenici, već zato što: "Sviđa mi se!"
3. Nemam puno za reći. Krećem se u svim tim smjerovima.

Zanimljiv intervju s pobjednicima Svjetskog prvenstva u programiranju s Uralskog federalnog sveučilišta.

Oduvijek me zanimalo zašto su natjecanja u programiranju toliko popularna u Rusiji (točnije, općenito na postsovjetskom prostoru) (vjerojatno je izraz korišten u ovom članku prikladniji: "sportsko programiranje"), unatoč činjenici da da na raspadajućem Zapadu govorim o njima Dugo nisam ni znao, a kad sam znao, iz nekog razloga uopće me nije privlačilo. To je kao potpuno odvojen svijet. Dugi niz godina sam aktivno sudjelovao u raznim programerskim zajednicama na internetu, visio sam na mailing listama raznih open source projekata, ponekad sam susretao ljude u stvarnom životu, ali nikada nije bilo govora o TopCoderu, recimo postoji, saznao sam iz ruskog LJ, po mom mišljenju (i nakon što sam saznao za to, nisam odmah i hitno otišao tamo, napravio račun i nisam sudjelovao.) Nekako je vrlo smiješno i zanimljivo razumjeti zašto.

Dio ove popularnosti objašnjavaju neke opaske iz ovog intervjua, po mom mišljenju:

"Zašto je UrFU ovaj put pokazao najbolji rezultat? Jesu li se zvijezde posložile?"

Mikhail Rubinchik: Imamo sjajan tim. Oleg, Lesha i svi ostali su vrlo jaki momci. Oleg je sada u šestoj godini, počeo je učiti u drugoj, ali u trećoj je već imao pristojan nivo.[...]

"Što vam je bliže? Startup? Ili velika tvrtka?"

Oleg Merkurjev: Nisam uopće nigdje radio. I neću nigdje raditi sljedećih šest mjeseci. Ići ću na postdiplomski, moram malo studirati znanost, inače sam uglavnom sve vrijeme provodio na sportskom programiranju.

Oni. doista se osjeća kao sport prije svega. Uključujući neka divlja ograničenja koja su tipična za sportska natjecanja:

"Ajmo malo o samom prvenstvu. Troje ljudi u ekipi. Jedno računalo. Zašto jedno? Zašto ne troje?"

Mikhail Rubinchik: Žiri je jednom tako odlučio. To je bilo prije trideset godina.

Oleg Merkurjev: Tada su možda postojali dodatni razlozi koji sada ne postoje. A onda je i jedno računalo po timu bilo puno, ali ne puno po osobi.

[...]Na Svjetskom prvenstvu možete koristiti printer. Prvi je sjeo, napisao neko rješenje, nije išlo. Mora pronaći grešku. Čitanje s računala je skupo, ali imamo samo jedan resurs. Stoga ga ispisuju na printeru i čitaju na komadu papira.

Pa, ne razumijem kako to može biti tako privlačno. Programiranje je kreativna aktivnost. Nije bilo programa, a sada ga ima. Niste mogli nešto učiniti s računalom, ali sada možete. Je li važno je li trajalo 20 minuta ili 40? To je samo neki nezanimljiv aspekt.

Ne, mogu zamisliti ograničenja koja donose sportsko uzbuđenje – ali na razini nekoliko dana i stvarno teških, zanimljivih zadataka. Kao natjecanje Ludum Dare - napišite igru ​​u dva dana. Ili ICFP Programming Contest, daju tri dana, a uvjeti su obično fantastični. Usporedite to sa zadacima Svjetskog prvenstva u sportskom programiranju. Ako se natječete minute i sekunde (također s jednim računalom između tri), tada zadaci ispadaju ovako - lukava upotreba nekoliko standardnih algoritama s nekim lukavim "zaokretom".

Općenito, čudan je ovo svijet. Ne zamjerite mi oni koji ga se boje. Ali nisam razumio i ne razumijem.

Kažu da ga je, kad se rodio, došao vidjeti sam Donald Knuth. Kažu da je, kada su ga pozvali da radi u Googleu, cijeli algoritam pretraživanja prepisao 16 puta u 15 minuta. Kažu da napredovanje kvantnog računalstva promatra sa smiješkom, jer kad ga vidi, brojke se same faktoriraju od straha. Ali jedno znamo sigurno: Peter je pravi bog sportskog programa.

Podaci

• Pobjednik brojnih prvenstava, Peter je dva puta osvojio TopCoder i dva puta drugo mjesto na ACM ICPC.
• U slobodno vrijeme Peter piše blog o redovitim natjecanjima “Algoritamski problemi za lutke”: petr-mitrichev.blogspot.ru.
• Mitričev trenutno radi u Googleu, gdje radi na kvaliteti pretraživanja. Petar također pomaže u pripremi Google Code Jam natjecanja.

Mnogi ljudi misle da su sportski programeri cool dečki, pravi geekovi koji razumiju algoritme i rješavaju složene probleme. No, kažu i da im se kasnije jako teško negdje prijaviti. To je istina?

Sportsko programiranje i općenito ono što radimo na Olimpijskim igrama doista nije nešto od čega možete živjeti. S druge strane, programiranje je, kao i svaki drugi sport, razvoj za čovjeka. Zahvaljujući njemu čovjek postaje pametniji, bolji programer i bolji u pronalaženju grešaka u programima. Nakon takve pripreme lakše je raditi i raditi druge zanimljive stvari.

Algoritmi su svakako primjenjivi u praksi programera, iako sam se na poslu susreo i s algoritmima koji su složeniji od onih na olimpijadama. Ali na olimpijadama smo ograničeni na algoritme koji se, grubo rečeno, mogu napisati za pola sata do sat vremena. Stoga zadaci tamo koriste vrlo specifičan, ograničen skup algoritama. U stvarnom životu, stvari su jednostavno... ekspanzivnije.

Na kojem jeziku ste napisali rješenja zadataka?

U Javi. U školi sam pisao na Pascalu jer u to vrijeme nisam znao ništa drugo. A onda, kada je trebalo odabrati na što prijeći, Java se pokazala bližom Pascalu.

U konkurentskom okruženju trebate napisati program za 20-30 minuta i on bi trebao odmah raditi ispravno. Stoga je vrlo važno da jezik ne dopušta podmetanje grešaka. C++, koji većina ljudi koristi, razlikuje se po tome što ga je prilično lako pisati pogrešan program. Možete slučajno nešto zaboraviti, dodijeliti krivi tip varijabli, ali sve će se to nekako prevesti i nekako će raditi. Najvjerojatnije ne na način na koji očekujete.

U Javi, ako pogriješite ili pogriješite pri upisu, program se najvjerojatnije jednostavno neće kompilirati. Ovdje je sve strože, kao u slučaju Pascala. Ovo mi se učinilo primjerenijim. stražnja strana medalje - Java programi često rade jedan i pol puta sporije od C++ programa. Ponekad tih jedan i pol puta nije dovoljno da se program uklopi u uvjete problema.

Svatko može izabrati svoj programski jezik, zar ne?

Postoje ograničenja. Naravno, postoje različiti natječaji... uzmimo za primjer Google Code Jam. Kad smo odlučivali kako to najbolje napraviti, došli smo na ideju da možemo raditi na bilo kojem jeziku. Preuzimate ulaznu datoteku s podacima o zadatku na svoje računalo, pokrećete svoj program na računalu, a zatim šaljete rezultat na poslužitelj. Koji god kompilator/interpreter imate na računalu, to je ono što možete koristiti. Nedostatak ovog sustava je što ljudi imaju različita računala. Neki ljudi imaju deset puta moćnije računalo od drugih. Stoga moramo kreirati zadatke gdje ispravno rješenje Brzina se razlikuje od ispravne barem sto puta. Tako da ako čovjek ima deset puta sporije računalo, ispravno rješenje će mu raditi, ili na deset puta bržem računalu krivo rješenje opet neće raditi. Stoga su nam potrebni zadaci s velikim razmakom između točnih i pogrešna odluka po brzini rada.

Koristi se na Topcoderu, Codeforcesu i ACM-u standardni sustav gdje šalješ izvor i pokreću ga na svom poslužitelju. Ovdje ste ograničeni onim što imaju na poslužitelju. Većina sudionika, 70–80% koristi C++, još 20% koristi Javu, a vrlo malo drugih jezika. Ovo je, čini mi se, jedan ciklus - novi ljudi koji dođu na natjecanja počinju komunicirati s drugim, starijim sudionicima, koji novopridošle uče što i sami mogu. Kao rezultat toga, novi ljudi također počinju koristiti iste jezike. Dakle, ne radi se o tome da su ova dva jezika posebno pogodna za natjecanja, već je to tako u povijesti.

Dakle, vrijedi li sve ovo u životu? Uostalom, vjerojatno je teško naći posao gdje bi to znanje bilo korisno. Da, možete otići na Google ili Yandex, ali je li teže doći u bilo koju banku?

Čini mi se da je to vrlo koristan dio vještine, dio koji je odgovoran za sposobnost da prvi put napišete program, bez grešaka, ili da pronađete grešku u programu prijatelja. Nisam radio u banci, ali čini mi se da bi mi takve vještine i tamo bile korisne. Iako se, naravno, sami algoritmi ne koriste baš u svakom poslu. Ali osobno, ova pozadina mi puno pomaže.

Vjerojatno ste imali neku posebnu priču o tome kako ste ušli u Google?

Da, nema priče, sve je bilo isto kao i drugi. Sada radim pretragu (općeniti dio, koji ne ovisi o zemlji i jeziku), ali, nažalost, ne mogu ništa reći o tome, jer je ovo vrlo povjerljiv dio.

Sportsko programiranje: prednosti i mane

Da ti pokušam postaviti jedno glupo pitanje :). Zašto mislite da bi se trebalo baviti sportskim programiranjem?

Ovdje je sve vrlo jednostavno i slično kao u bilo kojem drugom sportu. Morate to učiniti ako vam se sviđa, ako vam to pruža zadovoljstvo. Ovo ne bi trebalo biti samo sebi cilj. O sportskom programu trebate razmišljati kao o načinu da se dobro zabavite, upoznate zanimljive ljude i tako dalje.

Što ako pokušate smisliti razlog zašto ne biste trebali gubiti vrijeme na sportsko programiranje?

Mislim da morate biti svjesni da to nije glavna stvar u životu. Imajte još neke ciljeve osim ovog. Ako vam nešto počne zauzimati apsolutno cijeli život, to je vjerojatno razlog da razmislite barem o tome da napravite pauzu.

No, što kaže praksa, može li se, primjerice, graditi karijera oko sportskog programiranja?

U Rusiji postoji nekoliko ljudi koji se profesionalno bave obukom novih sportskih programera – trenera. Andrej Stankevič, Miša Mirzajanov i drugi. Svi oni predaju na fakultetima, ali značajan dio radnog vremena provode pripremajući studente i učenike za natjecanja u programiranju. Za njih je ovo doista posao i, reklo bi se, karijera.

Jeste li i sami ikada razmišljali o ovome? Sudjelujete li ikada u žiriju ili kao problemski pisac?

Pokušao sam predavati školarcima u školi br. 57, gdje sam i sam studirao. Pokušao sam pripremiti ekipe za Olimpijske igre. Sada je u Moskvi ova tema vrlo aktivna - postoje timovi na Moskovskom državnom sveučilištu, Phystech, Srednja škola Ekonomija. Ali nekako mi podučavanje nije išlo.

Što se tiče natječaja, prije svega pomažem raditi probleme za Google Code Jam, za našu konkurenciju. Osim toga, pomažem u polufinalu ACM-a, koje se održava u St. Ovo je izbor između ruskih momčadi i momčadi bivšeg SSSR-a za finale.

Može li se zaraditi od natjecanja? Uostalom, za pobjedu daju novčane nagrade.

Vjerojatnost je preniska. Jedna nagrada na deset tisuća sudionika?.. Ne bih to nazvao zaradom. Računajući na to kao glavni izvor prihoda... čini mi se da nema šanse.

Ali, kao što sam rekao, postoji mnogo različitih natjecanja. Isti Topcoder održava natjecanja u razvoju programa. Recimo da trebate razviti komponentu za program koji to radi. Na temelju rezultata ocjenjuju tko je što dobio, a koristi se ono najbolje - klijent kupuje to rješenje i plaća novac onome tko je tu odluku donio. Ljudi koji to rade puno radno vrijeme, koliko sam shvatio, zarađuju prilično pristojan novac.

Današnja natjecanja

Recite nam pobliže, kakva natjecanja sada postoje, kako se to sve događa?

Danas postoje dvije vrste natjecanja. Postoje tjedna, redovita natjecanja. Provode ih dvije glavne stranice - TopCoder i Codeforces. Svako natjecanje traje jedan i pol do dva sata. Tamo sudionici dobivaju nekoliko problema koje moraju riješiti i poslati program na poslužitelj. Organizatori provjeravaju funkcionira li program.

TopCoder je najstarija i najpoznatija stranica s tjednim natjecanjima. Imaju sljedeća pravila. Za rješavanje tri zadatka predviđen je sat i petnaest minuta.

Zadaci se obično dijele na vrlo jednostavne, srednje teške i teške. Organizatori ih nastoje odabrati tako da, recimo, petero ljudi riješi sve probleme, stotinu ljudi dva, a svi ostali barem jedan. Štoviše, za svaki zadatak važno je kada ga predate – što kasnije, to ćete manje bodova dobiti. Tako se dijele oni ljudi koji su riješili isti broj problema. Zatim se bodovi zbrajaju. Normalan zadatak vrijedi 250 bodova. Prosječno 500. Teško 1000. U prosjeku prvoplasirani dobivaju tisuću i nešto bodova po natjecanju.

Zatim se napravi pauza od pet minuta i još petnaest minuta traže greške kod drugih. Možete otvoriti rješenje bilo koje osobe, za bilo koji problem u vašoj “sobi”. "Soba" je mjesto gdje su ljudi koji sudjeluju u natjecanju nasumično podijeljeni u grupe od dvadeset. Podijeljene su u "sobe". Možete otvoriti bilo koje rješenje bilo koje osobe iz svoje "sobe". Ako vam se rješenje čini pogrešnim, tada možete unijeti ulazne podatke na kojima će biti pogrešno. A ako stvarno daje pogrešan odgovor, za to dobivate dodatnih 50 bodova. To je, naravno, manje od cijene zadatka. Ali ovo se opet radi da bi se podijelili ljudi. Glavni bodovi se i dalje dodjeljuju za rješavanje problema, a ne za pronalaženje pogrešaka.

Nakon svega toga slijedi provjera zadataka na testovima koje je pripremio žiri. Ako zadatak ne uspije, osoba dobiva 0 bodova.

Postoji i druga stranica, ruska, Codeforces. Njihova pravila su malo drugačija, ali je format približno isti - dva sata i nekoliko zadataka. Ako želite, ovaj se format može nazvati zabavnim, za razliku od studentskih natjecanja koja traju pet sati.

Ali postoje li još uvijek velika, godišnja natjecanja?

Da, uz dva opisana natjecanja koja se održavaju tjedno, postoji još mnogo godišnjih natjecanja. Obično su strukturirani ovako: određena velika tvrtka (Google, Yandex, TopSoder, IBM) održava natjecanje s nekoliko faza odabira. Prve faze odvijaju se online. A završna faza već se održava na određenom mjestu, gdje se odvode svi finalisti. Takvih je natjecanja svega pet do deset, ali su duga, pa se jedno od njih održava stalno.

Jesu li sva ta natjecanja individualna?

Većina natjecanja sada je individualna. Ekipna natjecanja uglavnom su studentska, a glavno je ACM ICPC. I druga studentska natjecanja također se obično pretvore u ekipna jer, grubo rečeno, već imaju ekipu. Tako je lakše zainteresirati ljude. Veteranska natjecanja su obično osobna.

Tjedna natjecanja imaju rejting, poput šaha, koji se ažurira nakon svakog natjecanja. Oni koji su se bolje pokazali dobivaju plus, oni koji su se pokazali lošije dobivaju minus. Ako uopće niste sudjelovali, ocjena se ne mijenja. Sustav je izgrađen na način da izjednači ljude koji posjećuju često i rijetko. Nema pritiska da "morate stalno sudjelovati". Ima mnogo ljudi koji su puno stariji od mene, pojavljuju se vrlo rijetko - jednom u dva mjeseca - a ipak imaju dobra ocjena, jer nastavljaju dobro rješavati probleme.

Da, na prvom mjestu je Gena Korotkevich, vrlo pametan student iz Gomelja, sada studira na ITMO-u. Moji rezultati na Codeforcesu su u posljednje vrijeme lošiji; sada sam šesti ili peti. I tu je Gena na prvom mjestu.

Vjerojatno je igranje online i offline potpuno drugačiji osjećaj i iskustvo?

Sigurno. Čini mi se da je vrlo važna pozitivna strana sportskog programa to što sva natjecanja završavaju rundom na licu mjesta, gdje se okupljaju svi najbolji. Zahvaljujući tome, upoznao sam puno cool ljudi iz cijelog svijeta. Općenito, glavna “nagrada” na takvim natjecanjima je, čini mi se, upravo upoznavanje ljudi. Provodite vrijeme s njima, komunicirate, naučite nešto novo. Vrlo je smiješno da je ljude iz drugih zemalja, koji često slabo govore engleski, ipak vrlo lako razumjeti jer imaju vrlo slične interese.

U takvim natjecanjima - sa selekcijama - obično sudjeluje više ljudi nego u redovnim. Ako osoba nikad nigdje nije sudjelovala, tjedna natjecanja mogu biti problem. Ima takvih problema da čovjek možda ništa ne riješi i uzruja se. U natjecanjima s kvalifikacijama obično je sve jednostavnije, barem u prvim fazama. Njihova glavna ideja je da se svi zabave. Opet, tu je i opipljiva nagrada na kraju - novčane nagrade za prvo mjesto. Osim toga, izlet nekamo, na primjer u Googleov ured, također je poprilična nagrada.

Događa li se da tvrtke tada pokušavaju u životu koristiti razvoj rješenja konkurencije?

Prilično rijetko. Glavni cilj tvrtki koje održavaju takva natjecanja je jednostavno popularizacija programiranja. Drugi cilj je pronaći nove zaposlenike. Ali ovo drugo nije ni toliko važno. Obično tvrtka organizira natjecanje upravo kako bi što više ljudi zainteresirala za programiranje, a o onima koji su direktno sudjelovali u natjecanju i ne govorimo. Zato takva natjecanja obično održavaju velike tvrtke.

Mijenjaju li se natjecanja tijekom vremena? Postaju li sve teži ili, obrnuto, lakši?

Postaju složeniji. Sve više i više algoritama smatra se nečim iz kategorije "ovo bi svatko trebao moći", "ovo svi znaju". Morate razmišljati jednako kao i prije deset godina. Broj koraka potrebnih za izradu rješenja je isti, ali su osnovni blokovi koji čine rješenje postali složeniji. Ljudi su naučili više algoritama. Uzmimo, na primjer, stablo sufiksa: kad se pojavilo, bio sam u školi, i činilo se da je to jako cool algoritam, svi koji su ga znali bili su jako pametni, i to je općenito bila revolucija. Sada se isti problemi rješavaju pomoću sufiksnog automata, a to je vrlo jednostavan algoritam koji traje deset redaka. Odnosno, naučili su jako pojednostaviti standardne stvari. Stoga se sada rješavaju složeniji problemi.

O zadacima i njihovoj pripremi

Kako se sastavljaju zadaci za natjecanja? Postoje li prevoditelji, ljudi koji to već znaju raditi ili je ovo nekakav crowdsourcing gdje svatko može ponuditi nešto svoje?

U spomenutim tjednim natjecanjima upravo je tako: svatko može predložiti svoj zadatak. Ali postoji uvjet da je osoba prethodno sudjelovala na dovoljnom broju natjecanja. Svojevrsna provjera da li osoba razumije o čemu bi zadaci trebali biti. Nakon toga možete poslati svoje zadatke, a žiri će odgovoriti mogu li se koristiti i jesu li prikladni. Ako su zadaci prikladni, daju se na natječajima, a autoru se za to plaća - ne baš puno, ali ipak.

Smišljati takve probleme posebna je vještina, zar ne?

O da. Možete doći do problema na temelju rješenja. Recimo da ste pročitali neki članak u znanstvenom časopisu o zanimljivom algoritmu. Ili sam samo pronašao određeni algoritam i sjetio se da sam se s njim već susreo, ali nedavno ga dugo nisam vidio. Možete smisliti zadatak koji zahtijeva njegovu upotrebu.

Drugi način: kada se pojavi određeni problem na poslu ili u životu, a vi shvatite da se to može iskoristiti na cool način. Možda ćete morati zakomplicirati stvari ili promijeniti ograničenja, ali onda će to ispasti zanimljiv problem za konkurenciju.

Postoje natjecanja različitog stupnja bliskosti životu. Obično se zadatak na natjecanjima ne daje u nekim formalnim terminima, poput “zadano: riješi tu i tu jednadžbu”. Obično se daje određena pozadina ili povijest. Kao u školskim udžbenicima matematike: “Kroz jednu cijev protječe deset litara vode u minuti.” Dakle, tu priču prvo treba nekako formalizirati, pronaći u njoj matematički problem, pa ga tek onda riješiti.

Postoje i drugi natječaji. TopCoder to naziva Marathon Match, a i druge tvrtke održavaju slična natjecanja. Dizajnirani su malo drugačije. Ovo više nije natjecanje u algoritmima, već u rješavanju približnih problema. Kada ne postoji točno rješenje i morate smisliti najbolju moguću opciju. Takva natjecanja obično traju dva tjedna ili mjesec dana. Možeš poslati različita rješenja i primijetite da, da, sada je moje rješenje 20% bolje od ostalih.

Znači li "bolje" brže, koristi manje memorije itd.?

Da. Na primjer, morate osmisliti shemu za raspodjelu autobusnog prometa na karti Moskve kako biste koristili što manje autobusa. Odnosno, u izjavi problema postoji određeni parametar koji treba optimizirati, ali ne postoji jedno "točno rješenje", samo neki približni algoritmi.

Isti taj Topcoder održavao je natječaje zajedno s NASA-om, a kažu da su rješenja koja su im ponuđena potom zapravo adaptirana i korištena na ISS-u. Tamo su rješavali neki konkretan problem, čini se kako okrenuti solarna baterija tako da ona prima više energije.

Gdje početi

Sa stajališta pripreme dobrog algoritamskog programera i sudionika u raznim natjecanjima - kako se pripremiti za to? Ako se zamislite na mjestu srednjoškolca ili studenta prve godine?

Mislim da najviše standardni način- probaj. Sva natjecanja imaju dostupnu arhivu prethodno održanih natjecanja; postoje tisuće problema koji se mogu riješiti u bilo kojem trenutku.

Što ako prihvatim zadatak i ne znam na koji način da mu pristupim?

Dakle, shvatite to jednostavnije. Oni su drugačiji. Postoje problemi koje svaki drugi maturant može riješiti. Postoje potpuno različite razine težine. Trebalo bi biti prilično lako uključiti se. Nema drugog načina, čini mi se. Osim toga, na ovaj način ćete odmah shvatiti sviđa li vam se ova aktivnost ili ne.

Što je potrebno učiniti da se dobije algoritamska baza? Gotovo da nema potrebe odmah požuriti čitati Knutha.

Čini mi se da treba krenuti od zadataka. Tek kasnije, kada shvatite da ne možete riješiti niti jedan konkretan, na tim natjecanjima svaki ima analizu. Možete pročitati rješenje ako ne možete sami. Primjerice, analiza pokazuje da se za rješavanje problema koristi određeni algoritam. Možete pročitati što je to algoritam i gdje se još koristi. Ovo je bolje nego čitati s popisa "da, imam algoritam koji moram proučiti tijekom ljeta." Bolje je krenuti od konkretnog problema koji niste mogli riješiti jer ne znate određeni algoritam. Ovo je ispravnije. Bolje pamtiš, motivacija ti je jača. Ova metoda učenja algoritama vjerojatno traje dulje od popisa, ali dovodi do boljih rezultata.

Ako se želite "napumpati" pomoću algoritama, postoji li literatura ili udžbenici?

Najstandardniji udžbenik je Cormen, Leiserson, Rivest s magarcem na koricama. Naziva se “Algoritmi: konstrukcija i analiza”. Ne znam, nisam dugo učila, sada vjerojatno postoje novi udžbenici koji bi mogli biti bolji. Ali u moje vrijeme koristili su Cormen. Knut je, prije, neka vrsta priručnika. Ako trebate nešto pronaći, a nema ga nigdje, velike su šanse da će biti tu. Ali čitati Knuth u nizu... to je prilično tužno iskustvo.

Nakon rezultata regionalnog polufinala Svjetskog prvenstva ACM ICPC, postali su poznati rezultati Sveruske olimpijade školaraca u programiranju. Unutar zidina Sveučilišta ITMO zlatne medalje dodijeljene su djeci iz Almatija, Astane i Moskve. Peterburžani su podijelili “srebro” s kolegama iz Tbilisija, a “bronca” je pripala momcima iz Jekaterinburga, Iževska, Kremenčuga i Vitebska. Treneri timova iz St. Petersburga Andrey Lopatin i Andrey Stankevich, voditelj odjela računalna tehnologija Sveučilište ITMO Lidiya Perovskaya, dekanica Fakulteta informacijske tehnologije i programiranje Vladimir Parfenov i svjetski prvaci u programiranju iz različitih godina ispričali su zašto dečki iz ZND-a zadnjih 15 godina obaraju sve rekorde.

Pobjednici ACM ICPC sa Sveučilišta ITMO

Vrijeme je za navijanje za programere

„Programiranje je budućnost: svaki dom ima ogroman broj programabilnih uređaja, a te tehnologije nastavljaju prodirati u sva područja naših života. Baš poput inženjera u Sovjetskom Savezu, programeri su sada na samom vrhu znanosti i tehnologije. Natjecanja u kodiranju postaju sve popularniji i spektakularniji sport, a budućnost je vrlo obećavajuća."- naglašava Andrej Stankevič.

Lidija Perovskaja, Kao iskusan organizator olimpijada raznih razina, slažem se s kolegom. Prema njezinim riječima, natjecanja u programiranju imaju složeniju strukturu od tradicionalnih natjecanja. U finalu se najčešće natječu tročlane ekipe, a samih ekipa zna biti i više od stotinu. U sportskom programiranju ima mjesta za ljubitelje, uvjeren je predavač s Katedre za računalnu tehnologiju: osoba koja se razumije u programiranje može navijati za tim koji mu je bliži po fakultetu, razini znanja ili strategiji/bistrini izvođenje.

Kao što napominje trener momčadi St. Petersburg State University: Andrej Lopatin, natjecanja u programiranju nisu samo spektakularna, već i uistinu korisna. Prema njegovim zapažanjima, moderni prvaci lako rješavaju probleme koji su se prije samo 10 godina činili nerješivima. Povećava se učinkovitost i brzina timskog rada, a kod je pojednostavljen, što omogućuje trošenje manje vremena na razvoj i debugovanje programa. A to je već korisno za velike IT tvrtke, kojima je važno smanjiti troškove proizvodnih procesa.

“Važno je da dečki ne samo da znaju dobro šutnuti loptu u gol, već su i predvodnici tehnologije, a svaka velika tvrtka koja poštuje sebe održava svoje veliko prvenstvo u programiranju kako bi naknadno pronašla najbolje stručnjake. Uostalom, finalisti prvenstva su ljudi koji brzo razmišljaju i pronalaze optimalna rješenja. Uostalom, u životu nam ne trebaju toliko idealna rješenja koliko optimalna. Stoga su čak i oni koji nisu dobili nagrade, nego su jednostavno sudjelovali u nekom od finala velikih natjecanja, jako cool i tvrtke se doslovno bore za njih.”“, rezimirao je trener.

Pobjeda od početka do kraja

Kako primjećuje Andrej Stankevič, sportski program se razvija u valovima. Postoje mnoge strategije za razvoj timova, ali ponekad na rezultat utječe ključni igrač. Na primjer, uglavnom zahvaljujući talentiranom studentu Sveučilišta ITMO Genadij Korotkevič Sveučilišni tim je dva puta postao apsolutni svjetski prvak ACM ICPC. No, lovorike idu i onima koji se pridržavaju dugoročna strategija, kada jedan tim godinama brusi svoje vještine i na kraju se zasluženo probija u vrh - tako je tim Državnog sveučilišta St. Petersburg postao apsolutni prvak ACM ICPC-2016. Stoga ne čudi kada jedna od momčadi ili jedan od igrača ustupi mjesto drugima na vrhu: to znači da je netko napredovao zahvaljujući dugom i mukotrpnom radu.

Ako govorimo u opći nacrt, pripreme momaka sastoje se od trening natjecanja, kada sudionici rješavaju zadatke s prošlogodišnjih turnira, ali i teorije - predavanja, analiza problema i ostalih ponekad rutinskih stvari. Kako dodaje Gennady Korotkevich, kampovi za obuku također igraju značajnu ulogu u razvoju programera sa sveučilišnim obrazovanjem, kada se timovi iz različitih gradova na postsovjetskom prostoru mogu ujediniti i pomoći jedni drugima u usavršavanju.

“U ovom sportu komunikacija među ljudima igra vrlo važnu ulogu. Timovi iz zemalja ZND-a uspješni su jer se okupljaju različita sveučilišta, praktički pod jednim krovom, komuniciraju i zajedno rade ono što vole. Trening kampovi te stvarno razvijaju, daju ti priliku da se dokažeš i pogledaš zadatak na novi način.”“, siguran je šampion.

Kako naglašava Alexey Maleev, direktor Centra za razvoj informatičkog obrazovanja Moskovskog instituta za fiziku i tehnologiju, oni koji se žele dokazati u sportskom programiranju trebaju shvatiti da ih čeka 4-5 godina pravog oranja. A pritom vam nitko ne može garantirati da ćete za pet godina biti barem među deset najboljih na ACM ICPC. Ali ovaj naporan rad, zajedno sa suradnjom sveučilišta, omogućuje diplomantima iz Rusije i zemalja ZND-a da uđu na globalno tržište obrazovanja s pravim adutom. I zato je ruska škola programera tražena u cijelom svijetu, uvjeren je predstavnik MIPT-a.

ACM ICPC prvak također se slaže da sportsko programiranje koristi sveučilištima Niyaz Nigmatullin. Prema riječima iskusnog sudionika međunarodnih natjecanja, po tome kako sveučilišna ekipa nastupa na prvenstvima, možete brzo shvatiti što vas njihova alma mater može naučiti. Pritom morate shvatiti da sportsko programiranje uopće nije nešto čime se bave stotine studenata, jer samo rijetki biraju i prolaze put sportskog programera, napominje Niyaz.

Ekonomsko pitanje

“Sada je pitanje relevantnosti sportskog programa prešlo u čisto ekonomski aspekt. Stvar je u tome da se nalazimo na određenoj kritičnoj točki, kada je do novog kruga razvoja informatičke tehnologije ostalo još malo vremena. Ovo je svijet u kojem ćemo se uskoro svi naći: bankovni sustav, medicina će se potpuno promijeniti, pojavit će se automobili bez vozača, a da ne govorimo o tome da će mnoge profesije jednostavno nestati - ljudi će ostati bez posla. Ali programeri će ga stvarno imati puno. I to sada vidimo: potražnja za njima je tolika da su plaće fizičara i matematičara, čak iu SAD-u, dvostruko niže od plaća programera. I one zemlje koje sada imaju visokokvalificirano osoblje na terenuIT će napraviti iskorak u sljedećih 10-20 godina", - siguran je Vladimir Parfenov.

Zbog toga su Olimpijske igre potrebne. Identificirati najbolje od najboljih, talentirane i one koji jednostavno vole programiranje i trebaju podršku, siguran je Vladimir Parfenov. Osim toga, talentirana djeca - upravo oni budući resursi - željni su natjecanja i dokazivanja od najranije dobi. Samo u Rusiji je 3 tisuće od 140 milijuna ovih momaka koji će uskoro promijeniti svijet, a najvažnije je vidjeti one koji im mogu praviti društvo. Uostalom, ni ostatak svijeta ne stoji na mjestu, dodaje dekan Fakulteta informacijskih tehnologija i programiranja - u proteklih 15 godina Kina je već napravila kolosalan skok, a SAD je ostao na vrhu zahvaljujući razvijenoj infrastruktura.

“Naš moderni programer počinje raditi odmah u četvrtoj godini, osim ako ne ode u znanost, gdje je, nažalost, plaća još uvijek manja. Istovremeno, dobiva puno ponuda od poslodavaca. Naravno, ako govorimo o Sankt Peterburgu, naših 400-500 IT tvrtki pokušava stvoriti nešto novo i u njih se isplati ići. Nije neuobičajeno da se oni koji počnu raditi za velike tvrtke poput Googlea vrate kući, ponekad i s pritužbama. Uostalom, jedno je kada sjedite u prekrasnom gradu Sankt Peterburgu, a sasvim drugo kada ste u selu koje se zove Silicijska dolina...”, - smije se učiteljica.

Doping

Unatoč beskrajnim pitanjima o dopingu, mladi šampioni ipak napominju da je u sportskom programiranju najvažnije da glava dobro radi. Na primjer, svjetski prvak iz 2016. Stanislav Ershov priznaje da se voli dobro naspavati na dane natjecanja i pojesti slatkiše. Istodobno, mladić napominje da ne sanja o povećanoj medijskoj pozornosti i slavi - poput ljudi iz znanosti, radije se kloni hypea. Pobjednik mnogih natjecanja Gennady Korotkevich, koji je jedan od rijetkih u svijetu koji može živjeti od sportskog programiranja, također ne vjeruje baš u doping. Prema Gennadyju, bilo bi sjajno kada bi jednog dana postojale profesionalne preporuke za sportaše programere - o režimu ili prehrani. Općenito, mladi ne poriču da bi u budućnosti mogao postojati pravi doping za rad mozga koji je ozbiljniji od čokolade, ali on im ne treba.