Új hozzászólás Aktív témák
-
axioma
veterán
Algoritmus es adatszerkezeti trukkok, memoria- es idoigenyek [ordok], rekurziok es mas nyelvfuggetlen megkozelitesek.
Az interjukerdeseken innen es tul, barmi johet ami belefer mondjuk 500 LOC-ba! [De jellemzobb az 1-100.][ Szerkesztve ]
-
axioma
veterán
Pelda: [link]
Hogyan lehet ismeretlen hosszu linkedlist-bol csak egyszer vegigmenve egyenletes valoszinuseggel valasztani egy erteket? [A discuss-ban megtalalhato a trukk, ha - akar a trivialis modon - megoldjatok; en is csak onnan tudom de szerintem erdekes.] -
kovisoft
őstag
Igen, ez egy jópofa feladat, egy másik formában találkoztam már vele, ott fájlból kellett számokat beolvasni, illetve ezek közül véletlenszerűen választani egyet egyenletes valószínűséggel úgy, hogy nem tudjuk a fájl méretét és hogy hány db számot tartalmaz, csak egyszer olvashatjuk, és nem tárolhatjuk a beolvasott számokat.
-
axioma
veterán
Kerestem egy masikat ami negyzetesen konnyu, de a linearis megoldashoz kell otlet is (besorolasa emiatt hard): [link]
-
kovisoft
őstag
Én itt vagyok, meg szoktam nézni a linkjeidet, agyalok is rajtuk, csak sajnos most elég kevés az időm, úgyhogy konkrét megvalósításig még nem jutottam el. Az előző (Sliding Window Maximum) feladatra csak egy n*log(n)-es megoldást tudtam kiagyalni. Nyugtass meg, hogy nincs lineáris megoldása.
-
axioma
veterán
Orulok hogy van aki nezi.
Letezik linearis, nem kell cimkezett heap (prisor) ha azzal lett n*log(k) (igen, elsore en is azt talaltam ki).
Viszont a feladat atmegy amugy azzal is (azt hiszem, mert most nem talaltam meg, valahogy eleg hulyen lehet keresni a sajat submit-jaimat csak ugy remlik), es utana mar elered a bejegyzeseket. Ilyenkor en igyekszem a kodot nezni csak magyarazat nelkul, az is erdekes abbol kibogozni mit jelent[ Szerkesztve ]
-
axioma
veterán
Mai OITM nyelvfuggetlen programozas feladat:
Egy 4xN-es sakktablabol kivesszuk a bal also es jobb felso sarkot, a maradekot hanyfelekeppen lehet 2x1-es dominokkal lefedni, csak az n=51-re kellett a keresett szam utolso 9 szamjegyet megadni]. Ez egy volt a 3 feladatbol 1 orara, nem jott ossze [segitsegkent meg volt adva hogy n=2 es 4 eseten 0 (na ja, aki ismeri a sakktablat), 3-ra 5, 11-re 2009][ Szerkesztve ]
-
axioma
veterán
A ma vegetert codechef dec challenge egyik gyongyszeme: [link]
Nem olvastam az editorialt, hogy az en megoldasom (28 LOC, ezeket mindig pythonban ertem) vajon az altaluk kitalalt-e, de ez peldaul egy libikokas eset: ugyanaz a kod a legutolso teszteseten python3-mal nem ment at (TLE), pypy3-mal meg igen (pedig mas a szorzo).Mas: ezt csak kb. sejtem, miert jo (van yt video magyarazata), egy szamomra szokatlan divide&conquer valtozat (nem fuggetlen a kornyezetetol a resz-szamitas, csak kb. ertem en is hogy miert mukodik). Bevallom, ezt nem is talaltam ki magamtol, de amikor ilyenek jonnek akkor orulok hogy nem szurtam el ra sok orat (mint a fentire, de ott megerte), es tanulni igy is lehet belole. A feladat: [link]
[ Szerkesztve ]
-
axioma
veterán
Ket feladat ami brute force-szal megoldhatonak tunik, de nem.
1. Mai leetcode: [link]
A lenyeg a K merete, nem lehet legeneralni a szot megoldashoz. Az encoded hosszahoz kepest linearis megoldast lehet/kell keresni. [Egyszerubb amugy a feladat, csak nem brute force.]
2. A tegnapi adventofcode is egesz hasonlo problema (masodik resze): az elso reszhez le lehet generalni az elfogadott szavakat, a rekurziot viszont mashogy kell kezelni, mert (mar a mintaban is) a 42-es legeneralja az 5 hosszuak felet, a 45 hosszu pelda ellenorzesehez 16^9 db stringet kene tarolni...
A 8-as szabaly me'g hagyja am (valahany darab 42-es), de a 11-esnel ugye fontos hogy ugyanannyi 42-es mint ahany 31-es, az emiatt is technikasabb. -
axioma
veterán
Egy aranyos feladat, bar a verseny me'g most fut, de utana lesz practice-ben is elerheto szerintem. A megoldas tkp. linearis kell legyen. [link]
Fontos hozza ismerni ezt a logikai feladvanyt (sajna nincs letakarva a megoldas a [link]-en, de rovid, igy be is masolom a zanzajat:
99 hangya alszik egy 1 m hosszú egyenes rúdon. Füttyszóra egyszerre felébrednek, és elindulnak a rúd valamelyik vége felé 1 cm/s sebességgel. Ha egy hangya a rúd végére ér, lemászik a rúdról. Ha két hangya találkozik, mindketten azonnal megfordulnak és az ellenkező irányba indulnak tovább. Legfeljebb mennyi ideig tarthat amíg minden hangya le nem mászik a rúdról? -
axioma
veterán
Egy konnyu feladat [link], plane ezekkel a constraint-ekkel. De mi lenne, ha len(arr)<10**6, a_i,k<10**18 lenne a nagysagrend?
Hasonlo szoveg, tok mas megoldas: [link] Ez is atmegy siman sort-tal es akkor a fentit kapjuk vissza k=1-gyel, de van linearis ido, 'konstans' tarhely [ezzel azert vitatkoznek... de a leetcode magyarazatokban a rekurziv algot is konstansnak veszik ha nincs helyi valtozo], szoval konstans tarhelynek kinezo megoldas. -
axioma
veterán
semmi, beneztem valamit
[ Szerkesztve ]
-
axioma
veterán
Azert me'gis, bar annyira nem szorit ra megsem arra amit gondoltam hogy lehetne rajta demonstralni, de szerintem az erdekes hogy ilyenkor milyen trukkok johetnek szoba/segitenek eleget: [link]
-
kovisoft
őstag
Ezt a "Kth Missing Positive Number" feladatot én is egy egyszerű módszerrel oldottam meg, és igazából nehéz elképzelni olyan nagy tömbméretet, ami még beférne a memóriába, de mégsem lehetne kivárni, hogy szimplán egyszer végigmenjen a kód a tömbön. De gondolom arra utaltál, hogy N helyett akár O(log(N)) lépésben is meg lehet oldani, hiszen ha egy tetszőleges tömbelemet nézünk, akkor annak indexéből és értékéből meghatározható, hogy hány hiányzó szám volt addig.
-
axioma
veterán
Nyilvan ha kulonbsegekkel csinalod az jo, csak az nem ha valaki egyesevel megnezi a szamokat h hianyzik-e es ha igen, hanyadik hianyzo [O(K)]. Mert az eredeti feltetelekkel az is atmegy [persz a tombben figyelve h hol tart]. Nem, nem binaris keresesre gondoltam, bar arr+i alapon mehetne az is [+-1 azt most nem gondoltam vegig].
-
axioma
veterán
Egy erdekes feladat: [link]. A negyzetes megoldast viszonylag hamar meg lehet talalni a kobos helyett (viszont elsore a negyzetes is TLE lett), de van linearis is (en egy n*log n -est gondoltam ki de azt vegul nem kodoltam le, el is felejtodott a napi hataridoig...)
-
axioma
veterán
Bedobom, de csak onbosszantasra: a hetvegen elszurtam a versenyben, de mint feladvany erdekes, onerobol probalom es tobb otlet elbukasa utan azota sincs meg... pedig tuti hogy valami nem tul bonyolult strategia lesz.
[link] -
axioma
veterán
Ez izgalmas volt konstans tarigennyel (amibe a leetcode a rekurziot nem szamolja bele). [link]
-
kovisoft
őstag
Mivel a "greedy" szerepel a tag-ek között, így valószínűleg valami mohó stratégia kell majd. Nem vagyok regisztrálva codechef-en, így ki nem próbáltam, de az alábbi legegyszerűbb módszer nem működik?
1. Vesszük mindig a legkisebb nemüres Ai-t (i>1). Ha nincs ilyen --> megoldottuk a feladatot.
2. Ha van ilyen Ai és nem nagyobb A1-nél, akkor átrakjuk az egészet az A1-be. Goto 1.
3. Ha Ai>A1, akkor vesszük a következő legkisebb nemüres Aj-t (j>1, j<>i). Ha nincs már ilyen --> nem megoldható a feladat.
4. Ha van, akkor erre átrakunk Ai-ből annyit, amennyivel Ai nagyobb A1-nél. Ezután Ai maradékát átrakjuk A1-be. Goto 1.Legfeljebb 2 lépésben kiürül egy Ai, tehát max. 2n lépés kell.
-
axioma
veterán
Bocs, rossz a leirt pelda, most nem tudok tobbet foglalkozni vele hogy megkeressem ahogy jo, de remelem a jelleg erzodik belole.
Valami hasonlot csinaltam:
1. eloszor csak azt hogy amik kisebbek azt A1-be
2. utana azt hogy felesleget tegyuk a kovetkezore, ez se valik mindig be, de azota elraktam a firkapapirt... valami olyan volt hogy a legnagyobbakrol kellett volna kirakni a 2-hatvanyokat jo sorrendben:2 1 1 1 24 35erre mukodne az algo?Azt kene hogy 24-bol 1-et a masodikra, 7-et a negyedikre, a 35-bol 3-at a harmadikra, akkor 2 2 4 8 16 32 lesz es "osszecsukhato". Nem mondom hogy mashogy nem, de az elso ket megkozelites (utobbi szerintem tiedhez hasonlo) megoldas nem talalja meg.Ezt az aggressziven feltoltos valtozatot nem kodoltam le (jol, nem figyeltem hogy max. annyit kaphat amennyi omaga), es elsore nem is latom hogy beleferne a lepesszamba mindig, figyelni kene hogy mindig 1 lepest hasznaljon csak "valamelyik" oldalrol szamolva.
(Alapvetoen is az jott ki, hogy amikor megtalalom a megoldast az jo, de nem mindet talalom meg.)[ Szerkesztve ]
-
kovisoft
őstag
Én úgy értettem a feladat leírásából, hogy nagyobb kupacból nem rakhatsz kisebbe, csakis egy nagyobba vagy ugyanakkorába tehetsz át valahány darabot (p-ből q-ba akkor rakhatsz át x-et, ha 1≤x≤Ap≤Aq). Tehát olyan nem lehet, hogy a 24-ből átraksz 1-et egy olyanra, ahol csak 1 van. Vagy félreértettem valamit? Ha nagyobb kupacből rakhatsz át kisebbe, akkor szimplán minden kupacot átrakhatsz az A1-be, és kész, nem?
-
axioma
veterán
A greedy csak azutan jelent meg hogy atrakjak practice-ba
Most nezem, ami miatt azt hittem hogy az onmaga elott gorgeto nem jo, az valami nagyon durvan egyszeruen nem a valos kodon ment a kiertekelo rendszer szerint! Bekuldtem 3x, egyszer van letarolva, de egy masik feladathoz kuldott kodommal... Mondjuk eleve szar volt verseny alatt a szerver elerhetosege, eleve vege elott 18 perccel kuldtem es utana 25-tel lett eredmeny - es utana toroltek is a 'rated'-seget - de azt nem gondoltam hogy rossz eredmenyt mutatott amikor neztem
Annyi vigasztal hogy en nem csinaltam a "jo" megoldasomban se heap-et, csak siman (eredeti nagysag szerint) sorba mentem, arra nyilvan bukta volt amint a gorgetes nagyobbra hizlalta mint a kovetkezo. De eleg sokat jart az agyam ezek szerint tok foloslegesen azon, hogy mi lehet me'g mogotte strategia (es rendszeresen kimaradt a "csak nagyobbra tehetunk" mint itt is elsore elirtam...)
Mind1, legalabb most mar ott is tudom hogy nem kell sajat heap-et irni, import-tal elerheto a heapq. -
axioma
veterán
[link]
n^2 nem de az n*logn mar atmegy, de van linearis, azt magamtol nem talaltam meg de jo
Ez egy bonyolultabb: [link]
Az editorial nagyon olyasmi mint amit en csinalok (na jo, en egy plusz adatot vittem vegig de nagysagrend ugyanaz), ami lefutott az jo, de sajnos maradt 2 TLE, igy csak a trivialisokert jaro pontokat tudtam sok melo utan is begyujteni...[ Szerkesztve ]
-
axioma
veterán
Na ezzel ma megkuzdottem, a masfel oras verseny vege utan (ha nem is szunet nelkul) de 4 oraval sikerult megoldani. [link]
TLE-s lett az amugy azt hittem mar elegge optimalizalt, de mar az is tul sok hogy minden szinten max. partiz darab indexekbol allo set-et cipelunk magunkkal (es uniozunk), at kellett irni teljesen elvure. -
axioma
veterán
Egy tok jo feladat lenne, ha nem lenne ugy szorozva a python ideje, ahogy 2*N+2*Q*logQ nem megy a't, de ha csak a felet dolgozom fel a query-knek, akkor igen (azaz nem nagysagrendi problema van). Raadasul 3 teszteseten kivul egybol 100e-es az input, tehat a reszpontszamok lehetosege is minimalis, legalabb valami logaritmikus novekedes lenne me'retben...
[link] -
axioma
veterán
c++ -nal elsore jo volt ugyanaz idore, pedig sorrol sorra forditottam (vagyis inkabb probaltam, szivtam sokat, c-s array-ektol kivagyok, egy nagyot foglaltam aztan probaltam nem tul sokszor elrontani a pointereiket...) de a lenyeg hogy megoldhato csak pythonnal nem, vagy necces (komment alapjan van aki class-okat kiirtotta es azzal belefert, en eleve list-eltem, aztan inkabb tuple az jobb lett bar par ertek masolodott, de abban az iranyban erdemi javulast nem tudtam volna mar).
-
axioma
veterán
Ez leginkabb TLE-re fut, de harmadik probalkozasra egy ismert adatstruktura hasznalatat is hozzaveve mar par sorbol megvan: [link]
-
axioma
veterán
Parhuzamos topikban feljott, hogy ennek: [link] mi a hatekony megoldasa.
Nekem a konstrukcios az egyik iranybol nezve linearis (ahany zarojel kell a vegso megoldasban, mivel 0-9 kozott vagyunk mondhatjuk hogy az input hossza szerint is az lesz), de tartalmaz rekurziot amit ugye eleg csunyan tud buntetni a futasi ido (tail-recursive igy itt nem annyira), a "programozos" az fogosabb kerdes, azt talan a szamok osszege szerint linearisra at tudnam irni kodban, ugyanazon elv menten, most egy ennel sokkal pazarlobb, de me'g mindig nagy hosszusagu inputokra is elegendo sebessegu megoldast ad (szamok osszege szorozva egy 20-nal nem nagyobb konstans). -
Silεncε
őstag
Hát nekem valami olyasmi volt a fejemben, hogy végigmenni a számsoron (ha jól gondolom, csak egyjegyű számok lehetnek) és mindig az előző és a current szám közötti különbségnyi zárójelet lerakni (ha negatív, akkor záró, ha pozitív, akkor nyitó), ez ha jól gondolom, input méretre lineáris, viszont memóriaigényre fogalmam sincs, az ugye az input tartalmától függ. De akkor ez valszeg nem jó
Szerk: jah, most így belegondolva, ez valszeg hülyeség, úh nem szóltam
[ Szerkesztve ]
-
axioma
veterán
Talalhattal egy harmadik megoldast, nyilvan eleve-vege 0-t leraksz akkor mar stimmel.
Nekem ket masik megkozelitesem van, de spoiler ugyhogy csak ha nem allsz neki akkor olvasd.Tehat az egyik, hogy rekurzivan hivjuk magunkat azaz kvazi minden szintre, az elozo szinten feldaraboljuk az aktualis szammal amink van (pl. 12105 eseten az elso korben a 0-val darabolunk, a rekurzioba 121 es 5 kerulnek kulon, ott 1-gyel stb), es ami darabonkent visszajon a hivas utan, azt egyszeres zarojelbe rakjuk es osszefuzzuk ujra a split-re hasznalt szammal (kiveve ha ures akkor nyilvan nem is hivjuk meg). Ez max. 9 hivasmelyseg, es konstrualja a minimumot az alapjan, hogy minden korul pont annyi zarojel lesz amennyi a minimum, mert ahol muszaj ott tesszuk csak ki.
A masik hozzaallas, hogy leraksz minden szamjegyet korbeolelve pont annyi zarojellel, amennyit jelent, majd amig van benne ")(" addig replace -elni az ures stringre. Ez is max. 9x fog lefutni, lehet hogy nem is erdemes keresni mert az is linearis lesz, csak 9x replace-elni. -
Silεncε
őstag
Erre gondoltam (igen, a kód olyan amilyen, nem volt kedvem már cicomázni): [link]
Viszont így tesztelve működik, persze a limiteket nem próbáltam, lusta vagyok megírni a beolvasásos részt
valszeg a sok stringconcatenálós rész meghágná a teljesítményt, Pythonban nem az igazi valszeg
[ Szerkesztve ]
-
axioma
veterán
Az csak annyi hogy
for case in range(1,int(input())+1):
, a ciklusban meginp=input().strip()
(a strip mert mar szivtam meg masik platformon), meg input-nak nem szerencses nevezni valtozot mert azzal felulcsapod az input fuggvenyt mar a kovetkezo korre, de amugy bekuldtem (remelem nem baj hogy sajat user alatt, mar tobbedik bekuldesem), es mint varhato volt atment a megadott constraint-ek mellett siman.
Kereshetsz itt lentebb sok tovabbi feladatot , ill. prog versenyekrol, elso hsz-ben site-okrol talalsz infokat a prog.versenyes topikban [link] -
axioma
veterán
Ez mar szerintem egy kicsit a lo tuloldala (bar pont a kickstart-ra azt mondjak, kezdoknek...): nagy fat kell epiteni, ellenben nem lehet utana azt "nativ"-rekurzivan feldolgozni, tehat sajat vermezni kell. Vagy persze barmi okos bejarasi mod kell, aminel nincs rekurziv hivas.[link]
-
-
axioma
veterán
Az ilyen feladatoknal az "analysis" ful alatt van a magyarazat a megoldasra miutan lejart a verseny, es ott van is egy link a "trie" kulcsszora (nevezik me'g prefix-tree-nek is, magyarul en szó-fa -kent hallottam hivatkozni ra bo 20 eve). Ezert irtam hogy "kell", mert ezt mondjak a hivatalos megoldasnak. Igen, a versenyfeladatok idonkent olyan algoritmikus vagy adatszerkezeti megoldasok ismereset alapnak veszik, amik elo szoktak fordulni versenyeken...
[link]En se ragtam magam rajta vegig, de ilyeneket osszegyujtve ebben a konyvben lehet peldaul talalni: [link] (viragbolti pdf a szokasos helyeken megtalalhato)
[ Szerkesztve ]
Új hozzászólás Aktív témák
- Politika
- Kerékpárosok, bringások ide!
- A fociról könnyedén, egy baráti társaságban
- Fejhallgató erősítő és DAC topik
- Telekom mobilszolgáltatások
- sziku69: Fűzzük össze a szavakat :)
- Mibe tegyem a megtakarításaimat?
- Mr. Y: Curve kártyával vigyázz tankolásnál!
- VR topik (Oculus Rift, stb.)
- A Microsoft feltalálta az olcsó AI-t
- További aktív témák...