Új hozzászólás Aktív témák
-
axioma
veterán
megmerettetes 3 ide vago feladata:
ipar4.0 (elvileg C# de a feladat csak a valaszt varta):
adott szavak egy listaja, amiben semelyik nem kezdoszelete a masiknak
roviditeni akarunk, a szavak vegerol lehet levagni karaktereket, de tovabbra is megmaradjon az a tulajdonsag, hogy egyik se kezdoszelete a masiknak
hany karakter kerul az optimalisan roviditett file-ba?
--
nyelvfuggetlen programozas:
1.) n input, ennyi bit hosszu "szamzar"-rol szol a feladat
valahany sor 3 tokennel, ezek a sorok xor kapukat jelkepeznek
az elso a kapu neve, a masik ketto hogy mi van a bemenetere kotve: korabban mar definialt kapu neve, vagy egy bitje a szamzarnak (akkor az indexe szerepel)
az utolso kapu nyitja a lakatot, ha 1-esen all, 0-nal zarva marad
mi a legkisebb szam binaris alakban, amelyik nyitja a zarat? [vagy "semmi" ha nincs ilyen]
2.) n hosszu tomb pozitiv egeszekkel, k<=n
mozgassunk valamennyi elemet mas indexekre ugy (hozzaadva, lenyegtelen), hogy osszesen k darab nemnulla kupac maradjon
a mozgatasi koltseg az indexek kozotti tavolsag szorozva az elem ertekevel (traktor mazsanyi koveket osszehord)
mi a minimalis osszkoltseg? (tesztadat legnagyobbikanal n=1000, k=200) -
axioma
veterán
Hackercup-rol: [link]
Fura a solutions, nekem at kellett allnom melo miatt c++-ban kodolasra, igy viszont egy eleg gagyi gepen belefert 3 percbe a futasi ido anelkul, hogy elokalkulaltam volna (memo az persze volt).
Az azert meglep, hogy alig volt itthonrol versenyzo... ugy latszik nem vagyok hatekony mozgositasban
-
axioma
veterán
Jobbulast! Gyorsan es nyom nelkul keveredj ki belole.
Nem feltetlen nehez az a feladat, ami annak latszik, a programos is az en hulyesegem hogy csakazertis modon oldottam meg... de pl. a memoization-t felirhatod a dynamic programming-gal egyutt a listadra, ami mar nem adatszerkezet vagy algo, hanem inkabb strategia mint pl. a moho.
Majd ha mar van ra energiad es nezel feladatokat barhonnan, szolj ha nem vilagos es tudunk hint-elgetni eleg light-osan. -
axioma
veterán
Ja en kigyujtottem az osszes x-y-z koordinatat [utolsok+1, szoval inkabb atkapcsolasi pontok] es minden igy adodott intervallumokra [3d] ta'roltam az allapotot. Ez nyilvan tobb darab, mint nalad, a kod maga volt egyszerubb. Biztos volt mas is amit messze nem a legjobb modon oldottam meg, itt akkor hatarozottan a lustasag volt a kulonbseg ;-)
-
axioma
veterán
Hat a kockaknal 800^3 darabot nem taroltam memoriaban, hanem a bekapcsolt koordinatakat. Nyilvan c-jellegu nyelvekben packed bitarray segithet... nekem a helyfoglalasig nem ment le 5 perc alatt, akkor tertem at koordinatakra. Igaz, nem tul jo gepen es ide-ben futtattam.
A rakosnal elegge mindent be kellett korlatozni [bar en mindig szoba-folyoso terveztem, az nem tul sok plusz], akkor emlekeim szerint gyors lett, holnap gepnel ujrafuttatom. Mondjuk en azt hittem hogy a folyoso nem marad vonalas es ugy kell optimalizalni, igy kicsit altalanosabb lett mint kellett volna. A legkesobb berakott szabaly az lett, h csak akkor mehet a szobaba ha nincs masik benne, es akkor is csak a legalso szabadra.
Gratula a gyozelmedhez!
[Meg akarom csinalni a 2015-t hogy milyen a szines karacsonyfa es ha az is jol nez ki akkor abbol polot jovore... iden a mikulas-sapkasbol mar lett egy ;-) ]
A naptarbejegyzes idozitesekhez csodakra kepes, most jol be is allitottam. Jo lenne egy friendly reminder toluk, de az oauth miatt gondolom nem mindenhol mukodne. -
axioma
veterán
Eh, hibas volt a minimumra atirt, a pluszban belerakott gyorsitasnal egy helyen elirtam a nullak szamat, ugyhogy azert nem talalta meg a megoldast (nem csak gyorsan nem). A vegen lefutott 30.5 perc alatt az inputonkent elta'rolt valtozat (az elso 13 inputbekeres elotti regiszter-allapot memorizalva, es mind a 9 inputtal kiprobalva; a 14. mar csak a megfelelo iranybol az adott allapotokra es hozzajuk tarolt min / max-ra).
Sztem ez me'g azert igy megoldas... -
axioma
veterán
Igen, ezert nem tetszett. Ha ugy lett volna hogy a feladatleirasban van a program, es az input (akar mindenkinek ugyanaz) az, hogy melyik valtozo melyik erteke eseten van elfogadva, akkor azt mondom hogy a program a feladatmegfogalmazas resze, nem az inpute'. Akkor arra siman megy (sot altalaban kell) a human elofeldolgozas.
En most mar csakazertis le akarom futtatni de sajnos mig tavol voltunk ismet leallt kapcsolat miatt... valamiert nem ment a tee -a. -
axioma
veterán
Nekem hatarozottan nem tetszett - legalabbis a subreddit alapjan amiert nem sikerult. Mi az hogy az inputtol fuggo programot irunk... ezt mindig probaltam kerulni, ugy megirni hogy altalaban mukodjon, legfeljebb a maximumokat lottem be annak ismereteben.
Mondjuk nekem az elso lefutott talan 10 perc alatt (vegul... persze ehhez kette kellett szedni az input programot es kulonbozo strategiat alkalmazni), de a masodik reszt ami nem nagyon kene kulonbozzon de itt hagytam ejjel brute force-olgatni, csak sajna nem akadalyozta meg hogy elmenjen a gep aludni... pedig szamitasaim szerint a full futasido max. 50 perc. Most meg folytatta ugyan de el kell mennunk.
Jav. most nezem az 50 perc felreszamolas volt... na mind1, ez most ennyi, este tudok arra is meg a maira ranezni. -
axioma
veterán
Hat a mai masodikra nem tudom milyen 10 eves hardveren futna le 20 masodperc alatt, pontosabban ahhoz milyen program kene (jo, nyilvan nem python hanem C/C++, de gyanus hogy akkor sem). Me'g azon is kellett buveszkedni hogy a memoriaba beferjen, nekem int-re konvertalva lett csak jo tuple-kent nem (nyilvan mar megapixelesitve).
-
axioma
veterán
-
axioma
veterán
Hat nekem nem tetszett a fa'val megoldas, de teny, megoldhato. A rekurzional mindig is jobban szerettem a normal ciklusokat.
A maiban jol megszivattam magam, a 24 iranybol (legalabb az) egyiknel elrontottam egy elojelet, nem jott ki a minta sem. Szerencsere (foleg mivel nem kerestem meg neten csak terszemleletbol probaltam leirogatni) eleg eros volt a gyanu egy ido utan, hogy ott irtam el.
Az azert jelentos segitseg, hogy nem "barmely korabbibol 12 pont" illeszkedik, hanem a scanner-parok - bar most pongyola voltam, es nem neztem meg hogy mennyire igaz, hogy mas pont nincs amit latnia kene, csak hogy van eleg ami jol atfed.
Nehezseg: szerintem ez a mai a legnehezebbnek szant: ha elolvasod akkor irja valahol, hogy a hetveget figyelembe veszi (hogy akkor tobb ido van megoldani, legalabbis altalaban). Igaz, 25-en is van me'g naluk, ami szombat, de csak nem az unnepre rak valami extrat. -
axioma
veterán
Hat, ezt megszenvedtem. Bar en a tegnapit is, igaz azert mert a) kerestem a (logikailag adodo) hatarokat b) negyzetesen (x es y kulon linearis szorozva lepesek ertelemben) oldottam meg, nem kobosen (x szorozva y szorozva lepesek), a limitek ismereteben sem... raadasul negativ y az elejehez nem is kellett... na ebbol az alapbol darabszamot varazsolni... de meglett, me'g ha semmi jelentosege nincs is hogy elvben gyorsabb (na jo, nem teljesen negyzetes, mert van benne x koordinatas set-ek unioja is...)
Igazabol a maira nem is tudom, mi lenne a szep megoldas, mert neha lista neha fa kell. Mondjuk az segit hogy mindig a legbelsot hasznaljuk igy en kicsit atkonvertaltam kicsit nem... de nem volt rovid/gyors, es van benne sok string/list slice-olas meg osszeadas. Mindkettot tartalmazo objektummal nem szenvedtem. -
-
axioma
veterán
En a mait buta modszerrel oldottam meg. Eredmenymatrix mindenki szumma all value, bal felso sarok 0. Amig van javitas, addig vegigmegyek minden cellan es akinek az eredmenye+adott szomszed kockazata kisebb, mint ami a szomszed eredmenye, ott a szomszedot felfrissitem a kisebbel, modositasjelzo on. Nyilvan output a jobb also sarok. Lehetne rengeteget optimalizalni (itt most konkretan ha nagyon akarod, dijkstra-zhatsz), de szerintem tok felesleges. Ez is lefut a nagyra is online ide-ben is par max. partiz masodperc alatt. Es kodsorban joval kevesebb (konkretan az elso 20 sor, pythonban).
A temakorokhoz:
A linked list szerintem ma mar eloben tok folosleges, ha valami nagyon beszuras-torles-heavy es gyors is kell legyen, akkor van a nyelvekben beepitett megoldas ra.
A stack es queue kell, plusz kene a priority queue. Nem feltetlen kell sajat megvalositassal foglalkozni (pl. heap), csak a beepitetteket hasznalni.
Fa talan, de pl. kiegyensulyozott keresofa tok folosleges...
Tree traversal egyes esetekben lehet, de sztem ilyen verseny jellegu feladatnal meg interjun, a valo eletben ez szerintem ritkan jon elo. Legjellemzobb hogy a levelektol felfele tudod szamolni az adott tulajdonsagot, erdemes root node-bol feldolgozasi listat csinalni (ennek nem feltetlen kell valamelyik nevesitett bejarasnak lennie, persze jellemzoen azokat konnyebb programozni). Ha valami 20-50-nel tobb melysegi hivas lenne, en mar kerulnem a tiszta fuggvenyrekurziot.
Heap: en egy esetben szoktam hasznalni, ha modositassal kell a priority queue, de sztem ez se fontos igazan, az elvet tudni nice to have.
Graf es bejarasok: ez szokott kelleni, valami tokegyszeru objektumos tarolast erdemes a matrix helyere betenni (pl. id+e'lek listaja a tuloldali node id-vel), bejaras nyilvan kellhet, backtrack itt ugyis elojon. De egyebkent nyelvektol fugg, szokott lenni kesz graf, csak beparameterezed es tudsz tole pl. akar max. parositast is lekerdezni (ami tok altalanos esetben kezzel nem egy leanyalom).
Dijkstra: akar. De lasd fent, nem tartom mindig szuksegesnek. Ha ordo-ssagot kell teljesiteni akkor persze nem art. Szerintem me'g az is lehet, hogy ez a mai megoldhato (most nem tudom kiprobalni) cska jobbra es le lepesekkel, akkor meg siman eleg egyszer vegigmenni a tombon (a balrabb es fentebb levo ertekek mar veglegesek), ilyen jellegu szerintem tobb volt.Azert tedd hozza hogy nem en vagyok az etalon, en tul sok eleve is feladvanynak keszult problemat oldok meg.
-
axioma
veterán
A grafoshoz a backtrack kulcsszo tartozik. Valahol az is egy rekurzio, de ezt talan erdemesebb allapot-listaval lekovetni [azt is stack-kent hasznalod].
Szolj ha kersz hintet, vagy ha az neked jobb, megoldast es abbol visszafejted h mi a logika. [Lehet mas grafos backtrack megoldas.] A graf reprezentacio az viszont kelleni fog pluszban. -
axioma
veterán
Nem sok a kulonbseg logikailag szerintem a maiban, annyi hogy te az egesz inputot adjustalod, en meg abbol olvasom csak, es azt ta'rolom csak el (stack), amit mar feldolgoztam de nem volt me'g parja. A te megkozelitesed logikailag tok ugyanaz, csak a string-ek (vagy list-ek is) kozeprol torlese, vagy osszefuzesi muveletek a valosagban az adott struktura hosszaval azonos muveletigenyuek (jo, meglevo linkedlist-es implementaciotol eltekintve), ezert szakmabeliek ahol lehet rutinbol keruljuk... Alternativ megoldas lefoglalni egy tombot es azt irogatni/torolni indexszel (elso ures hely), es akkor nem is valtozo hosszu strukturara tamaszkodsz. A list/array csak vegerol torteno irogatasa (veremkent hasznalata) is optimalisabb lesz mert azert nem egyesevel kell uj helyre tenni, a stringek azok viszont jellemzoen ujrafelhasznalas nelkul masolodnak, akar a vegere fuzessel is.
Termeszetesen ezekre a feladatokra amik az AOC-n vannak ez nem erdekes kulonbseg, csak gondoltam mint szempont felvetem.Masikhoz nyugodtan kerdezz, szivesen vegigveszem - de a rekurzio fogalma kelleni fog hozza. A kulcs az, hogy a cellat mar azelott 9-re allitom, mielott a szomszedokat elkezdenem feldolgozni, igy onmaga ugyan szomszedja a szomszedjanak, de a "visszahivasbol" mar a 9-es miatt szo nelkul 0 db uj elemmel visszater. Effektive 4*rows*col lekerdezes lesz, csak osszevissza sorrendben.
-
axioma
veterán
(tegnapihoz nem volt ertekben 1-nel nagyobb kikotes, a 0 is eleme a medencenek, szerintem...)
Hat en siman rekurziot irtam (ez esetben valodit, mert velheto volt hogy nem lesz ezres melyseg, persze lehet ciklussa atirni is amikor olyan a feladat). Egy tetszoleges koordinata "medenceje" 0, ha az 9-es, ha viszont mas, akkor rekurziv hivassal (ha nem szelso az adott iranybol akkor meghivom arra a szomszedra) kapott mereteket hozzadom -- de kozben amikor beleszamolom egybol 9-esitem is oket, mert egy hivasbol is eljut tobbszor ugyanarra a pontra. Igy ha minden koordinatat lekerdezek, akkor is csak a diszjunkt medencek lesznek nemnulla me'rettel.
Mivel mar reg kirakhato a kod (sajat csatornaikon is), ime egy pelda a megoldasra:def get_size(arr,i,j):
if arr[i][j]==9:
return 0
res=1
arr[i][j]=9
if i>0:
res+=get_size(arr,i-1,j)
if i+1<len(arr):
res+=get_size(arr,i+1,j)
if j>0:
res+=get_size(arr,i,j-1)
if j+1<len(arr[0]):
res+=get_size(arr,i,j+1)
return res
arr=[list(map(int,list(s))) for s in input().split('\n')]
areas=[]
for i in range(len(arr)):
for j in range(len(arr[0])):
act=get_size(arr,i,j)
if act>0:
areas.append(act)
areas.sort()
print(areas[-3]*areas[-2]*areas[-1])A mai feladat tipikus veremmel (stack) megoldando feladat, de ha a masodik fele ment, akkor azt valoszinuleg ugy is csinaltad, akkor viszont nem kene az elejenek se neheznek lennie.
-
axioma
veterán
Hat a betuk gyakorisagat is lehet nezni (a 0-9 mintaban). 4->e, 6->b, 9->f, azon szamjegyek amiben ebf is van a 0,6,8, ezeknek tovabbi kozoseik a 7->g, 8->a, a maradek 7->d, 8->c.
(Van rovidebb is de most pont nem akartam kihasznalni hogy tudjuk hogy melyik hany szegmens... amugy 9 db = f, a ketto hosszu 1-es masikja a c, a 3 hosszu harmadikja az a, az e,b, mint fent gyakorisagbol akar, a g/d az lehet az alapjan hogy amelyik szerepel 6 hosszuban az a d, masik a g)
Valoszinuleg lehetne altalanosabban is, de 7! se olyan nagy sza'm, ha gondolkodas nelkulit keresunk. -
axioma
veterán
Az elsonel van, mindig a medianhoz kell lepni, hiszen 1 egyseget ha mozogsz jobbra-balra, akkor csak attol fugg az osszeg valtozasa, hogy mennyi van toled jobbra es mennyi balra (egyikeknel no, masikaknal csokken a tavolsag). De ha nem is rendezed sorba, akkor is eleg azokat az ertekeket nezni, amelyik valamelyik elem is egyben, jobban szetszort sorozatnal ez hasznos gyorsitas.
A negyzetesre most en is megcsinaltam ciklussal, leven erosen korlatos volt az ertekhalmaz, nem gondoltam ki hogy lenne-e "matematikusabb" megoldas, erzesre azt tippelnem hogy nincs, de nem neztem utana. -
axioma
veterán
Bocs, C style-ban ritkan irok. Ez a 8 iranyt egyben lefedi, ha csak diagonalra kene, akkor nem kellenek a 0 vizsgalatok.
// from (fx,fy) to (tx,ty)
int dx=(fx==tx)?0:((tx<fx)?-1:1); // ugyanaz mint sign(tx-fx) ha van...
int dy=(fx==tx)?0:((tx<fx)?-1:1); // sign(ty-fy)
int len=(dx!=0)?(tx-fx)/dx:((dy!=0)?(ty-fy)/dy:0);
for (int i=0;i<=len;i++) {
x=fx+i*dx;
y=fy+i*dy;
// tomb manipulacio
}
(lehetne x,y beallit es akkor csak +=dx/dy a ciklusban a koordinata kiszamitas, az mar mind1, szerintem igy inkabb lathato az osszefugges)Nem feltetlen mondanam jobb megoldasnak, teny hogy kompaktabb, inkabb az az elonye hogy altalanositasra epul. Hatranya hogy ha muszaj debug-olni, akkor nehez kivalasztani, hogy mikor akarsz megallni (persze lehet), meg fejben kovetni hogy melyik esetben vagy.
-
axioma
veterán
Ennel sokkal benabb hibakat kovetek el nem keves prog.versennyel a hatam mogott, nyugi...
Kieg. most en is pluszban tettem be a diagonalt es csak ott alkalmaztam, de egyebkent ha elore megneztem volna (en azt hittem teglalapok lesznek a nem tengelyiranyuak), akkor ennyi esetnel mar a sok if-nel jobb dx,dy kepzese es utana vegigsetalas, az a 8 iranyra jo. Elonye nem a kevesebb gepeles, hanem ilyen problemak elkerulese hogy fele jo, fele nem.
-
axioma
veterán
Az inputot biztos hogy teljesen, elejetol vegeig kimasoltad? Azzal en szivtam mar. (Egyszer nekifutottam hogy a programom fix resze legyen az url-bol beolvasni, de az autentikaciot par netrol masolt probalkozas utan feladtam, pedig tuti megoldhato csak nem volt olyan surun hiba hogy tobb idot raaldozzak.)
Me'g egy, nem szamolod tobbszor ha lesz egy 3-4-stb. lefedettsegu? A mintaban csak 2-es van, ott eleg az hogy mar volt es most is jott, nem kell az hogy 1x volt vagy mar tobbszor (ha ugy szamolsz ossze egybol ahogy jon). -
axioma
veterán
-
axioma
veterán
Hat nem tudom, de ezekben a problemakban ez a ket dolog szokott lenni, eleg kovetkezetes me'g indiai-angol weboldalon is a hasznalat
1. contiguous sublist/substring/subarray: valamely i<=j indexekre az [i,j] -be eso indexu elemek - ilyenkor vagy eleve az indexekkel definialjak, vagy a contiguous odakerul (tipikusan ilyenek a Fenwick-tree-t igenylo feladatok)
2. subsequence of array/list/string: kivalasztasz valahany darabot es eredeti sorrendben, a tobbieket kihagyva tekinted mint reszet a nagynak, mint itt; szoktak neha formalizalni hogy valamely k-ra 0<=i1<i2<...<ik<n indexekre Ai1,Ai2,...,Aik, ezt is irhattam volna magyarazatkent ha eszembe jut. -
axioma
veterán
Igen, kb. ennyi amit ketten osszeadtatok. Ha ures return 0, ha palindrom return 1, else return 2.
Nem rosszul specifikalt a feladat, hanem nem is akart ennel nehezebb lenni. De azert en elsore elkezdtem a rekurziv gondolkodast (persze nem kodot irni csak fejben), majd jott a homlokomra csapas
Mi lenne ha nem csak fixen 2-fajta jel lenne? Mar akar 100 hossz de mind a 26 betu eseten is vegig kene gondolni, hogyan ellenorizzuk, hogy van 26-nal kevesebb lepesu megoldas. Ott mar az se latom biztosnak hogy igaz, hogy maximalisat kell kiszedni (ami nem bovitheto, akar csak abban az ertelemben hogy azonos "kozepponttal"). Peldaul zyxyzwzz -bol az yxy jobb kivenni mint a zyxyz-t. -
axioma
veterán
-
axioma
veterán
Egy "feladvany" az interjus topik kedveert bemasolt formaban:
Given a string
sconsisting only of letters'a'and'b'. In a single step you can remove one palindromic subsequence froms.
Return the minimum number of steps to make the given string empty.
A string is a subsequence of a given string, if it is generated by deleting some characters of a given string without changing its order.
A string is called palindrome if is one that reads the same backward as well as forward.Example 1:
Input: s = "ababa"
Output: 1
Explanation: String is already palindromeExample 2:
Input: s = "abb"
Output: 2
Explanation:"abb" -> "bb" -> "". Remove palindromic subsequence"a"then"bb".Example 3:
Input: s = "baabb"
Output: 2
Explanation:"baabb" -> "b" -> "". Remove palindromic subsequence"baab"then"b".Example 4:
Input: s = ""
Output: 0Constraints:
0 <= s.length <= 1000sonly consists of letters'a'and'b' -
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)
-
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 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
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. -
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). -
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
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
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
[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... -
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
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.) -
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
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 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
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
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
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]
-
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] -
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 -
par helyen nem illek a mintaba, attol fe'lek...
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...
Ezert erdemes foglalkozni vele mert eszrevetlenul noveli az eszkoztarat [mondjuk nem hiszem h melohoz, inkabb masik feladvanymegoldashoz...]Új hozzászólás Aktív témák
- HIBÁTLAN iPhone 14 256GB Starlight -1 ÉV GARANCIA - Kártyafüggetlen, MS4678
- MacBook, Apple M1 / M2 kompatibilis dokkolók, DisplayLink 4K, USB-C, Type-C
- Új Honor X7d 128GB, Kártyafüggetlen, 1 Év Garanciával
- BESZÁMÍTÁS! GIGABYTE RTX 5080 AERO OC 16GB videokártya garanciával hibátlan működéssel
- HIBÁTLAN iPhone 15 Plus 128GB Blue -1 ÉV GARANCIA - Kártyafüggetlen, MS4504
Állásajánlatok
Cég: Laptopműhely Bt.
Város: Budapest