- iPhone topik
- Xiaomi 14T Pro - teljes a család?
- Motorola Edge 40 - jó bőr
- Egy szenzor, két zoomkamera: újraírta a Huawei a mobilfotózás történetét
- Google Pixel 9 Pro XL - hét szűk esztendő
- Google Pixel topik
- Megérkezett a Google Pixel 7 és 7 Pro
- Honor Magic7 Pro - kifinomult, költséges képalkotás
- Poco M3 - felújított állomás
- Térerő gondok, tapasztalatok
Új hozzászólás Aktív témák
-
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]
-
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 
) -
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. -
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.
-
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
Dijkstra -
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 😁
-
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. -
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
-
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.
-
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
-
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.
-
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
-
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.
-
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?
-
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. -
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.
-
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.
-
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.
-
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). -
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.
-
axioma
veterán
-
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.
-
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] -
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
-
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
-
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. -
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.) -
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]
-
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 -
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.
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.
De ez nem code golf. 
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
- Csere-Beszámítás! Asus Dual RTX 4060Ti 8GB GDDR6 Videokártya!
- Telefon felvásárlás!! Xiaomi Redmi Note 10, Xiaomi Redmi Note 10s, Xiaomi Redmi Note 10 Pro
- BESZÁMÍTÁS! Apple MacBook Air 15 M3 8GB 256GB SSD garanciával hibátlan működéssel
- Bomba ár! Lenovo ThinkPad T490 - i5-8GEN I 16GB I 256GB SSD I 14" FHD I Cam I W10 I Garancia!
- Gombászkönyvek egyben
Állásajánlatok
Cég: PC Trade Systems Kft.
Város: Szeged
Cég: Liszt Ferenc Zeneművészeti Egyetem
Város: Budapest