Topkooderi

Topcoder Inc.
Tyyppi Yhtiö
Pohja huhtikuuta 2001
Sijainti Yhdysvallat , Connecticut , Glastonbury
Ala IT-henkilöstö
Ohjelmistokehitys
Ulkoistuspalvelut
Työntekijöiden määrä 75 (2006) [1]
Verkkosivusto www.topcoder.com

Topcoder  on yhtiö, joka isännöi urheiluohjelmointikilpailuja . Toisin kuin ACM International Collegiate Programming Contest , kaikki kilpailut ovat yksilöllisiä.

Perustettu huhtikuussa 2001. Heinäkuussa 2008 käyttäjiä oli yli 160 000, joista noin 28 000 osallistui Algoritmikilpailuun vähintään kerran.

Kilpailutyypit

Algoritmit ( eng.  Algorithm Competition )

Suosituin turnaustyyppi on kilpailu algoritmisten ongelmien nopeasta ratkaisusta (samanlainen kuin koulujen ja opiskelijoiden ohjelmointikilpailut). Se johtuu siitä, että jokaiselle osallistujalle annetaan 3 tehtävää, jotka ovat monimutkaisia ​​ja luokiteltu 3 tasolle. Jokaisella tehtävällä on oma maksimiarvonsa pisteinä. Yleensä 250, 500 ja 1000. Pisteitä saa vain oikeiksi tunnustetuista ratkaisuista, osaratkaisuja ei huomioida. Ennen kilpailun alkua osallistujat jaetaan virtuaalisiin huoneisiin (enintään 20 henkilöä).

Tällaiset ottelut, joita kutsutaan nimellä SRM (Single Round Match), järjestetään noin kerran kahdessa viikossa. Lisäksi järjestetään vuosittain turnauksia. Ottelu koostuu kolmesta päävaiheesta - koodaus, haastaminen ja järjestelmätestaus.

Ohjelmointivaihe  _ Koodausvaihe

Ensimmäisessä vaiheessa osallistujat yrittävät ratkaista heille ehdotetut kolme tehtävää, joiden arvo on yleensä 250, 500 ja 1000 pistettä, varatun ajan kuluessa. Ratkaisu on luoda ehdossa määritetty luokka ja toteuttaa ehdossa määritetty menetelmä läpäisemällä kaikki valmiiksi valmistetut testit. Osallistujat voivat kirjoittaa ratkaisuja jollakin seuraavista kielistä: C++ , C# , Java , VB.NET tai Python . Ratkaistun tehtävän pisteiden määrä riippuu epälineaarisesti lopullisen ratkaisun lähetysajasta: mitä myöhemmin, sitä vähemmän pisteitä. Jokaisesta uudelleenlähetyksestä veloitetaan 10 % tehtävän hinnasta. Pisteiden määrä ei voi olla pienempi kuin 30 % tehtävän hinnasta.

Kiertueen kesto tavallisissa otteluissa ( eng.  Single Round Match , lyhennettynä SRM ) sekä turnausten karsintakilpailuissa ( eng.  Online Elimination Rounds ) on 75 minuuttia. Onsite-finaalissa ( eng.  Onsite Events ) ensimmäisen vaiheen kesto on 85 minuuttia.

Kilpailullinen  testausvaihe Haastava vaihe

Toisessa vaiheessa osallistujat yrittävät löytää testin (syöttötietovaihtoehto), jossa sen kilpailijoiden (jotka ovat samassa virtuaalihuoneessa) ratkaisut toimivat väärin. Samaan aikaan lähdekoodin katselu on sallittua, mutta kilpailijoiden ohjelmien suorittaminen on mahdotonta (mahdotonta). Jokainen onnistunut lähestymistapa antaa 50 pistettä ja epäonnistunut 25 pistettä. Jos lähestymistapa onnistui, testi voidaan lisätä seuraavassa vaiheessa käytettävään testisarjaan. Tämän vaiheen kesto on 15 minuuttia kaikissa otteluissa paitsi vastakkain finaalissa (10 minuuttia). Osallistujaa ei saa yrittää sovittaa testiin, jossa muut ratkaisut eivät toimi, jos hänen pistemääränsä ei ole positiivinen.

Viimeinen  testausvaihe Järjestelmän testausvaihe

Kolmannessa vaiheessa testataan kaikkien osallistujien kaikki ratkaisut, joita ei todettu virheellisiksi toisen vaiheen tulosten mukaan. Otteluiden lopulliset tulokset ovat muodostumassa.

Tulokset

Osallistujien luokittelu ja lopullinen sijoituspaikka määräytyy osallistujien lopullisen pistemäärän mukaan. Enemmän pisteitä saaneet osallistuvat korkeammalle sijalle. Jos pisteet ovat yhtä suuret, kaikki osallistujat, joilla on tietty määrä pisteitä, ovat (jakavat) saman paikan.

Jos kilpailun aikana ei ilmennyt teknisiä vikoja, pisteet lasketaan uudelleen kaikille osallistujille.

Suunnittelu- ja  kehityskilpailu edit

Tämä on teollista ohjelmointia lähinnä oleva kilpailu. Niihin osallistuu ohjelmoijapareja. Ensimmäinen kirjoittaa yksityiskohtaisen määrityksen jollekin kolmannen osapuolen tilaamalle komponentille ja toinen toteuttaa sen .NET- tai Java-muodossa. Teoksen arvioivat useat tuomaristot ja niiden perusteella lasketaan lopullinen pistemäärä.

Maratonit ( English  Marathon Competition )

Maratoneissa osallistujat ratkaisevat monimutkaisempia ja epätyypillisempiä ongelmia kuin muissa olympialaisten ohjelmointikilpailuissa. Maratoneissa ei jaeta sarjoihin, vaan jokaisessa kilpailussa annetaan vain yksi tehtävä. Toisin kuin Algorithm, "oikea" tai paras algoritmi ei ole edes ongelman tekijän tiedossa. Usein jokaiselle syötteelle on olemassa parempia ja huonompia vastauksia, ja ohjelma, joka löytää aina parhaan vastauksen kohtuullisessa ajassa, on ongelman tekijälle tuntematon, eikä sitä ehkä ole olemassakaan. Osallistujan tulee kirjoittaa ohjelma, joka löytää parhaan mahdollisen vastauksen tietyssä ajassa (yleensä 10 sekunnissa). Joissakin tapauksissa oikea vastaus on löydettävä mahdollisimman lyhyessä ajassa. Muitakin vaihtoehtoja on.

Tehtävän suorittaminen kestää yleensä 1 tai 2 viikkoa.

Osallistujat ovat sallittuja:

  • Kokeilutestit. Osallistujan lähettämää ohjelmaa testataan 10 aiemmin tunnetulla tietojoukolla. Osallistuja saa kunkin tietojoukon ohjelman tulokset, sen tulosteet ja ajoajan. Muut osallistujat voivat oppia vain tekotestin tosiasiasta. Voit suorittaa koetestin 10 minuutin välein.
  • Täydelliset testit. Ohjelmaa testataan 100:lla satunnaisesti ennen kilpailun alkua luodulla tiedolla, joka on sama kaikille osallistujille ja vakiona koko kilpailun ajan. Osallistujalle ilmoitetaan vain ohjelman kokonaispisteistä. Osallistujan nimi ja hänen viimeisimmässä täydessä kokeessa tekemänsä pisteet kirjataan kaikkien osallistujien käytettävissä olevaan taulukkoon. Täysi testi voidaan tehdä kerran 1 tunnin välein.

Päätöksenteon päätyttyä täystestiin lähetetyt ohjelmat (viimeinen jokaiselta osallistujalta otettu ohjelma) testataan suurella määrällä (yleensä 500) salaisia, satunnaisesti luotuja tietojoukkoja, sama kaikille osallistujille. Osallistujat saavat paikkoja saamansa pistemäärän mukaan.

Lyhyt kuvaus joistakin tehtävistä

Alla on esimerkkejä maratoneilla tarjotuista tehtävistä. Esimerkeistä on jätetty pois monia yksityiskohtia.

  • osagraafin isomorfismi. Annettu graafi G ja graafin G aligraafin kanssa isomorfisten kärkien graafi H. Selvitä mikä graafin G kärki vastaa kutakin graafin H kärkeä. Jos graafi H on isomorfinen kahdelle tai useammalle graafin G aligraafille, mikä tahansa isomorfismi on hyväksytty. Ohjelma saa ensin 5-pisteisen graafin G ja graafin H, oikean vastauksen jälkeen toisen 6-pisteisen graafin H, oikean vastauksen jälkeen uuden 7-pisteisen graafin H ja niin edelleen. Pisteet ovat yhtä suuria kuin aligraafien lukumäärä, joille ohjelma onnistui löytämään isomorfismin. Ohjelman suoritusaika on enintään 10 sekuntia. [1] Arkistoitu 13. huhtikuuta 2012 Wayback Machinessa
  • Matkapuhelinautomaatti. Säännöt soluautomaatin käyttäytymiselle suorakaiteen muotoisella alueella, alkusijainti, N ja K on annettu. Etsi alkusijainti, joka poikkeaa annetusta korkeintaan N solulla siten, että K askeleen jälkeen elävien lukumäärä solut ovat mahdollisimman suuria. Pisteet ovat yhtä suuria kuin elävien solujen lukumäärän suhde sen suorakulmion kokonaispinta-alaan, jossa soluautomaatti toimii. [2] Arkistoitu 25. toukokuuta 2014 Wayback Machinessa
  • tasomaisuus. Annettu kaavio. Etsi graafin tasainen asettelu, jossa kärjet ovat pisteitä 700×700 kokonaislukuhilassa ja reunat ovat kärjet yhdistäviä segmenttejä siten, että reunojen leikkauskohtien määrä on mahdollisimman pieni. Pisteet ovat kääntäen verrannollisia reunojen leikkauspisteiden lukumäärään. [3] Arkistoitu 13. huhtikuuta 2012 Wayback Machinessa

Arvio

Topcoder on ensimmäinen ja arvostetuin urheiluohjelmointimuoto, jossa on sijoitusjärjestelmä, joka perustuu heidän suoritukseensa verkkokilpailuissa. Sen pohjalta tehtiin suljettu valkovenäläinen sivusto Test The Best ja venäläiset Codeforces .

Luokitusjärjestelmä jakaa osallistujat seuraaviin luokkiin:

Ryhmän väri Luokitus
Valkoinen Osallistujat, jotka eivät koskaan esiintyneet
harmaa alle 900 pistettä
Vihreät 900-1199 pistettä
Sininen 1200-1499 pistettä
keltainen 1500-2199 pistettä
Punainen 2200 pistettä tai enemmän
Johtajat ( englanninkielinen  tavoite ) 3000 pistettä tai enemmän

Algoritmikilpailun osallistujat, joiden luokitus on vähintään 1200, kilpailevat ensimmäisessä divisioonassa. Kaikki muut ovat toisessa. 18. tammikuuta 2010 mennessä noin 800 vahvimmalla ohjelmoijalla on Algorithm Competitionin keltainen luokitus, noin 200:lla punainen ja vain 17 ihmisellä maailmassa on "Target". [2]

Suunnittelu-, kehitys- ja maratonotteluissa kukaan ei ole vielä onnistunut saamaan Target-tasoa, ja punaiseen ryhmään kuuluu enintään 10 henkilöä (Kehityksessä vain kaksi).

Kilpailut

Turnauksista suurimmat ovat Topcoder Open (epävirallinen ohjelmoinnin maailmanmestaruus ammattilaisten keskuudessa) ja Google Code Jam (vuoteen 2007, vuodesta 2008 lähtien Google on järjestänyt sen itsenäisesti [3] ).
Niiden lisäksi järjestettiin vuoteen 2007 asti opiskelijoille suunnattu turnaus - TopCoder Collegiate Challenge. [4] .
Vuodesta 2006-2007 lähtien on järjestetty yksittäisiä otteluita ja vuosittainen koululaisten turnaus - TopCoder High School.

Muistiinpanot

  1. ↑ Topkooderin työt ja profiili (downlink) . Yahoo! Kuumia töitä . Haettu 29. marraskuuta 2006. Arkistoitu alkuperäisestä 1. kesäkuuta 2005. 
  2. ↑ TopCoder Statistics - Parhaiten sijoitetut algoritmikilpailijat . Haettu 18. tammikuuta 2010. Arkistoitu alkuperäisestä 17. tammikuuta 2021.
  3. ↑ Code Jam -säännöt . Haettu 25. kesäkuuta 2008. Arkistoitu alkuperäisestä 22. kesäkuuta 2008.
  4. ↑ TCCC: Vaikea päätös . Haettu 25. kesäkuuta 2008. Arkistoitu alkuperäisestä 19. helmikuuta 2011.

Linkit