GoldenLine
Zaloguj się

konto usunięte

Temat: Codility Helium 2013

Ciekawe zadanie testowe na codility:
http://codility.com/cert/start/helium2013/

Czy ma ktoś pomysł jak uzyskać liniową złożoność obliczeniową?

Mi zdecydowanie nie wyszło: http://codility.com/cert/view/cert9YRKC3-GA3MK3CJJ9KGN...
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

Nietrudno było znaleźć podobny problem na Stack Overflow:

http://stackoverflow.com/questions/17495944/find-num-o...

Rozwiązanie tam zaprezentowane również przedstawia ten sam problem, moim zdaniem przyczyną może być np. zastosowanie w pętlach funkcji wyszukujących np. podciągi (zwraca indeks) lub sumujących elementy z tablic które to same w sobie używają pętli.

Z Codility jest taki problem, że aby poprawnie rozwiązać takie zadania to należałoby być jednocześnie bardzo dobrym matematykiem i programistą. Ale prawdę mówiąc jest to niezłe sito.Ten post został edytowany przez Autora dnia 20.07.13 o godzinie 19:46
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

też tam trafiłem.
rozwiązanie zaprezentowane (python) ma niską skalowalność. jeden człowiek się chwali, że mu się udało, ale nie podaje rozwiązania i jeden dywaguje, że wie jak to zrobić "prawie" liniowo.

mnie problem na dzisiaj przynajmniej przerósł i interesuje mnie zobaczenie działającej implementacji lub chociaż w miarę zrozumiale i wyczerpująco opisanego sposobu rozwiązania problemu.
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

W pythonie jest sprawa względnie prosta ponieważ nie ma konieczności zawracania sobie głowy deklarowaniem typów zmiennych, te są ustalane na podstawie tego co konkretnie zostanie przypisane. Te zadania wcale nie są takie proste jak by się wydawało, prawdę mówiąc to nawet na takiej funkcji jak EQUI można się wyłożyć.

Nie wiem czy jest sens publikować rozwiązania tych funkcji, z pewnością zaszkodziłoby to Codility, podejrzewam że to właśnie dlatego nie zostały opublikowane właściwe rozwiązania na Stack Overflow.
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

trudność nie leży w języku, bo w każdym się da podobnie zaimplementować, czy będzie dynamicznie typowany jak python czy statycznie jak c, tylko w algorytmie. to jaki kto wybrał język nie ma znaczenia.

może faktycznie codility by nie chciało, żeby rozwiązanie wyciekło, niemniej jednak ciekawi mnie jak można dojść przy czymś takim do liniowej złożoności.
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

Michał P.:
trudność nie leży w języku, bo w każdym się da podobnie zaimplementować, czy będzie dynamicznie typowany jak python czy statycznie jak c, tylko w algorytmie. to jaki kto wybrał język nie ma znaczenia.

No niezupełnie. Codility może wywalić błąd przy testowaniu wartości ekstremalnych np. przy sumowaniu elementów z tablic, ponieważ akurat przez małe niedopatrzenie lub niewiedzę zmienna suma została zadeklarowana np. jako longint a funkcja sumuje elementy z tablicy longintów. Wtedy jest jasne że suma musi być long long, co nie jest żadnym problemem w pythonie.

może faktycznie codility by nie chciało, żeby rozwiązanie wyciekło, niemniej jednak ciekawi mnie jak można dojść przy czymś takim do liniowej złożoności.

Zastosowanie pętli w pętli zamiast tylko jednej powoduje wzrost złożoności obliczeniowej czyli nie jest O(n) ale O(n*2). Całość sprowadza się do zastosowania jednej pętli, bez innych pętli lub funkcji wykorzystujących pętle w niej samej.

Weźmy taki mały przykład (JAVA):





public int[] solution(int[] A)

{

    long sum = 0;

    int[] B = new int[A.length];

    int len = A.length;

    

    //sumowanie elementów tablicy

    for (int i = 0; i < len; i++)

    {

        sum += A[i];

    }

    

    //przypisanie różnicy sumy i kolejnego elementu z tablicy

    for (int j = 0; j < len; j++)

    {

        B[j] = sum - A[j];

    }

    

    return B;

}


Nieco oderwany od rzeczywistości przykład (a może i nie), funkcji która zwraca tablicę jakichś tam wartości ale proszę zauważyć, że użyłem dwóch pętli, pierwsza sumuje wszystkie elementy z tablicy intów (tablica A), zakładam jednak że ilość elementów jest ograniczona np. do 1000, druga przypisuje do tablicy B różnicę sumy i elementu w każdym indeksie. I teraz jaka będzie złożoność obliczeniowa w przypadku:

1. użycia pierwszej pętelki sumującej w drugiej pętli przypisującej wartości do tablicy B
2. użycia wcześniej już zdefiniowanej fukcji sumującej elementy z tablicy w pętli

Nonsens. W obu przypadkach każdorazowe sumowanie elementów z tablicy w pętli jest bezsensowne, kiedy to można zrobić tylko raz. Powyższy przykład miał na celu zobrazowanie problemu związanego z tym że na złożoności obliczeniowej można się wyłożyć w przypadku pominięcia albo nie zauważenia pętli w pętlach, zresztą niektórzy nawet na blogach "chwalili" się tym że na początku nie wyszło, czego ja bym nie robił, rozumiem że ma to pokazać jakie to Codility jest świetne (i w sumie się zgadzam). Problem jest taki, że zawsze można postawić zdolniejszemu koledzę flaszkę wódki w zamian za rozwiązanie zadanka albo ściągnąć to ze Stack Overflow, kiedy to zadanie rozwiązuje się zdalnie, wtedy to wiarygodność całego badania szlak trafia.

Nie chcę się tu bawić w rozwiązywanie tej funkcji przedstawionej z Codility w ramach certyfikacji i przedstawiania tego publicznie żeby nie mieć zarzutów działania na szkodę (no chyba że Codility wyraziłoby na to zgodę).Ten post został edytowany przez Autora dnia 21.07.13 o godzinie 07:35
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

Dariusz R.:
No niezupełnie. Codility może wywalić błąd przy testowaniu wartości ekstremalnych np. przy sumowaniu elementów z tablic, ponieważ akurat przez małe niedopatrzenie lub niewiedzę zmienna suma została zadeklarowana np. jako longint a funkcja sumuje elementy z tablicy longintów. Wtedy jest jasne że suma musi być long long, co nie jest żadnym problemem w pythonie.

Czyli niedopatrzenie albo niewiedza programisty, a nie język winny :-) To temat na inną dyskusję, czy lepsze są statycznie czy dynamicznie typowane.
Dariusz R.:
Zastosowanie pętli w pętli zamiast tylko jednej powoduje wzrost złożoności obliczeniowej czyli nie jest O(n) ale O(n*2). Całość sprowadza się do zastosowania jednej pętli, bez innych pętli lub funkcji wykorzystujących pętle w niej samej.

OK, dzięki za wyjaśnienie , z tym że wiem co to jest złożoność obliczeniowa. Chodzi mi o to, że w tym konkretnym przypadku nie widzę, jak to można rozwiązać.
Dariusz R.:
Problem jest taki, że zawsze można postawić zdolniejszemu koledzę flaszkę wódki w zamian za rozwiązanie zadanka albo ściągnąć to ze Stack Overflow, kiedy to zadanie rozwiązuje się zdalnie, wtedy to wiarygodność całego badania szlak trafia.

Wątpię, żeby jakakolwiek firma traktowała te "certyfikaty" poważnie. To raczej każdy sam dla siebie robi, a siebie samego to tak trochę głupio oszukiwać. Ja już wiem, że nie dałem rady - za to mnie ciekawość zżera.
Dariusz R.:
Nie chcę się tu bawić w rozwiązywanie tej funkcji przedstawionej z Codility w ramach certyfikacji i przedstawiania tego publicznie żeby nie mieć zarzutów działania na szkodę (no chyba że Codility wyraziłoby na to zgodę).

Ok, to może ktoś inny? Albo chociaż wskazówka?
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

Złożoność obliczeniowa:

http://pl.wikipedia.org/wiki/Z%C5%82o%C5%BCono%C5%9B%C...

Problem związany ze złożonością O(n*2) jest związany z tym, że operacje na tablicy zawierającej 1000 elementów są rozwiązywane w czasie 100x dłuższym niż operacje na tablicy ze 100 elementów a przecież chodzi żeby czas ten był tylko 10x dłuższy. W moim przykładzie wyżej przy zastosowaniu pętli sumującej wewnątrz tej drugiej ten problem by wystąpił.

Próbowałem już rozwiązywać różne zadania codility, to co bym proponował to może najpierw wejście na:

http://www.codility.com/train

Tam można poćwiczyć na przykładach, są też rozwiązania.

Też kiedyś próbowałem uzyskać certyfikat, niestety te zadania są ciężkie dla kogoś kto nie jest na bieżąco w algorytmach i nie jest dobrym matematykiem. Ten certyfikat a właściwie to jego ważność po pewnym czasie wygasa, więc pytanie co można przez to uzyskać. Ja to bym wolał najpierw poćwiczyć algorytmy a dopiero później można rozważyć certyfikację.
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

Poddaję się. Może mam jakieś problemy z komunikacją, sam już nie wiem...
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

No cóż, napisałem najjaśniej jak potrafię...

Najprościej to by było przedstawić tu gotowe już rozwiązanie, niemniej jednak nie mam zamiaru ułatwiać nikomu życia w ten sposób, z powodu który tu podałem. Prawdę mówiąc sam wyłożyłbym się na Codility biorąc pod uwagę krótki czas na napisanie funkcji, choć miałem do czynienia z bardziej zaawansowanymi algorytmami które zresztą sam opracowałem. Nie spodziewałbym się także tego że ktokolwiek inny podałby tu gotowe rozwiązanie.
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

Coś w stylu:
Q: czy ktoś wie jak zrobić panierkę do kurczaka jak w KFC?
A: od lat zajmuję się hodowlą drobiu, uważam, że mięso karmazynów jest najlepsze, aczkolwiek one same są trudne w utrzymaniu i często chorują. kurczaki po ubiciu nadają się do panierowania.

Pozdrawiam.
:-)
Link do wypowiedziLink
Krzysztof Krakowiak

Krzysztof Krakowiak Software Developer

Temat: Codility Helium 2013

mój wynik: http://codility.com/cert/view/cert6JJEET-H2UTUKDQVD293...
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

Ja myślę że nie ma co się chwalić słabym wynikiem na tak poważnym forum jak to, robicie tylko reklamę Codility i to niestety swoim kosztem bo dajecie do zrozumienia pracodawcom że jesteście kiepskimi algorytmikami. Tak czy inaczej widać że jest to bardzo dobre narzędzie skoro potrafi zrobić taki przesiew.
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

Dariusz R.:
Ja myślę że nie ma co się chwalić słabym wynikiem na tak poważnym forum jak to, robicie tylko reklamę Codility i to niestety swoim kosztem bo dajecie do zrozumienia pracodawcom że jesteście kiepskimi algorytmikami. Tak czy inaczej widać że jest to bardzo dobre narzędzie skoro potrafi zrobić taki przesiew.

A ja myślę, że jak ktoś nie ma nic wartościowego do powiedzenia to nie powinien się wypowiadać. Poważne forum, chwalić wynikami...
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

Krzysztof K.:
mój wynik: http://codility.com/cert/view/cert6JJEET-H2UTUKDQVD293...

Mnie po przemyśleniach udało się dobić do 85 [ O(n) lub O(n**3) ], ale wciąż 3 testy na dużych danych siadają. To fajne ćwiczenie jest, bo (o ile oczywiście nie ma jakiegoś błędu w logice) można zobaczyć jak wewnętrzne funkcje JavaScriptu się sprawują. Dla porównania ten sam kod w Javie dał 90 punktów i przeszedł jeden test więcej.

Mam przeczucie (może błędne), że warto się przyjrzeć algorytmowi Knutha-Morrisa-Pratta.
Link do wypowiedziLink

konto usunięte

Temat: Codility Helium 2013

Michał P.:
A ja myślę, że jak ktoś nie ma nic wartościowego do powiedzenia to nie powinien się wypowiadać. Poważne forum, chwalić wynikami...

Ja bym się nie chwalił a jeżeli już to tylko w przypadku gdybym uzyskał 100%. I to wtedy można się szczycić certyfikatem. Z przerażeniem patrzę jak to na niektórych blogach i dyskusjach na programistów patrzy się w kategoriach lepszy, gorszy a już te wszystkie testy to też nie taka prosta sprawa. Np. tutaj:

http://www.devblogi.pl/2010/01/dlaczego-programisci-ni...
http://forum.gazeta.pl/forum/w,26,125677237,136305637,...
http://blog.rbenkel.me/2012/05/czego-nie-robic-na-rozm...

Daje to wiele do myślenia.

Nigdy też nie publikowałbym rozwiązania jakiejś funkcji, gdybym nie miał absolutnej pewności, że działa poprawnie, zawsze znajdzie się ktoś bardziej kompetentny kto by po mnie pojechał. Znam to z innych dyskusji.

No cóż, mam nadzieję że dojdziecie do 100% czego wam życzę, ja starałem się pomóc najlepiej jak potrafię. A skoro ten sam kod w JS i w JAVA daje inne wyniki to albo jest tak że są jakieś niuanse języka i to ujawnia się w testach albo całe te automatyczne testy w właściwie rekrutacja przy ich użyciu to jakieś totalne nieporozumienie.
Link do wypowiedziLink
Krzysztof Krakowiak

Krzysztof Krakowiak Software Developer

Temat: Codility Helium 2013

80 punktów

http://codility.com/cert/view/certS7T5FA-SEU5DQ8JYZQ85...
Link do wypowiedziLink
Sebastian B

Sebastian B IT

Temat: Codility Helium 2013

W PHP dobicie do 82 pkt i O(n) lub O(n**3) dla kogos kto ma pojecie o algorytmach to kilka minut zastanowienia i trzy linijki kodu, troche trudniej jest pokonac ten wynik. (zostaja trzy testy)Ten post został edytowany przez Autora dnia 02.08.13 o godzinie 17:04
Link do wypowiedziLink
Krzysztof Krakowiak

Krzysztof Krakowiak Software Developer

Temat: Codility Helium 2013

Widziałem ze to zadanie dobiegło już końca.

Za moje rozwiązanie dostałem 88 punktów (JavaScript), jak ktoś chce jeszcze pociągnąć ten temat to mogę wkleić kod z rezultatem. Pozostały mi dwa testy których moja funkcja nie przeszła.
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy


Następna dyskusja:

onGameStart 2013




Wyślij zaproszenie do
Anuluj