Programozasi feladvanyok - Szoftverfejlesztés fórum

üzenetek

hozzászólások


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]


axioma
(veterán)

Egyedul maradtam?
A lentire van egy 13LOC -ba belefero megoldas, ami kb. 15.-re ment at es nem tudnam most hosszabb elemezgetes nelkul megmondani, h mit is csinal ugy globalice... de tetszett a rajta agyalas, arra tisztan emlekszem.
[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. :)


kovisoft
(őstag)

Kicsit elhamarkodtam ezt a posztot. Egyrészt n*log(k)-t akartam írni, de mindegy is, mert körvonalazódik egy lineáris megoldás, úgyhogy inkább afelől nyugtass meg, hogy ilyen létezik. :B


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 ]


kovisoft
(őstag)

Meglett a lineális megoldás. :)
Amúgy tényleg át kell menjenek az n*log(k) megoldások is, mert k<=10^4, vagyis a logaritmusa max 14, és fogadtak el az én megoldásom futásidejének >20-szorosát is.


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.


kovisoft
(őstag)

Megcsináltam ezt a tegnapi leetcode feladatot, tetszett. És valóban nem kell legenerálni (még csak részben sem) a dekódolt szöveget a megoldásához.


axioma
(veterán)

:K Ezert erdemes foglalkozni vele mert eszrevetlenul noveli az eszkoztarat [mondjuk nem hiszem h melohoz, inkabb masik feladvanymegoldashoz...]


kovisoft
(őstag)

882998937?


axioma
(veterán)

Azaz, gratula:)


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 35 erre 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)

(nyilvan Q*logN van a Q*logQ helyett, csak elirtam, bar mind1 mert minden nagy tesztesetben N==Q)


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 :DDD

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 meg inp=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]


Silεncε
(őstag)

Igen, az input jogos, nem figyeltem rá, ennél általában jobb minőségű kódot szoktam produkálni :DDD

Köszi szépen, hogy kipróbáltad, legalább tudom, hogy működik a határok között :)


axioma
(veterán)

Ja nem kodminoseg-minosites volt, segitsegnek szantam, ha tudnad kezdo pythonoskent (10+ ev programozoi multtal) mennyi orat (na jo, de egyet tuti) szivtam mire kiderult hogy a "len" nevu valtozo nem szerencses:)

[ Szerkesztve ]


Silεncε
(őstag)

Nem is vettem zokon, csak mondom ez tipikusan az a kód, amit 8 óra munka után kitolok magamból :DDD megy ez ennél amúgy jobban is (bár nem sokkal). Meg Pythonnal is már régebben foglalkoztam (talán egy jó fél éve utoljára)


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]


Silεncε
(őstag)

Lehet, hogy szégyen, de én ebből nem látom, hogy lehetne fát építeni. Esetleg ha van egy kis időd, le tudnád írni röviden (érdekelne)?

Nekem rögtön a full naiv módszer jutott eszembe, ahogyan én fejben is csekkolnám, de valszeg az lassú lenne túlságosan


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 ]


Silεncε
(őstag)

Tudom, mi az, hogy fa, azért vicces lenne, ha proginfos diplomával (raadasul 5 körüli átlaggal...) nem tudnám :DDD de igen, így már megvan

Az Analysis fül meg eddig kiverte a szemem, csak baxtam észrevenni :W


axioma
(veterán)

Nem lehet hogy felreertes van? A trie != tree , itt kimondottan a szavak (pontosabban azok es prefixeiknek) halmazanak tarolasara hasznalt farol van szo.


Silεncε
(őstag)

De, sry, ne is vedd figyelembe, amit az előbb írtam... :R legközelebb majd nem debugolas közben kommentelgetek

üzenetek