Adatok
kdano
70 bejegyzést írt és 8 hozzászólása volt az általa látogatott blogokban.
Az eredeti feladat itt. Segítség itt.
Megoldás
A tűzijáték helyét szeretnénk megkeresni, azaz az x-tengely egy (p,0) pontját. Rögzített pont súlyát, azaz a sétálandó össztávolságot könnyű kiszámolni N lépésben: minden lakosról konstans időben meghatározhatjuk,…..
Az eddigi nyaraim közül az idei volt a legintenzívebb matekozás terén (bár az elkövetkező években valszeg ennél is intenzívebb lesz).
Az Erdős-konferenciával kezdődött, egy héttel azután, hogy hazaértem. Ez életem azon ritka eseményei közé tartozott ahol a férfi vécénél…..
Minthogy nem voltak óráim (pontosabban csak az az egy, amit én tartottam), ez a tavasz viszonylag kellemesre sikerült. Vagy unalmasra, nézőpont kérdése. Mindenesetre tényleg nem nagyon csináltam semmit azon kívül, hogy időnként gondolkoztam az előző postban vázolt problémán.…..
Legyen G egy egyszerű gráf. Tudjuk róla, hogy ha e egy tetszőleges nemél (szóval e nem éle a gráfnak), akkor G+e-ben több teljes r-es található, mint G-ben. Vagyis e-t hozzávéve a gráfhoz növeljük a Kr részgráfok számát. Még másképp fogalmazva: van r csúcsa G-nek, hogy a…..
Nem éppen átlagos héten vagyunk túl. Legalábbis nagyon remélem, hogy ezentúl nem ez lesz a hét megszokott menete.
Hétfőn kezdődött. Délután egy körül olvastam először az indexen, hogy robbantottak a bostoni maraton befutójánál. Ezek után egész este a CNN-t olvastam és…..
Az eredeti feladat itt.
Megoldás
Egy tetszőleges gráfban a maximális független csúcshalmaz megtalálása nehéz feladat (lényegében NP-teljes), úgyhogy extra feltételek kihasználása nélkül reménytelen lenne hozzálátni a megoldáshoz. Koncentráljunk tehát arra, hogy mit tudunk…..
Az eredeti feladat itt.
Megoldás
Ez egy meglehetősen sztenderd dinamikus programozási feladat. Jelöljük F(i,j)-vel azt, hogy az i-edik mezőről indulva hányféleképp juthatunk el az N-edikre legfeljebb j dobással. Mindössze annyit kell észrevennünk, hogy teljesül a következő…..
Az eredeti feladat itt.
Megoldás
A legegyszerűbben úgy oldhatjuk meg a feladatot, ha minden csúcsra leellenőrizzük, hogy teljesíti-e a feladat feltételét, majd ezek közül megadjuk a gyökérhez legközelebbit. Rögzített csúcsra az ellenőrzést egy ügyes szélességi kereséssel…..
Feladat
Adott egy N csúcsú gráf, ahol legfeljebb 5 kivétellel minden csúcs foka legfeljebb 2. Adjuk meg a maximális független csúcshalmaz méretét. Avagy mesével: N ember közül – legfeljebb 5 kivétellel – mindenki legfeljebb 2 másikat ismer. Legfeljebb hány ember tudunk…..
Feladat
Egy társasjáték mezőit megszámoztuk 1-től N-ig, a bábunk az 1-es mezőn áll. Dobókockát dobálunk, és mindig annyit lépünk előre, amennyit dobtunk. A cél az N-edik mező, de csak pontos dobással érhetünk be: ha többet dobnánk, a maradékot hátrafelé kell lelépni. Ha a…..
Megpróbálom sorra venni a 2013-as válogatóverseny feladatait.
Feladat
Adott egy bináris fa (van egy gyökérpont, az 1-es csúcs, és minden csúcsnak lehet egy bal és egy jobb oldali gyereke – és persze a gyökér kivételével pontosan egy szülője van). Keressük meg a gyökérhez…..
Nemrég véget ért a téli negyedév, az azóta eltelt két hét így számomra lényegében szünet volt. Az elején mondjuk még kellett íratnunk egy vizsgát, aztán persze ki is kellett javítani, de a többi viszonylag rugalmas időtöltés volt. Most így hirtelen nem is nagyon emlékszem,…..
Az eredeti feladat itt.
Megoldás
Először is gondolkodjunk el azon, hogy milyen intervallumokat tartalmaz [a,b]: egész pontosan azokat, amelyek kezdőpontja legalább a, és végpontja legfeljebb b. Arra nincs időnk, hogy végigmenjünk az összes többi intervallumon, hogy leellenőrizzük…..
Már megint igencsak régóta nem írtam, mondjuk nagyon sok izgalmas dolog nem is történik körülöttem. Még a legizgalmasabbak közé tartozik talán a workshop, amit Bennyék szerveztek január végén. Mint kiderült, egy workshop kábé olyan, mint egy konferencia, csak kisebb. Négy napnyi…..
Az eredeti feladat itt.
A tűzijáték helyét szeretnénk megkeresni, azaz az x-tengely egy (p,0) pontját. Rögzített pont súlyát, azaz a sétálandó össztávolságot könnyű kiszámolni N lépésben: minden lakosról konstans időben meghatározhatjuk, hogy ő mennyit gyalogol, majd…..
Feladat
Volt nekünk egy szabályos zárójelsorozatunk, gömbölyű és szögletes zárójelekből: (,),[,]. Precízen most nem definiálom, hogy mi az a szabályos (ha valakinek kell, ott van az eredeti feladatleírásban), de pont az, amire gondolunk. Igen ám, csak valami elromlott a…..
Íme ismét egy válogatópélda, méghozzá 2006-ból. Akkor és abban a mezőnyben olyan nehéznek számított, hogy senki nem oldotta meg, pedig két teljesen különböző megoldása is van. Remélem, ez már a múlt, és ti mind a két módon meg tudjátok oldani. (És ezt komolyan mondom, mind…..
Az eredeti feladat itt.
Megoldás
Mindig jó ötlet lerajzolni, hogy mi történik. Ez jelen esetben a részösszegek grafikonját jelenti, azaz az i-edik helyen ábrázoljuk az első i elem összegét. Ha a grafikon végig a nemnegatív tartományban marad, akkor az alap sorozat (vagyis a…..
Az eredeti feladat itt.
Megoldás
Ezt a feladatot bemelegítésnek szántam, ez egy relatíve egyszerű dinamikus programozási példa. Egy trükk kell hozzá, de az is lehet, hogy ez nem trükk, hanem rutin. Mindenesetre érdemes észrevenni, hogy a feladat szimmetrikus, a bemenet is csak egy…..
Feladat
Adott egy város a négyzetrácson. Az utcák a tengelypárhuzamos, rácspontokon keresztül húzott egyenesek, közülük a főút az x-tengely. A polgármester tűzijátékot szeretne rendezni a főút valamelyik rácspontjában, azonban azt csak a rácsponton keresztül haladó…..
Van néhány magyar versenyről származó feladat is, amely érdekes, nem triviális, sőt fontos. Ugyanakkor ezekkel nagyobb eséllyel is találkozhattatok, úgyhogy igyekszem mellettük máshonnan származó, és talán valamivel nehezebb feladatokat is kitűzni, hogy ne unatkozzatok. Ez az…..
Bevallom, 30 repülőút és az első amerikai határátlépésem után úgy éreztem, sok izgalomban nem lesz részem a téli szünetet követő visszaút során. Azért ez nem teljesen jött be. És itt még nem arra gondolok, hogy kicsit későn értem a reptérre, mert ez igazából nem olyan…..
Feladat
Adott egy n tagú egész számokból álló sorozat: a0, a1, ..., an-1. Hívjuk az ak, ak+1,...,an-1, a0, a1,..., ak-1 sorozatot ennek a k-adik elforgatottjának (0<=k<n). Úgy szeretnénk elforgatni a sorozatot, hogy az első i elem összege nemnegatív legyen minden i=1,2,...,n-re.…..
Feladat
Adjuk meg, hogy a Cn gráfban, vagyis az n hosszú körben hány párosítás található. A csúcsokat megkülönböztetjük. Párosítás alatt az élek egy csúcsdiszjunkt részhalmazát értjük, azaz néhány élt úgy, hogy semelyik kettőnek nincs közös végpontja.
Például…..
Ez itt egy blog. Mégpedig egy olyan blog, amely remélhetőleg segít a komolyabb, algoritmikus jellegű programozóversenyekre való felkészülésben, mint amilyen az informatika OKTV, az olimpiai válogatóverseny, a nemzetközi diákolimpiák (a CEOI és az IOI), vagy egyetemi szinten az ACM…..
Belépve többet láthatsz. Itt beléphetsz