Hajrá evosoft!

Adott a síkon páros számú pont. Párosítsuk a pontokat úgy, hogy a pontpárok által meghatározott szakaszok összhossza minimális legyen! Speciális esetekben több helyes megoldás is létezik, de elég ezek közül egyet megtalálni.

A verseny menete

• A leggyorsabb helyes megoldás a nyerő. Más szempontot nem veszünk figyelembe.
• A megoldás készülhet Java, C# vagy C++ nyelven, ezek külön kategóriákban lesznek értékelve.
• Mindenki csak egy kategóriában indulhat!
• A versenyben egymás ellen versengenek:
  • az evosoft Hungary Kft. dolgozói
  • a Budapesti Műszaki Egyetem hallgatói
  • a Miskolci Egyetem hallgatói
  • Ha részt szeretnél venni a versenyen, küldj egy emailt az evoprogcontest@evosoft.com címre. A tárgy JOIN neptunid university Gipsz Jakab legyen ahol
    • neptunid helyére írd be a Neptun azonosítódat (ezzel ellenőrizzük, hogy valóban egyetmista vagy)
    • university helyére azt írd, hogy bme vagy azt, hogy me attól függően, hogy melyik egyetem hallgatója vagy
    • Gipsz Jakab helyére a saját igazi nevedet írd
    • Példa: JOIN gija01 me Gipsz Jakab
• A regisztrációról kapni fogsz egy automatikus értesítő levelet.
• A megoldásodat ugyanerre a címre küldd CODE tárggyal, és egy csatolmány tartalmazza a forráskódodat GipszJakab.java, GipszJakab.cs vagy GipszJakab.cpp névvel. Ha ennek nem felel meg a levél, arról szintén megy automatikus válasz.
• FONTOS: Az első beküldött megoldással választod ki, hogy melyik kategóriában indulsz. Ezen később változtatni nem lehet!
• A verseny ideje alatt korlátlan számban küldhetsz be megoldást (javítást, gyorsítást).
• Minden munkanapon nem meghatározott időpontban, de várhatóan estefelé indul egy nem hivatalos verseny az addig beérkezett helyes megoldásokkal, a részeredményeket itt a blogon közzétesszük, de a regisztrált versenyzők emailben is megkapják majd.
• Ha az aznapi versenyen a programoddal valami gond volt, arról automatikus választ fogsz kapni levélben - lehetőség szerint - a hiba okával.
• A végső beküldési határidő május 4. kedd délelőtt 10 óra. A döntő futamra aznap 15 órakor kétórás összejövetel keretében kerül sor az evosoft budapesti és miskolci irodájában egy videokonferencia keretén belül, ahol a legjobbak megmutatják forráskódjukat, és elmagyarázzák a megoldás elvét. Erre a megoldást beküldő egyetemistákat is szeretettel várjuk.
• Ezután publikáljuk az összes forráskódot, és május 7. délelőtt 10 óráig, péntekig lehetőség van hibát keresni a többiek programjában.
• Töröljük a versenyből azokat a megoldásokat, amelyre ezek alapján tud valaki olyan bemenetet mutatni, amelyben a pontok száma megegyezik a hivatalos versenyben a alkalmazottal, és amelyre hibás eredményt ad.
• És a végére a legfontosabb: FAIR PLAY!!! Igaz, hogy vannak nyeremények, de ez elsősorban egy játék.

Díjazás

Mindhárom kategóriában (Java, C#, C++) a következő díjak kerülnek szétosztásra:

• Első díj: Netbook
• Második díj: iPod touch 8GB
• Harmadik díj: 15 ezer Ft értékű vendéglátás két fő részére

Kategóriájában az első helyes megoldást beküldő különdíjban részesül.

Követelmények

A megoldás elkészítéséhez kötelező használni a lent ismertetett keretrendszert.

• Java:
  • A com.evosoft.evorace.pairing.Pairing interfészt kell implementálni.
  • Az implementációs osztály neve com.evosoft.evorace.pairing.<Vezeteknev><Keresztnev> legyen (az email címednek megfelelően, csak fordított sorrendben, "ext" nélkül).
  • Ezt az osztályt az src\com\evosoft\evorace\pairing\<Vezeteknev><Keresztnev>.java fájlba tedd.
  • Ezt a .java fájlt kell feltölteni.
  • Az osztály pair() metódusának futási idejét mérjük.
• C#:
  • Ugyanaz a Java keretrendszer futtatja a C# megoldásokat is. A .NET részhez webszolgáltatáson keresztül csatlakozik.
  • A evorace2010.Pairing interfészt kell implementálni.
  • Az implementációs osztály neve evorace2010.<Vezeteknev><Keresztnev> legyen (az email címednek megfelelően, csak fordított sorrendben, "ext" nélkül).
  • Ezt az osztályt a secret\competitor_net\<Vezeteknev><Keresztnev>.cs fájlba tedd.
  • Ezt a .cs fájlt kell feltölteni.
  • Az osztály pair() metódusának futási idejét mérjük.
• C++:
  • Ugyanaz a Java keretrendszer futtatja a C++ megoldásokat is JNI-n keresztül.
  • A cpp\Pairing.h fájlban lévő IPairing osztályt kell kiterjeszteni.
  • Az implementációs osztály neve <Vezeteknev><Keresztnev> legyen (az email címednek megfelelően, csak fordított sorrendben, "ext" nélkül).
  • Ezt az osztályt a secret\competitor_cpp\<Vezeteknev><Keresztnev>.cpp fájlba tedd.
  • A versenyzők kódjai közötti névütközések elkerülése végett ebben a fájlban ne legyenek globális változók és függvények, minden az implementációs osztályhoz tartozzon!
  • Ezt a .cpp fájlt kell feltölteni.
  • Az osztály pair() függvényének futási idejét mérjük.

• A pontok számát a napi futamokon és a végső versenyben is dinamikusan határozzuk meg a beküldött megoldások alapján! A pontok száma 2n lesz, ahol 2n pontra az aktuális leggyorsabb megoldás 1 másodpercen belül lefut, és 2(n+1) pontra ugyanez a megoldás több, mint 1 másodpercig fut. Mindhárom kategóriban ugyanannyi pontot alkalmazunk, tehát az abszolút leggyorsabb megoldás számít.
  
• A pontok x és y koordinátái 0 és 999 közé eső egész számok, ezeket a határokat tartalmazzák a Point osztály/struktúra MIN, MAX konstansai.
• A programnak tetszőleges ennyi pontból álló bemenet esetén helyesen kell működnie, de a versenyben a pontok koordinátái kvázi egyenletes eloszlású véletlenszámok lesznek.
• Hogy reális legyen a mérés, többször fog lefutni minden résztvevő program.

Fejlesztõi környezet

Keretrendszer

evorace2010.zip 1.2-es verzió

Változások az 1.2-es verzióban:

• Pontok ismétlődése kizárva generáláskor
• Csak Java megoldás esetén nem okoz gondot a nant hiánya, ha aktiválod a build.xml-ben a következő sort:

 <!--property name="java.only" value="yes"/-->

Változások az 1.1-es verzióban:

• C#: felvettünk hivatkozást néhány alapvető assembly-re.
• A pair() metódus elvárt visszatérési értékének leírása az interfészek forráskódjában pontosítva.
• Nem C++ megoldás esetén nem baj, ha nincs beállítva az nmake.exe elérési útvonala.
• Több C++ megoldás is fordítható/futtatható egy lépésben
• Pontpárok kirajzolása működik mindhárom nyelv esetén.

Szükséges szoftverek

• Eclipse SDK (ez nem kell feltétlen, az Ant-tal meg lehet csinálni mindent)
• J2SE SDK 6.0
• Apache Ant 1.7
• ant-contrib-1.0b3.jar - Ezt a jar fájlt másold be az %ANT_HOME%\lib mappába.

Ha C#-ban készítesz megoldást, akkor ezek is:

• .NET Framework >=3.0
• NAnt >=0.85 Ezt közvetlenül nem kell használnod, csak az Ant-os build szkript használja. Ha .NET Framework 3.5-ös újdonságokat is akarsz használni, akkor 0.90-es verzió ajánlott.

Ha C++-ban készítesz megoldást, akkor ezek is:

• Valamilyen C++ fordítóprogram (a versenyben a Visual Studio 2008-ba beépített nmake.exe és cl.exe programokat fogjuk használni, a keretrendszer is erre van beállítva.)

Telepítés

1. A keretrendszer zip fájlját csomagold ki az Eclipse workspace-be.
2. File -> New -> Project -> Java Project
3. A projekt neve legyen evorace
4. Választ ki, hogy Create project from existing source, és add meg az evorace mappát.

Fordítás, futtatás

Csak Java megoldásnál

• Aktiváld a build.xml-ben a következő sort:

 <!--property name="java.only" value="yes"/-->

C# vagy C++ megoldásnál

• szükség esetén módosítsd az evorace\build\build.xml-ben ezt az elérési útvonalat:

C# megoldásnál

• szükség esetén módosítsd az evorace\build\nbuild.xml-ben ezt az elérési útvonalat:

<property name="service.model.dll" value="C:\Program Files\Reference Assemblies\Microsoft\Framework\v3.0\System.ServiceModel.dll"/>

• Windows 7 esetén: netsh http add urlacl url=+:8070/PairingService user=[HELYI USERNAME]

C++ megoldásnál

• szükség esetén módosítd az evorace\cpp\makefile.win fájlban a C++ fordító nevét és elérési útját:

• Ha nmake-et használsz, akkor Visual Studio Command Promptból indítsd az ant parancsot!

Minden esetben

• Állítsd be a JAVA_HOME környezeti változót a JDK telepítési könyvtárára
• Tedd be a %JAVA_HOME%\bin mappát a PATH-ba
• Állítsd be az ANT_HOME környezeti változót az Ant telepítési könyvtárára
• Tedd be az %ANT_HOME%\bin mappát a PATH-ba
• Egy konzolban lépj be az evorace\build könyvtárba.
• Fontosabb Ant parancsok:
  • ant build.net - C# kód fordítása
  • ant run.server - "C# szerver" futtatása. Ez csak akkor kell, ha C# implementációd (is) van.
  • ant - verseny futtatása
  • ant wsimport - ezt csak akkor add ki, ha véletlenül előtte letörölted a evorace\gen\generated_classes tartalmát (pl. a ant clean.wsimport paranccsal. :)

Konfiguráció

src/com/evosoft/evorace/pairing/pairing.properties

A konfigurációlható paraméterek leírása a fájlban található. Figyelj arra, hogy a paramétereket tartalmazó sorok végén ne legyen space vagy tab!

GY.I.K.

Folyamatosan bővül, nézz rá később is!

• Új!!! Az init() mikor hívódik meg?
  • Amint a metódus kommentjében is írtuk, csak az garantált, hogy legalább egyszer lefut az első pair() hívás előtt. Gyakorlatban viszont ti is kipróbálhatjátok, hogy ha több inputot adsz meg, akkor a két pair() hívás között már nem hívódik meg. Emiatt már több versenyzőnek is elbukott a programja.
• Új!!! Nem akar generálni inputot, hiába adom meg, hogy "input.generate=true". Mi a baj?
  • Meg kell adnod a reference.name property-ben a sajat programod nevet, tehat pl. reference.name=Net_GipszJakab
• Új!!! Neten lévő algoritmusokat szabad felhasználni?
  • Szabad, de a végén el kell magyaráznod, hogy működik.
• Új!!! Egybeeshet-e két pont?
  • Nem, és a keretrendszer 1.2-es verziójától kezdve erre már a generátor is figyel.
• Hogyan történik a verseny futtatása?
  • Többször fut különböző véletlen adatokkal minden versenyző. A futások számát menet közben határozzuk meg a versenyzők számának és a programok futási idejének függvényében.
• Nettó futási időt mérsz?
  • Igen, csak pair() metódus futási idejét mérjük.
• Lesz-e mérve a teljesítmény speciális inputokra?
  • A verseny futtatásakor csak véletlen input lesz, de ellenőrzésre ilyenekkel is lesz futtatva.
• Mi az a referencia program, és mire való?
  • A programok helyességének ellenőrzésére szolgál. Természetesen nem kizárt, hogy a referencia program hibás, de ha ez így van, ez menet közben úgyis ki fog derülni.
• A referencia programot én is futtathatom?
  • Nem, azt nem publikáljuk.
• Milyen gépen fut a verseny?
  • Intel Core2 Duo 2.33 GHz, 32 bit, 2GB RAM
• Az inputok feldolgozását párhuzamosan vagy szekvenciálisan végzi?
  • Szekvenciálisan.
• A szervezők indulnak-e a versenyben?
  • Nem.
• Miért van szükség Ant-ra és Java SDK-ra, ha C# vagy C++ megoldást akarok készíteni?
  • Mert a keretrendszer Java-ban íródott, és az egységes keretrendszer szükséges ahhoz, hogy könnyen tudjuk együtt futtatni a megoldásokat.
• Miért van szükség a NAnt-ra?
  • Mert a C# forrás fordítása a NAnt-on keresztül van megoldva, de neked közvetlenül ezt nem kell használnod, hanem helyette az Ant-ot!
• Több verziómat szeretném összehasonlítani, ezért különböző osztályneveim vannak. Feltöltés előtt viszont mindig át kell írnom az osztálynevet GipszJakab-ra. Nem lehetne ezt kikerülni?
  • Küldhetsz be ilyen fejléccel is C#-os megoldást:

#if OFFICIAL_COMPETITION
  public class GipszJakab : Pairing
#else
  public class TetszolegesOsztalynev  : Pairing
#endif

ugyanis a szervezőknél be van állítva a fenti szimbólum, tehát itt az előírásnak megfelelő osztálynév lesz.

• C#-ban unsafe megoldásokat lehet használni (fordításnál engedélyezed az opciót)?
  • Nem.
• Elfogadható egy megoldás, ha csak annyi pont esetén működik helyesen, amennyit a versenyben használni fogunk?
  • Igen, csak ez elég kockázatos, mert nem tudhatod, hogy hány pontra fog futni a végső futam. :)
• Mennyi memóriával lehet gazdálkodni?
  • A Java esetén a -server kapcsolóval indítjuk a JVM-et. C# és C++ esetén az operációs rendszer, a .NET framework és a fizikai memória szab csak határt.
• Vannak-e speciális bemeneteid, amelyeket használsz ellenőrzésre?
  • Egyenlőre nincsenek, de majd lesznek. Küldhettek ti is, és akkor azokat is hozzáveszem, hátha sikerül mások programját megbuktatni. :)

Kapcsolat

Ha bármilyen kérdésed van, írj az evorace_support@evosoft.com címre.

Szervezők

• Brunczel András
• Monoczki Pál