21 / 38
May 2021

Nie wiem czy to było konkretnie do mnie czy bardziej do ogółu, ale pozwolę sobie skomentować :smiley:

Blockquote Niepotrzebnie. Wszelkie problemy i zadania można rozwiązać na wiele sposobów i chociaż jedne sposoby będą lepsze a inne trochę gorsze, to najważniejsze, abyś rozwiązał czy dążył do tego swoim własnym sposobem.

Nie wiem czy się zgodzę z Tobą :smiley: Ja na przykład się mega podjarałem jak zobaczyłem ten “trik” z iloczynem wektorowym. Szansa że sam bym na to wpadł nie była duża, a wolę się rozwijać poznając nowe rzeczy (bez względu na to czy kiedykolwiek użyje tego gdzieś poza Spojem :D) niż rozwiązując kilkadziesiąt kolejnych zadań często “przepałowanych” tylko dla uzyskania AC. Ja rozumiem że radzenie sobie samemu z problemami, ćwiczenie cierpliwości itd też ma swoje plusy, ale czasem chyba można poprosić o pomoc żeby ruszyć dalej :wink: (dobra może ja czasem za często proszę :smiley: )
(Tak na marginesie rozwiązałem to zadanko po przeczytaniu tego linku :wink: )

Trik to pojęcie względne. Akurat w przypadku omawianego tricku związanego z iloczynem wektorowym, jest on tak znany i tak prosty w użyciu (przynajmniej w 2D), że uznaje się go za wiedzę dość elementarną. Rozwiązywanie zadań robionych pod tę sztuczkę bez jej znajomości mija się z celem.

Proszenie o pomoc nie jest problemem. Ba - jest wskazane. Choć spotkałem się pośród starszych speców od AjTi z takim podejściem do projektu:

  1. możesz zadać pierwsze pytanie bo niczego nie wiesz,
  2. możesz zadać drugie pytanie bo złożona odpowiedź, którą udzielono Ci za pierwszym razem musi zostać przetrawiona,
  3. jak pytasz po raz trzeci to nie ma sensu Ci odpowiadać bo zapytasz po raz czwarty :slight_smile:

Zadania łatwe są w dużej mierze do “przepałowania”. Od średnich robi się bardziej wesoło. Tak w zasadzie zadania łatwe, jak już ogarniasz kodowanie, wymagają wyłącznie cierpliwości i chęci.

Na koniec kilka innych tricków, które przychodzą mi do głowy, a na których ludzie często wypieprzają się na SPOJu

  1. Robienie czegoś samemu, następnie kopiowanie i wklejanie do kolejnych zadań. Dotyczy to zwłaszcza funkcji sortujących albo różnych innych, de facto bibliotecznych rozwiązań. Jeżeli masz taką możliwość + chęć nauki to ok - zrób raz własnego sorta, pobaw się, ale przechodząc do kolejnych zadań korzystaj z możliwości języka a nie twórz własny.
  2. Eliminacja Gaussa dla układów równań liniowych. To klasyka, a ludzie często nie wiedzą jak zabrać się za układ równań i kombinują jak koń pod górę.
  3. Problem plecakowy i wydawanie reszty. To akurat na tyle kultowe, że fajnie o tym wiedzieć coś więcej i nie walić zachłannymi algorytmami bez sensu.
  4. Flood fill. W zasadzie pierwsza myśl gdy jesteś na środku szachownicy (tablicy) zwłaszcza z “bajerami” typu ściany (labirynt). Proste w implementacji, nie wymaga wiedzy o grafach/BFS bo zwyczajnie “to widać”. Ewentualnie można sobie pograć w Sapera.
  5. brak wiedzy o źródłach takich jak np. oeis.org4 . Często masz “wizję”, po godzinie widzisz pięć kolejnych liczb w jakimś dzikim ciągu i czujesz, że to się da jakoś prosto wygenerować, ale nie wiesz jak ani czy Twoja intuicja jest dobra. To dobre miejsce do jej zweryfikowania.
  6. Jest sobie jakiś punkt na płaszczyźnie w metryce Manhattan. Masz też dość skomplikowany układ poziomych i pionowych kresek wyznaczających coś typu ściany budynków. Pytanie brzmi czy punkt jest wewnątrz jakiegoś budynku. Problem kultowy choć mniej niż iloczyn wektorowy, ale również prosty.
  7. Fajnie umieć zapisać graf do tablicy i po nim przejść. Wysiłek niewielki, żadnych cudów ogarniać nie musisz, ale już dostajesz niewielkim wysiłkiem (mało nauki) świetne narzędzie do trzaskania nieraz złożonych problemów. Może i niewydajnie, ale już poprawnie. Po dodaniu iluś tricków, o które mniejsza, grafy pozwalają rozwalić niemalże wszystko. Ba - często widzisz, że dany problem jest grafowy, choć może nie widzisz finalnego algorytmu.

Mistrzostwo :wink: niestety żadnego z wymienionych nie znałem … więc albo to jest klasyka tylko dla informatyków a nie koniecznie dla osób z innym wykształceniem albo ja zmarnowałem sporą część swojego życia :joy: Więc jakbyś kiedyś przypomniał sobie coś jeszcze i zechcesz dopisać to będę wdzięczny :wink: Plus macie jakieś książki z których można się takie rzeczy dowiedzieć ? Ja znalazłem przy innym poście jedną “wprowadzenie do algorytmów” , będzie dobra “na start” czy coś innego polecacie ?
P.S Ok jednak eliminacje Gaussa się uczyłem ale pamięć zawodna :man_shrugging:

Jestem inż. technologii chemicznej. Więcej w tym kontekście w wątku SPOJ a praca... i życie.

Sam nie kojarzę w tej chwili niczego więcej. Ściślej: nic z takich bardziej oczywistych rzeczy nie rzuca mi się w oczy.

Dla mnie trick ma to do siebie, że widzisz problem realny (np. układy r. liniowych są dość powszechne w życiu), możesz nie wiedzieć jak to roztrzaskać (bo faktycznie widząc 1000 równań liniowych z 1000 zmiennych… jest wesoło), możesz to wymyślić (w czasie zależnym od wielu czynników, ale umówmy się - tricki na samym końcu okazują się proste i myślisz coś w rodzaju “kurde, faktycznie!”), ale lepiej by ktoś Cię nakierował. I po tym nakierowaniu wszystko staje się jasne.

Pośród różnych innych tricków, od wzorców projektowych z kwestii technicznych po drzewa rozpinające w kwestiach matematycznych, trzeba już jednak nieco więcej wiedzieć, widzieć, rozumieć, kodować, … . To nie jest ani takie proste do ogarnięcia ani takie kultowe ani nie daje takiego efektu “łał”.

To najbardziej kultowa książka, ale niestety nie ma jakiejś magicznej literatury, która gwarantuje sukces. Poza tym musisz odróżnić podejście teoretyczne (np. udowodnij, że dany algorytm ma złożoność O(nlogn)) od praktycznego (król Bajtomir …). Literatura, siłą rzeczy, jest bardziej teoretyczna.

Z Cormena polecałbym zaprzyjaźnienie się ze schematami. W moim odczuciu są klarowne, tzn. łatwo było mi zrozumieć działanie - bo ja wiem - wyznaczania otoczki wypukłej czy problemów dla sieci przepływowych. Fajne są też przykłady: polecam robić wszystko, od byle sortowań, na kartce. Z pełnym zrozumieniem: dlaczego tak, co to daje itd. Może dużo pisania na papierze gdy 10 razy sortujesz coś insertion sortem, ale za to w końcu kod staje się intuicyjny i szybciej klepiesz + widzisz rzeczy algorytmiczne.

Bardzo fajne źródła zlinkował @quenthui. Dodałbym https://eduinf.waw.pl/inf/alg/001_search/index.php12 . Cenię sobie https://www.youtube.com/channel/UCZCFT11CWBi3MHNlGf019nw6 , ale esencja algorytmów jest też zawarta w różnego rodzaju materiałach typu https://www.youtube.com/watch?v=TyWtx7q2D7Y6 .

Są oczywiście inne pozycje, ale na start masz tu podane aż nadto, a inne znajdziesz z czasem sam. Choćby na forum. Na start polecam Tarnów bo w zasadzie jak to opanujesz, roztrzaskasz wszystkie łatwe + większość średnich + kilka trudnych.

To teraz spoza algo.

Początkującym w kwestiach technicznych zalecam https://www.cplusplus.com/reference/2 a zaawansowanym https://en.cppreference.com/w/1 + odpowiednie pdfy.

Jak zapomniało Ci się coś z matematyki i z jakiegoś powodu jej potrzebujesz, pierwszy strzał to zawsze Biblioteka Opracowań Matematycznych (chyba wydawnictwa Bila). Wszystkie inne źródła bierz pod uwagę gdy nie zadowalają Cię wymienione zeszyty.

Może warto zerknąć na Khan Academy (matma, może podstawy IT)? Oczywiście wersja english.

Może nie bez powodu? Jak wolisz: zastanów się, na ile potrzebujesz SPOJa i jakie zadania są Ci potrzebne. Jak dla zabawy i ile zdołasz to spoko, ale co do zasady niewielu ludzi wie co to jakieś rozkłady Gaussa bo niewielu ludziom to jest potrzebne. SPOJ to nie branża IT i w większości sytuacji się nie przydaje (moja opinia; więcej w pierwszym linku w tym poście).

PS
Znam człowieka, który sukcesy w algo- konkursach świętował X lat temu i jak to mówi, kiedyś był w tym świetny, ale od tego czasu mało ćwiczył, mało kodował i raczej obecnie nie kwapi się do tych tematów.

PS2
Kurcze, jednak sobie o czymś jeszcze przypomniałem :slight_smile:

Drzewo gry. W realu może nie jest najczęstsze, a już przy “byle” szachach są z nim problemy. Niemniej kodując sztuczną inteligencję w różnego rodzaju grach turowych (albo szerzej: problemach, które można do nich sprowadzić) warto znać ten twór bo może on sporo ułatwić.

1 month later

W dzisiejszych czasach nie jest problemem znaleźć źródło/a wiedzy lecz wręcz z ich nadmiarem i ich jakością. Nawet na spoju, można znaleźć wręcz bezcenne perełki, np Elementarz - wystarczy poszukać. To Ty jako użytkownik, musisz potrafić ocenić jakość i przydatność tych wszystkich żródeł. Nauczyć się korzystać z nich i studiować. Patrzeć na “ręce” autora - czy nie wprowadza Cię w maliny. Nikt ne zrobi tego za Ciebie, bo dla mnie bezcennym żródłem jest dzisiaj X a za jakiś czas może być żródło Y, a najczęściej nie jest to pojedyńcze źródło, ale nie znaczy że są one dobre i przydatne też tak samo dla Ciebie.

Poczytaj wątek Jak zostać PRAWDZIWYM PROGRAMISTĄ?, a tam linki, np “Poradnik początkującego programisty”.

Inne źródła -książki znajdziesz na zdjęciu półki w/w wątku.

4 months later

Hej.
Mam problem z tym zadaniem. Rozwiązuje prawidłowo wszystkie 477 testów od użytkownika @redysz, a mimo to sędzia nie przyjmuje.
Mój kod tu był.
Nieprawidłowy jest tylko iloczyn który do 50 do potęgi 10 działa prawidłowo(a może nie?).
Jakby się komuś chciało to mógłby zerknąć, będę bardzo wdzięczny.
Nie chodzi mi o dokładne badanie kodu, tylko może o znalezienie testu na którym popełnia błąd.
Dziękuję i pozdrawiam.

1
2 2 2 2
1 1 2 2

Takie coś znalazłem
Twój out: 50
Mój out: 1

Z treści wnioskuję, że taki zdegenerowany przypadek należy traktować jako brak liczby.

1 year later

Witam, męczę się z tym zadaniem już bardzo długo, a jednak wciąż dostaję w odpowiedzi od sędziego WA. Kod rozwiązuje prawidłowo 477 testów od użytkownika redysz. Ja sam już nie mam pomysłu, co może być przyczyną ciągłego odrzucania. Byłoby mi bardzo miło, jakby ktoś poświęcił odrobinę czasu na przeanalizowanie mojego programu.
Kod: usunięty

Dziękuje ci bardzo za podpowiedź. Musiałem sobie przeanalizować to zadanie jeszcze raz, teraz jest AC :grinning:.

7 months later

0 0 2 0
0 0 4 0
komputera nie trzeba, żeby widzieć kąt 0 to jak V??? W jaki sposób sędzia dał AC???
A bierki
1 1 4 4
2 2 5 5 tworzą X? czy jednak -?

wystarczą zmienne całkowite, używamy wzoru ogólnego na prostą i badamy położenie punktów względem niej (po “której są stronie” - geometria analityczna, szkoła średnia)

1 month later

Hej,

Z jakiej racji dla:

0 2 6 0
6 0 7 2

Ma być ‘-’ (tak jest w output.txt)?
Te 2 bierki mają wspólny punkt (6,0) i tworzą kąt ostry. Czyż nie powinno być zatem ‘V’?

narysuj te dwie bierki na układzie współrzędnych i zaznacz ten kąt ostry

przyłóż ekierkę albo kątomierz do monitora w takim razie jeżeli jest tam 82 stopni :slight_smile:

Albo narysuj dodatkowy odcinek (0, 3) (6, 0)
Lub (6, 0) (7, 3) … A uzyskany nowy kąt będzie ostrzejszy od twojego ale nie wystarczająco ostry ::=)

Kąt pomiędzy tymi odcinkami wynosi 98.1301 stopnia. Można to łatwo policzyć z własności iloczynu skalarnego. Kąt, który Ty podajesz to nie jest kąt pomiędzy odcinkiem AB i CD. Jest to kąt pomiędzy odcinkiem CD i przedłużeniem odcinka AB.