Informatyka UJ forum

kap00ch

Jak tam samopoczucia ? zmeczeni ? bo ja zdecydowanie tak:D

co do zadowolenia to raczej czesciowe;]
pomijam fakt ze nam skradli ;p 30minint pisania ;] ale btw wg mnie i tak kolos byl nieco za trudny...to tak obiektywnie pomijajjac moja niska wydajnosc w dzisiejszym dniu ;] Cos jednak czuje ze nie bedzie wesolo z wynikami i mam nadzieje ze TCS bedzie lagodny i da chociazby po punkciku za sam pomysl algosa , albo algosy zachlanne ktore nie do konca dzialaly ;p

tak czy siak wyglada na to ze mam na 90% 2 pelne zadanka git, jedno ze skopanym zachlanny i jedno ktore wlasnie se udowadniam czy dobrze ;] ale znajac zycie okaze sie ze jedno mam dobrze;p

no nic ide spac wiec milej nocy ;]

Fen

ja także nie jestem zadowolony... ale nie zakładałem innego toku wydarzeń...

mam jedno zadanko na pewno dobrze: Wojna... zrobiłem także Pałeczki, ale metodą zachłanną, a podobno trzeba było dynamiką... no cóż zobaczymy
w sumie jakbym miał jeszcze chwilę czasu to bym wpadł także i na rozwiązanie zadania Prom, no ale już jest po wszystkiemu...

liczę na łaskawe potraktowanie przez TCS :)

Rogal

Jak można było zrobić pałeczki (te prostsze) nlogn? I jak można było zrobić nlogn te trudniejsze?

hansu

W sumie to fajny byl nawet ten kolos :] Wszystkie 4 zadanka (5 nawet nie przeczytalem ;)) byly robialne, tylko zdecydowanie w pelne 3 godziny. Nie wiem jak Wam, ale mi braklo mniej wiecej 10-15 min na pelne zapisanie wszystkiego na czysto. Uwazam, ze troche to nie w porzadku ze nam tak czas obcieli bez zapowiadania chocby dzien wczesniej. Ale ogolnie to nie jest zle, zobaczymy jaka bedzie surowosc oceniania...

P.S. Widze ze zaloga quakemobila przoduje na forum ;)

EDIT: I dupa z przodowania, lamka sie wbila :P

@Rogal: kecim mowil ze oba zadania o paleczkach maja wzorcowki kwadratowe...

Stasiu

nie wiem, ja paleczki (te prostsze) mam n^3 ale jeszcze nie wiem czy poprawnie ;) mam tez oba zachlanne i licze na to ze sa dobrze zrobione (poza glupim bledem w Wojnie gdzie nie wskazalem w ktorej zmiennej trzymam wynik :/ ) Jakby bylo te 30/45 min wiecej to pokminilbym jeszcze 4 zadanie i pewnie cos bym napisal. No ale czekam na wyniki... TCS zweryfikuje moja pewnosc siebie ;)

Rogal

@hansu: Nie wiem jaka jest wzorcówka, słyszałem, że Mateo zrobił to jakoś nlogn i chciałbym się dowiedzieć jak bo mi się to za ch... nie składa do takiego algorytmu. Inna rzecz, że ogólnie nie jestem dzisiaj dysponowany do myślenia.

Spectro

Za dużo zadań na myślenie. Część z was pewnie potrafi szybko wymyślać rozwiązania - ja nie :/ . Gdyby było 5h, to mógłbym sobie poradzić ze wszystkimi zadaniami, choć z możliwymi drobnymi błędami. Nieprzypadkowo tyle czasu jest na Olimpiadzie Informatycznej czy UZI.

No to odtworzyłem 2 zadania, które przepuściłem przez Playgrounda ;] . I okazało się, że istnieje asymptotycznie lepszy algorytm niż pierwszy, a drugi da się inaczej zrobić niż na drzewach (znaczy się: wiedziałem, że można zadanie 3. zrobić inaczej niż na drzewach, ale nie potrafiłem tego wymyśleć).

Madras

A ja zrobiłem wszystkie obowiązkowe, piąte zacząłem, coś naskrobałem, ale chyba punktów za to nie będzie ;].

ostoj

a ja powiem tyle, ze http://www.matinfuj.fora.pl/viewtopic.php?p=21608#21608

mateo

jagm

hehe, wiedzialem, ze cos jest nie tak w tym Twoim algorytmie :P

Madras

Czyli tylko ja tego kolosa nie spieprzyłem?

kafex

Cóż fortuna nie była dziś po mojej stronie :] podszedłem źle taktycznie a potem już tylko nadrabiałem co sie dało :P

kg86

mi tez chujowo poszlo, zrobilem tylko 2 zadania :P za dlugo myslalem na Paleczkami :P
dlatego trzeba to zapic :D

aaa

[deleted]

hansu

Rogal

mówisz masz

Skrobocik

Heh, ja zrobiłem trzecie i czwarte na pewno na maksa (tak sądzę i będę się tej wersji trzymał ;) ), troszkę za późno zawymysliłem metodę na pałeczki (zachłanną) i nie zdążyłem jej do końca zapisać......ale złożoności podałem :D
Promu jakoś nie zobaczyłem :?

Szkoda tylko, że pierwsze pół godziny, w porywach do godziny przebąkałem :?

hansu

Skrobocik

aaa

[deleted2]

jagm

hm. no to jeśli mamy pałeczki
1 3 4 6 16, to jak działa ten algos? bo wydaje mi się, że da coś takiego:
różnice: 2 1 2 10
po posortowaniu: 1 2 2 10
bierzemy 1, oznaczamy, że 2 i 2 nie możemy wziąć i bierzemy 10.

dobrze myślę?
w takim razie nie działa ;]

aaa

[deleted3]

Madras

Zachłanne rozwiązanie nie działa:

N=2 K=6

1 20 25 26 30 50

Algorytm zachłanny weźmie pałeczki 26-25, a potem będzie musiał wybrać 20-1. A jak widać w tym przypadku optymalne jest 25-20 i 30-26.

jagm