Matematické Fórum

Olin · 11. 03. 2009 15:21

Zdravím všechny. Nějakým nedopatřením se mi letos podařilo postoupit do celostátního kola Matematické olympiády kategorie P (programování). Mé znalosti a zkušenosti v tomto oboru jsou však dost chabé, proto bych si je alespoň trochu chtěl rozšířit.

Dostal jsem na naprogramování tady tyto úlohy:
http://forum.matweb.cz/upload/539-mop1.jpg
http://forum.matweb.cz/upload/795-mop2.jpg

Mám nějaké tipy, jak to řešit, a tak bych vás poprosil, abyste mi je potvrdili/vyvrátili a případně i něco navrhli.

1) Pokud by nebylo možných hodnot prvků množiny mnoho, šlo by použít pole příznaků (jestli tam člen je nebo není). Při větším počtu bych měl setříděný seznam prvků množiny, ve kterém bych vždycky prohledával binárním vyhledáváním.
(v zadání je chyba, místo D maže řádek R)

2) Cyklím posloupnost od začátku do konce, vždy, když narazím na člen menší či roven než předchozí, zakládám novou podposloupnost, pokud je větší, přidám a aktuální podposloupnosti. Nejdelší nalezenou podposloupnost si pamatuji.
(výstup u příkladu v zadání je špatně)
Nic lepšího mě v tuto chvíli nenapadá…

3) Analogické ke dvojce. Využívám toho, že pro získání součtu další podposloupnosti stačí od předchozí odečíst její první člen a přičíst následující.

4) Použiju nějaký z algoritmů na hledání cesty v grafu, který se bude snažit dosáhnout opět začátku?

5) Všechny pluky vezmu jako vrcholy biparitního grafu. Z našeho pluku vede hrana do nepřátelského pluku právě tehdy, když je v našem pluku více vojáků. Následně nějak najdu maximální párování v grafu (nevím jak…)

Dál jsem se zatím nedostal, díky za všechny vaše připomínky a rady!

Kondr · 12. 03. 2009 15:55 — Editoval Kondr (12. 03. 2009 20:08)

↑ Olin:
1) Pokud ti jde o to jak to běhá uvnitř:
Množiny se obvykle dělají pomocí binárního stromu nebo hashovací tabulky. U setříděného seznamu budeš mít problém s přidáním prvku: budeš ho přidávat v lineárním čase. Do stromu ho přidáš v logaritmickém. Co se týče hashovacích tabulek, to je na docela divočina.

Nicméně na celostátku je předpokládám dovoleo používat STL, ta úloha byla nejspíš míněna tak, abyste si přečetli dokumentaci ke třídám Set, Vector, Map atd. na zmíněné stránce cpprefference.com a naučili se používat jejich metody.

2) dynamické programování -- kuchařka na webu ksp. Nestačí ti pamatovat si nejdelší.

3) proč odečíst první? nerozumím

4) víceméně ano; pustí se na to DFS/BFS, když dojde do navštíveného cyklu vypíše Y, jinak N

5) tvoje řešení by běhalo. Maximální párování v bipartitiním grafu se hledá tak, že ke grafu přidáme zdroj a stok, jednu partitu spojíme se zdrojem, druhou se stokem a hledáme maximální tok (Edmond -- Karpův algoritmus, snadno vygoooglíš). Všechny hrany (původní, přidané od zdroje i přidané od stoku) přitom mají kapacitu 1. Obávám se ale, že to může být dost pomalé řešení, určitě to jde naprogramovat v O(N log N) a bez grafových úvah.

Olin · 13. 03. 2009 13:07

↑ Kondr:
Díky za odpověď. No, všechno to má jeden zásadní problém, a to ten, že já jsem jen takový sváteční programátor a z programovacích jazyků umím jen Pascal. Budu se muset podívat, jestli Freepascal nemá něco podobného jako STL.

1) OK, hashování snad chápu. Ovšem nějak mi nejde do hlavy, jak vypadá to uspořádávání v binárním stromu. Můžeš to prosím nastínit nebo poskytnout nějaký odkaz?

2) Nevím, jestli si úplně rozumíme, zkusím to dneska napsat a dám sem link.

3) Aha, já blbě přečetl zadání. Myslel jsem, že ty podposloupnosti mají zadanou fixní délku. Tak toto je asi fakt na to dynamické programování, mrknu na to.

5) Jo, přesně tento postup jsme si ukazovali v teoretické přípravě v pondělí. Myslel jsem teda, že existuje i nějaký "netokový" postup, ty toky mi přišly dost takové teoretické. Ještě se nad tím zkusím zamyslet.

Každopádně díky. Pokusím se podívat i na ty další, jen se obávám, že přes víkend nebudu mít mnoho času, chtěl bych se taky konečně podívat na jednu jinou soutěž…

Kondr · 13. 03. 2009 15:33

1) K těm stromům: http://en.wikipedia.org/wiki/Red-black_tree

2) Záleží na tom slově souvislá. Já jsem ho napoprvé ignoroval, navíc tomu odpovídal i výstup (tuhle úlohu jsme spolu s autorem zadání řešili onehdá ve škole a slovo souvislá v ní nebylo :) ). Pokud bychom hledali souvislou podposloupnost, máš pravdu. Pokud ne, dynamické programováí by bylo na místě.

5) Dají se hledat nějaké vylepšující cesty ... ale bude se to chovat velmi podobně, jako tokový algoritmus. (cesta z A do B je vylepšující, pokud do A ani B nevede hrana a hrany na této cestě střídavě jsou a nejsou v párování. Když pak podle této cesty půjdeme, hrany, které v párování byly, vyhodíme, hrany které v párování nebyly, přidáme, zvětšíme párování o 1 hranu.)

Lukee · 13. 03. 2009 16:58

↑ Kondr:
„U setříděného seznamu budeš mít problém s přidáním prvku: budeš ho přidávat v lineárním čase.“
U setříděného seznamu při použití binárního vyhledávání (metoda půlení intervalů) lze najít daný prvek (a vložit tam další) v klasickém logaritmickém čase.

A jinak bych doporučil pro začátek nějaké jiné než red-black stromy, ty jsou podle mě zbytečně moc složité, na pochopení stačí klasický Binární vyhledávací strom.

Olin · 13. 03. 2009 17:08 — Editoval Olin (13. 03. 2009 17:09)

↑ Lukee:
Ale nevznikne u toho setříděného seznamu ta linearita tím, že se musí všechny prvky výše posunout?

BTW objevil jsem na ty stromy hezkou stránku…
http://people.ksp.sk/~kuko/bak/index-sk.html

Lukee · 13. 03. 2009 17:10

↑ Olin:
Já předpokládal, že ten seznam bude opravdu spojový seznam. Pokud to bude pole, tak jo, ale pokud to bude spojový seznam, tak se prostě přesměrují dva pointery/reference; stejně jako v případě binárního stromu.

Kondr · 13. 03. 2009 20:13

↑ Lukee:Problém "lineárních" struktur (spojový seznam, pole) je v tom, že pokud chci rychle (logaritmicky) najít pozici, kam mám vkládat, trvá mi lineárně dlouho provést vložení. Pokud chci rychle provádět vložení, pak mi zase dlouho trvá najít pozici, kam chci vkládat. Proto jsou lepší různé stromy či haldy.

Lukee · 14. 03. 2009 11:18

↑ Kondr:
Jo, já si to uvědomil, když jsem se ráno vracel z koncertu, že je to nesmysl, co jsem napsal :-). Buď použiji pole a pak můžu použít binární vyhledávání, ale vložení bude trvat dlouho, nebo použiji spojový seznam a pak nemůžu použít binární vyhledávání. Takže ano, strom je řešení.

Olin · 27. 03. 2009 23:55

Sice mi to asi na nic nebylo, ale díky všem (vám oběma) za pomoc a podněty, v celostátku jsem nějakým zázrakem nakonec dal úspěšného řešitele…

Kondr · 28. 03. 2009 00:44

↑ Olin:Gratuluju! Koukám že letos jsi nejen dvojnásobný úspěšný řešitel matiky, ale i vítěz fyziky :)

Matematické Fórum

#1 11. 03. 2009 15:21

Příprava na MO P

#2 12. 03. 2009 15:55 — Editoval Kondr (12. 03. 2009 20:08)

Re: Příprava na MO P

#3 13. 03. 2009 13:07

Re: Příprava na MO P

#4 13. 03. 2009 15:33

Re: Příprava na MO P

#5 13. 03. 2009 16:58

Re: Příprava na MO P

#6 13. 03. 2009 17:08 — Editoval Olin (13. 03. 2009 17:09)

Re: Příprava na MO P

#7 13. 03. 2009 17:10

Re: Příprava na MO P

#8 13. 03. 2009 20:13

Re: Příprava na MO P

#9 14. 03. 2009 11:18

Re: Příprava na MO P

#10 27. 03. 2009 23:55

Re: Příprava na MO P

#11 28. 03. 2009 00:44

Re: Příprava na MO P

Zápatí