Fraktal XV

Jeżeli ktoś jest zainteresowany to dostępne jest również omówienie zadań:

Witam,

Pare slow ode mnie na temat zadan:

Bardzo ciekawe bylo zadanie ‘Bramka’,
trzeba bylo rozpatrzyc czasami zaskakujace ustawienia bramki wobec pilki.
Udalo sie to zrobic na int’ach, bez uzywania biblioteki ‘math’.

Foordle - moje ‘szybko’ napisane rozwiazanie nie przeszlo,
pomogla stara praktyka, czyli:

• zaprogramowanie rozwiazania naiwnego,
  ktore jest bardzo wolne, ale zawsze dobrze dziala
• zaprogramowanie generatora losowych danych wejsciowych
  (zgodnych oczywisicie z zalozeniami zadania)

Wtedy dopiero bylem w stanie ponaprawiac oryginalny kod i uzyskac AC.

‘World of Bajtcraft’ - ostatnie zadanie,
okazalo sie dosyc proste, szczerze mowiac,
puscilem swoje rozwiazanie o 19:56 mowiac do zony,
ze to jest niemozliwe, aby taki nieskomplikowany kod byl
poprawny, zaraz bedzie jakies TLE albo WA,
a tu niespodzianka - wyskoczylo zielone okno,
az krzyknelismy w mieszkaniu, sasiedzi pewnie slyszeli :).

Dziekuje za mozlwiosc wziecia udzialu w takim konkursie,
ktory wymaga profesjonalnego przygotowania i przetestowania.
Zawsze powtarzam ludziom, ze satysfakcja po rozwiazanym
zadaniu na SPOJ’u jest nieoceniona.

–
Maciek

Maciek gratuluje rozwiązania zadania w samej końcówce, takie AC smakują najlepiej! Cieszę się, że o tym napisałeś bo ja zawsze powtarzam zawodnikom, żeby się nie poddawali i walczyli do samego końca.

Odnośnie zadania Bramka to tutaj brawa dla Grześka, który wymyśla nam tak ciekawe zadania. Myśle, że mogę zdradzić, że w zanadrzu ma jeszcze kilka, które tez wymagają pokombinowania, ale to musicie poczekać do 16 edycji

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.

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:

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 i oczywiście mib ujemne oznacza zły zwrot, czyli strzał od bramki zamiast do bramki

Świetny komentarz!

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?

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