Informatyka UJ forum

Rogal

No i nie zdążyłem raków :?

Madras

A jak słowa? Bo moje zachłanne dostały 2 punkty. Pole nlogn 9 punktów. Zawsze coś, może mi zapewnić koszulkę ;).
BTW Mateo gratulacje, i powodzenia. Dokop TCSowcom :twisted:.

Rogal

@Madras:

Moje pole liniowe dostało chyba 6pkt. Gdzieś zmienna wychodziła poza zakres dla dużych zestawów :( . A specjalnie o tym pomyślałem i używałem long long'a do zapamiętywania wyników. Jakoś tak z obliczeń mi wynikało, że taki rozmiar w zupełności wystarczy.

btw. wie ktoś jak wypisać long long'a printf'em?

A co do słów to moje dynamiczne dostały 5, ale poprawności jak zwykle bozia poskąpiła. Z tym, że tutaj to raczej nie chodzi o szczegóły, a po prostu cały algorytm był do bani.

O rakach to się nawet wypowiadał nie będę. Trzeba mi było chodziaż bruta wysłać, pewnie 2-3 pkt. bym dostał :D A tak okrągłe 0.

@Mateo:
Gratulacje, trzymam za Ciebie kciuki w dalszej fazie. A mógłbyś jeszcze wytłumaczyć na czym polegał twój algorytm ze słowami?

A jeszcze apropo tych obecnych 4 zadań, to na pierwszy rzut oka 2 z nich wyglądają na banalne, 1 na do-przełknięcia i 1 na NPC :lol: - czyli (biorąc pod uwagę że są 2 dni) na prostsze niż ostatnio. To dla mnie w sumie niespodzianka :shock:

mateo

Rogal

Zacząłem kminić mrówki. Najpierw trochę myślałem, potem zrobiłem jakiegoś bruta żeby mi liczył początkowe wartości. Znalazłem jakieś zależności. Z tych zależności jakieś kolejne zależności.... Bynajmniej całkiem ciekawe. Ale dalej nie widzę sposobu żeby to zrobić szybciej niż liniowo względem ilości ścieżek :cry: Może rano mnie oświeci :wink:

mateo

Mrowki sa bardzo proste... tzn dopiero potem sie o tym dowiedzialem :) bo sam zrobilem tak zamotanym sposobem ze masakra. Wykminilem rozne wzory rekurencyjne no a majac wzor rekurencyjny mozna latwo zrobic tak zeby obliczac n-ty wyraz takiego ciagu w czasie (lgn)^2... Wystarczy bowiem obliczyc wszystkie wyrazy postaci 2^k - a kazdy taki wyraz mozemy policzyc w czasie conajwyzej lgn. A majac policzone juz takie wyrazy tego ciagu mozemy potem dla dowolnego n obliczyc w czasie conajwyzej (lgn)^2 n-ty wyraz tego ciagu. No i ja wlasnie tak to mam zrobione. Z tym ze to zadanie da sie zrobic tak ze tworzymy sobei macierz reprezentujaca ten graf i podnosimy ja do potegi rownej dlugosci sciezki i po sprawie :D. Latwo mozna sprawdzic ze to dziala.

Rogal

Rzućże prosze tym wzorem na liczenie n-tego wyrazu w czasie (lgn)^2...

Ja w tym zadaniu doszedłem do wzoru x(n)=-(x(n-1)+2*x(n-2)) i nic dalej nie mogłem z tym zrobić...

A świątynie jak robiłeś? Dijkstra(przeszła?)? Czy można było jakoś szybciej?

mateo

Tak na wstepie to powiem ze piszac tego posta sobei liczylem dokladnei ta zlozonosc i mi wyszlo jednak ze ta zlozonosc jest troche inna:
samo obliczanie n-tego wyrazu odbywa sie w czasie lgn*(lgn + D)*D, lecz stworzenie strktury umozliwiajacej to zajmuje czas ((lgn)^2)*(lgn + D)*(D^2), gdzie D to ilosc wyrazow we wzorze rekurencyjnym potrzebnych do obliczenia wyrazu n-tego...
-------------------------------------------------------------------------------------

Ja w moim rozwiazaniu mialem 6 wzorow :) tzn pierwszy wzor byl rekurencyjny wzgledem siebie a 5 pozostalych odwolywalo sie do pewnych wartosci pierwszego wzoru.... a ten pierwszy mialem postaci: a(n) = a(n - 2) + 8*a(n - 4) + 16*a(n - 8 ), gdzie a(0) = 1/2, a(2) = 0, a(4) = 2; Juz nie pametam skad mi to wyszlo ale wiem ze dziala :D.... No ale sama postac wzoru jest w sume niewazna...

Rogal

Mateo jesteś wielki 8)

Madras

256 madras 65
Mam wyczucie 8).
Dla niezorientowanych - koszulki otrzymuje pierwsze 256 miejsc 8).

ostoj

a tak mnie ciekawi.... napisali ze pierwsze 256 osob ma mozliwosc podjecia pracy w adb w ciagu najblizszych 2 lat. caly ich oddzial polski zatrudnia 320 osob. wiec gdzie oni kolejne 256 osob chcieliby pomiescic? ci co beda chcieli to beda przyjmowani, ale na tydzien i out?

Robson

Prawda jest taka ze jak sie zgłosi do nich 10 z tych 256 osób to będzie dobrze... bo wiekszość z czołówki ma juz dobra pracę, a wiekszość z pozostałych to studenci/licealiści/gimnazjaliści, którzy o podjęciu pracy nie myślą jeszcze.