Makači

Čaute! Na tejto stránke sa budú pridávať informácie ku skupine makačov na Online Škole Programovania.

Vždy si si chcel/a nakódiť treap, ale nikdy sa ti nechcelo? Vďaka Online Škole Programovania máš na to jedinečnú príležitosť!

Čo sa tu bude diať?

Každý deň-dva (uvidíme, ako dlho budú prázdniny pokračovať) zverejním výber úloh z rýchlostného programovania podľa dopytu vieme mať tematické (online, streamovanú, platformu uvidíme) prednášky.

Každý druhý výber úloh (číslujúc od nuly) bude sada z contestu, aby si si precvičil riešenie úloh, keď nevieš aká presne techniku treba použiť, ostatné výbery úloh budú zamerané na rôzne témy. Z aktuálnej sady tu budem priebežne publikovať výsledkovku.

Na Discorde budú vždy (počas rozumných denných hodín) prítomní vedúci, ktorí radi pomôžu (či s kódom, či dajú nejaký hint).

Taktiež sa v tomto dokumente nachádza zoznam nadchádzajúcich contestov (budú sa priebežne aktualizovať), ktoré odporúčam riešiť.

Ak si už všetky úlohy vyriešil/a, napíš na Discord Paulinke (@Paulinia) (alebo na email paulina.smolarova@trojsten.sk) a nájdem ti ďalšie :)

Niektoré problémy sú v angličtine, ak by si s ňou mal/a problém, tiež napíš Paulinke.

Nové úlohy

Dlho sa to tu neupdatovalo, ale robili (a robia sa) tieto úlohy:

• slitherlink Táto úloha má prekvapivo pekné riešenie na toľko koľko málo riešiteľov má

• interconnect - je to exponenciálne? Nie je to exponenciálne?

• roadlen a lca už viete?

• fencerepair [hint: teória kódovania]

Výsledkovka za nové úlohy

Pondelok - Utorok

• koniky

• fillparens

• ab

• optimistic

• karavana1 (ľahšia karavánová úloha)

• karavana2 (ťažšia karavánová úloha)

Štvrtok

Na štvrtok som vybrala všehochuť: tri úlohy ktoré odporúčam na predvýberkovú prípravu:

• kbest

• zstrikovanie

• holecutter

Pondelok - Utorok: Stringy

Táto sada je dedikovaná stringovým algoritmom. Výskúšaj si ich na týchto úlohách:

• antisym

• mispelling

• wildcard

• fibsubstr

• masina

• yohoho

Víkend 28.-29. Marec: US Open

Tenisový turnaj? Možno, ale aj americká olympiáda v informatike! Beží tento víkend a môžte si 5-hodinový contest zapnúť kedykoľvek (ako rýchlostné) a potom vám beží čas. USACO má 4 divízie - bronze, silver, gold a platinum. Ak vyriešite nižšiu na (temer) plný počet bodov, potom si môžte pustiť contest tej nalsedujúcej atď. Ak ste už usaco niekedy riešili, riešite od vašej poslednej divízie, inak začínate na bronze. Úlohy sú ako na olympiáde - parciálne riešenia sa rátajú. Tak šup do riešenia! - A keď doriešite, môžte riešiť úlohy z predchádzajúcich dní, v pondelok príde nová tematická sada.

Streda

Dnes je posledný deň pred olympiádou v informatike tak tento deň venovaný exponenciálnym a iným pomalým úlohám:

• bond

• batohy

• buymilk2

• interconnect

• vacuum

Utorok

V utorok ťa čaká deň dedikovaný dynamickému programovaniu.

• rozdelkozy

• countpath

• budova

• bankomat

• digitprod

Nedeľa a Pondelok

Dnes je posledný deň, kedy sa dá riešiť contest rýchlostného Sada úloh z marca 2020.

Ak si ho už riešil/riešila, potom si skús tieto úlohy:

mhsplit

podretazce

veze1

veze2

Piatok - Párovanie a Toky

Nie si si istý/á bipartitnými grafmi?

Bipartitnosť

Ešte si si neprogramoval/a maximálne párovanie? Skús si to na rýchto úlohách:

Taxi cab scheme

Rhombiná

Toky:

Win

Elektrárne, Elektrárne 2, Elektrárne 3 - tri sťažujúce sa úlohy o elektrárňach

Žranica

Ak si roadreform v stredu nestihol/a naprogramovať, máš ďalšiu šancu: Road Reform

Štvrtok - Codeforces contest

Dnes je na codeforces contest, ktorý nahradí zvyčajnú sadu úloh. Začína o 15:35 slovenského času, treba sa dopredu (5 minút minimálne) zaregistrovať na contest.

Úlohy bývajú zoradené od najľahšej po najťažšiu a počas contestu bývajú testované iba na pretestoch - takže ak ti niečo zbehne počas contestu, neznamená to, že riešenie je nutne správne, to zistíš až po konci (podobne ako na súťaži Zenit v programovaní). V kole vieš hackovať riešenia ostatných účastníkov - po submitnutí úlohy si vieš pozrieť ich riešenia a ak im nájdeš príklad, na ktorom im program nefunguje, vieš za to získať body.

Streda - Začiatok novembra 2016 (04. November 2016):

Na stredu dávam do pozornosti tieto úlohy:

brexit

cukraren

halucradar

roadreform

zdvihacimost

Pondelok, Utorok - Stromové dátové štruktúry

Relevantné kuchárky: Intervalový strom

Lazy Intervalový Strom

Treap

Intervalové stromy

Ak si si ešte klasické intervalové stromy neprecvičil/a, tieto úlohy ti v tom isto pomôžu:

napoleon - minimový/maximový intervaláč

poháriky - trikové riešenie

bilboard

Lazy Loading

Niekedy potrebujeme updatovať interval, vtedy pomôže takzvaný lazy-loading. Preskúšať si ho môžeš na tejto úlohe:

miestenky

Iné stromové štruktúry

eustats - Perzistentný intervaláč - pamätanie si minulosti

riecnyboj - Skús si naprogramovať inú vyvažovanú štruktúru, napríklad Treap

setmod - naprogramuj si vyvažovaný strom ktorý vie nájsť k-tý element

nicestplace - vlastný vyvažovaný strom, vo spojení s ďalšou technikou

Vzoráky

Na niektoré úlohy sme nahrali vzoráky :) Nájdeš ich tu: https://www.youtube.com/watch?v=WX7L4aO-1SA&list=PLKwWTveCFVDs8Nn5hsDV3hSflOunbDlBs

Nadchádzajúce contesty

codeforces 3.4. o 15:35 je tu ďalší dvojdivíziový contest! Na codeforces bývajú dvoj-dva a pol hodinové contesty. Úlohy sú zoradené podľa obtiažnosti a do dvoch divízií. Úlohy bývavajú zaujímavé a navyše môžete “hackovať” druhých ľudí - úlohy sú testované len na pretestoch, nie celých sadách, a po vyriešení úlohy si môžete prezerať riešenia iných ľudí a skúsiť im nájsť chybu.

rýchlostné Ďalší contest začína 9. Apríla.

Google Code Jam 3.4.-5.4. Výročný contest organizovaný googlom. Po kvalifikácii (stačí získať 30 bodov na postup) nasledujú tri contesty prvého kola: 1A, 1B a 1C, z nich stačí riešiť jedno, obtiažnosť sa postupne sťažuje, ale kvalifikácia býva ľahká.

Codechef March LunchTime 28.3. 14:00-17:00 Indické contesty. Nemávajú úžasnú kvalitu, ale niekedy bývajú zaujímavé.

Atcoder 28.3. 13:00 Japonské contesty, s podobným formátom ako codeforces. Bývajú dosť dobré, ale pomerne skoro. Tento nasledujúci je Beginner contest, takže úlohy sú ľahšie ako zvyčajne.