Regulamin działu


Zachęcamy do dyskusji na temat zadań z konkursu Zadanie Tygodnia. Można dzielić się uwagami i np. testami do zadań. Pamiętaj, aby nie publikować metody ani samego rozwiązania zadania z bieżącej rundy.



Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 33 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4  Następna strona
runda 11 
Autor Wiadomość
Gwiazda 3

Dołączył(a): 27 maja 2010, o 23:08
Posty: 32
Post Re: runda 11
Ja napisałem ze strumieniami oraz wyłączoną synchronizacją i przeszło. Co to jest LL? W jaki sposób liczyłeś odwrotność mod p? I po co liczyłeś ją dla każdego pola, pól jest maksymalnie 10^6, a testów 10^5. Dla każdego testu liczyłem odwrotność mod p dwa razy, więc maksymalnie 2*10^5 razy.


21 lut 2011, o 18:17
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: runda 11
Wojtku, śmiesz pisać "żal"?
?
?!

To ja zrobiłem coś naprawdę żalowego.
Jak wszystkim wiadomo w takim przypadku:
1 2 3
4 5 6
7 8 9
Należy od połączenia (sumy, mnożenia, itp.) t[3][3] i t[1][1] zabrać (odjąć, itp.) t[3][1] i t[1][3].
A skoro lewy górny róg to (2,2) to ja oczywiście zabieram t[3][2] i t[2][3].
Po dopisaniu "-1" w kilku (4) miejscach w 1 linijce mam AC i max czas = 0.3s
Argh


Ostatnio edytowano 21 lut 2011, o 18:27 przez Kamil Dębowski, łącznie edytowano 1 raz



21 lut 2011, o 18:22
Zobacz profil
Gwiazda 3

Dołączył(a): 27 maja 2010, o 23:08
Posty: 32
Post Re: runda 11
To ja zrobiłem coś żalowego, miałeś rację z emotem :wali głową w ścianę:. Zamiast po prostu podzielić mod p, specjalnie szukałem odwrotności mod p. Maksymalny czas mam ponad 1,5 s.


21 lut 2011, o 18:32
Zobacz profil
Gwiazda 3Gwiazda 3

Dołączył(a): 17 lis 2009, o 02:37
Posty: 141
Post Re: runda 11
Skoro każdy się chwali, to ja też. Nie uaktualniałem liczby zer, jeśli na poletku rosła liczba != 0.


21 lut 2011, o 18:37
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: runda 11
No ja chciałem mieć coś takiego ala sumy częściowe.
Dla każdego pola trzymam:
-Ile jest zer w prostokącie od jakiegoś pola (1, 1) do aktualnego (x, y)
-Jaki jest iloczyn niezerowych liczb w prostokącie od (1, 1) do (x, y)
-I odwrotność mod p tego powyżej
Ale co jest mi potrzebne do liczenia drugiej wartości? No iloczyn drugich wartości w polach [x-1][y], [x][y-1] i odwrotność z pola [x-1][y-1].
Dzięki temu ile jest zer w każdym takim prostokącie mogę się dowiedzieć ile jest zer w prostokącie, o który nas pytają i jak jest więcej niż 0, to wypisuje 0.
A jeżeli nie ma żadnego zera to mnożę odpowiednie 2 iloczyny i jedną odwrotność, a to już mam i odpowiadam na zapytania w czasie stałym, zatem złożoność O(nm log p +t)

Ale w zasadzie jak się teraz zastanowić, to można do liczenia drugiej wartości za każdym razem liczyć iloczyn niezerowych liczb w wierszu, w którym aktualnie jesteśmy i nie potrzebujemy żadnej odwrotności wtedy mamy złożoność O(nm +t log p).
Ale to nie zmienia faktu, że moje O(nm log p +t) ze strumieniami i ios_basem dostaje 2 TLEki na 2 ostatnich testach, a ze scanfami i printfami zajmuje to ciutek ponad sekunde.


21 lut 2011, o 18:38
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: runda 11
Btw: To ja zrobiłem coś żalowego, miałeś rację z emotem :wali głową w ścianę:. Zamiast po prostu podzielić mod p, specjalnie szukałem odwrotności mod p. Maksymalny czas mam ponad 1,5 s.
- nie rozumiem.
Co rozumiesz poprzez podzielenie mod p, a co przez szukanie odwrotności mod p?


21 lut 2011, o 18:40
Zobacz profil
Gwiazda 3

Dołączył(a): 27 maja 2010, o 23:08
Posty: 32
Post Re: runda 11
Ale w zasadzie jak się teraz zastanowić, to można do liczenia drugiej wartości za każdym razem liczyć iloczyn niezerowych liczb w wierszu, w którym aktualnie jesteśmy i nie potrzebujemy żadnej odwrotności wtedy mamy złożoność O(nm +t log p).
- Ja dokładnie tak zrobiłem (chociaż jaką mam złożoność, to ja nie wiem).

Przez podzielenie mod p rozumiem operację reszty z dzielenia przez p (czyli np. a%p). Z kolei przez szukanie odwrotności liczby a mod p (inaczej: a^-1 mod p) rozumiem szukanie takiego x, że a*x przystaje do 1 (mod p) (inaczej: (a*x)%p == 1).

Edit: Co do zer, to zrobiłem tablicę dwuwymiarową, w której trzymałem posortowaną listę pozycji wszystkich zer w danym wierszu, później dla każdego wiersza sprawdzałem binary searchem czy jakieś zero znajduje się w prostokącie. Nie udało mi się wymyślić nic lepszego.


21 lut 2011, o 19:01
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post Re: runda 11
Przyjrzę się dzisiaj zgłoszeniom - jeśli faktycznie time limit exceeded wynikał z jakichś tymczasowych obciążeń serwera i prowadziłoby to do krzywdzącego dla kogoś wyniku - rozważymy ponowne ocenienie takich zgłoszeń.


21 lut 2011, o 19:17
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: runda 11
Co do zer to najlepiej trzymać tablice ile_zer[n][m] gdzie ile_zer[i][j] to ilość zer w prostokącie ((1,1),(i,j)).

Co do rejudge'a ciastek to jestem jak najbardziej za - gdy już wygram w tym miesiącu, nie chcę żebyście mówili, że to przez przeciążenie serwa :twisted:


21 lut 2011, o 19:22
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: runda 11
Mateusz: Dla mnie dzielenie mod p, to mnożenie przez odwrotność, a nie branie reszty z dzielenia mod p...
Czy ty dla każdego zapytania sprawdzasz oddzielnie dla każdego wiersza, czy jest w nim jakieś 0 :D?

Kamilu, skoro piszesz, że to żalowy bug, to chyba bardzo rzadko Ci się bugi zdarzają i miałeś z nimi mało do czynienia, bo bugi tego rodzaju wg mnie nie zaliczają się do żalowych, o to trzeba się dużo bardziej postarać ;p.

A co do TLEków, to mnie one wcale nie krzywdzą, bo i tak miałem WA ;p.


21 lut 2011, o 19:23
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 33 ]  Przejdź na stronę Poprzednia strona  1, 2, 3, 4  Następna strona


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL