Informatyka UJ forum

Rogal

W ramach wprawki wrzucam linki do kilku zadań, które rozwiązywałem dynamicznie / zachłannie. Enjoy.

[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]
[link widoczny dla zalogowanych]

dzendras

Dzięki Rogal!

kap00ch

[link widoczny dla zalogowanych] - zapraszam...

chlebek

Fidel

zadanie z kolokwium z zeszlego roku podobno:

polduzne ciasto podzielone jest na n nierownych kawalkow gdzie n jest parzyste. dwie osoby chca zjesc ciasto w tym celu jedna naprzemian naklada kawalki na swoj talerz i na talerz drugiej osoby. osoba nakladajaca wybiera kawalek na lewym lub prawym koncu. osoba ta najpierw naklada na swoj talerz i chce zjesc jak najwiecej, podaj ile moze zjesc. oczekiwana zlozonosc O(n^2)

kto mi powie albo znajdzie kontrprzyklad dlaczego tego nie mozna zrobic zachlannie biorac z kawalkow brzegowych dla siebie wiekszy dla drugiej osoby mniejszy?

tak poza tym 4 zadania sa tutaj
[link widoczny dla zalogowanych]

kap00ch

@Fidel - wg mnie to wlasnie jest taki zachlanny ;]

r4ku

[link widoczny dla zalogowanych]

2 poprzednie kolosy + rozwiazania do pierwszego.

Fidel

r4ku

bo zakladamy ze nasza strategia to zjesc jak najwiecej, a strategia przeciwnika to zjesc jak najmniej (wszak my sie o to postaramy nakladajac ciasto:))

Drakk

11 10 10 1 1 1 1 10 - kontrprzyklad

kap00ch

eeee? jaki kontrprzyklad:d przeciez biore dla siebie ciagle najwikesze a dla tamtego najmniejsze:O

EDIT: zobaczylem rozwiaania i ja chyba nie rozumiem tresci bo dla mnie 3 dalej mozna robic tak prosto zachlannie...

Drakk

z brzegowych bierzesz ciagle najwieksze czyli dla siebie 11 a dla niego 10 i sie sypie a moglbys wziac 10 i dla niego 1 - nie bierzesz tych kawalkow rownoczesnie tylko na zminae i po wziecu odslana ci sie kolejny kawalek ciasta

Fidel

kap00ch

dobra juz rozumiem....zmeczony jestem...moj blad ;]

EDIT: musze przyznac ze rozwiazania TCSu sa...no...pezyznam fajne :P

EDIT2: btw czy w 4 wg was wariant z tym ze kazdy gra na wlasna reke dawalby oczekiwany rezultat dla pierwszego jedzacego taki jak gdyby obaj sie skumali przeciwko nam? pytam bo jak to rozkminialem to wlasnie rozwalilem taki wariant ;pi teraz mnie to ciekawi:d

Rogal

Kap00ch: Nie. Jeden z nich może działać jako kamikadze i swoim kosztem podkładać najlepsze kawałki drugiemu kolesiowi.

r4ku

w zad 3. mi nie chodzilo ze bierzemy tak na chama dla siebie najwieksze a dla przeciwnika najmniejsze, ale jesli mamy tablice:
T[i,j] - maksymalna ilosc ciasta jaka mozemy zjesc od kawalka i do j
M[i,j] - minimalna ilosc ciasta jaka mozemy zjesc od i do j

to:
T[i,j]=max(Ci+ suma-M[i+1,j],Cj+suma-M[i,j-1])
M[i,j]=min(Ci+suma-T[i+1,j],Cj+suma-T[i,j-1])

edit:
proboje znalezc cos na pizze z kolosa2 i widze tylko n^3:/ ale intuicja podpowiada mi ze mozna to pojechac n^2. czy ktos wie jak? kecim mowil dzis ze bardzo latwo przerobic rozwiazanie ciagle na takie okragle, ale jak to sie robi?

mateo

r4ku

@mateo: dzieki, za cholere nie moglem tego dostrzec i probowalem przerobic tablice trojkatna, taka jak mielismy w ciescie a wtedy wychodzilo n*ciasto po prostu... juz jestem zbyt zmeczony zeby racjonalnie myslec... teraz moze pomoc tylko sen...

exeman

Rogal, jaka ma byc zlozonosc w [link widoczny dla zalogowanych] I czy da sie to zrobic zachlannie? Ja to chyba zrobilem zachlannie w n^2, ale nie wiem czy poprawnie.

Moze ma ktos jakis kontrprzyklda dla mojego rozumowania? :P

kap00ch

@exeman - to byl chyba dynamik n^2

hansu

Zadanie trzecie (o ciescie). Moglby ktos obalic wzor:

T[i,j] = max [(T[i+2,j] + C[i]) , (T[i,j-2] + C[j]) , (T[i+1,j-1] + max(C[i],C[j])]

Czyli chodzi o to ze w kazdym kroku rozpatrujemy co jest dla nas najlepsze: Wziecie dla siebie z prawej i nastepnego z prawej dla oppa, to samo z lewej, czy dla nas z jednej, dla oppa z drugiej.

Rogal

kg86

zadanko z zeszlorocznego ASD2:

kg86

@rogal - czy to zadanie RENT nie sprowadza sie do znajdowania maksymalnego wypelnienia sali zajeciami, z tym ze, zamiast dlugosci zajec beda ceny wynajmu samolotow w danym czasie? :)