Új hozzászólás Aktív témák
-
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.
-
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
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.
-
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.
-
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
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).
-
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 ]
-
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 ]
-
-
-
-
-
-
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
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
-
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
-
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
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... -
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
-
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
Új hozzászólás Aktív témák
- Milyen belső merevlemezt vegyek?
- AMD GPU-k jövője - amit tudni vélünk
- Adobe Photoshop
- AMD K6-III, és minden ami RETRO - Oldschool tuning
- Autós topik
- Mini-ITX
- Motorola Moto G24 Power - hol van az erő?
- Otthonfelújítási program (2024.)
- Escape from Tarkov
- eBay-es kütyük kis pénzért
- További aktív témák...