1 / 31
Sep 2023

Jak w temacie, czy wiadomo kiedy odbędzie się następny Fraktal?

  • created

    Sep '23
  • last reply

    Jan '24
  • 30

    replies

  • 1.0k

    views

  • 10

    users

  • 56

    likes

  • 17

    links

Czy chciałbyś żeby była kolejna edycja Fraktala?

  • Tak
  • Nie

14voters

Votes are public.

W tym momencie nie ma jeszcze konkretnej daty, ale jeśli wszystko pójdzie dobrze, to można się spodziewać kolejnej edycji pod koniec roku.

Bardzo nam miło, że nie możecie się już doczekać

Dziękuję za odpowiedź. Szkoda, że Fraktal jest tylko dwa razy w roku, powinien być częściej robiony.

Pamiętaj, że konkurs jest organizowany przez ochotników (w tym momencie jest ich tylko 3), którzy poświęcają na to swój wolny czas.
Jeśli Ty lub ktoś inny jest zainteresowany pomocą w organizacji konkursu i jest gotowy przygotować chociaż jedno zadanie, to zapraszamy do współpracy. :handshake:

Warto skorzystać z zaproszenia. Chcesz doskonalić swoje umiejętności programowania? Kręci Cię jeszcze zielony kolor ;-)? Jest to niebywała i całkowicie darmowa okazja dla każdej i każdego chcącego, albo dla prawie każdego. …

Możesz kliknąć w googlach: kurs programowania w języku takim, śmakim i wyskoczy Ci multum odpowiedzi, ale nawet jak dodasz darmowe kursy, to i tak google na pierwszych pozycjach “wysypie” Ci płatne kursy lepszej i gorszej jakości - tego dowiesz się dopiero jak zapłacisz i sam skończysz taki kurs …

Są też i darmowe, ale …

Tutaj możesz mieć to za darmo, bo na czym w/w współpraca będzie polegała? Na twoim dużym wkładzie i samodzielnej nauce ale nie zostaniesz sam. “Fraktal” [owcy] Ci napewno pomogą. Jeżeli odpowiedziałeś tak - kręci mnie zielone, to zostając problem setterem będziesz kręcony dwa, a może cztery razy bardziej, gdy inni będą męczyć się i rozwiązywać twoje zadanie - warto aby było dobre - a Ty będziesz kibicował online ich wysiłkom w czasie konkursu a potem na spoju.
Będziesz miała/miał nieograniczony dostęp do wglądu rozwiązań twojego zadania. Będziesz miała/miał dużo większą pomoc niż ta na forum. …

Może to już taka ostatnia okazji? Więc nie czekaj i nie pytaj co Fraktal zrobi dla Ciebie [czy będzie kolejny] tylko pytanie brzmi co Ty zrobisz dla Fraktala [np żeby się odbył] ;-).

Po prostu wstań, walcz i pytaj organizatorów Fraktala co i jak i co ewentualnie zyskasz dzięki swojemu zaangażowaniu.

Ja dzięki temu, że kiedyś zostałem problemsetterem zyskałem bardzo, bardzo dużo, ale to już another story …

Nie wymieniłem wszystkich korzyści i wymagań, ale jeśli jesteś zainteresowana/ny, to pytaj a będą Ci dane i udzielone odpowiedzi …

2 months later

FRAKTAL XVIII

2023-12-09 11:04:46 FRAKTAL XVIII by Marcin Kasprowicz

Cześć!

Z przyjemnością chcielibyśmy Was zaprosić na XVIII edycję Konkursu Programistycznego FRAKTAL. To doskonała okazja do sprawdzenia swoich umiejętności programistycznych i rywalizacji z innymi pasjonatami programowania.

Szczegóły konkursu:

  • Data: 6 stycznia, 12:00 - 7 stycznia, 20:00
  • Miejsce: Link do konkursu na SPOJ18
  • Autorzy zadań: Marcin Kasprowicz, Grzegorz Spryszyński, Rafał Jezierski, Mariusz Śliwiński, Maciej Boniecki, Trapauwatratar
  • Języki programowania: Można używać większości języków programowania
  • Poziom trudności: Dedykowany zarówno początkującym, jak i zaawansowanym programistom

Jest to świetna okazja, aby rozwijać swoje umiejętności, zdobyć doświadczenie i poznać innych entuzjastów programowania. Warto wziąć udział w tym wyjątkowym wydarzeniu!

Pamiętaj, że doświadczenie to nie wszystko - konkurs jest przyjazny dla wszystkich, bez względu na poziom zaawansowania. Niech każdy będzie zwycięzcą!

Powodzenia i do zobaczenia pod adresem spoj.com/FRAKTAL!

Pozdrawiamy!

22 days later

I cała moja maskirowka z “szyfrowaniem” imienia jako tar pa uwat ra tar (taki tam “szyfr” z dzieciństwa) kaput :wink:

Dzieki za fajny konkurs i super zadania, oto mój taki feedback:

“Opony” - Treść zadania powoduje uśmiech, miejscowość Gumowo i panowie Wentyl i Sortowicz.
Ten opis powoduje, że trzeba się przymierzyć do tego zadania aby im pomóc,
po prostu nie ma innego wyjścia.

“Waga Szalkowa” zacząłem robić bez myślenia, nie przeszło.
Dopiero później zacząłem nad nim myśleć i przeszło.
Wniosek: myślenie jest potrzebne w takim konkursie.

“Mały Książę” - Na początku źle to narysowałem na kartce,
i za chiny ludowe nie potrafiłem wyprowadzić wzoru.
Następnego dnia, po przeanalizowaniu na świeżo, okazało się to proste.

“Skrzyżowanie 1” - nie było skomplikowane, dużo czasu mi zajęło,
bo wymyśliłem sobie, że wzór na przyspieszenie to
a = droga/(czas*czas)
co jest nieprawdą. Dopiero po konsultacji u córki (Liceum) i jej
reprymendzie wzór został poprawiony no i przeszło.

“Nocna zmiana” - no tutaj tytuł adekwatny, ja się do niego zastosowałem.
U mnie własnie tak to wyglądało, że poszedłem spać z myślami jak to rozwiązać.
Następnego dnia rozwiązanie wpadło do łba, udało się.

“Najkrotszy ciąg” - jakoś udało mi się szybko znaleźć rozwiązanie,
aż byłem tym faktem naprawdę zaskoczony.

“Odległość” - dla mnie to było dosyć pokiełbasione,
jakoś to zrobiłem, ale widzę, że inni mają dużo lepsze czasy,
pewnie moje rozwiązanie jest algorytmicznie słabe.

Zadanie którego nie zrobiłem, a jest warte komentarza:
“Epidemia” - nie ruszyłem go, bo jako cholerny leń, nie chciało mi się czytać.
Jednak po zawodach, przeanalizowałem sobie ten cały opis i wychodzi, że to fajne zadanie.
Mam nadzieję je zrobić, jak juz będzie dostępne na głównej stronie SPOJ’a

Najbardziej trudnych zadań nie zrobiłem, nawet nie ruszałem,
pewnie wymagają nadludzkich umiejętności, gratuluję zwycięzcom,
jesteście mistrzami.

Jeszcze raz podziękowania dla organizatorów i autorów zadań.
Wykonaliście super robotę.

PS: Fajnie, jakby w takim konkursie brało więcej ludzi, chcociaż i tak nie było źle.

Bardzo fajny konkurs :heart_eyes::heart_eyes::heart_eyes: Zadania faktycznie były dla osób na każdym poziomie. Nie rozwiązałam wszystkich, ale wszystkie przeczytałam. Moje ulubione zadania:

  • Ego - myślę, że pod względem trudności to nie było ono najprostsze, ale podczas czytania treści pojawił się uśmieszek. PS Kłamczuszki jesteście, bo autorów zadań było 5, a nie 6 :stuck_out_tongue_winking_eye:
  • Zakres czujnika - doceniam “złośliwość” autora przy doborze zakresów danych. Naprawdę duuużo czasu nad nim spędziłam.
  • Nocny patrol - super pomysł na zadanie. Trzeba trochę pogłówkować, ale satysfakcja ogromna.

Jeżeli chodzi o uwagi to:

  • Epidemia - niech Autor nie ma mi za złe :blush: zadanie fajne, ale nie na taki konkurs. Już sama długość treści zniechęca, liczba przypadków do zakodowania też mogłaby być mniejsza itd. itp.
  • Karuzela VAT - jak dla mnie treść trochę chaotyczna, niby wiem o co chodzi, ale pewna nie jestem :sweat_smile:

Ja tylko napiszę kilka wyjaśnień odnośnie Epidemii, jako jej nieomal wyłączony autor:

zadanie miało być kontynuacją serii zadań średniej trudności (https://pl.spoj.com/problems/FR_08_14/5), z uwzględnieniem jednej różnicy: zamiast fikcyjnych języków i męczenia się z wymianą ‘-a’ na ‘-b’, o ile wyraz nie zaczyna się na ‘-c’ i w implementacji dopełniacza nie wystąpiło ‘-g’, miało być więcej (w domyśle: ułatwiającej wszystko) abstrakcji. I podobnie: zero trudnych testów, liczy się implementacja specyfikacji, sekcja po sekcji.

Wzorcówka została napisana w Pythonie (to też miało być ułatwienie: po co męczyć się z pointerami i klepać unordered_map jak jest np. dict). Do tego testy do pobrania miały działać jako “pobieram, klepię u siebie kod i widzę, że u mnie przechodzą, wrzucam kod na SPOJa, na 100% jest AC”.

No i podobnie jak pierwowzór, zadanie miało być przeznaczone dla tych, którzy nie znajdą siły na trudniejsze zadania, a będą chcieli walczyć dalej (mając na to np. cały dzień wolnego).

Nie jestem pewien, czy aż tak bardzo mi to nie wyszło, bo jak wskazuje ranking, dużo osób walczyło z ostatnimi zadaniami, zgłaszając i kilkadziesiąt rozwiązań. Jeśli ktoś walczy z trudnymi zadaniami to naturalnym jest, że nie traci czasu na coś takiego jak klepanie symulacji. I wychodzi z założenia, że podoła tym trudnym - tym bardziej, po co się rozpraszać i czytać dłuuugą treść.

No i wreszcie, na co zwrócili uwagę @m_labanowicz oraz @pannazuzanna, kilka zadań planowanych przez nas jako proste, okazało się dość złożonych. Dotyczy to nade wszystko zadań “Mały Książę”, w którym rekordziści np. klepali szeregi Taylora, a także “Zakres Czujnika”, gdzie właśnie nie miało być żadnej złośliwości (serio!). Byłem szczerze przekonany - i nie tylko ja, bo gadaliśmy o tym w trakcie konkursu z ekipą - że zakresy danych “rzucają się w oczy” jako naturalna trudność zadania. Możliwa do obejścia na kilka sposobów, z których jeden był absurdalnie wręcz trywialny i nazywał się Python.

Ale o tym i nie tylko, w szczegółach, jak wrzucę rozwiązania. I rozpiszę co i jak.

Dołączam się do gratulacji dla zwycięzców i podziękowań dla autorów i organizatorów. Jestem tylko zły na siebie za nierozwiązanie zadania Skrzyżowanie II, eeech…

@korkirw, właśnie jestem na etapie rozpisywania rozwiązań. Jak sam się wkrótce dowiesz, formalnie rzecz ujmując rozwiązywałem to prostsze skrzyżowanie około 15 lat :slight_smile: Więc i tak poszło Ci nieźle!

Jestem fizykiem, pierwsze skrzyżowanie to była dla mnie sprawa kilku minut (w sensie rozpisania algorytmu). Idea drugiego też jest prosta, ale chyba byłem już trochę za bardzo zmęczony (oprócz konkursu, miałem wczoraj jeszcze imieniny u szwagra - naprawdę całkiem serio). Poszedłem w siłowe rozwiązanie problemu, ale nawet wyszukiwanie binarne w mojej metodzie okazał się zbyt wolne i rozwiązanie nie przeszło czasowo. Ale nic, teraz można będzie sobie to zrobić spokojnie bez pośpiechu :slight_smile:

To całkiem zrozumiałe, po imieninach u szwagra to nawet wyszukiwanie binarne działa wolniej :smiley:

Paliwo [FR_18_02] [link3]
Poziom trudności wg autora zadania: łatwe
Złożoności występujące w zadaniu: zadanie elementarne (arytmetyczne)

Inspiracja
Zadanie wynikające z rzeczywistości zawodowej dosyć wielu osób, w tym funkcjonujących na niniejszym portalu. Rzeczywistość ta została opisana pokrótce w treści zadania. W aktualnym stanie prawnym obliczenia prowadzić należy identycznie, przy czym pojawia się jeszcze zagadnienie zaokrągleń, np. VAT naliczony podlegający odliczeniu zaokrągla się do pełnych złotych. W zadaniu abstrahowałem od tej kwestii.

Rozwiązanie

Wskazówka nr 1 Z treści wynika, że:

netto + vat = brutto.

Wskazówka nr 2 Czyli:

vat = brutto - netto

Wskazówka nr 3 Czyli:

print(vat / 2, netto + vat / 2)

Oczywiście, wynik należy podać z dokładnością do 2. miejsca po przecinku!

Uwagi pozostałe

  • To nie są przychody, jak niektórzy pisali w swoich rozwiązaniach, ale koszty (uzyskania przychodów)! Jaś kupił paliwo więc nie zyskał, ale stracił!
  • Niektórzy mnożyli netto przez 23% by uzyskać VAT. Było to niezgodne z treścią zadania, ale też - co może zaskoczyć rozwiązujących - ze stanem prawnym! Stawki podatku (tzw. matryca stawek) ustalane są zupełnie inaczej (por.: art. 41 Ustawy z dnia 11 marca 2004 r. o podatku od towarów i usług (Dz.U. Dz.U.2023.1570, a zwłaszcza art. 41 ust. 16). Jeszcze dość niedawno stawki podatku za paliwo były obniżone.

Zakres czujnika [FR_18_09] [link1]
Poziom trudności wg autora zadania: łatwe
Złożoności występujące w zadaniu: zadanie programistyczne dotyczące systemu binarnego

Inspiracja
Zadanie rozszerzające problematykę kodowania, której poświęcono już problem FR_02_114. Moim celem było jednak wyjście poza kwestię U2 (bo formalnie kodujemy co chcemy jak chcemy) przy szerszym zakresie danych.

Rozwiązanie

Wskazówka nr 1 Z treści wynika, że unsigned long long int zmieści liczby dodatnie, ale czy zmieści liczby ujemne?
Wskazówka nr 2 W języku C++ można wczytać liczbę jako string, a następnie informację o znaku przechować np. w zmiennej typu bool, a moduł liczby - w zmiennej typu unsigned long long. Można też wykorzystać język Python. Nie są to jedyne rozwiązania, żeby wspomnieć o __int128_t.
Wskazówka nr 3 Pozostaje implementacja i tu nie ma żadnych wskazań ani przeciwwskazań. Bitesty, operatory bitowe, rozwiązania elementarne (np. pisanie po tablicy charów), ... .

Uwagi pozostałe

  • Brak.

Mały Książę [FR_18_10] [link1]
Poziom trudności wg autora zadania: łatwe
Złożoności występujące w zadaniu: trygonometria

Inspiracja
Problem pochodzi z kultowego podręcznika fizyki. Zawsze bardzo mi się podobał i jak się okazało, spodobał się również zespołowi od Fraktala. W istocie, było to jedno z zadań, które przygotowałem w 2018 r., a którego nie mogłem wrzucić na SPOJa. No i tak od słowa (zdania?) “weźta se moje zadania jeśli chceta bo ja je chciałem wszystkie wywalić” doszliśmy do mojego udziału w przygotowywaniu tej edycji konkursu :slight_smile: W ten sposób, w miarę płynnie, przechodzę do podziękowań dla ekipy, a zwłaszcza dla @quenthui, za anielską wręcz cierpliwość przy testowaniu zadań, tym bardziej przy moich licznych problemach z systemem, który dopiero poznawałem, a także dla @macbon, za naszą ostatnią rozmowę i dalsze prowadzenie za rękę oraz poprawki np. w treści zadania Karuzela VAT. Bez Twojej uwagi o skrzyżowaniach, liczba rozwiązań byłaby mniejsza. A wracając do zadania, poniżej cytat na zachętę.

Rozwiązanie

Wskazówka nr 1 Zajrzyj do książki. Z niej też dowiesz się, czy problem wymyślili autorzy podręcznika, czy też jest on znany od dłuższego czasu.

Uwagi pozostałe

  • Zadanie posiada sporą wadę, która wyklucza je na większości konkursów algorytmicznych: nie operuje na liczbach całkowitych. Fakt ten starałem się zniwelować oczekując bardzo niskiej dokładności rozwiązania.
  • Zauważyłem, że wielu ludzi operowało błędnym wzorem, ale było na tyle przekonanych o jego poprawności, iż walczyło z dokładnością obliczeń.
  • W ramach testów odporności na obliczenia numeryczne testowanych było wiele rozwiązań operujących na wielu zależnościach trygonometrycznych. Wydaje mi się, że jeśli ktoś nie przekombinował (np. wykorzystując 200 sinusów i 50 sekansów), AC nie powinno być problemem. Jeżeli jednak ktoś jest pewien, że nie mam racji, proszę o info - poprawię testy (zadanie zyska na wartości dla przyszłych rozwiązujących) oraz poprawię się (mniejsza szansa na wtopę, np. gdybym w przyszłości miał coś układać na Fraktal).
  • W książce zwrócono uwagę na dwa rozwiązania: uproszczone (wynikające z obserwacji, iż wzrost człowieka jest pomijalny względem rozmiarów planety) oraz pełne. Testy do zadania dobrałem tak, że oba rozwiązania dostaną AC.

Skrzyżowanie I [FR_18_11] [link]
Poziom trudności wg autora zadania: łatwe / średnie
Złożoności występujące w zadaniu: kinematyka

Inspiracja
Problem, w postaci bardzo ogólnej i nieścisłej, został zaprezentowany po raz pierwszy przez fizyka dr Krzysztofa Kaczora, bodaj na jakimś zastępstwie, jeszcze w czasach gdy “cierpiałem” na szkołę. Moje autorstwo sprowadza się do jego uściślenia, wprowadzenia wymiarów, zdefiniowania kilku pojęć oraz znalezienia rozwiązania (dobrą dekadę po “wyleczeniu” się ze szkoły). A przypomniałem sobie o tym problemie dlatego, że pracowałem kiedyś nad sztuczną inteligencją (przetwarzanie mowy i tekstu, coś typu “czy jutro będzie padać między trzecią a czwartą na najbliższej stacji benzynowej?”) do samochodów, a że moda na samochody autonomiczne już trwała to aż się chciało zapytać, czy zmniejszą one korki (patrz: Skrzyżowanie II). Dokładnie stąd wzięła się seria zadań o skrzyżowaniach.

Rozwiązanie

Wskazówka nr 1 Czy wymiary wszystkich zmiennych są zgodne i nadają się do przeliczeń? Czy wiesz, czym są w kinematyce: droga, prędkość, czas, przyspieszenie?
Wskazówka nr 2 Rozwiązanie buduj kawałek po kawałku. Przykładowo, wyobraź sobie, że wszystkie auta ruszają jednocześnie i zatrzymują się jednocześnie po jakimś czasie, np. po minucie. Każde z nich przebyło pewną drogę (identyczną jak inne pojazdy). Przez co należy podzielić tę drogę, aby ustalić, ile aut łącznie przejechało przez skrzyżowanie?
Wskazówka nr 3 Funkcje min oraz max mogą Ci pomóc zapisać jedno zgrabne wyrażenie na drogę pokonaną przez każdy pojazd zamiast wielu ifów. Oczywiście, jeśli wolisz ify, nie ma w tym niczego złego.
Wskazówka nr 4

floor((a * pow(min(V / a, dt), 2.0) / 2.0 + V * max(dt - V / a, 0.0)) / (l + d))

Uwagi pozostałe

  • Porównaj wyniki zadań Skrzyżowanie I oraz Skrzyżowanie II. Odpowiedz na pytanie: czy samochody autonomiczne mogą usprawnić przejazdy przez skrzyżowania?
  • Czym są w kinematyce udar i zryw?
  • (Jeżeli potrafisz rozwiązać równania różniczkowe oraz umiesz rozwijać funkcje w szereg to) wychodząc od przyspieszenia a = const, wyprowadź wzór na drogę. Wykonaj te same kroki dla udaru = const, a potem dla zrywu = const. Czy uzyskane wyniki kojarzą Ci się z czymś ważnym w matematyce?

Epidemia [FR_18_15] [link1]
Poziom trudności wg autora zadania: łatwe / średnie
Złożoności występujące w zadaniu: dużo treści (symulacja)

Inspiracja
Modele epidemii są dość liczne i różne. Zainteresowanych odsyłam np. do modelu SIR. Zainteresowanych równaniami różniczkowymi odsyłam jeszcze bardziej, bo można sobie ułożyć układ równań samemu. Ten model jest modelem - nazwa własna - typu zombie. Ot, Antosia coś ugryzło, ale jeszcze chodzi do szkoły. To rączka odpadnie, to dieta stanie się mniej wegańska, … . Aż w końcu zacznie gryźć innych i zarażać. A potem zgnije. Więcej o inspiracji napisałem już odnosząc się do (słusznej) krytyki problemu.

Rozwiązanie

Wskazówka nr 1 W gruncie rzeczy to zadanie jest proste, choć żmudne. Pałujemy punkt po punkcie Pythonem. Żeby nie było TLE, wystarczy odpowiednia ilość słowników. Wg mnie to zadanie jest świetne do nauki Pythona! Komentarze nie stanowią dodatkowej trudności, ale kolejne ułatwienie: można je wrzucać w testowych inputach żeby np. coś zakomentować albo napisać sobie rzeczy potrzebne do debuggu.

Uwagi pozostałe

  • Treść zadania była wielokrotnie zmieniana, między innymi dzięki słusznym uwagom poczynionym przez @quenthui. Dziękuję za te uwagi i mam nadzieję, że zadanie posiada walor dydaktyczny oraz jest możliwe do zrozumienia i rozwiązania. A także, że jego rozwiązanie może się komuś spodobać.
  • Polecam prostą apkę w konsoli. Jakieś zombie ‘X’ chodzi sobie losowo po planszy, np. 20 x 20. Jak zarazi to zdrowy (’#’) zamienia się w chorego (‘C’), a z czasem zaraża innych (staje się ‘X’). Po jakimś czasie ‘X’ gnije i znika z planszy. Albo zdrowieje i staje się odporny więc też znika, bo drugi raz się nie zarazi. Zostawiam zainteresowanym np. rozwiązania takie jak szczepienia, dzięki którym zniknie z symulacji 50% zdrowych. Albo np. symulowanie drogi do pracy czy zakupów.
  • Jeśli pojawi się takie życzenie, mogę do .zipa zapakować wszystkie testy do tego zadania.

Karuzela VAT [FR_18_16] [link2]
Poziom trudności wg autora zadania: średnie
Złożoności występujące w zadaniu: przejście grafu w odpowiedni sposób

Inspiracja
O przestępstwach karuzelowych dużo by pisać. Wrzucę zamiast tego link do strony Ministerstwa Finansów, gdzie nawet znajdziecie gotowy schemat. Dokładnie o niego chodziło w treści zadania. Schemat ten nie jest żadną tajemnicą - jego różne wersje można znaleźć w wielu źródłach, w tym medialnych. Dostępne są również materiały audiowizualne, np. na YouTube.

Rozwiązanie

Wskazówka nr 1 Pamiętaj o sortowaniu leksykograficznym.
Wskazówka nr 2 Spośród iluś możliwych rozwiązań, wystarczy nawet DFS. Ważne, żeby analizować każdy towar oddzielnie oraz odpowiedzieć na pytania wynikające z kryteriów przedstawionych w treści zadania.
Wskazówka nr 3
  • Czy firma X, którą aktualnie rozważasz, jest polską firmą i sprzedaje towar Y za granicę?
  • Czy z dostępnych danych wynika, że towar Y został zakupiony za granicą przez polską firmę inną niż X?
  • Czy istnieje ścieżka wskazująca, że towar Y (zakupiony za granicą przez polską firmę inną niż X) może dotrzeć od tej innej firmy do firmy X?

Uwagi pozostałe

  • Treść zadania była wielokrotnie zmieniana, między innymi dzięki słusznym uwagom poczynionym przez @macbon. Ponadto, w trakcie testów przeprowadzonych przez @quenthui okazało się, że randomowo generowane testy wprowadzają pewne komplikacje (patrz: jednoznaczność danych opisana w treści zadania). Dziękuję za te uwagi i mam nadzieję, że zadanie posiada walor dydaktyczny oraz jest możliwe do zrozumienia i rozwiązania. A także, że jego rozwiązanie może się komuś spodobać.

Skrzyżowanie II [FR_18_18] [link]
Poziom trudności wg autora zadania: trudne
Złożoności występujące w zadaniu: kinematyka, wyszukiwanie binarne po wyniku

Inspiracja
Patrz: Skrzyżowanie I

Rozwiązanie

Wskazówka nr 1 Rozwiąż prostszą wersję zadania.
Wskazówka nr 2 Wzór istnieje i da się go wyprowadzić, ale może lepiej szukać binarnie po wyniku wykorzystując coś "prostszego" do zaklepania?
Wskazówka nr 3 Wiesz już, jak obliczyć czas, w jakim dowolny samochód pokona pewną drogę, o ile tylko żaden pojazd nie znajduje się przed nim.

Dla pierwszego auta czas wydłuża się o 0 * t = 0, bo stoi bezpośrednio przed światłami i rusza od razu. Drugie auto musi odczekać dodatkowo 1 * t = t, bo poprzedni samochód musi odpowiednio się oddalić. Trzecie auto ma “opóźnienie” 2 (bo tyle aut jest przed nim) * t = 2t, czwarte - 3t itd.

Wskazówka nr 4
bool count_it(const double a, const double V, const double tx, const double dt, const double l, const double d, const int n)
{
     const double timeLeft = dt - (n - 1) * tx;
     const double tA = max(min(timeLeft, V / a), 0.0);
     const double tB = max(timeLeft - tA, 0.0);

     return 0.5 * a * pow(tA, 2) + V * tB >= n * (l + d);
}

Uwagi pozostałe

  • Porównaj wyniki zadań Skrzyżowanie I oraz Skrzyżowanie II. Odpowiedz na pytanie: czy samochody autonomiczne mogą usprawnić przejazdy przez skrzyżowania?
  • Istnieje wiele dróg prowadzących do rozwiązania. Przedstawiona we wskazówkach jest jedynie przykładową z nich. Nie twierdzę, że najlepszą.

Mam parę takich przemyśleń na temat zadania Epidemia3 co to chciałbym je tutaj przedstawić.

Pod pewnymi względami to zadanie ma swoje walory edukacyjne, dlatego, że takich właśnie wyzwań (zaimplementowania symulacji, itd.) z dodatkowo nieścisłą specyfikacją można spodziewać się w realnym życiu programisty.

Wiem, że niektórzy mogą się oburzyć, że jak to, specyfikacja dla zadania musi być idealna. Fakt, że idealna specyfikacja bardzo ułatwia zaprogramowanie rozwiązania, ale tak w życiu nie ma, często trzeba sie domyślać, co autor miał na myśli.

Żeby zrobić to zadanie, należy przeczytać opis, następnie sprawdzić testowe dane in/out i się zszokować, że opis chyba nie odzwierciedla stanu faktycznego, chodzi o komendy:

NEW <x>, <y> <FINE | ILL | CONTAGIOUS> <id> [CONTAGIOUS AFTER <t>]
QUERY <x>, <y>

Można by się spodziewać, że x jest na osi X, a tutaj pierwsza niespodzianka :wink:

Następnie, jak juz się z tym uporamy, to dzięki dodatkowym testom (archiwum zip5) widać, że w danych wejściowych czasami mogą pojawić się przecinki, o których specyfikacja nie wspomina, a czasami może ich nawet zabraknąć.

Myślę że tego typu nieścisłości mogły być wynikiem, że nikt tego zadania nie rozwiązał podczas konkursu (widać, że były próby6 przeprowadzone przez mocnego zawodnika), w którym liczył się czas.

Osobiście sądzę, że takie zadanie poza konkursem jest jak najbardziej godne polecenia do zaimplementowania i sprawdzenia swoich umiejętności.

Hej. Przede wszystkim gratuluję AC!

Specyfikacja powinna być idealna, tylko niestety jest pewien problem: każdy ma swoją wizję takowej… . Jak dorzucisz do tego ograniczone moce przerobowe - bądź co bądź - wolontariuszy, wychodzi problem. No i kwestia percepcji - idealne rozpisanie treści zajmuje dużo miejsca, a to wcale nie pomaga. Np. jest więcej miejsca na pomyłkę w treści.

Co do przecinków: faktycznie, ostatecznie są używane w jednych miejscach, a nie używane w innych. Mogłem postępować spójnie - moja wina. Gdybym miał okazję w przyszłości popełnić podobną wtopę, postaram się jej uniknąć.

Co do reszty - cieszę się, że archiwum z testami pomogło. Po to jest, by nie kodować w ciemno i szukać potem tego jednego, jedynego błędu w jednym na milion przypadków.

Hej wszystkim. No to ja chciałem tylko dodać, że konkurs bardzo fajny. Czuję do niego sentyment, gdyż tutaj rozpocząłem swój competitive programming (choć w moim przypadku to może za duże określenie). Zostawię mały feedback, może komuś się przyda.

Co mi się podobało:

  1. Ciągłość konkursów.
  2. Zadania o różnym poziomie trudności.
  3. Zadania przygotowywane są przez różnych autorów.
  4. Fajna atmosfera.
  5. Spalenie całego weekendu na rzecz pisania contestu.

Co mi się nie podobało:

  1. Spalenie całego weekendu na rzecz pisania contestu.

Co bym poprawił:

  1. Sponsor. Myślę, że tutaj jak najbardziej można by było o takim czymś pomyśleć. Nie mówię już o samych nagrodach, ale też o wynagrodzeniu dla osób poświęcających swój czas. IMHO wiele firm byłoby zainteresowanych w takim przedsięwzięciu :slight_smile:
  2. Mam wrażenie, że niektóre zadania sztucznie podbijaną trudność. Przykłady:
  • https://www.spoj.com/FRAKTAL/problems/FR_18_09/4
    Wczytywanie danych jako int128 to lekka przesada, w szczególności, że limity są na tyle dopchane, że rozwiązanie w Pythonie nie przechodzi (tego nie jestem pewien, ale tak to pamiętam). W szczególności powoływanie się w zadaniu na test przykładowy w celu wytłumaczenia problemu jest czymś złym (nie tyczy się to zadań z enigmą czy czymś takim, pamiętam, że coś takiego było i było to bardzo fajne). Np. w tym zadaniu naturalną reprezentacją wydawał mi się zapis w U2.
  • https://www.spoj.com/FRAKTAL/problems/FR_18_16/2
    No z tym sortowaniem leksykograficznym jest coś nie tak… Żeby można było posortować coś leksykograficznie musi najpierw być porządek. Jeśli nie jest o tym nic wspomniane to zakłada się raczej, że jest to kolejność alfabetyczna. A co jeśli rozpatrujemy litery, cyfry, a nawet i podłogi? No właśnie. Takie zabiegi nie są dobre. Te podłogi nie zmieniają nic w trudności zadania. Jedyne co wnoszą to albo dodatkowy opis w zadaniu o porządku (przez co treść zadania jest mniej przejrzysta) albo błąd w treści zadania poprzez właśnie brak specyfikacji.
  1. Za mało testów przykładowych, w szczególności gdy SPOJ trochę skąpi informacji jeśli chodzi o werdykt. Nie wiadomo, na których testach nie przechodzi, jakie są czasy itp. itd.

Swoją drogą dalej nie mogę dobić dwóch zadań. Jakby ktoś coś podpowiedział to bym był mega wdzięczny! :blush:
https://www.spoj.com/FRAKTAL/problems/FR_18_16/2 verdict: WA - wydaję mi się że dobrze sortuje. Obce kraje traktuje jako jeden wierzchołek w grafie. Idę dfsem i biore krawędzie które mają połączenie do obcego kraju. Następnie moim wynikiem są tylko te krawędzie, które mają polskiego poprzednika.

https://www.spoj.com/FRAKTAL/problems/FR_18_17/6 verdict: TLE - O(n * M), proste DP gdzie M < 10^4 okazuje się być za dużo.

Pozdrawiam i mam nadzieję że zobaczymy się na kolejnej edycji!
MB