Hirdetés
- Akciófigyelő - Epic Store ajándékozás 6. nap: Dredge
- 2024 - Békés, boldog karácsonyt kívánunk minden olvasónknak!
- Akciófigyelő - Epic Store ajándékozás Dark and Darker: Legendary Status
- Jövőre érkezik az új Agatha Christie: Death on the Nile játék
- Alig két nap múlva konzolokra is befut a Star Trek Legends
Új hozzászólás Aktív témák
-
sztanozs
veterán
Koszi a linkelest, a Programozas topikban.
Ha mar feladvanyok, akkor az egyik altalam kovetett Discord szerveren vannak heti python feladvanyok (altalaban pofonegyszeruek, szoval csak a tanuloknak erdekesek inkabb):
https://discord.com/invite/twt[ Szerkesztve ]
JOGI NYILATKOZAT: A bejegyzéseim és hozzászólásaim a személyes véleményemet tükrözik; ezek nem tekinthetők a munkáltatóm hivatalos állásfoglalásának...
-
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)[ Szerkesztve ]
-
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. -
DopeBob
addikt
Nálam sajnos beütött a covid... talán most már jövök kifelé belőle. Még meg sem néztem, miről maradtam le, de lehet, hogy jobb is, elég nehezek voltak már a feladatok nekem így a vége felé. Majd megpróbálom valamikor befejezni.
Nagyon tetszettek a feladatok, nagyon jópofák voltak, jövőre mindenképpen jövök már a kezdésre
Gratulálok Nektek, látom sikerült végig megcsinálni mindent
MZ/X
-
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 ;-)
-
dabadab
titán
Köszi, a verseny motivált a koránkelésben
SPOILER
Én csak a kockák* koordinátapárjait tároltam el, abból is csak a bekapcsolósakat, illetve az újonnan beolvasott kockák tárolásánál mindig megnéztem, hogy az új kocka átfedésben van-e már az eltároltakkal és amelyikkel igen, azt szétszedtem több kockára úgy, hogy az átfedésben lévő rész ne legyen benne.
*: igen, téglatestek
[ Szerkesztve ]
DRM is theft
-
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. -
dabadab
titán
Ez a kockakapcsolgatós?
A B feladat nálam gyakorlatilag instant lefutott (a time olyan 0,06 másodperc körüli értékeket adott). Hogy csináltad?
Ami nálam sokáig futott, az a 23-i folyosós-szobás rákok voltak, az A az elsőre úgy 40 perc alatt köpte ki az eredményt (aztán reszeltem rajta és akkor ez lement úgy két másodpercre), a B-vel meg ez a reszelt változat megint úgy 50 percet elszöszölt, viszont rossz (a kelleténél alacsonyabb) eredményt adott és ekkor merült fel benne, hogy lehet, hogy rendesen végig kellene olvasni a feladatot
(és ekkor persze kiderült, hogy a mozgás szabályai sokkal kevesebbet engednek meg, mint ami egy gyors átfutás után megmaradt a fejemben).És most látom, hogy mindketten sikeresen befejeztük a kalendáriumt - ez jó móka volt, ismét köszi, hogy szóltál!
[ Szerkesztve ]
DRM is theft
-
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
-
dabadab
titán
Én ismerem magam meg az elírási hajlandóságomat
, eleve meg se próbáltam kézzel megcsinálni, legenerálom mind a 64 lehetséges forgatási mátrixot abból meg a 24 különbözőt (ez tulajdonképpen egy lépés, egy setbe pakolom őket) és azzal vitézkedek a továbbiakban.
Mondjuk így utólag sokat gyorsított volna a dolgokon, ha nem saját magam írom meg a vektorokat meg a mátrixokat, hanem vmi libraryt használok.DRM is theft
-
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. -
dabadab
titán
Én tisztán fával csináltam meg, a bal/jobboldali szomszéd levél megkeresése szerintem nem olyan feladat, ami indokolná, hogy az ember listába szervezzze őket.
Viszont az feltűnő, hogy azért egyre durvább feladatok vannak, ahogy elnézem, ez a mai szkenneres is egy nagyobb faladat.
DRM is theft
-
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.[ Szerkesztve ]
-
-
dabadab
titán
De kell hozza egy prisor
Az egy nagyon jó implementációs fogás, de magához az algoritmushoz igazából nem kell, ahogy azt DopeBob példája is mutatja
Sőt, én is pont azt csináltam, amit ő (C++-ban, C stílusú tömbökkel még így is elfogadható sebességet produkált, bár a B rész eltartott pár percig). Most megcsináltam egy majdnem-prisorral (egy pozíció-risk map a potenciális csomópontokkal), az így ránézésre legalább egy nagyságrenddel gyorsította a futást és a kód hossza se változott.DRM is theft
-
DopeBob
addikt
Köszi, tegnap néztem róla YT-n videókat, tényleg egyszerű maga az algoritmus. Lekódolni már nem volt annyira az, de működik.
Sikerült is vele megoldani a tegnapi első részét, majd megcsinálom a másodikat is.
Már tudom melyik a lassú része, kell hozzá csinálnom egy listát, hogy ne kelljene mindig végignézni az összes csomópontot, hogy melyik a legkisebb.
Ez a mai viszont...
egyre magasabb szintekre jutok önsanyargatásban, ez már valami 4 óra volt, mire kész lett de ezeket a típusú feladatokat jobban élvezem, mint pl a tegnapit.Igyekeztem szép kódot írni, nem rövid, de így könnyen olvasható volt nekem. [link]
[ Szerkesztve ]
MZ/X
-
dabadab
titán
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).
Megcsináltam dijsktrával, maga a lényegi részt csináló függvény (tehát a betöltés meg ilyenek nincsenek benne, hanem előkészítve megkapja az adatot és kiköpi az eredményt) nekem 36 sor lett C++-ban, az Pythonban (a zárójelezés miatt) 28 sor és az olvashatóság miatt ebben van három üres sor is, szóval 25 sornál vagyok
, vagyis kódban ez sem igazán több (mondjuk nem csoda, a dijsktra tényleg nagyon egyszerű logikával működik, saját bevallása szerint húsz perc alatt találta ki, amíg a barátnőjére várt shoppingolás közben )DRM is theft
-
dabadab
titán
Szerintem a Dijkstra mehet az első helyre (szerintem van elég egyszerű ahhoz, hogy ne legyen értelme saját megoldáson töprengeni), a többi meg igazán nem is kell.
Én egyébként nekiálltam tisztán brute force-szal (miszerint végigpróbálni az összes lehetséges útvonalat), de az már a példa 10x10-es mátrixával sem végzett azelőtt, hogy meguntam volna várni rá
, aztán közbejött minden más, de most az ebéd utáni sziesztában nekiállok megcsinálni rendesen.[ Szerkesztve ]
DRM is theft
-
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.
[ Szerkesztve ]
-
DopeBob
addikt
Hát ez a két útkeresős kifog rajtam.
Annyi segítséget kérnék, hogy ezeket a témaköröket szedtem össze, amik kellhetnek az ehhez hasonló feladatok megoldásához, jó ez a sorrend?
Single linked lists
Stack & Queues
Binary search trees
Tree traversal
Binary heaps
Graphs
Graph traversal
DijkstraMZ/X
-
DopeBob
addikt
Koszi, egyelore nem kell egyik sem. Redditen is csak a memeket nezem meg. Eddig ezt leszamitva ossze tudtam szenvedni oket, nekem eleg nehezek, joberzrs mikor vegre sikerul. Ha lesz egy szabad oram nekiallok. Elso korben ugy ahogy a tobbinek, megprobalok kitalalni egy mukodo megoldast egyedul, akkor is ha van ra kesz jol bejaratott algo.
Biztos nem szep, de a grafot tudom abrazolni 2d-s tombkent, indexek a csomopontok, es mondjuk egy jeloli, ha ket csomopont kozott van ut.
Talan utana jobban megertem a normalis adatszerkezeteket es algoritmusokat, mar kb ket oldalnyi temakort irtam ossze amit at kellene nezni 😁
[ Szerkesztve ]
MZ/X
-
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. -
DopeBob
addikt
Ha lesz egy kis időm megpróbálom valahogy megoldani.
Sajnos hétvégén nem nagyon volt időm, de ma megcsináltam a d13, ez nagyon tetszett és egyszerű is volt, aztán jött a d14... így a halason megedződve, már neki se álltam stringeket gyártani, gondoltam, hogy megint megszívnám a p2-ben.
Elég hamar (
na jó, egy óra) kitaláltam, hogy tudom megoldani, hogy egy objektumban tárolom az párokat és a darabszámokat, egy másikhoz pedig mindig hozzáadom a párok közé aktuálisan beszúrt betűket, aztán 2 órán át néztük egymást hogy miért nem jó...Mikor az aktuális párokból legeneráltattam az új párokat, akkor sima inkrementálást használtam, ahelyett, hogy azt adtam volna hozzá, ahány darab volt belőle.
Lehet kéne tartani egy kis szünetet már.MZ/X
-
DopeBob
addikt
Ah, értem, köszi. Kijavítom akkor úgy, hogy amíg nyitó jelek jönnek, azokat pakolom egy tömb végére, ha záró, akkor megnézem, hogy az van e tömb végén, ha igen, akkor kitörlöm, ha nem akkor megvan a hiba. Így talán logikusabb is lesz, mint ez a törlés és visszalépkedés.
Köszi a sok segítséget
MZ/X
-
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.
[ Szerkesztve ]
-
DopeBob
addikt
Hát ezt még emésztem
const errorScores = {
')': 3,
']': 57,
'}': 1197,
'>': 25137
}
const autoCompScores = {
'(': 1,
'[': 2,
'{': 3,
'<': 4
}
const pairs = {
')': '(',
']': '[',
'}': '{',
'>': '<'
}
let syntaxtErrorScore = 0;
const autoCompleteScores = [];
sampleData.forEach((line) => {
let i = 0;
let valid = true;
while (i<line.length && valid) {
if (pairs.hasOwnProperty(line[i])) {
if (line[i-1] === pairs[line[i]]) {
line = line.slice(0,i-1) + line.slice(i+1)
i-=2;
} else {
valid = false;
syntaxtErrorScore+=errorScores[line[i]]
}
}
if (i === line.length-1 && !pairs.hasOwnProperty[line[i]]) {
let autoCompleteScore = 0;
for(let i = line.length-1; i>=0;i--) {
autoCompleteScore = autoCompleteScore * 5 + autoCompScores[line[i]];
}
autoCompleteScores.push(autoCompleteScore)
}
i++
}
})A mait így tudtam megcsinálni. Megkeresem az első 'bezáró' jelet, ha előtte a párja van, akkor törlöm őket visszalépek a törlés előtti pozira és megyek tovább, ha nem akkor az a bezárójel az érvénytelen.
Innen a második rész már csak annyi volt, ha nem volt érvénytelen és nyitó jel van a végén, akkor ezt a maradék stringet lepontozom hátulról előre
[ Szerkesztve ]
MZ/X
-
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.
[ Szerkesztve ]
-
DopeBob
addikt
Hát ennél a mainál eléggé megizzasztott a part1
második rész ahhoz képest már csak 3 perc volt.Ha kérdezgethetek még, a tegnapinak (d9:p2) mi a szép megoldása? Első részből megvannak a minimumpontok koordinátái. Első körben megnézem ennek a pontnak melyik szomszédja ami értékben 1-el nagyobb és nem 9, ezeket elmentem egy tömbben. Utána ezen a tömbön végig megyek, és minden koordinátára megnézem ugyan ezt, az eredmény tömböt ennek a tömbnek a végéhez adom. Itt van bőven ismétlődés. Ha elérek a végére, akkor nem volt már ilyen újabb szomszéd, összeszámolom hány különböző elem volt.
Nekem szerencsére, eddig inkább logikai feladatok voltak, és minimális prog és algo ismerettel lehet őket abszolválni, persze a kódomat nem mutatnám meg szívesen senkinek
[ Szerkesztve ]
MZ/X
-
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. -
DopeBob
addikt
Igen.
Kéne ide is spoiler tag
hátha valaki még csinálja.Én úgy indultam el, hogy az eredeti és az összekevert szegmenseket megfeleltetem egymásnak. Pl, (1->7 megvan az 'a' utána 4+'a' szegmens->megvan a 'g' (4 és 9 különbsége), 8 és 9 különbsége, megvan az 'e') stb. és utána erre írtam programot, ami végigmegy így sorban a szabályaimon és megkeresi az összes szegmens helyét.
De azóta eszembe jutott egy egyszerűbb megoldás, pl azok a szegmensek, amik az 1-ben és a 7-ben is megvannak, az 5 szegmenses számok közül csak a 3. ra igaz. Azok amik a 4-ben vannak a 6 szegmensesek közül csak a 9-re igaz, stb.
[ Szerkesztve ]
MZ/X
-
dabadab
titán
Sikerült valami olyan megoldást találni, ami kidobja, hogy melyik szegmensnek melyiknek kellene lennie?
Mert nekem arra sikerült csak jutnom, hogy vannak szabályaim (ezekhez elég volt a sorok bal oldaláról a hat legrövidebb string - nem hiszem, hogy ennél kevesebből ki lehetne találni) és ezeken végigpróbálgatom a betűket, ami azért nem olyan nagyon elegáns.
DopeBob: te vagy vendash a leaderboardon?
[ Szerkesztve ]
DRM is theft
-
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.[ Szerkesztve ]
-
DopeBob
addikt
Szia,
kész a mai, de hiányérzetem van. Van annál jobb megoldás, mint hogy minimumtól maximumig az összes lehetséges pozícióra kiszámolom a fogyasztást és megjegyzem a legkisebbet?
Így a tegnapi után, attól féltem a part2-re majd nem lesz jó ez a favágó módszer, de nem tudom, hogy lehetne máshogy.
MZ/X
-
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.
[ Szerkesztve ]
-
DopeBob
addikt
{
if (x1 < x2 && y1 < y2) {
for (let i = x1; i<= x2; i++) {
ventMap[y1+(i-x1)][i] += 1;
}
}
else if (x1 > x2 && y1<y2) {
for (let i = x2; i<=x1;i++) {
ventMap[y2-(i-x2)][i] += 1;
}
}
else if (x1 < x2 && y1 > y2) {
for (let i = x1; i<=x2;i++) {
ventMap[y1-(i-x1)][i] += 1;
}
}
else if (x1>x2 && y1>y2) {
for (let i = x2; i<=x1;i++) {
ventMap[y2+(i-x2)][i] += 1;
}
}
}Ez a diagonal rész, lehet, hogy van jobb megoldás, x tengelyen mindig növekvő sorrendben jönnek a koordináták iránytól függetlenül.
Ez javascript nincs rendes 2d array, csak azért vannak felcserélve a koordináták tömbbe írásnál, hogy kirajzolva jó legyen, de igazából mindegy.
[ Szerkesztve ]
MZ/X
-
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.
[ Szerkesztve ]
-
-
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).[ Szerkesztve ]
-
DopeBob
addikt
Igen, a maira sikerült rájönni, az első pár "out-of-memory" után
Még este "friss" fejjel megnézem újra a tegnapit, hogy mi a bibi vele.
Diagonálnál úgy csináltam, hogy mint a négy variációt lefedtem, és demo adatokkal jól működik, illetve ami a feladat leírásban benne van 10 koordináta az is jó, stimmel a rajz és az eredmény is.
[ Szerkesztve ]
MZ/X
-
axioma
veterán
[Ja ujraolvasva ugy tunik megoldottad a mai part2-t, akkor nem spoilerezek.]
A tegnapinal mind a 4 diagonalis iranyt jol feded le, vagy normalsz arra hogy pl. x-ben a kisebb legyen az elso? Tedd be a kodot aztan megtalaljuk hogy mi a problema (remelhetoleg).[ Szerkesztve ]
-
DopeBob
addikt
AdventOfCode:
Hát, ez a mai (day6) azért eléggé megizzasztott már
. Sajnos elég korlátozott az "eszköztáram". Viszont örülök, hogy sikerült kitalálnom, hogy lehet megcsinálni a part2-t, nyilván for ciklussal csináltam meg az első részt, aztán jött a pofára esés.Tegnapinak a 2. részét viszont félretettem, a part2 ott nem megy, ha a feladatkiírásokban lévő adatokat használom, ugyan az az eredmény jön ki, ha kirajzoltatom a térképet, az is stimmel, de ha a tényleges adatokkal számolok, nem jó az eredmény és nem jövök rá miért.
Talán az "örökös újrakezdő" a legjobb kifejezés rám, nem fejlesztőként dolgozom (sima it support), és ahogy időm engedi, próbálom ezt megtanulni, de elég nehezen megy, munka, család, gyerek mellett. Kb fősuli óta bennem van a kétely, hogy nem lennék elég jó hozzá, így már ott elengedtem a dolgot, és nem mentem sw fejlesztés szakirányra. Aztán mikor van egy ilyen kis minimális sikerélményem, akkor újra lelkes leszek, egy darabig foglalkozom vele, aztán 1-2 évre megint feledésbe merül a dolog.
[ Szerkesztve ]
MZ/X
-
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.[ Szerkesztve ]
-
-
axioma
veterán
-
-
bambano
titá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'[ Szerkesztve ]
-
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 ]
-
-
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] -
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
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
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
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...[ Szerkesztve ]
-
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. -
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
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
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
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].
-
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
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]
[ 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
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 ]
-
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
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.
par helyen nem illek a mintaba, attol fe'lek...
egyre magasabb szintekre jutok önsanyargatásban, ez már valami 4 óra volt, mire kész lett 
Hogy kapcsolódjon valahogy az Odin Projekthez, csináltam hozzá egy kis UI-t. 
Új hozzászólás Aktív témák
Hirdetés
Állásajánlatok
Cég: PCMENTOR SZERVIZ KFT.
Város: Budapest