trochu vám závidím, že na to máte v tomto predvianočnom čase čas. My máme toľko deadlinov, že neviem čo skôr. Ale o to viac sa teším na dovolenku, že sa na to trošku pozrem, aspoň si prečítam zadania a porozmýšlam ako by som to riešil, keď už nič iné.
Toto posledné, čo aacid spomenul vyzerá na krásny príklad grafov. Síce neviem o čo v tom zadaní presne ide, len som ho prebehol pohladom, ale zrejme by som siahol po neo4j. Nadefinovať si vzťahy medzi nimi, a potom sa Cypherom spýtať na najdlhšiu kružnicu

k tým iteráciam by som sa musel pozreť, prečo je tam taký radikálny nárast medzi 40. a 50. krokom, keď dlžka sa nezvyšuje exponenciálne. Zrejme to bude nejaká issue daného jazyka, že sa dosiahne plný stack a začne si optimalizovať veci v pamäti, prípadne sa začnú spúšťať garbage collectory. Istotne ale existuje lepší algoritmus ako to spraviť efektívnejšie. Skúšal niekto aj aplikovať rozdeluj a panuj? Ono ten reťazec sa dá pekne rozdeliť, len treba optimálne nájsť body delenia (optimálne čo najbližšie k stredu, ale nesmie to byť medzi dvoma rovnakými číslami) a tieto fragmenty spracovať v samostatných procesoch. Spojenie je potom celkom jednoduché, a neverím že by to trvalo o toľko dlhšie ako pre kratšie sekvencie. Nápad so substitučnou tabuľkou je tiež zaujímavý

tu je to video:


velmi zaujimave ci uz niekto programuje alebo nie

riesite niekto tento rok?
my mame skupinku v praci kde kazdy den diskutujeme a porovnavame vysledky a cim dakej tym viac zistujem ze moj mozog skratka nevie tak abstraktne rozmyslat ako u inych asi. ludovo povedane asi som sprosty.

vcera sa mi stalo ze som ozaj nevedel vyriesit druhu cast. nech som svoj algoritmus optimalizoval ako som chcel tak stale to nevedel vypocitat v realnom case.
ked som quitol tak som pozrel riesenia na reddite a kukal som ako puk ze ako to bolo elegantne vyriesitelne uplne jednoducho.
dnes som sice vyriesil bez problemov a celkom som spokojny s mojim algoritmom ale po porovnani s kolegami tiez som neprisiel na to najoptimalnejsie riesenie...

Nevedel som že také niečo existuje.

Keďže po celom dni programovania sa mi nechce programovať ešte nejaká súťaž, tak si už ďaľšie programovanie odpustím.
Ale úlohy sú to zaujímavé, tak som si aspoň na papier načtrtol nejaký algoritmus ako by som pri tom postupoval.
Pri tej včerajšej som si myslel že by to šlo vyriešiť nejako analyticky, aj napriek tomu že som zlyhal som si aspoň zopakoval trochu matiku

Po tých dvoch dňoch sa ale moje algoritmi celkom zhodovali s tými na reddite.

nepoznam, ale skusil som. je to celkom haluz na prevetranie mozgu.

prve tri mi prisli celkom easy, tak som skocil rovno na 8 (dnesny) a ten uz veru trochu zabrat dal. riesenie sice nie moc elegantne, sam uz sa v tom kode nevyznam, boli to take hokusy pokusy a urcite by to slo na menej ako 250 riadkov, ale mam uz dost na to ze je to v PHPku a vysledok je real time, tak ani nie je moc dovod sa v tom hrabat viac. algoritmy ostatnych radsej ani nepozeram, lebo mam zo seba aspon trochu dobry pocit teraz.

ale dobra vec, urcite sa budem snazit pokracovat dalej

Autoeditácia príspevku po 12 hod 51 min 58 sek:
tak dnesna uloha mi prisla nepomerne lahsia k tej vcerajsej .. ci tam nema byt stupajuca obtiaznost? alebo som mozno trochu velmi prekombinoval tu vcerajsiu a bolo tam ovela jednoduchsie riesenie ..

obtiaznost nie je uplne linearna, niekedy je to lahsie, niekedy tahsie.

ja som napriklad zakapal na tom siestom dni. vcera (osmy den) som sa trapil celkom dlho tiez s tou druhou castou a dnes to bolo zase jednoduchsie.

ja si prave rad citam tie redditove riesenia lebo sa tak clovek nauci nieco nove.
robim to tak ze najprv to nakodim tak aby to hadzalo spravny vysledok. potom to skusim zoptimalizovat, refaktorovat aby sa mi to aj pacilo ako riesenie a potom pozriem reddit aby som zistil ze sa to dalo 100x lahsie len ma to nenapadlo

napriklad siedmy den bol zaujimavy (hladat najmensiu spotrebu "paliva" aby sa kraby dostali k ciare), mne rychlo doslo ze netreba ratat uplne kazdu moznost a teda ze sumy roznych poloh sa postupne zmensuju az pridu k tej najnizsej. tak som vybral stredne 2 hodnoty, porovnal ich, podla toho zobral hornu alebo dolnu polovicu a zase rozpolil a takto az kym som nemal vysledok. celkom som bol spokojny lebo na ziskanie vysledku som potreboval iba 20 vypoctov paliva.
no a potom si precitam ako to robili kolegovia a zistil som ze na part 1 stacilo median pouzit a na part 2 mean average a vysledok bol hned

k tej sedmicke - ten median a mean average - fungovalo by to pri extremoch? v tom ich inpute sice ziadne nie su, ale zadanie ulohy tomu nijak nebrani. co keby jedna skupina ponoziek bola v ~50000 a druha v ~1000? ja som to zatial spravil brute forcom, ale este sa k tomu urcite vratim. nechcem si to zatial spoilovat vysledkami, ale tiez som rozmyslal o tych strednych hodnotach, resp zacat pocitat v tej strednej hodnote a pokracovat po jednom (alebo viacerych?) krokoch nahor/nadol, sledovat pri tom rastuci/klesajuci trend spaleneho paliva, tym smerom posuvat aj vypocet a na zaklade toho najst v tom strednom regione (alebo aj uplne inde - podla toho kam ma to zavedie) tu najmensiu hodnotu. lenze pochybujem ze by toto fungovalo pri extremoch, resp si to teraz neviem predstavit v hlave. a keby hej, bolo by stale najefektivnejsie to pocitat touto cestou?

tiez asi dost spravi, ci sa ten spaleny benzin v zavislosti od krokov pocita debilne loopkou alebo sa do toho tiez zakomponoju maticke znalosti o postupnostiach

Autoeditácia príspevku po 53 min 36 sek:
dnesny bol asi zas jeden z lahsich samizda.

ale skusil som este aj tu sestku s rybickami a co ja viem, to mi prislo asi jedno z najlahsich ja tam vidim len 2 moznosti .. bud mas pole "ryba => timer" alebo "timer => pocet ryb" .. najintuitivnejsia je pre vacsinu asi ta prva moznost a tiez som ju na prvu cast pouzil .. no druha cast uz bola nerealna, tak to bolo treba upravit na tu druhu moznost .. mozno tieto veci aj rozhoduju pri kompetetivnom programovani na cas, ze ludia, co im uz na zaciatku dopne, ze nemusia riesit kazdu rybu zvlast (a hlavne este pred tym, nez sa dostanu do pruseru), ale stacit riesit sumar, maju vyhodu

HERO
Ad cast 1 a median - Ano, funguje to pre vsetky hodnoty. Jednoduchy dokaz, pre lubovolne zoskupenie 2N + 1 hodnot ma median na lavo od seba N ponoriek a na pravo od seba tiez N ponoriek. Uvazujem ze median je optimalna hodnota. Kebyze sa posunieme oproti medianu o X krokov doprava, tak vsetky ponorky vlavo musia urobit o X krokov viac, cize ich spotreba narastie o X krat N. Zaroven vsetky ponorky napravo musia urobit najviac X krat N krokov menej. Tieto dve sa najvzajom prinajlepsom vynuluju, zaroven ale median este musi urobit o X krokov viac. Akakolvek zmena X oproti medianu teda zvysi spotrebu paliva prinajmensom o X.

Ad cast 2 a priemer. Toto tiez funguje pre vsetky hodnoty, ale dokaz je trochu narocnejsi a nechce sa mi ho rozpisovat. Da sa ale dokazat ze rozdiel medzi priemerom a optimom bude najviac 1/2, co ti v tomto pripade uz staci.

*****HERO***** napísal: 10 dec 2021, 12:15ale skusil som este aj tu sestku s rybickami a co ja viem, to mi prislo asi jedno z najlahsich ja tam vidim len 2 moznosti .. bud mas pole "ryba => timer" alebo "timer => pocet ryb" .. najintuitivnejsia je pre vacsinu asi ta prva moznost a tiez som ju na prvu cast pouzil .. no druha cast uz bola nerealna, tak to bolo treba upravit na tu druhu moznost .. mozno tieto veci aj rozhoduju pri kompetetivnom programovani na cas, ze ludia, co im uz na zaciatku dopne, ze nemusia riesit kazdu rybu zvlast (a hlavne este pred tym, nez sa dostanu do pruseru), ale stacit riesit sumar, maju vyhodu

ja som s tymto zabil mrte casu. najprv som spravil prvu cast kde som iteroval kazdu jednu rybicku. ale ako si pisal, pre 256 dni to bolo nerealne.
tak ma napadlo ze predsa ked si odmyslis tie uvodne hodnoty (teda napr ze rybicke ostavaju 3 dni do "porodu") tak kazda ryba bude robit to iste, kazdych 7 dni porodi a vzdy ta nova ryba bude 2 dni robit nic a potom rovnaky cyklus. a ze teda sa to musi dat vypocitat ked vies pocet dni. trebars ak pocitas 20 dni a ryba zacina s cislom 3 tak 20-3=17 dni / 7 su dve nove rybicky z coho jednej bude ostavat 10 -2 8 dni a teda porodi dalsiu rybicku a druhejbude ostavat 3 - 1 dni a uz nic neporodi. a teda tento cyklus staci opakovat pre 0 az 6 ostavajucich dni a teda iba 7 krat.
trvalo mi mrte dlho kym som to napisal tak aby to fungovalo a potom som zistil ze pre 256 dni je to aj tak nerealne...

no a potom som sa na to uz vykaslal lebo vela casu som minul a pozrel ako to maju ini.
stacilo pole s 9 hodnotami (pocet ryb s casom do porodu 0, pocet ryb s casom od porodu 1 a tak podobne) a potom len pre kazdy zobrat prvu hodnotu (ryby ktore maju rodit) a dat ju na koniec pola (ryby ktorym ostava 9 dni do porodu) a zaroven pocet tych ryb pripocitat do pola [6] teda pocet ryb ktorym ostava 7 dni do porodu.
mas queue ktoru kazdy den zrotujes o jedna a este priratas do toho siedmeho dna. proste totalne primitivne ale v zivote by ma to nenapadlo.

eMPiko napísal: 10 dec 2021, 19:06 HERO
Ad cast 1 a median - Ano, funguje to pre vsetky hodnoty. Jednoduchy dokaz, pre lubovolne zoskupenie 2N + 1 hodnot ma median na lavo od seba N ponoriek a na pravo od seba tiez N ponoriek. Uvazujem ze median je optimalna hodnota. Kebyze sa posunieme oproti medianu o X krokov doprava, tak vsetky ponorky vlavo musia urobit o X krokov viac, cize ich spotreba narastie o X krat N. Zaroven vsetky ponorky napravo musia urobit najviac X krat N krokov menej. Tieto dve sa najvzajom prinajlepsom vynuluju, zaroven ale median este musi urobit o X krokov viac. Akakolvek zmena X oproti medianu teda zvysi spotrebu paliva prinajmensom o X.

Ad cast 2 a priemer. Toto tiez funguje pre vsetky hodnoty, ale dokaz je trochu narocnejsi a nechce sa mi ho rozpisovat. Da sa ale dokazat ze rozdiel medzi priemerom a optimom bude najviac 1/2, co ti v tomto pripade uz staci.

jo diky, ked si ten median predstavim takto, tak to uz zmysel dava.

s castou 2 a priemerom som sa trochu pohral a veru tiez vychadza presne pri roznych situaciach, aj ked este uplne neviem preco

aacid napísal: 10 dec 2021, 22:55 no a potom som sa na to uz vykaslal lebo vela casu som minul a pozrel ako to maju ini.
stacilo pole s 9 hodnotami (pocet ryb s casom do porodu 0, pocet ryb s casom od porodu 1 a tak podobne) a potom len pre kazdy zobrat prvu hodnotu (ryby ktore maju rodit) a dat ju na koniec pola (ryby ktorym ostava 9 dni do porodu) a zaroven pocet tych ryb pripocitat do pola [6] teda pocet ryb ktorym ostava 7 dni do porodu.
mas queue ktoru kazdy den zrotujes o jedna a este priratas do toho siedmeho dna. proste totalne primitivne ale v zivote by ma to nenapadlo.

asi si to chce uvedomit, ze ta ryba okrem timeru nic ine nema, to je jej jedina property, cize ked to podla toho zgrupujes, ziadne data nestratis. ale uprimne netusim ake myslienkove pochody k tomu rieseniu priviedli napr mna

Tento rok sa chystate na Advent of Code?

jasne, my v praci kazdy rok organizujeme skupinu, mame tam vlastny leaderboard a tak zdravo sutazime (niektori nie uplne zdravo)..
ja som sa zacal 2 tyzdne dozadu pripravovat, chcel by som to tento rok robit v ruste a kedze som v tom nikdy nerobil tak som cital a skusal...
neviem ako dlho mi to vydrzi, predsalen niektore veci sa tam robia dost zlozito. ako fallback mam python v tom ide vzdy vsetko lahko

nice, dam si. ja verim v PHP - jeho nativne array_* funkcie mi minule dost ulahcili robotu ... ale tak samozrejme kusy kody sa daju predpripravit v hocicom

aacid: Rust je super. Dufam, ze sa podelis o niektore riesnia. Sice mi uz opadol ten entuziazmus, ked som v nom robil nejake veci, no je to zaujimavy jazyk, co sa oplati naucit.

Nechystam sa, prvy krat to vidim a bezne riesim dost problemov, nepotrebujem si este prikladat dalsie arbitrarne

ja tiez kazdy rok pri AoC zistujem ze som len priemerny programator. zatial co niektori kolegovia zvladaju kazde zadanie vyriesi do hodiny, ja som schopny sa pri niektorych zaseknut totalne. aj minuly rok som skoncil na 17ke lebo som sa nevedel pohnut a povedal si ze uz to nie je zabava ale praca a tej mam dost uz tak.

ale u nas nastastie manazeri to maju tiez radi takze nam umoznuju to riesit v pracovnom case (samozrejme nie 8 hodin denne) a minimalne prve 2 tyzdne byvaju vzdy zaujimave a zabavne, su to proste programatorske puzzle.

Ja sa do toho pustim, mna trochu zdrzuje blba anglictina, a nedostatok casu. Casto vyriesim len dva tri a potom pridu deadliny v ronbote
No rozhodne to beriem ako odregovanie a je to urcite lahsie ako slovenske KSP, kde byvaju podobne ulohy.

KSP nepoznam, vravis ze AoC je lahsie ako toto urcene pre stredoskolakov?
to uz sa teda ozaj citim ako uplny amater

dnes nam manazer co AoC ozaj zerie prezentoval tento rocnik a spominal ze sa mu konecne podarilo dokoncit vsetky stare rocniky a ze sa tak zaradil k cca 800 ludom na svete co maju vsetky hviezdicky...

aacid napísal: 29 nov 2022, 14:24 KSP nepoznam, vravis ze AoC je lahsie ako toto urcene pre stredoskolakov?
to uz sa teda ozaj citim ako uplny amater

Takto, tazsie je to v tom, ze KSP (mozno kecam davno som to nepozeral) odovzdavas program, ktory musi vypocitat vysledok do urciteho casu na ich serveri. Zatial co pri AoC to mozes nabastlit a je ti jedno, ze sa to pocita hodinu, len zadas do webu vysledok.

To nie je o amterizme, taketo ulohy su viac pre matfizakov, ja ako informatik riesim uplne inu triedu problemov.

aacid napísal: 29 nov 2022, 14:24 dnes nam manazer co AoC ozaj zerie prezentoval tento rocnik a spominal ze sa mu konecne podarilo dokoncit vsetky stare rocniky a ze sa tak zaradil k cca 800 ludom na svete co maju vsetky hviezdicky...

Tak to je macher a este ma aj vela volneho casu No viem, ze ked v tomto clovek ziska cvik, tak kazda dalsia uloha ide lahsie.

ok, tak to chapem ked musis odovzdavat program s popisom ze je to zlozitejsie... to mi pride take tradicke komunisticke ze z nieco co vypada celkom zaujimavo treba spravit nieco extremne administrativne otravne.

k manazerovi, tak je to manazer jasne ze ma kopu casu
zalezi velmi ako to riesis, ci si ozaj zoberies programovaci jazyk v ktorom mas najviac skusenosti a riesis tak aby to dalo spravny vysledok a viac ta nezaujima. mam kolegov co sa s tym hraju totalne, maju cely framework napisany aj s testami a performance monitorom a nasledne si porovnavaju komu to program vyrata rychlejsie.

ja som niekde v strede, teraz som mal dost casu tak som si spravil jednoduchy skriptik co mi kazdy den spravi novy projekt uz s nejakou strukturou aby som mohol rovno zacat riesit.
jedine co mi chyba je aby to samo stahovalo input ale nechcelo sa mi babrat s autentifikaciou...