MWP3_1B1 - Dlaczego rozwiązanie błędne?

ifinox 2016-08-06 15:18:41 UTC #1

Hej, mam problem z zadaniem Cyfry MWP3_1B1.
Problem mam taki, że wszystkie testy jakie znalazłem w internecie do tego zadania program realizuje prawidłowo, a spoj ten program odrzuca z powodu błędnej odpowiedzi.

Program wygląda tak:
http://ideone.com/SNffjr

Tutaj wykonanie z wszystkimi testami jakie pojawiły się na starym forum:
http://ideone.com/Uz6OzD
(wszystko się zgadza)

Wiem, że pewnie kod trochę za długi jak na to zadanie, jednak zwraca wszystko poprawnie. Wie ktoś gdzie konkretnie mam błąd albo ewentualnie znajdzie 2 odcinki gdzie program zwraca błędne dane?

//edit
Znalazłem jeden błąd - brak sprawdzania metodą null();
Jednak po poprawieniu dalej spoj odrzuca.
Poprawiony kod:
http://ideone.com/kscqgL

mariusz193 2016-08-07 07:44:40 UTC #2

wątpię, by ktokolwiek sprawdził poprawność twojego programu - strasznie długi i zagmatwany

mam natomiast uwagi:

1) używanie typów rzeczywistych, gdy dane są całkowite to proszenie się o kłopoty (to moja stała uwaga)

w szczególności porównanie (a / b) * (c / d) == -1 może dać inny wynik niż a * c == - b * d
bo np. (a / b) * (c /d) może być równe -0.99999999999999999

także sprawdzanie czy kąt pomiędzy odcinkami == 90 poprzez atan2() jest wątpliwe

efektem tych dwóch powyższych, może być nierozpoznanie układu dwóch bierek jako L, a następnie rozpoznanie jako V

2) funkcje L i V powinny być bardziej do siebie podobne - różnia się przecież tylko kątem pomiędzy bierkami

ifinox 2016-08-07 10:07:29 UTC #3

1) W treści zadania nie doczytałem się właśnie nigdzie że współrzędne muszą być całkowite.
2) Różnią się tak bardzo bo "L" to tylko sprawdzenie czy odcinki są prostopadłe a do "V" muszę obliczyć konkretny kąt.

W każdym razie postaram się program całkowicie przebudować bo faktycznie może być dużo niejasności.

//edit
Po całkowitym przebudowaniu programu w końcu zaliczyło, ale nie wiem czy jest się z czego cieszyć - dalej nie wiem gdzie był błąd a większość algorytmu żywcem skopiowałem ze starego - dalej atan, dalej algorytmy do liczenia L i V totalnie nie są do siebie podobne etc. Jedynie przebudowałem trochę ify, usunąłem jedną klas, skróciłem funkcję główną i trzy funkcje LVX upchnąłem w jedną zwracającą odpowiedni char.

Jak ktoś znajdzie błąd albo test zwracający niepoprawny wynik w poprzednim kodzie będę wdzięczny

redysz 2017-07-12 20:14:57 UTC #4

Odpisuję po latach. Mój program, który dostał AC ma inną wartość dla testu numer 8 (V zamiast -). Oraz inny iloczyn, ale raczej mój jest poprawny (więcej zer na końcu, a w iloczynie występuje wiele dziesiątek i pięćdziesiątek).

Coby kiedyś nie zniknęło z ideone wklejam testy:

input.txt (9.6 KB)
output.txt (1.5 KB)

narbej 2017-07-13 05:02:43 UTC #5

Niby że co!? Jak twoje wklejenie może zapobiec czemukolwiek? Jak zniknie forum to razem z twoim wklejeniem. I co discuss ma wspólnego z ideone.com oraz pl.spoj.com?

W pierwszej linii wejścia znajduje się jedna liczba naturalna N (1 ≤ N ≤ 10) określająca ilość par bierek.

Wiec tamten test jest raczej błędny i jest bezznaczenia, jaki jest iloraz oraz pewnie w takim razie wynik dla 8 zestawu.

redysz 2017-07-13 05:54:57 UTC #6

Nie pojmuję o czym piszesz, nic nie pisałem o zniknięciu forum. Napisałem, żę jeżeli zniknie z ideone, padnie ideone, albo autor tematu usunie swój link do ideone to wklejam po to testy by były na forum.

Wiec tamten test jest raczej błędny i jest bezznaczenia, jaki jest iloraz oraz pewnie w takim razie wynik dla 8 zestawu.

Rozumiem, że w zadaniu będzie (1 ≤ N ≤ 10), ale dlaczego z tego powodu wynik dla 8 zestawu miałby być bez znaczenia? I jaki iloraz w ogóle?

Nie ogarniam o czym piszesz. Niemniej... chciałem by testy były dostępne na forum to je wkleiłem. Napisz co zrobiłem źle, bo nie wiem... czy ja czegoś oczywistego nie dostrzegam?

narbej 2017-07-13 06:10:31 UTC #7

Ja też nie zrozumiałem o czym pisałeś. Przeczytałem tylko twój post, a nie zwróciłem w ogóle uwagi na wcześniejsze [i na umieszczone tam linki do ideone]. Teraz zrozumiałem

Mimo to, iloraz w tamtym teście [błędnym] a więc i twoim, jest bez znaczenia, bo, jeśli się nie mylę max =:
10*{L} = L*L*L.... = 50**10 = 97656250000000000

Co do zestawu bierek nr 8, to w takim razie ok [teraz wiem do czego się odniosłeś] - ale ocxzywiście nie sprawdzam tego - wierzę Ci na słowo.

redysz 2017-07-13 06:12:50 UTC #8

Na pewno chodzi Ci o iloraz?

narbej 2017-07-13 06:43:57 UTC #9

Oczywiście że tak

Oczywiście, że tak, masz rację, ale nie wymagaj za dużo odemnie, o tak wczesnej porze

PS
Chociarz, rzeczywiście, iloraz jest zupełnie bez znaczenia, jaki tam on by niebył

PS 2
Co do znikającedgo forum, to odniosłem się do wątku: http://discuss.spoj.com/t/old-spoj-forum/12301

r_inf 2018-07-29 21:08:34 UTC #10

tu był kod

redysz 2018-07-30 07:33:36 UTC #11

Test:

2
-6972 -1134 2372 3381
8640 3272 708 4918
-4378 6434 5139 -1959
171 -8850 -3760 -3614

Mój out:

-
-
1

Twój out:

X
X
100

r_inf 2018-07-30 07:48:22 UTC #12

Dzięki Ci bardzo! Wystarczyło zmienić int na long long int

bieniek_k 2021-03-14 16:22:12 UTC #13

Co prawda udało mi się zdobyć AC za to zadanie, ale ten komentarz nie daje mi spokoju Czy naprawdę udało się komuś rozwiązać to zadanie nie używając zmiennych rzeczywistych ? Jeśli tak to standardowo może podzieli się ktoś wskazówką naprowadzającą co nieco (głownie odróżnienie przypadku X od dwóch bierek nie przecinających się (ewentualnie kiedy punkt przecięcia jest końcem któreś bierki))

quenthui 2021-03-14 19:51:37 UTC #14

Polecam poczytać o iloczynie wektorowym 2D: http://www.algorytm.edu.pl/olimpiada-informatyczna/iloczyn-wektorowy.html

narbej 2021-03-21 20:02:17 UTC #15

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. A ocena co jest lepsze jest czasami subiektrywna. W komentarzu, na który się powołujesz, @mariusz193 zaleca, do tego zadania, używanie zmiennych całkowitych. I to jest słuszne, ale jeżeli zrobiłeś inaczej i uzyskałeś AC, to też jest super, chociaż zmienne całkowite, są po prostu szybsze i często wystarczają do rozwiązania wielu problemów [zadań].
Porównaj np mój komentarz do zadania: FR_12_18 - Liczba monet

Z kilku komentarzy powyżej twojego pytania, wynika, że np r_inf to uzyskał, więc równie dobrze, twoje pytanie możnaby odwrócić, czy naprawdę ktoś rozwiązał to zadanie nie używając zmiennych całkowitych? [wiem, tak Ty ]

@quenthui, podał link, ale możliwe, że początkujący nie bardzo potrafi z niego w pełni wykorzystać.

Więc np tak:

IF Sprawdzamy czy bierki mogą utworzyć cyfrę L lub V, a więc najpierw, czy istnieje co najmniej jeden wspólny punkt. Jeżeli tak, to sprawdzamy jaki bierki tworzą kąt, korzystając np z iloczynu wektorowego. Jeżeli były dwa wspólne punkty - to jaki kąt?
ELSE IF Jeżeli w pkt 1. stwierdzimy, że nie ma żadnych wspólnych pktów, a więc ani L ani V, to może bierki tworzą cyfrę X?
Jak to srawdzić? Korzystając z opisu iloczynu wektorowego i odręcznego rysunku. Jeżli punkty drugiej bierki leżą po przeciwnych stronach pierwszej [jedna na lewo, a druga na prawo] oraz punkty pierwszej bierki też leżą na po przeciwnych stronach bierki drugiej, to tworzą one cyfrę X. W sumie aby to stwierdzić, wykonujemy max cztery iloczyny wektorowe, prawda?
ELSE, bierki nie stworzyły żadnej cyfry.

bieniek_k 2021-03-22 08:54:30 UTC #16

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

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ą 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 (dobra może ja czasem za często proszę )
(Tak na marginesie rozwiązałem to zadanko po przeczytaniu tego linku )

tarpauwatratar 2021-03-22 13:24:10 UTC #17

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:

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

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

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.
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ę.
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.
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.
brak wiedzy o źródłach takich jak np. oeis.org . 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.
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.
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.

bieniek_k 2021-03-22 15:26:29 UTC #18

Mistrzostwo 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 Więc jakbyś kiedyś przypomniał sobie coś jeszcze i zechcesz dopisać to będę wdzięczny 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

quenthui 2021-03-22 16:38:58 UTC #19

Z książkami jest ciężko. Ja zawsze polecam te wykłady: https://www.youtube.com/channel/UCUUbh9zSmNy8RD4LJRiHGFQ. Nagrania są w słabej jakości, ale kontent pierwsza klasa.

Jest jeszcze ten kanał: https://www.youtube.com/channel/UC3iG4wr8CiCAGvKF_-e4Jrg, gdzie są wykłady z algorytmiki i opis rozwiązań różnych zadań (nie ze spoja). Zawsze można podpatrzeć jakieś rozwiązania.

tarpauwatratar 2021-03-22 17:19:59 UTC #20

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.php . Cenię sobie https://www.youtube.com/channel/UCZCFT11CWBi3MHNlGf019nw , ale esencja algorytmów jest też zawarta w różnego rodzaju materiałach typu https://www.youtube.com/watch?v=TyWtx7q2D7Y .

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/ a zaawansowanym https://en.cppreference.com/w/ + 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

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ć.