NepřihlášenKSP fórum
Fórum Hlavní stránka Nápověda Hledat Přihlásit
Nahoru Téma KSP / CodEx / 24-3-1 Intervalová minima
- - Od Vojtěch Sejkora (Org) Dne 02. 01. 2012 14:25
jakto, že pro 2 4 ten váš algoritmus vypíše NE? vždyť 4ka tam je 2x
Nadřazený - - Od Jan Maria Matějka (Org) Dne 02. 01. 2012 14:31

> jakto, že pro 2 4 ten váš algoritmus vypíše NE? vždyť 4ka tam je 2x


indexováno od 1
Nadřazený - - Od Vojtěch Sejkora (Org) Dne 02. 01. 2012 14:34
a? asi to nějak nechápu... nebo ty čísla, co tam udáváte, to je kolikrát tam to dané ité číslo je nebo co?

jestli jsem to dobře pochopil, tak 4,5 je dvakrát 7,8 jednou
Nadřazený - - Od Jan Maria Matějka (Org) Dne 02. 01. 2012 14:51

> a? asi to nějak nechápu... nebo ty čísla, co tam udáváte, to je kolikrát tam to dané ité číslo je nebo co?


indexy  1 2 3 4 5 6
hodnoty 5 8 4 5 4 7

Interval 2-4 obsahuje čísla 8,4,5 → žádné z nich tam není vícekrát.
Nadřazený - Od Vojtěch Sejkora (Org) Dne 02. 01. 2012 14:53
aha...tak teď už to chápu lépe...díky :-)
- - Od VojtaP Dne 02. 01. 2012 21:17
Ahoj, jsem tady úplně nový a doufám, že píšu na správné místo. Neměl jsem odvahu zakládat nové vlákno.

V prvé řadě bych chtěl poděkovat autorům za existenci tohoto portálu, škoda jen, že jsem už v posledním ročníku gymnázia, a tak si soutěžení už moc neužiji.

Přesto jsem se ale pustil do řešení některých úloh z aktuálního kola. Programovat se učím 3 měsíce - sám. Taky mi trochu trvalo pochopit zadání k 24-3-1 a možná by nebylo od věci trošku to zadání upřesnit. Pochopil jsem to nejprve stejně jako Vojtěch, až po vygooglení tohoto fóra se mi dostalo řádné odpovědi, jak tedy na to. Přesto mám s programem stále problém.

Nevím jak moc můžete k řešení úloh poradit, aby to ještě nepokazilo smysl soutěžení, a pokud chci vědět moc, klidně mi to dejte najevo a odpovědi samozřejmě nepište. Přesto to ale zkusím...

Podařilo se mi napsat program, který projde polovinou testů (mám tedy 6 bodů). Nevím si však rady s optimalizací. Nevím co dál už bych kde ubral, aby program pracoval rychleji a s méně pamětí. Porovnávání každého prvku intervalu s každým jsem se vzdal hned v počátku, protože to se projevilo jako extrémně pomalé, hned když se počet čísel v posloupnosti trošku zvýší. Proto jsem vymyslel algoritmus, kdy se četnost čísel zapisuje do pole (tj. pokud se číslo vyskytuje dvakrát, odpovídající buňka pole bude mít hodnotu 2). Problém je ten, že takové pole musí být dostatečně velké - musí mít 10^9 prvků, aby mohlo obsahovat četnost pro každé číslo, které by se mohlo v intervalu vyskytovat. Zkusil jsem v rámci šetření paměti předělat toto pole četnosti na pole znaků (char), a také jsem ho zmenšil tak, aby postačovalo pouze rozsahu mezi největším a nejmenším číslem, ale stále to nepomáhá. Ve dvou předposledních testech vyprší čas a v posledním dojde paměť.

Nebyly by nějaké náznaky či rady, kudy se pustit? Díky moc a doufám, že jsem neporušil nějaká pravidla.
Nadřazený - - Od Jan Maria Matějka (Org) Dne 02. 01. 2012 21:40
Ahoj

> Ahoj, jsem tady úplně nový a doufám, že píšu na správné místo. Neměl
> jsem odvahu zakládat nové vlákno.


Ano, píšeš na správné místo.

> V prvé řadě bych chtěl poděkovat autorům za existenci tohoto portálu,
> škoda jen, že jsem už v posledním ročníku gymnázia, a tak si soutěžení
> už moc neužiji.


Nu což, aspoň něco. Bohužel nemá každý to štěstí, že mu někdo vrazí KSP do ruky ve 13 letech ...

> Přesto jsem se ale pustil do řešení některých úloh z aktuálního kola.
> Programovat se učím 3 měsíce - sám. Taky mi trochu trvalo pochopit
> zadání k 24-3-1 a možná by nebylo od věci trošku to zadání upřesnit.
> Pochopil jsem to nejprve stejně jako Vojtěch, až po vygooglení tohoto
> fóra se mi dostalo řádné odpovědi, jak tedy na to. Přesto mám s
> programem stále problém.


Já doufám, že to tady zodpovědný org čte a že s tím něco udělá.

> Nevím jak moc můžete k řešení úloh poradit, aby to ještě nepokazilo
> smysl soutěžení, a pokud chci vědět moc, klidně mi to dejte najevo a
> odpovědi samozřejmě nepište. Přesto to ale zkusím...


Tohle je tak na hraně … kdybys chtěl řešit víc, piš prosím soukromě na
ksp@mff.cuni.cz nebo rovnou nějakému konkrétnímu orgovi, třeba mně ;o).

> Podařilo se mi napsat program, který projde polovinou testů ...


Well done na začátečníka.

> Nebyly by nějaké náznaky či rady, kudy se pustit? Díky moc a doufám, že jsem neporušil nějaká pravidla.


No, v tomhle směru nejspíš nesmíme ani naznačovat.

Nicméně jak sám píšeš, jsi začátečník. Takové poměrně silně zvýhodňujeme
takzvanou lamí křivkou … což je obskurní přepočet bodů, aby se trochu
vyrovnaly rozdíly mezi zkušenými řešiteli a nováčky.

Lamí křivka má tu vlastnost, že je výhodnější nakousnout víc úloh a mít
z každé pár bodů, než napřít síly do jedné úlohy a mít ji za full.

Nechci tě tedy odrazovat od dodělání téhle úlohy, ale možná bude lepší
ji nechat na chvíli u ledu, pokud zrovna nevíš, a vrhnout se na nějakou
další – počítáme 5 nejlepších úloh.
Nadřazený - Od VojtaP Dne 02. 01. 2012 21:52
Díky moc za perfektní odpověď. Vše jasné.. Lamí křivka pobavila :).
Nadřazený - - Od Vojtěch Sejkora (Org) Dne 02. 01. 2012 22:24
OT:

>>počítáme 5 nejlepších úloh


od kdy 5? bejvávali jen 4 taky jste to mohli někam dostatečně viditelně dát napsané :-(
Nadřazený - - Od Medvěd (Org) Dne 02. 01. 2012 22:26
První odstavec v každém letošním letáku není dost viditelný? ;-)
Nadřazený - - Od Vojtěch Sejkora (Org) Dne 02. 01. 2012 22:27
přesně tak, protože někdo letáky nečte, a čte jen na webu úložky neboť dělá ještě další souteže, které ho nebaví, ale chtějí to po něm učitelé na škole
Nadřazený - - Od Medvěd (Org) Dne 02. 01. 2012 22:28
Abych tak parafrázoval jedno staré dobré přísloví, líné oko, holé neštěstí :-)
Nadřazený - - Od Vojtěch Sejkora (Org) Dne 02. 01. 2012 22:31
no a na webu jste to snad ani nikde psané neměli ne?:-)
Nadřazený - - Od Medvěd (Org) Dne 02. 01. 2012 22:36
I ty letáky na webu visí ;-)

Ale i v HTML verzi pravidel KSPčka to napsané je. Jen to asi není u HTML podoby sérií.
Nadřazený - Od Jan Maria Matějka (Org) Dne 02. 01. 2012 22:44

> I ty letáky na webu visí ;-)
>
> Ale i v HTML verzi pravidel KSPčka to napsané je. Jen to asi není u HTML podoby sérií.


A možná to nešlo jako novinka, ale kdo by se s tím vším taky patlal, že jo ...
Nadřazený - - Od savage2@email.cz Dne 03. 01. 2012 15:31
Dobrý den,
taky zde soutěžím prvním rokem. Chodím do prvního ročníku čtyřletého gymnázia. Programovat C se taky učím sám, nějaké ty 3-4 měsíce. Bohužel mám taky problém s optimalizací, algoritmus projde prvními 3 testy a pak skončí (TO:Time limit exceeded). Zkoušel jsem párkrát vyhledávací algoritmus přepsat, teď už se bohužel nehnu (na mém desktopovém pc to běží rychle, core i5, FreeBSD 9). Ale to není pointa mého dotazu. Chtěl bych se zeptat, jak je to s tou ' Lamí křivkou '? Jak funguje? To, i kdybych měl jen těch 6 bodů z CodExu, připíšete mi nějaké navíc?

>počítáme 5 nejlepších úloh


Hm... to jako kdybych nakousnul další 2 úlohy a nedodělal je, tak Vy je neopravujete? Děkuji za odpověď.
Nadřazený - Od Medvěd (Org) Dne 03. 01. 2012 15:38
Princip bodování je popsaný v pravidlech KSPčka, stručně řečeno to funguje takto: nejprve všechna Tvá řešení obodujeme, pak body proženeme zmíněnou křivkou a nakonec pokud jsi odevzdal víc než pět úloh, započítáme do Tvého skóre za sérii jen 5 nejlépe obodovaných (po přepočtu křivkou). U všech řešení se samozřejmě dozvíš komentáře opravujících a počet bodů.

Křivku najdeš nadefinovanou i nakreslenou v pravidlech, stručně řečeno se chová takto: 0 bodů vždy přeloží na 0 bodů, maximum na maximum, ale hodnoty mezi tím, které odpovídají nedokonalým řešením, překládá podle služebního stáří řešitelů (měřeno počtem odevzdaných sérií): těm mladším body přidává, starším naopak ubírá.
Nadřazený - - Od Jan Maria Matějka (Org) Dne 03. 01. 2012 15:40
Ahoj

> Chtěl bych se zeptat, jak je to s tou ' Lamí křivkou '?  Jak funguje?
> To, i kdybych měl jen těch 6 bodů z CodExu, připíšete mi nějaké navíc?


Tohle je asi nejlepší odpověď: http://ksp.mff.cuni.cz/zaciname/rules.html

>> počítáme 5 nejlepších úloh
>
> Hm... to jako kdybych nakousnul další 2 úlohy a nedodělal je, tak Vy je neopravujete? Děkuji za odpověď.


Opravíme všechny, počítáme nejlepších 5. Řekněme, že vyřešíš všech
8 úloh, my je opravíme, obodujeme, body se proženou Lamí křivkou a z té
vypadne 4, 5, 10, 3, 0, 2, 8 a 9 bodů. Tedy vybereme úlohy
1, 2, 3, 7 a 8, ze kterých máš 4, 5, 10, 8 a 9 bodů, což dá
dohromady 36, což je tvůj součet pro danou sérii.
Nadřazený - Od savage2@email.cz Dne 03. 01. 2012 15:47
To jsem nevěděl, děkuji Vám oběma za rychlou odpověď.
- - Od Dominik Macháček (Org) Dne 05. 01. 2012 21:16
Co znamená, že hodnoty prvků posloupnosti splňují 1<=Xi<=10^9? Co je to Xi? Znamená to, že všecky hodnoty posloupnosti jsou z intervalu <1;10^9>?
Nadřazený - Od Vojtěch Sejkora (Org) Dne 05. 01. 2012 23:44
přesně to by to mělo znamenat :-)
Nadřazený - Od Jan Maria Matějka (Org) Dne 06. 01. 2012 00:09

> Co znamená, že hodnoty prvků posloupnosti splňují 1<=Xi<=10^9? Co je to Xi? Znamená to, že všecky hodnoty posloupnosti jsou z intervalu <1;10^9>?


Xi je prvek posloupnosti na i-tém místě. Ano, všechny hodnoty
posloupnosti jsou z intervalu mezi 1 a 10⁹ včetně.
Nahoru Téma KSP / CodEx / 24-3-1 Intervalová minima

Powered by mwForum 2.29.7 © 1999-2015 Markus Wichitill