Fórum: Informatika kömal

akkor ugye az elfogadható, ha az tgz kiterjesztést átírtam gz-re?

Igen, valóban van O(N+Q)-as algoritmus is: http://en.wikipedia.org/wiki/Lowest_common_ancestor

S66-ot nem ismertem, én találtam ki hozzá az algoritmust. (Nem azt állítom, hogy a világon elsőként, csak hogy nem ismertem előtte.)

És csak egy sejtés: Nem lehet a feladatot O(N)+O(Q) idő alatt megoldani? Szerintem igen, de ez csak sejtés, mert O(Q)+O(Nlog N)-es megoldást adtam, az időkorláthoz az is elég volt.

Bocsánat, valóban értelmesebb lett volna .tgz kiterjesztéssel kérni a tömörített állományokat.

I274. A triviális megoldást tették fel, ami 8 pontot ért. Miért nem láthattunk egy 10 pontos megoldást (9 darab is volt belőle)?

Visszatérve az S jelűekhez: (lejárt) S66. megoldható O((N+Q)*log(N)) időben. Ez is halálismert feladat volt.

Igen, én is ezen agyalok, hogy akkor i279.tgz, vagy i279.gz, vagy i279.tar.gz néven küldjem be. Nem szeretnék egy ilyenen elhasalni, és bukni jópár pontot.

Abban igazad van, hogy a gzip nem csomagol, csak tömörít, (esetleg egymás után ír).

Ha info szerkesztő lennék, és több fájlt várnék összecsomagolva és gzippelve, akkor inkább "i279.tar.gz" vagy "i279.tgz" néven kérném a fájlt.

Az i279-es feladatban, az i279.gz fájlban ha egy tar fájlt tárolok, az gond? Csak mert a gzip csak egy fájlt képes tömöríteni.

A képet meg szeretnénk nézni, ezért egy billentyű lenyomása után záródjon be.

Valamit grafikus felülethez ugyan ez a kérdésem. Azonnal záródjon be, vagy egy billentyűlenyomásra, vagy x idő múlva?

Sziasztok!

Az i277-es feladatban, a program ahogy kirajzolta a képet, azonnal záródjon is be, vagy egy billentyűlenyomáskor záródjon be?

Köszi

Igen.

S66-ban feltehetjük-e, hogy a házakat 0-tól N-1-ig számozzuk?

Az, hogy egy feladat ismert, még nem jelenti, hogy könnyű is. Sőt, sokszor épp az ellenkezője; a sudoku szerintem pont ilyen.

OK, bár annak nem látom sok értelmét, hogy ismert feladatokat tűznek ki, mondjuk ez I jelű feladat volt, de S-ben is volt teljesen ismert probléma, mondjuk a sudoku.

A probléma spec. esete annak, amikor egész számok vannak a téglalapba írva, és keressük azt a téglalapot, amiben a számok összege a legnagyobb. Magasabb dimenzióban is láttam már kitűzve ezt a feladatot, nincs nagy újdonság benne, csak többet kell írni.

De d=2 dimenzióban is érdekes a feladat, nem ismert a bonyolultsága, nyilván n² művelet kell, de O(n³)-nél van gyorsabb algoritmus is. Talán -es, nem emlékszem.

Egy másik már érdekesebb általánosítás, amikor nem egy téglalapba, hanem egy tóruszra írjuk az egész számokat, és keressük a téglalapot amiben a számok összege a legnagyobb.

Nem is írta senki, hogy azt kell implementálni. (Remélem legalábbis, hogy nem, mert a ,,halálismert'' változatot csináltam.)

I274. Amit második megoldásnak írtok az egy O(n²*m²)-es algoritmus. De van O(n*m*min(n,m))-es megoldás is. Igazából halálismert.

A tiétek nem is hinném, hogy n=m=500 esetén lefutna egy perc alatt a gépeteken.

Igen, így már helyes a kód.

Egyébként tree[i] méretére helyes volt az n>>i. Egy bizonyítás erre: 2-hatványok összeadása miatt látható, hogy pos=u*2ⁱ-1 valamilyen u égeszre, így pos2=w*2ⁱ-1 is teljesül, de akkor pos2>>i=w-1 és n>pos2=w*2ⁱ-1 miatt (n>>i)w, kettőt összerakva (pos2>>i)<(n>>i). Talán emiatt is célszerű pos=-1-ről indulni, hogy tree[i] mérete n>>i legyen.

Ezt azért nem nevezném interval tree-nek. Amit írsz, az valójában teljesen analóg a versenyző által készített megoldással, annyi különbséggel, hogy te csak a bináris fa leveleiben "tárolsz" elemeket, illetve egy tömböt indexelsz ügyesen ahelyett, hogy külön objektumok lennének a csúcsok.

Mindenesetre ha már lekódoltad, kirakom ezt is megoldásnak, köszönjük! (Annyit módosítottam rajta, hogy a szükséges méretű tömböket foglalja le dinamikusan, ne pedig eggyel rövidebbet, mert így gyakran elszállt. Remélem, most már jó.)

Olvasva a hivatalos megoldást az S64. feladatra nekem úgy tűnt, hogy a kiírók nem ismerik az interval tree-t. Nem mellesleg sokkal egyszerűbb kódot kapunk vele, mint a feltett max. 10 pontos kód.

Megoldásom itt van: http://ideone.com/ay5q3

Az S.64. javítása épp most készült el, már ki is került.

Egyébként ugyanaz a javítási határidő/időköz, mint a többi pontversenyben: igyekszünk a következő feladat határideje előttre kijavítani, de ez nem mindig sikerül.

Szaisztok! Csak annyit szeretnék kérdezni, hogy az informatika feladatokat milyen időközönként/határidővel javítják? Hamarosan az októberi forduló beküldési határideje is lejár, de még a szeptemberi feladatok sincsenek javítva... remélem, nem költözött el az e-munkafüzet...?

Köszi a válaszokat!

Kérdés visszavonva.

Az S.65. feladattal kapcsolatban szeretném megkérdezni, hogy a második és harmadik példában biztosan helyes-e a megadott kimenet.

A feladatban leírt feltételeket/korlátokat egyfajta szerződésként tekintsd: mi garantáljuk, hogy csak ennek eleget tevő -- helyes -- bemenetekkel hívjuk meg a megoldásod, te pedig (a maximális pontszámért) garantálod, hogy a helyes bemenetekre hiba nélkül lefut és helyes választ ad a programod. (Illegális bemenetre akár el is szállhat, itt ez nem érdekes.)

Tehát ellenőrzést semmiképpen ne végezz, viszont bizonyosodj meg alaposan, hogy minden (a feladat szövege által nem kizárt) speciális esetet lekezeltél.