Na początku podziękowanie dla autorów zadań, testerów, oraz organizatorów za przygotowanie fajnych zdań i przeprowadzenie konkursu. Od zawsze jestem pełen podziwu dla ludzi, którzy poświęcają swój czas i energię i czasami nie tylko nie są doceniani, ale spotykają się z pretensjami i krytyką. Żałuję, że nie mogłem wyrwać więcej czasu na konkurs, może rozwiązałbym jeszcze ze dwa zadania… 
Oczywiście gratulacje dla zwycięzców i wszystkich uczestników.
Wielkie dzięki za miłe słowa. Jestem przekonany, że gdybyś miał więcej czasu to więcej niż 2 zadania by wpadły jeszcze.
Bardzo ciekawe jest to zadanie Bramka. Wprawdzie nie brałem udziału w konkursie XV, ale rozwiązałem to zadanie trochę inaczej niż w omówieniu do zadań, którego wcześniej nie czytałem . Używam tylko 2 wektorów: bramka i piłka i równania “prostej” w postaci umożliwiającej łatwe sprawdzenie czy punkt na prostej jest pomiędzy czy na zewnątrz 2 punktów ją definiujących. Metoda wzięta z książki o grafice komputerowej. Chciałbym się podzielić moim rozwiązaniem, ale nie wiem gdzie wkleić kod, bo przy próbie zgłoszenia pojawia się błąd “Wrong problem!”.
Po zakończeniu konkursu zadanie Bramka zostało dodane do problemów średnich na polskim SPOJ i można go rozwiązywać.
oto link do niego:
Ciekawe podejście, ale wymaga znalezienia punktu przecięcia dwóch prostych, zgadza się?
Link do zadania jest powyżej. @pwojszepielak był szybszy
Zgadza się, dlatego to w zasadzie na jedno wychodzi w porównaniu do metody iloczynów wektorowych. Równania prostych sa w postaci wektorowej typu b+mi*d,
gdzie b=(xpocz, ypocz), a d=(xkonc-xpocz, ykonc-ypocz)
Dla mi=0 mamy punkt początkowy, dla mi=1 końcowy, 0<mi<1 pomiędzy nimi, a dla mi<0 lub >1 na zewnątrz. Bardzo wygodne.
W tym zadaniu mamy taki układ:
(xp, yp) + mig * (x l- xp, yl - yp) dla gate
(0, 0) + mib * (dx, dy) dla ball
Dla przecięcia się tych prostych mamy więc taki układ do znalezienia mib i mig:
| dx -(xl-xp) | xp |
| dy -(yl-yp) | yp |
Sposób takiej formy przedstawiania prostych opisał Ian O. Angel w swojej książce “Wprowadzenie do grafiki komputerowej”, WNT, 1988, wyd.2, str 24 i str 62. ISBN 83-204-0997-7
No właśnie różnica jest taka, że korzystając z iloczynu wektorowego cały czas działasz na liczbach całkowitych, więc nie ma błędów w dokładności.
W tym konkretnie zadaniu, to jest akurat bez znaczenia. Zmienne są rzędu ~1000.
Ale dla wartości rzędu ~1e9 lub więcej to już może mieć znaczenie.
Twoje rozwiązanie jest jak najbardziej prawidłowe i szacun, że je rozumiesz i umiesz wykorzystać.
Tworząc zadanie Bramka chciałem zachęcić do korzystania z iloczynu wektorowego, bo wiem że jest to narzędzie dokładne, proste w implementacji, niewrażliwe na wszelkie obroty, nie ma warunków brzegowych do rozpatrywania osobno i ogólnie bardzo użyteczne w rozwiązywaniu różnych zagadnień z geometrii.
Cześć
Męczę się z zadaniem “Trener Fraktaliusz”7.
Od początku przyszło mi do głowy, by zrobić dla każdego zapytania (zawodnika) wyszukiwanie binarne po tablicy rosnących dystansów. Napisałem szybciutko programik w Pythonie, wysłałem i… TLE. No cóż, myślę sobie, może limity czasowe dobrane pod C++, co często ma miejsce. Zaimplementowałem więc ten sam algorytm w C++, wysłałem i… znowu TLE.
Po bezowocnej analizie swojego algorytmu, poszukałem czegoś na temat tego zadania w necie i trafiłem na opis rozwiązań zadań z tej edycji konkursu “Fraktal”. Super, pomyślałem. Czytam opis rozwiązania i lekko się dziwię, bo zrobiłem dokładnie tak, jak napisał autor zadania - wyszukiwanie binarne i złożoność O(q * log n).
Próbowałem też innego podejścia: sortowanie zawodników po ich możliwościach, liniowe przejście przez tablice i ponowne sortowanie, by uzyskać właściwą kolejność odpowiedzi. Złożoność O(q * log q). Też powinno przejść bo n<10^6 i q<10^6. Niestety nadal TLE.
Ktoś może ma sugestię, co robię nie tak?
Hej
Rozwiązanie Twojego problemu jest bardzo proste: NIGDY nie używaj cout!
Trochę nie dopilnowaliśmy podczas przygotowań i to zadanie da się zaliczyć tylko używając scanfa. Nawet cout << “\n” jest za wolny.
Co do Pythona, użycie tego pozwala zaliczyć to zadanie
W C/C++ w przypadku problemów gdzie odpowiedzi na zapytania udziela się “na bieżąco”, następujące aspekty mogą być dość istotne:
W C++ cin jest domyślnie powiązany z cout, czyli przed każdą operacją wejścia na cin następuje operacja flush() na strumieniu cout. Tą funkcjonalność można wyłączyć za pomocą std::cin.tie(nullptr);.
W C może być też istotne włączenie pełnego buforowania, zamiast buforowania linii setvbuf(stdout, nullptr, _IOFBF, 0);.
Dzięki za podpowiedzi.
IMHO zaliczenie zadania nie powinno wymagać użycia FAST IO. Choć jestem autorem kilkudziesięciu zadań na polskim SPOJu, nie przyszło mi do głowy, że muszę tego użyć.
A już na pewno powinno przejść rozwiązanie w C++, w którym wyłączy się synchronizację strumieni i flusha (jak pisał wyżej tjm).
Program z kodem
ios_base::sync_with_stdio(0); cin.tie(0);
jaki proponują stosować organizatorzy olimpiady informatycznej, nie powinien dostawać TLE.
Dziękuję jednak za szybką odpowiedź, bo w końcu zadanie mam “z głowy”.
Jako współorganizator konkursu (i tester zadań) mogę tylko przeprosić. Staramy się, żeby takie sytuacje nie miały miejsca.
To nam umknęło i za późno się zorientowaliśmy co stworzyliśmy.
Z drugiej strony jestem zaskoczony, jak dużo osób ciągle używa cout << endl.
I nie dostaje. Dodatkowo nie używam endl i uzyskałem czas 0.23. Gdybm użył fast i/o czas byłby na pewno lepszy.
WIĘC!!
Gdy kodujesz w C++ to raczej używaj cin/cout i ewentualnie powyższych “przyśpieszaczy” a tylko w ostateczności scanf/printf lub fast io – chyba, że wiesz co robisz i bardzo zależy Ci na…
czasie czy brzydszym kodzie.
cin.tie(0)
Nie jest w cale takie popularne. Ja w sumie dopiero teraz z postu Tomasza dowiedziałem się, co to właściwie robi.
W zgłoszeniach, do których mam wgląd, też nie widzę tego codziennie.
Ja zawsze powtarzam: do wczytywania użyj cin (mniej pisania), do wypisywania printf (większa kontrola nad formatem wyjścia i mniej pisania).
Po to tu chyba jesteśmy, czyż nie?
Każden ma swoje priorytety I powody, ale większość:
1 AC
2 AC
3…
4 …
5 i dopiero czas
…
10. Piękno i the art of programming
Co do cin.tie(), to nie jest to wiedza ukryta i tajemna. Jest o tym multum w internecie, trzeba tylko umieć znaleźć. Sam o tym pisałem tu na forum jakiś czas temu, ale sam nie zawsze stosuję, tak jak i fast i/o.
Zwiększyłem limit czasu na tym wydajnościowym teście do 3s. Teraz nie powinno być problemów z AC na cin/cout. Co ciekawe ja podczas testów tego zadania przed Fraktalem dostałem AC na cin/cout właśnie. Wychodzi na to, że później Marcin musiał zmieniać testy.
ostatnimi czasy SPOJ spowolnił - zadania które przechodziły z czasem 0.00 później przechodziły z 0.02
| Topic | Category | Replies | Views | Activity |
|---|---|---|---|---|
| Fraktal XX | Konkursy | 7 | 225 | 5d |
