English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
A okej, dzięki.
Ja nie mam pojęcia. W poprzednich latach to pewnie było kilkanaście godzin nawet.
A jakieś ETA na wyniczki?
Moim zdaniem nic nie trzeba zmieniać, choć zgodzę się z tym, że więcej języków to pewnie więcej zarejestrowanych uczestników. C++ jaki jest taki jest, ale nie widzę dla niego alternatyw. Uważam, że zezwolenie tylko na jeden język jest sprawiedliwe - zgodnie z żołnierską zasadą (trochę parafrazując) "kijowo, ale jednakowo".
Co do alternatyw. Wszystkie języki z automatyczną zarządzeniem pamięcią prawd. odpadają, bo z jaką pewnością uczestnik można stwierdzić czy program mieści się w limicie pamięci? Co więcej, jak mają traktować organizatorzy operacje czyszczenia pamięci, liczyć je w limicie czasowym?
Liczba mankamentów rośnie, bo języki są coraz bardziej abstrakcyjne. Wiem, że inne zawody zezwalają na inne języki, ale ma to swój koszt.
Moim zdaniem język do takich zawodów powinien być dobitnie prosty, z w miarę rozwiniętą biblioteką standardową. Marzy mi się GO, ale z wyżej wymienionych powodów prawd. odpada.
Zgodzę się, że C++ jest językiem bardzo cebulastym, ma dużo warstw. Długa jest też droga programisty, który chce się nazwać ekspertem C++. Komitet mało usuwa, lubi dodawać. Jak ktoś się nie interesuje to nie nadąży za wszystkimi nowościami. Z drugiej strony używanie podstawowego podzbioru możliwości (standard przed 0x) powinien być wystarczający do rozwiązania zadania.
Co do względnie małej liczby użytkowników, to moim zdaniem innym czynnikiem odstraszającym jest format zawodów. Dla ludzi pracujących 8h dziennie z wieloma obowiązkami ciężko jest jeszcze wygospodarować kilka godzin dziennie, żeby wymyślić, zaimplementować i przetestować rozwiązanie - i to przez 6 dni pod rzad. W szczególności, jeżeli weźmiemy pod uwagę uczestników, którzy robią to raz na rok, a ich umysł nie jest już tak lotny, jak dawniej (kiedyś to było).
To moje 3 grosze.
Pozdrawiam wszystkich.
Co do alternatyw. Wszystkie języki z automatyczną zarządzeniem pamięcią prawd. odpadają, bo z jaką pewnością uczestnik można stwierdzić czy program mieści się w limicie pamięci? Co więcej, jak mają traktować organizatorzy operacje czyszczenia pamięci, liczyć je w limicie czasowym?
Liczba mankamentów rośnie, bo języki są coraz bardziej abstrakcyjne. Wiem, że inne zawody zezwalają na inne języki, ale ma to swój koszt.
Moim zdaniem język do takich zawodów powinien być dobitnie prosty, z w miarę rozwiniętą biblioteką standardową. Marzy mi się GO, ale z wyżej wymienionych powodów prawd. odpada.
Zgodzę się, że C++ jest językiem bardzo cebulastym, ma dużo warstw. Długa jest też droga programisty, który chce się nazwać ekspertem C++. Komitet mało usuwa, lubi dodawać. Jak ktoś się nie interesuje to nie nadąży za wszystkimi nowościami. Z drugiej strony używanie podstawowego podzbioru możliwości (standard przed 0x) powinien być wystarczający do rozwiązania zadania.
Co do względnie małej liczby użytkowników, to moim zdaniem innym czynnikiem odstraszającym jest format zawodów. Dla ludzi pracujących 8h dziennie z wieloma obowiązkami ciężko jest jeszcze wygospodarować kilka godzin dziennie, żeby wymyślić, zaimplementować i przetestować rozwiązanie - i to przez 6 dni pod rzad. W szczególności, jeżeli weźmiemy pod uwagę uczestników, którzy robią to raz na rok, a ich umysł nie jest już tak lotny, jak dawniej (kiedyś to było).
To moje 3 grosze.
Pozdrawiam wszystkich.
Taki ogólny zarys:
kom(n, k) - Newton n po k
suma(n, k) sum po kom(n, i) dla i od 0 do k
suma(n, k)=suma(n-1, k)*2-kom(n-1, k)
kom(n, k)=kom(n-1, k)*n/(n-k)
k znamy, nołdy dzielą się po prostu przedziałami możliwych n, każdy spamiętuje ala macierze prefiksowe (bo wzorki wyżej to przemnożenie wektora dwuelementowego przez macierz). Po spamiętaniu macierzy przekazują sobie ten wektor no i n, ten który wykryje, że n jest w jego przedziale, kończy obliczenia.
kom(n, k) - Newton n po k
suma(n, k) sum po kom(n, i) dla i od 0 do k
suma(n, k)=suma(n-1, k)*2-kom(n-1, k)
kom(n, k)=kom(n-1, k)*n/(n-k)
k znamy, nołdy dzielą się po prostu przedziałami możliwych n, każdy spamiętuje ala macierze prefiksowe (bo wzorki wyżej to przemnożenie wektora dwuelementowego przez macierz). Po spamiętaniu macierzy przekazują sobie ten wektor no i n, ten który wykryje, że n jest w jego przedziale, kończy obliczenia.
Też chętnie się dowiem. Co do silni w O(sqrt(P) log(P)) to można ją znaleźć tutaj: https://codeforces.com/blog/entry/63491 ale nie chciało mi się wnikać w szczegóły nie wiedząc jak to wykorzystać.
"Okazuje się, że całe zadanie FUT da się zrobić na jednej maszynie w O(sqrt(P) * log(P)) z jakimiś wielomianami i FFT. Nie mieliśmy o tym pojęcia i na szczęście niewielu zawodników znało taką metodę."
Ja coś takiego znalazłem (nie mylić z zaimplementowałem) do obliczania silni, ale jak to daje radę rozwiązać całe zadanie?
Ja coś takiego znalazłem (nie mylić z zaimplementowałem) do obliczania silni, ale jak to daje radę rozwiązać całe zadanie?
Podzadanie ze znamym N jest warte 5 punktów w zadaniu FUT.
Okazuje się, że całe zadanie FUT da się zrobić na jednej maszynie w O(sqrt(P) * log(P)) z jakimiś wielomianami i FFT. Nie mieliśmy o tym pojęcia i na szczęście niewielu zawodników znało taką metodę.
Rzeczywiście można było wczytać całe wejście w TEA w 3.5s, ale trzeba było być bardzo szybkim w reszcie kodu. W szczególności, linia "for(int i = 0; i < N; ++i) ++count[GetElement(i)]" może nawet przekroczyć 5s. Bezpieczniej było napisać rozwiązanie w O(N log (N) / sqrt(100)) lub ewentualnie podzielić ciąg na nierówne przedziały w rozwiązaniu z czytaniem całego wejścia - maszyny, które mają przeczytać prawie cały ciąg, powinny dostać mniejszy przedział do policzenia inwersji w środku.
Bonus: Zadanie TEA da się zrobić w O(N / sqrt(100) + N log(N) / 100).
Okazuje się, że całe zadanie FUT da się zrobić na jednej maszynie w O(sqrt(P) * log(P)) z jakimiś wielomianami i FFT. Nie mieliśmy o tym pojęcia i na szczęście niewielu zawodników znało taką metodę.
Rzeczywiście można było wczytać całe wejście w TEA w 3.5s, ale trzeba było być bardzo szybkim w reszcie kodu. W szczególności, linia "for(int i = 0; i < N; ++i) ++count[GetElement(i)]" może nawet przekroczyć 5s. Bezpieczniej było napisać rozwiązanie w O(N log (N) / sqrt(100)) lub ewentualnie podzielić ciąg na nierówne przedziały w rozwiązaniu z czytaniem całego wejścia - maszyny, które mają przeczytać prawie cały ciąg, powinny dostać mniejszy przedział do policzenia inwersji w środku.
Bonus: Zadanie TEA da się zrobić w O(N / sqrt(100) + N log(N) / 100).
W TEA ja mam zrobione tak:
Najpierw rozdaje kazdej instancji kolejne bloki tablicy. Nastepnie, kazda z instancji liczy liczbe inwersji w swoim bloku (zrobilem to drzewem BIT, bo szybsze niz mergesort tu chyba bedzie) jak policzy to wysyla do mastera. Master, po odebraniu wszystkich podwynikow ze wszystkich instancji najpierw dodaje te podwyniki do koncowego wyniku i jedyne co mu pozostaje pozniej to policzenie inwersji pomiedzy elementami w roznych blokach. Robie to tak: wczytuje wszystkie elementy tablicy od pierwszego do ostatniego, ale w kawalkach odpowiadajacych dlugosciom blokow oraz utrzymujac dwie tablice: cnt[x] := ile razy widzialem x, larger[x] := ile razy widzialem wartosci wieksze od x. Teraz, dla kazdego wczytanego elementu x, dodaje do wyniku wartosc larger[x] oraz dodaje 1 do cnt[x]. Jak skoncze przerabiac kawalek dlugosci bloku, to przeliczam na nowo tablice larger uzywajac wartosci z cnt. Poniewaz liczymy tylko inwersje pomiedzy elementami roznych blokow, to tablice large przeliczamy po przerobieniu kazdego bloku, a ze wszystkie wartosci sa nie wieksze niz 10^6 to wszystkie przeliczenia takiej tablicy zajmuja sumarycznie O(10^6 * liczba blokow).
W FUT nie wpadlem na ten wzorek, ktory pozwala podzielic sume na kawalki, w ktorych nie ma n, i mam tylko rozwiazanie, w ktorym kazda instancja musi znac n. Uzywalem wzorka bin(n, k) = bin(n, k-1) * (n+1-k) / k, a kazda instancja liczyla swoja sume iloczynow i ostatni mnoznik jaki policzyla, a takze unikala robienia odwrotnosci modulo. Na koncu master to wszystko scalal.
Najpierw rozdaje kazdej instancji kolejne bloki tablicy. Nastepnie, kazda z instancji liczy liczbe inwersji w swoim bloku (zrobilem to drzewem BIT, bo szybsze niz mergesort tu chyba bedzie) jak policzy to wysyla do mastera. Master, po odebraniu wszystkich podwynikow ze wszystkich instancji najpierw dodaje te podwyniki do koncowego wyniku i jedyne co mu pozostaje pozniej to policzenie inwersji pomiedzy elementami w roznych blokach. Robie to tak: wczytuje wszystkie elementy tablicy od pierwszego do ostatniego, ale w kawalkach odpowiadajacych dlugosciom blokow oraz utrzymujac dwie tablice: cnt[x] := ile razy widzialem x, larger[x] := ile razy widzialem wartosci wieksze od x. Teraz, dla kazdego wczytanego elementu x, dodaje do wyniku wartosc larger[x] oraz dodaje 1 do cnt[x]. Jak skoncze przerabiac kawalek dlugosci bloku, to przeliczam na nowo tablice larger uzywajac wartosci z cnt. Poniewaz liczymy tylko inwersje pomiedzy elementami roznych blokow, to tablice large przeliczamy po przerobieniu kazdego bloku, a ze wszystkie wartosci sa nie wieksze niz 10^6 to wszystkie przeliczenia takiej tablicy zajmuja sumarycznie O(10^6 * liczba blokow).
W FUT nie wpadlem na ten wzorek, ktory pozwala podzielic sume na kawalki, w ktorych nie ma n, i mam tylko rozwiazanie, w ktorym kazda instancja musi znac n. Uzywalem wzorka bin(n, k) = bin(n, k-1) * (n+1-k) / k, a kazda instancja liczyla swoja sume iloczynow i ostatni mnoznik jaki policzyla, a takze unikala robienia odwrotnosci modulo. Na koncu master to wszystko scalal.
Zależy, co się wstawi w funkcję GetElement(). Przy czym zgadza się, że nie może to być nic dłuższego niż 0.035 mikrosekundy.
fajne jest
Można wszystko wczytać, maxczasy na tes około 1s... Limit raczej wygórowany, jak się zdaje.
Muszę się trochę pożalić, ale może wyjdzie jaki pożytek z tego gadania :)
Zadanie KON wymagało złożoności w miarę liniowej. Nie mogłem skumać, co takiego złego zrobiłem w moim programie. Wiem, że nie powienienem działać na stringach, że wystarczyły liczby całkowite. A jednak, czemu taki dramat - 20 sekund?
2 breaki, które musiałem dołożyć, to ok, ale dalej coś było nie tak. No i w końcu mam:
-string f(string &astr, string &bstr) {
+string& f(string &astr, string &bstr) {
Brakowało mi tego pierwszego &. Ale długo do tego dochodziłem. Ostatecznie zacząłem dokładniej oglądać raporty profilera i go dopadłem. Po dodaniu znaczka schodzę poniżej sekundy.
To jest "urok" c++. Jeden znaczek, którego brak robi ci po cichu algorytm kwadratowy. A ja pisałem po javowemu. Tam taka konstrukcja jest bezkosztowa. No nic, odbiłem sobie na kolejnym zadaniu. Ale na pocieszenie mam, że algorytm sam w sobie nie był kiepski :)
Zadanie KON wymagało złożoności w miarę liniowej. Nie mogłem skumać, co takiego złego zrobiłem w moim programie. Wiem, że nie powienienem działać na stringach, że wystarczyły liczby całkowite. A jednak, czemu taki dramat - 20 sekund?
2 breaki, które musiałem dołożyć, to ok, ale dalej coś było nie tak. No i w końcu mam:
-string f(string &astr, string &bstr) {
+string& f(string &astr, string &bstr) {
Brakowało mi tego pierwszego &. Ale długo do tego dochodziłem. Ostatecznie zacząłem dokładniej oglądać raporty profilera i go dopadłem. Po dodaniu znaczka schodzę poniżej sekundy.
To jest "urok" c++. Jeden znaczek, którego brak robi ci po cichu algorytm kwadratowy. A ja pisałem po javowemu. Tam taka konstrukcja jest bezkosztowa. No nic, odbiłem sobie na kolejnym zadaniu. Ale na pocieszenie mam, że algorytm sam w sobie nie był kiepski :)
Ok. Czy ja robie cos glupiego w B, czy kazdy ma poprostu czas wczytac wszystko (3.5s) a potem ma 2.5 s zeby zajac sie soba i wyslac reszcie.
w A natomiast:
kluczem jest wzorek f(n, n-k) = sum_(j=0)^(n-k) (k+j-1 po j) 2^(n-k-j)
co pozwala podzielić sumę na kawałki w których nie ma n.
Potem tylko optymalizacja liczenia odwrotnosci mod p.
Trochę mnie martwi, że działa mi 2.5s na probnym (u mnie powinno dzialac tak samo niezaleznie od testu).
w A natomiast:
kluczem jest wzorek f(n, n-k) = sum_(j=0)^(n-k) (k+j-1 po j) 2^(n-k-j)
co pozwala podzielić sumę na kawałki w których nie ma n.
Potem tylko optymalizacja liczenia odwrotnosci mod p.
Trochę mnie martwi, że działa mi 2.5s na probnym (u mnie powinno dzialac tak samo niezaleznie od testu).