Sziasztok!
Az első kérdésem az lenne, hogy pénteken a szünet befolyásolja a
foglakozást is?
És küldenék még egy feladatot is, a 2006-os CH24 EC-en volt anno (lehet,
hogy többen ismeritek):
Problem B: Building Pipe Systems
In the country of Elbonia, the citizens are gettingtir ed of havingno
sanitation system.
Together, they have saved some money to build a new pipe system that
will connect
their houses to the communal sanitation system. But since this is a
small country,
where most of the people have small incomes, they really want to build
the cheapest
system possible. The largest cost in this whole endeavour will be the
pipes that must
be put in the ground, connecting all the houses. Therefore, they need
your help in
minimizingthe total length of these pipes.
A pipe system will connect all the houses together. The houses may either be
connected house to house, or they may be connected via arbitrarily
positioned junction
points. Since Elbonia consists entirely of mud, the cost of layingdo wn
the pipes is
uniform over all the land. In other words, the only thingt hat matters
is that the total
length of pipes is as small as possible.
Input
Each test case contains the layout of one town. The consists of a number
N, denoting
the number of houses. Followingthis number come N lines, each
containtinga pair
xi yi denotingthe position of one house. The values xi and yi are both
floatingp oint
numbers of single precision length.
Output
For each test case, you will need to produce an output that represents a
fully-connected
pipe system. The smaller the total length of this pipe system, the
higher the value
of your solution will be. The representation of this pipe system should
consist of the
followingelemen ts.
On the first line, a number M, where N ≤ M < 10 · N, denoting the number of
points on the pipe system. Followingthis come M lines, each containinga
pair xi yi
denotingthe position of one house or one junction. The first N lines
should contain
the house locations from the input in the same order, while the next M −
N lines
contain your choosen junction postitions.
Followingthis, on a new line, the number K of pipes that your pipe
system has. On
the following K lines, you should print pairs aj bj of numbers, where 0
≤ aj, bj <M)
and aj = bj, specifyingthe points connected by the pipe. Furthermore,
each pair aj bj
may only occur once in the pipe system. The indexingo f the points is
zero-based.
Scoring
Your base score for a test case will be calculated as follows. Let Val
be the length of
your solution, and Opt be the length of the best solution of any team,
including the
judges’ solution. Then the base score of your solution is given by
1002−Val/Opt.
In other words, if your solution matches the best solution, the base
score will be 100,
and if your solution is twice as longas the best solution, the base
score will be 1.
Üdv.
Robi
Sziasztok!
Egy újabb topcoderes feladat, nem olyan túl bonyolúlt, de nem is
sablon, ha jól emlékszem. :)
You are organizing a local Rock-Paper-Scissors Tournament, where the
best N players in your town will compete for fame and prizes. You have
already ranked the participants according to their performance in the
qualifying round, so each one of them will have a seed for winning the
tournament in the range from 1 to N.
The tournament will be in a knockout format and will consist of
multiple rounds. During each round the competitors still left in the
competition are randomly paired up with each other. The winners from
each game advance to the next round. The great champion is the winner
of the final game between the last two remaining players.
The tournament starts soon, and you are preoccupied with some
pre-statistics. You estimate that a player with any seed S can win
against players with greater seeds, and against ones with lower seeds,
if the difference between their seeds is not greater than sqrt(C * S),
where C is a constant. Assuming that the outcome of all the played
games during the tournament agrees with your estimation, a player can
win the tournament if there exists an assignment of games in each of
the rounds such that the player can win each round.
You will be given two ints, rounds, denoting the number of rounds, and
the constant C. Return the greatest seed of a player that could win
the tournament. Note that N, the number of competitors will be N =
2rounds.
Definition
Class:
RPSTournament
Method:
greatestSeed
Parameters:
int, int
Returns:
int
Method signature:
int greatestSeed(int rounds, int C)
(be sure your method is public)
Constraints
-
rounds will be between 1 and 16, inclusive.
-
C will be between 0 and 1500, inclusive.
Examples
0)
2
0
Returns: 1
There is no room for surprises here. Since nobody can win against a
higher-rated opponent, the lowest seed will win the tournament.
1)
3
1
Returns: 6
Player 2 can win against player 1, so both of them can win the final
if they are to meet in that phase of the competition. Since players 3
and 4 can beat player 2, they can win the tournament as long as player
2 wins against player 1 somewhere before the final. Finally, players 5
and 6 can beat player 4 in the final, as long as player 4 wins against
player 2 in the semifinals and player 2 eliminates player 1 in the
first round. It is impossible for players 7 and 8 to win the
tournament. We return the greatest seed of those who can win, namely
6.
2)
4
1
Returns: 9
3)
7
3
Returns: 50
4)
15
180
Returns: 9755
Watch out for timeout!
Hi! A feladat linearis idoben megoldasa egy ismert feladat suffix tree-kkel
kapcsolatban
A megoldas benne van Dan Gusfield "Algorithms on Strings, Trees and
Sequences: Computer Science and Computational Biology" cimu konyveben (201.
oldal), a konyv joresze (tobbek kozt ez is) fent van Google Books-on
Errol a megoldasrol viszont se azt nem latom, hogy helyes lenne, se pedig
hogy linearis ideju, mondjuk lehet hogy csak azert nem bizok ebben, mert az
ismert megoldas ennel joval bonyolultabb (Ukkonen-algoritmus es Lowest
Common Ancestor-problema <O(n),O(1)> ideju megoldasa is kell hozza) De
persze lehet hogy mukodhet, csak tul konnyunek tunik
NGG
Message: 1
Date: Sun, 20 Sep 2009 23:31:50 +0200
From: G?bor Feh?r <feher_g(a)freemail.hu>
To: acm-valogato(a)cs.bme.hu
Subject: Re: [acm-valogato] acm-felkeszites - feladat
Message-ID:
<328f8b410909201431v2e1006e9y42ff8ae782aeb07f(a)mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-2
Sziasztok,
megpr?b?ltam leprogramozni ezt az algoritmust, de elakadtam, ?s van
egy k?rd?sem.
J?l ?rtettem, hogy visszavezett?k a probl?m?t egy leghosszabb
ism?tl?d? r?szstring keres?s?re? P?ld?ul: ha "abcvucbaww"-ben keres?nk
leghosszabb r?szpalindromot, akkor ehelyett "abcvucbaww$wwabcuvcba"
-ban keres?nk leghosszabb ism?tl?d? r?szstringet? Ezzel az a
probl?m?m, hogy ?gy az eredm?ny "abc" vagy "cba" lesz a helyes "zz"
helyett. Sz?val val?sz?n?leg rosszul ?rtettem. Konkr?tan az nem
vil?gos, hogy mit csin?lunk, amikor elk?sz?lt a "gyors?t?t?mb?nk".
Viszont, line?ris id?ben is megoldhat? a probl?ma! Ezt ?ll?t?lag n?gy
h?napig tartott kital?lni egy PhD hallgat?nak, ?hgyhogy nem j?v?heti
feladatnak aj?nlom, hanem belinkelem a megold?st:
http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-i…
Ett?l f?ggetlen?l szeretn?m meg?rteni M?t? verzi?j?t is!
G?bor
2009/9/17 Ildi Schlotter <schlotterildi(a)gmail.com>:
> Sziasztok,
>
>
> Mate kuldott egy feladatot (koszonjuk!), lehet rajta gondolkodni holnapig:
>
>> Adott egy maximum 10^4 hosszu string (mondjuk az angol abc kisbetuibol).
>> Keressuk meg a leghosszabb palindrom-reszstringjet.
>
> Ildi
> _______________________________________________
> acm-valogato mailing list
> acm-valogato(a)sziami.cs.bme.hu
> http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato
>
Sziasztok,
Mate kuldott egy feladatot (koszonjuk!), lehet rajta gondolkodni holnapig:
> Adott egy maximum 10^4 hosszu string (mondjuk az angol abc kisbetuibol).
> Keressuk meg a leghosszabb palindrom-reszstringjet.
Ildi
Sziasztok,
alakul a holnapi tema, ime a harmadik jelolt:
http://code.google.com/codejam/contest/dashboard?c=32002#s=p2
Ildi
---------- Forwarded message ----------
From: Gábor Fehér <feherga(a)gmail.com>
Date: 2009/9/17
Subject: Re: [acm-valogato] acm-felkeszites - feladat
To: Ildi Schlotter <schlotterildi(a)gmail.com>
Szia,
úgy tűnik csak read-only vagyok a listán.
Szerintem a következő is egy érdekes feladat:
Gábor
Sziasztok,
meg egy ajanlat erkezett, lasd a mellekletet.
Lehet am egybol a listara is kuldeni! :)
Ildi
---------- Forwarded message ----------
From: Akos Ludanyi <llutyo(a)gmail.com>
Date: 2009/9/17
Subject: ACM felkészítő feladat
To: schlotterildi(a)gmail.com
Szia!
A csatolt feladattal TopCoderen találkoztam, és szerintem érdekes
feladat a felkészítőre (van megoldásom is).
Üdv.:
Ákos
Kedves érdeklődők!
A BME Számítástudományi és Információelméleti Tanszéken a
mostani félévben is szervezünk az algoritmusok iránt érdeklődőknek
foglalkozásokat. Ezeken elsősorban versenyfeladatokat oldunk meg,
így ez egyben jó lehetőség az őszi ACM nemzetközi programozó
csapatversenyre való felkészülésre is. Várjuk az új jelentkezőket, de
azokat is, akik már korábban jártak.
Az előző évekhez képest szeretnénk jobban bevonni a hallgatóságot,
hogy olyan feladatokról beszéljünk, ami akár a rutinos versenyzőknek
is érdekes. Ezért már előre arra szeretnék buzdítani minden érdeklődőt,
hogy ha van olyan algoritmikus feladata (versenyről vagy máshonnan),
amit szerinte érdemes közösen megnézni, az hozza el és adja fel a
többieknek.
Akit érdekelnek a foglalkozások és járni szeretne, jöjjön el
időpont-egyeztetésre
2009. szeptember 14-én, hétfőn 16.15-kor az I.B.134-es terembe
(a tanszék területén levő terem)!
Ha valaki szeretne járni, de hétfőn nem tud eljönni, akkor lehetőleg
még a megbeszélés előtt írja meg nekem, mik számára a rossz időpontok
-- amit a lehetőségek szerint figyelembe veszünk.
Friedl Katalin (friedl(a)cs.bme.hu)
Kedves Listatagok!
Az idei Challenge24 programozási versenyre keresek csapattársat.
Jelenleg ketten vagyunk, én most fejeztem be a mérnök informatikus
BSc-t, a barátom pedig matematikus az ELTE-n. Korábbi években is
indultunk a versenyen 'asdf' néven (2008 - 86., 2007 - 59., 2006 -
106.), sajnos még 'valódi' harmadik tagunk egyszer sem volt... Idén
célunk a döntőbe kerülés, valamint a verseny előtt 1-2 alkalommal
felkészülést is tartanánk. További érdekesség, hogy egy GRID-szerű nagy
számítási kapacitással rendelkező számítógép-hálózattal is rendelkezünk,
speciális - főleg a verseny kedvéért készített - keretprogrammal, hiszen
a versenyen az időnek is nagyon fontos szerepe van.
Ha érdekel, írj: siprob(a)gmail.com
Üdvözlettel:
Sipos Róbert
*2009. május 1-3. között kilencedik alkalommal kerül megrendezésre a már
hagyományosnak tekinthető BME Nemzetközi 24 órás Programozóverseny. Az
extrém kihívásokat kereső programozóknak 2009. február 21-ig van lehetősége,
hogy jelentkezzenek Európa egyik legrangosabb versenyére. A versenyt idén is
a Magyar Villamosmérnök- és Informatikus-hallgatók Egyesülete (MAVE)
szervezi a Simonyi Károly Szakkollégium támogatásával, a döntő pedig a
Budapesti Műszaki és Gazdaságtudományi Egyetemen (BME) kerül megrendezésre.*
A háromfős csapatok 2009. február 21-i jelentkezési határidőig interneten
keresztül, a www.challenge24.org weboldalon jelentkezhetnek, amit február
28-án az első forduló, egy online erőpróba követ. A legjobbnak bizonyuló
harminc csapat jut tovább a Műegyetemen 2009. május 1-3. között
megrendezendő 24 órás döntőbe, ahol a nyeremények összértéke meghaladja az
5000 Eurót.
Sem az elektronikus előválogató, sem a helyszíni döntő során nincs megkötés
a versenyzők által használt fejlesztőeszközökre, könyvekre, operációs
rendszerre vonatkozóan. Akárcsak a selejtező fordulóban, a helyszíni
versenyen is a saját számítógépeiken dolgoznak a résztvevők, a szervezők a
helyszínen csak elektromos áramot és a verseny idejére létrehozott helyi
hálózathoz való csatlakozást biztosítják. Ezzel a megközelítéssel oly módon
lehet egyenlőséget tenni a csapatok között, hogy mindegyikük a számára
leginkább kényelmes körülmények között versenyezhet, természetesen külső
segítség igénybevétele nélkül.
A feladatokat idén is a BME informatika karának doktorandusz hallgatói
írják, így a tavalyihoz hasonlóan érdekes megmérettetésre számíthatnak a
versenyzők. A problémák megoldásához, az eredményes szerepléshez gyors és
precíz kódírási képesség mellett szükség van hálózati-, mesterséges
intelligencia-, algoritmus elmélet- és számítógépes grafikai jártasságra,
valamint jól működő csapatmunkára. (Korábbi évek feladatai:
http://challenge24.org/2009/history)
A verseny rangjához és színvonalához az elismerésen túl a támogatókon,
valamint az általuk felajánlott 5000 Eurós díjazás járul hozzá. A győztes
csapat az idei verseny után is hazaviheti a vándorkupát és a fődíjat.
A szervezők az eddigi hagyományokhoz híven ebben az évben is népes
nemzetközi mezőnyre számítanak. A versenyre tavaly 207 csapat nevezett, 5
kontinens összesen 41 országából. Az európai országokon kívül olyan
helyekről is regisztráltak, mint Brazília vagy Ausztrália. A tavalyi
döntőben egy immáron harmadik éve visszatérő amerikai csapatot is
üdvözölhettünk. A szervezők természetesen mindent megtesznek, hogy a
versenyzői gárdát idén még tovább bővítsék és egy olyan versenyt
rendezzenek, mely minden résztvevő számára felejthetetlen élményekkel és
hasznos tapasztalatokkal fog szolgálni.
Az események minden érdeklődő számára nyomon követhetők lesznek a verseny
hivatalos honlapján, a www.challenge24.org oldalon.
Amennyiben bármilyen kérdés felmerül, írjanak a
challenge24-2009(a)challenge24.org
címre.
