Autor Wątek: Compo "Zrozumieć programowanie" - 03-17.11.2015 [wyniki]  (Przeczytany 8470 razy)

Offline hashedone

  • Użytkownik

# Listopad 04, 2015, 10:41:27
Może za dużo swego czasu się bawiłem na OI i ACM, ale mi to wygląda jak typowe zadanie na miotłę i z dodatkiem wektorów na liczbach całkowitych wyznaczenie oświetlenia wygląda że można zrobić o O(1) względem liczby pikseli.
Zaraz ale jak? Jeśli O(1) to znaczy że względem niczego. Ewentualnie może miałeś na myśli O(n) względem liczby pikseli - co by miało jakiś tam sens, chociaż nijak nie potrafię sobie wyobrazić 100% dokładnego algorytmu o takiej złożoności (naiwna implementacja to jakieś n*sqrt(n)*m dla bitmapy kwadratowej o rozmiarze n pikseli dla m świateł, oraz n^2*m dla bitmapy 1*n i m świateł). Myślę że zastosowanie algorytmu o dokładności "good enaugh" a sporo mniejszej złożoności może mieć tu znaczenie.
« Ostatnia zmiana: Listopad 04, 2015, 10:44:10 wysłana przez hashedone »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Listopad 04, 2015, 11:57:22
Cytuj
Jeśli O(1) to znaczy że względem niczego. Ewentualnie może miałeś na myśli O(n) względem liczby pikseli - co by miało jakiś tam sens
Cóż, dawno nie używałem tej notacji i wyszło. Chodziło mi oczywiście o O(n).

Cytuj
chociaż nijak nie potrafię sobie wyobrazić 100% dokładnego algorytmu o takiej złożoności
Jak pisałem - miotła. A w miotle beam tree w którym przedziały są określone wektorami o współrzędnych całkowitych. Drzewo przedziałowe w teoretycznie jest O(log N), ale tutaj przechodzimy elementy po kolei, więc można startować z poprzedniej znalezionej pozycji, więc może się udać dostęp O(1) dla pojedynczego piksela jak się dobrze zakombinuje.

Offline hashedone

  • Użytkownik

# Listopad 04, 2015, 14:13:01
Pomijając rozważania nad rozwiązaniem, które być może idą za daleko więc je utnijmy - Dab, Gyn, pytanie KK jest szczerze mówiąc też dość istotne, mianowicie:
Cytuj
czy piksel zasłania sam siebie? (tj. czy wszystkie blokujące piksele mają być nieoświetlone, czy zewnętrzna warstwa pikseli jednak ma być oświetlona?)

Offline Dab

  • Redaktor
    • blog

# Listopad 04, 2015, 14:17:53
Piksele będące przeszkodami powinny być nieoświetlone.

Offline świrus

  • Użytkownik
    • Tu trolluje

# Listopad 07, 2015, 21:49:14
Co do RLE, to ja bym ustalił czy bitmapa ma mieć kompresje, gdyż np. taki "stb_image.h" nie obsługuje takich cudów.

Offline pajadam

  • Użytkownik

# Listopad 08, 2015, 01:03:44
@up Przynajmiej jest lekkie utrudnienie ;) Ja sobie poradziłem, nie miałem większego problemu.
Nie udało mi się jednak zapisać skompresowanej bitmapy, więc niestety będzie musiała zostać zapisana bez kompresji. Zostało mi tylko ogarnąć generowanie oświetlenia. Mam już plan brakuje mi implementacji. Pozdrawiam i życzę wszystkim powodzenia :)

Offline karol57

  • Użytkownik

# Listopad 08, 2015, 22:58:24
Pokonałem Mystery challenge!, mail poszedł.

5. Bitmapa wyjściowa również musi być w trybie 8BPP, gdzie następujące indeksy oznaczają:
  • 0 - światło nie dociera do danego piksela
  • 255 - światło dociera do danego piksela
Mam dwa pytanka:
1. Jaki jest zasięg światła (dowolny/ustalony, nieskończony)?
1b. Jeżeli nie nieskończony to ma to być binarnie (255 i 0), czy można zrobić płynnie (np. 128 - 50,2%; 129 - 50.6% itd)?
1c. Jak dowolny to rozumiem, że nie może = 1 px :D
« Ostatnia zmiana: Listopad 09, 2015, 18:25:52 wysłana przez karol57 »

Offline Lerhes

  • Użytkownik

# Listopad 09, 2015, 16:48:46
Walczyłem jak lew z tym plikiem, ale niestety nie udało mi się odszukać zakodowanej wiadomości :(
O ile to możliwe, proszę o sprawdzenie czy karol57 dobrze rozwiązał zagadkę (czego oczywiście mu życzę), bo jeżeli nie to wracam do dłubania :D.
Bardzo mnie ciekawi gdzie ta ukryta wiadomość się znalazła :) - jeżeli rozwiązanie Karola jest dobre, to proszę o informacje jak została ona zakodowana.
Lerhes

Offline karol57

  • Użytkownik

# Listopad 09, 2015, 18:36:20
Zagadkę rozwiązałem dobrze, ale okazało się że byłem trzeci.

Co do rozwiązania to uważam, że najlepiej je ujawnić (jeżeli w ogóle) dopiero po zakończeniu compo i zrobić jakąś listę tych co sobie poradzili.

// EDIT:
Światło raczej nie pójdzie mi tak dobrze, więc będę musiał się postarać z GUI.

Co do złego wyświetlania bitmapy to (przynajmniej Firefox) zakłada, że drugi nagłówek to BITMAPINFOHEADER, a nie BITMAPV4HEADER i myśli, że paleta kolorów jest znacznie wcześniej niż znajduje się w rzeczywistości.

Mam jeszcze jedno pytanie: Kodem się dzielimy, czy nie?
« Ostatnia zmiana: Listopad 09, 2015, 19:15:32 wysłana przez karol57 »

Offline Dab

  • Redaktor
    • blog

  • +1
# Listopad 10, 2015, 01:25:45
Prosimy na razie nie publikować rozwiązania do ukrytej wiadomości - dajmy każdemu szansę do pogłówkowania.

Światło ma nieskończony zasięg. Piksele powinny być albo w pełni oświetlone (255) albo zaciemnione (0).  Do oświetlenia piksela wystarczy żeby dosięgało go przynajmniej jedno źródło światła.

Offline Dab

  • Redaktor
    • blog

# Listopad 16, 2015, 01:56:26
Jak tam postępy? :)

Offline karol57

  • Użytkownik

# Listopad 17, 2015, 17:16:30
Ja odpadam, nie dam rady. Mam tylko obliczanie swiatla, ale jest dosyć wolne i pomija część pikseli. Ani tego poprawić, ani gui raczej nie zdążę napisać, więc zostaje mi wieczna chwała za 3 miejsce w Mystery Challenge ^^

//EDIT: W wiadomości wysłałem tylko odszyfrowany tekst i opis gdzie był ukryty, wysyłać kod i/lub nick z forum czy nie ma takiej potrzeby?
« Ostatnia zmiana: Listopad 17, 2015, 17:20:27 wysłana przez karol57 »

Offline pajadam

  • Użytkownik

# Listopad 18, 2015, 00:38:47
Projekt poleciał.

Niestety nie wyszło do końca tak jakbym chciał... przysiadłem nad nim porządnie dopiero dzisiaj, zabrakło czasu na poprawki. Wydajność leży a nadmiar niepotrzebnych i co gorsza powtarzających się if'ów aż prosi się o wywalenie, ale nie ma czasu ;) Na szczęście programu da się używać :)

Mam nadzieje że poszło wam lepiej niż mi :D

Pozdrawiam, Adam.

Offline Compo

  • Użytkownik

# Grudzień 09, 2015, 16:31:45
Wyniki Compo: http://warsztat.gd/news/1323/zrozumiec_programowanie_-_wyniki_compo

Cytuj
W kategorii Wydajność i Interakcja zwycięzcą został Adam Pajkert.

W kategorii Security miejsca na podium zajęli:

1. Dominik Olejnik

2. Tomasz Danielewski

3. Karol Rudnik

Offline karol57

  • Użytkownik

# Grudzień 15, 2015, 13:29:00
Jej III miejsce. W takim razie chciałem podziękować za książkę. Książkę dostałem gdzieś koło 6, ale nie miałem czasu napisać.

Jeżeli chodzi o samą książkę to fajnie się ją czyta, szczególnie (jak w moim przypadku) ktoś lubi wiedzieć jak wszystko działa na niskim poziomie, a nie chce mu się szukać każdej pierdółki z osobna.