Kraj pro elfky

Nepochopili jste zadání či naopak vzorové řešení? Chcete se zeptat na některé jiné algoritmy?
Zamčeno
dzejkob
Příspěvky: 5
Registrován: 03-03-2018 18:59
Škola: Soukromá střední škola výpočetní techniky, Litvínovská 600 Praha 9
Rok ukončení studia: 2018

Kraj pro elfky

Příspěvek od dzejkob » 01-04-2018 13:34

Děkuji za rychlé ohodnocení. Nicméně opět bych si dovolil lehce oponovat:

"Nalezení "všech lichých cyklů" určitě nepůjde v takovéto složitosti zvládnout - tento počet může být až exponencielně velký"

Toto bude patrně pravdou - a ačkoliv jsem tu složitost odfláknul (neboť nemám šanci se stát "úspěšným řešitelem" s průměrem bodů na kolo - když jsem neřešil první kolo - neboť jsem se o soutěži dozvěděl na dni otevřených dveří) - tak nehledám všechny cykly - nýbrž pouze alespoň dva liché cykly, které nemají průnik (jeden uzel se musí vyskytovat ve všech cyklech)

Potom ačkoliv ohodnocení respektuji, uniká mi, jak je vlastně rozloženo - což se týká i minulé úlohy - "naprogramuj" mám, "popiš" patrně taky - ovšem vždy dostanu penalizaci poloviny bodů a vlastně ani nevím za co.

Samozřejmě chápu, že je nereálné se detailně věnovat každému řešení.

Budou na konci ročníků zveřejněny vzorová řešení alespoň řešitelům?

blazeva1
Organizátor
Příspěvky: 27
Registrován: 22-11-2015 10:24
Škola: fakulta informačních technologií
Rok ukončení studia: 2042

Re: Kraj pro elfky

Příspěvek od blazeva1 » 01-04-2018 17:05

Ahoj,
hodnocení je podle mě adekvátní -- jde o neefektivní řešení s pokusem o analýzu složitosti. Najít dva liché cykly nestačí, protože jejich průnik může být mnoho vrcholů., tak mi není úplně jasné, jak to má fungovat, pokud nehledáš všechny cykly. Jinak je řešení poměrně pěkné, ovšem ta neefektivita je hlavní vada na kráse, proto máš 6b.

Referenční řešení rozhodně budeme zveřejňovat. Z toho, že se ti nemusí povést být úspěšný řešitel pouze ze 3 kol fiksu si nic nedělej, ještě je otevřená přihláška na soustředění, kam jsme tě už pozvali, a tam nám můžeš předvést, že jsi úspěšný řešitel :). Mimochodem, pokud pojedeš na soustředění, tak se dozvíš řešení mnoha úloh už před zveřejněním řešení na webu, a můžeš je probrat s organizátory.

Jestli máš ještě nějaké otázky ohledně hodnocení nebo soustředka tak neváhej a ptej se.

Za organizátory,
Vašek

dzejkob
Příspěvky: 5
Registrován: 03-03-2018 18:59
Škola: Soukromá střední škola výpočetní techniky, Litvínovská 600 Praha 9
Rok ukončení studia: 2018

Re: Kraj pro elfky

Příspěvek od dzejkob » 02-04-2018 16:46

No myšlenka byla taková, že se postupně prochází uzly a u každého uzlu se hledají cykly se kterými daný uzel souvisí. Zároveň se sleduje uzel, který je nejčetnější ve všech cyklech s lichým počtem. Jakmile se tento uzel v nějakém dalším cyklu ztratí, tak pak je jasné, že elfky nelze umístit a algoritmus končí. Pravda, že něco je popsáno pouze jako dovětek v dokumentu - protože jsem to už prostě nestihl - ten strom pro každý uzel to sestavuje rozsáhlejší než by bylo potřeba (asi by to nějak mělo vylučovat ty uzly, které nemají stejného nejnižšího předka než je ten referenční). Případ, kdy to projde všechny cykly je ten, když všechny liché cykly budou mít právě jeden uzel pro umístění elfek - což je nepravděpodobné u větších grafů - ale vyloučit to samozřejmě nelze.

Je to ale skutečně funkční - random test s naivní implementací běží nekonečně dlouho.

Nevím teda, zda tam nebylo nějaké úžasně jednoduché řešení a já to dělal zbytečně složitě. Když se třeba dívám na vzorové řešení "knihovna" - tak jsem netušil, že std::hash nepoloží string dlouhý 10^5 a že se to může použít. Možná tedy šlo použít nějakou undirected graph library a popsat, jak to funguje - a nemusel jsem nic vynalézat.

Za pozvánku děkuji - je to nicméně na celý týden - navíc to vypadá, že scio testy vyšly, takže být úspěšný řešitel nutně nepotřebuji.

Zamčeno