|
|
 |
|
|
 |
Dostawa
Damian Gronczewski - 5 mar 2010, o 19:14
" />Mam pytanie co do danych wejściowych w tym zadaniu.
Może mi ktoś wytłumaczyć co znaczą poszczególne cyfry w przykładowym teście.
1
2
1 1
2 3 4
1 5
8 3 2
5 2
Wiem że jest 1 test a miasto ma szerokość i długość 2 ulic ale reszta danych jest dla mnie zagadką.
Oczywiście proszę o zgłaszanie przykładowych testów.
Wojtek Nadara - 5 mar 2010, o 19:17
" />
Damian Gronczewski - 5 mar 2010, o 19:17
" />no teraz tak dzięki:D
Dawid Dąbrowski - 5 mar 2010, o 19:20
" />To są ilości ciężarówek, które dana ulica może zdzierżyć.
I tak, masz podane na przemian:
pierwszy rządek ulic poziomych, pierwszy rządek ulic pionowych, drugi rządek ulic poziomych, ...
Adrian Jaskółka - 5 mar 2010, o 23:56
" />jakieś testy może? jeden mój ręcznie wklepany:
in:
1
5
10 12 5 3 65
17 5 7 34 65 6
45 9 12 54 6
4 10 56 12 5 10
3 10 20 54 10
15 16 10 50 10 50
10 9 6 2 65
9 6 2 20 54 20
20 12 64 54 10
8 9 6 20 10 20
10 17 9 10 54
out:
27
Marcin Smulewicz - 6 mar 2010, o 00:39
" />Potwierdzam i wrzucam test od siebie.
in:
1
5
10 1 3 2 10
12 8 1 1 11 10
5 1 2 5 10
18 2 1 1 4 3
16 7 5 2 5
2 10 1 2 4 3
8 8 6 5 4
10 5 2 2 13 10
1 3 2 1 1
12 10 4 3 12 30
13 2 10 11 20
out:
20
Adrian Jaskółka - 6 mar 2010, o 00:51
" />potwierdzam.
Aleksander Kramarz - 6 mar 2010, o 02:37
" />Potwierdzam oba testy
Aleksander Kramarz - 6 mar 2010, o 02:52
" />Większy test: http://www.sendspace.pl/file/140eeb6d0241ce876012269
time ./dos < in
420213910
real 0m3.006s
user 0m2.960s
sys 0m0.012s
Grzegorz Milka - 6 mar 2010, o 08:13
" />Potwierdzam większy test.
Aleksander Kramarz - 6 mar 2010, o 13:13
" />A jak czasy?
Krzysztof Puzdrowski - 6 mar 2010, o 21:58
" />http://w258.wrzuta.pl/plik/3kBai0Xe6xS/dos2.tar.gz
ubuntu@ubuntu:~/Desktop$ time ./dos<dos2.in
846623873
real 0m1.416s
user 0m1.324s
sys 0m0.088s
Potwierdza ktoś? I z jakim czasem? Sorry, jeżeli odpowiedź można jakoś trywialnie znaleźć, to jest tylko w 100% losowy test wydajnościowy?
Dawid Dąbrowski - 6 mar 2010, o 23:06
" />Potwierdzam, Krzysiu Ładny test, Krzysiu Aleś sie napracował, KRZYSIU!
I potwierdzam wszystko z forum
Łukasz Solak - 6 mar 2010, o 23:13
" />[fingon@fingon-notebook 3]$ time ./dos < dos2.in
846623873
real 0m1.956s
user 0m1.857s
sys 0m0.090s
Aleksander Kramarz - 6 mar 2010, o 23:17
" />time ./dos < dos2.in
846623873
real 0m2.818s
user 0m2.436s
sys 0m0.060s
Marcin Smulewicz - 7 mar 2010, o 11:58
" />To może ja wrzucę jakiś ambitniejszy test:
http://w755.wrzuta.pl/plik/aE3cidjD90g/max
out: 1000000000
Mój czas na tym teście 3,6s.
Ktoś potwierdzi i pochwali się czasem?
Łukasz Solak - 7 mar 2010, o 12:43
" />time ./dos < max.in
1000000000
real 0m4.284s
user 0m4.180s
sys 0m0.100s
Grzegorz Milka - 7 mar 2010, o 15:04
" />Test Krzysia, potwierdzam:
real 0m0.543s
user 0m0.480s
sys 0m0.060s
Test Marcina, potwierdzam
real 0m1.402s
user 0m1.360s
sys 0m0.030s
Skompilowane z opcją O2.
Wojtek Nadara - 7 mar 2010, o 17:36
" />Cóż, zabrakło mi jakiejś godziny, aby to zadanie napisać :<. Niestety już nie zdążę :/. Implementacja mi idzie zawsze jak krew z nosa xp (Owce na OI'u implementowałem 3h, aby i tak dostać 20 pkt xp).
Krzysztof Puzdrowski - 7 mar 2010, o 17:45
" />O kurde w odpowiedzi do testu Smulewicza jest błąd !! Przeczytajcie dokładnie treść zadania. Ja pierdziele dobrze że sprawdziłem na wszelki wypadek jeszcze raz moje rozwiązanie przed wysłaniem
daredeva - 7 mar 2010, o 17:59
" />tez sie cieszymy.
Łukasz Kalinowski - 7 mar 2010, o 18:03
" />17:57 - godzina zgłoszenia... Teraz pozostaje cierpliwie czekać na to, czy nie popełniłem jakiegoś błędu, bo nie odważę się już tego testować ^^
Aleksander Kramarz - 7 mar 2010, o 18:17
" />No cóż, to jak należało to napisać na 10pkt? Bo maksymalny przepływ metodą Dinica radził sobie dobrze z losowymi danymi, test Marcina go ubił.
Dawid Dąbrowski - 7 mar 2010, o 18:21
" />Z twierdzenia o maksymalnym przepływie i minimalnym przekroju. Bądź też jak kto woli z przepływu w grafach s,t-planarnych, które to wynika z tego pierwszego twierdzenia. Do wyboru, do koloru.
Grzegorz Milka - 7 mar 2010, o 19:04
" />W praktyce ja dostawę zrobiłem jako znajdowanie najkrótszej ścieżki między którymś z wierzchołków za górnym/prawym bokiem a lewym/dolnym. Przyczym wierzchołek to parcele między skrzyżowaniami a krawędzie łączące to drogi między parcelami o odpowiednich wagach.
Adrian Jaskółka - 7 mar 2010, o 19:06
" />Generalnie problem przedstawiony w zadaniu jest problemem maksymalnego przepływu w grafie. Korzystamy z twierdzenia że maksymalny przepływ w grafie równy jest minimalnemu przekrojowi w tymże. Postać grafu (kratka taka) ułatwia znalezienie minimalnego przekroju. Tworzymy sobie drugi graf gdzie wierzchołkami są przestrzenie między ulicami a dwa wierzchołki są połączone krawędzią gdy te przestrzenie się stykają. Długość owej krawędzi jest równa przepustowości ulicy która jest między tymi dwoma przestrzeniami. Tworzymy sobie również 2 dodatkowe wierzchołki specjalne. Jeden łącze z każdą przestrzenią brzegową z dołu i lewej strony miasta i długość krawędzi jest równa przepustowości zewnętrznej ulicy. Drugi tak samo łącze z każdą przestrzenią brzegową z góry oraz prawej strony. Między wierzchołkiem specjalnym a normalnym może istnieć więcej niż jedna krawędź (z zasadzie tylko między specjalnym oraz lewym dolnym, bądź prawym górnym). W tak utworzonym grafie musimy znaleźć najkrótszą ścieżkę od jednego do drugiego specjalnego wierzchołka. Robimy to Dijkstrą i mamy rozwiązanie o złożoności O(n*n*log n).
Podziwiajcie mego skilla w paincie:
To jest graf dla przykładu z treści zadania. Czerwone wierzchołki to dodane wierzchołki specjalne.
Krzysztof Puzdrowski - 7 mar 2010, o 19:08
" />Fajne zadanie, jak Dawid wymyślił u góry, bazuje na tw. maxflow-mincut, a mincuta znajdujemy rysując dikstrą taką kreskę przecinającą kolejne ściany począwszy od ścian towarzyszących lewemu dolnemu bokowi kwadratu, do ścian towarzyszących prawemu górnemu rogu (wierzchołki grafu, to środki kwadracików).
Aleksander Kramarz - 7 mar 2010, o 19:13
" />No nie powiem, sprytne. Niestety nie wpadłem. Gratuluję.
Krzysztof Puzdrowski - 7 mar 2010, o 21:22
" />Adrian, miałem dokładkie taki sam rysunek do debugowania przykładów :p tzn. chodzi o rozmieszczenie wierzchołków
Wojtek Nadara - 7 mar 2010, o 22:02
" />Ja wymyśliłem algorytm do dostawy w złożonosci O(2^{n^{2}}*n^{6}), ale jakoś nie chciało mi się go kodzić xD. Polegał na obserwacji, że nie ma sensu jechać w trakcie 1 ścieżki jedną krawędzią w jedną stronę, a na innej ścieżce z drugą stronę, a wiec mogę sobie rozpatrzyć 2^{n^{2}} grafów skierowanych, bo każdej krawędzi mogę przyporządkować skierowanie, a potem Edmonds-Karp. O maksymalnych przepływach zacząłem się uczyć trochę wczoraj i jeszcze trochę dzisiaj się uczyłem, ale to, że w grudniu złapałem niemickiego wirusa, którego jeszcze nie wykurzyłem spowodowało to, że filmik z wykładu o przepływach z http://www.was.zaa.mimuw.edu.pl ładował mi się 10 razy wolniej niż normalnie się go ogląda i obejrzałem tylko metodę Forda-Fulkersona i algorytm Edmondsa-Karpa, a maxflow-mincut był dopiero po nich xp. A notatek mi się czytać nie chciało xD.
Jak nagadałem jakieś brednie, to mnie poprawcie xp.
Wojtek Nadara - 7 mar 2010, o 23:20
" />Btw istniało inne rozwiązanie w złożoności O(n^2 log n). Jest ono autorstwa Łukasza Kalinowskiego (niestety dostał on tylko 6 pkt przez TLEki mimo optymalnej złożoności, najprawdopodobniej przez używanie seta).
Najpierw wybieramy se ścieżkę idącą po lewym boku miasta, a potem po dolnym. Całe miasto kolorujemy na zielono (kolory przydzielamy polom). Przez daną ścieżkę będziemy w każdej chwili rozumieli granicę między zielonymi, a czerwonymi polami, przy czym to co jest na lewo i w dół od miasta jest czerwone xp.
Wszystkie krawędzie wrzucamy do seta. Bierzemy najmniejszą drogę z seta, dodajemy ją do wyniku i ją objeżdżamy zamieniając sąsiadujące z nią pole na czerwone, przez co przy każdej zmianie zmieniamy stan maksymalnie 4 dróg. Wyrzucamy z seta te krawędzie, które usunęliśmy, do wyniku doliczamy wartość najmniejszej i wrzucamy do seta wartość nowej drogi.
Wartym zauważenia faktem jest, że wszystkie drogi w czerwonej części zostały w pełni wykorzystane, a wszystkie drogi w zielonej części są nienaruszone.
Trzeba jednak jeszcze pamiętać o aktualizacji wartości dró, czyli o tym, że jak usuwamy krawędź o wartości 2, to trzeba wszystkim krawędziom, które należały do tej drogi zmniejszyć wartość o 2. To jednak jest trochę za długie, bo liniowo od krawędzi dla każdej drogi. Jednak z tym można sobie poradzić w taki sposób, że za każdym razem wrzucamy do seta wartość danej drogi jaki wartość danej drogi+ wynik, a gdy wyjmujemy, to do wyniku dodajemy zmodyfikowaną wartość drogi minus aktualny wynik.
Dowodu poprawności nie znam, ale może nim być chociażby 7 na 7 zaliczonych testów, w których Łukasz nie przekroczył czasu xp.
zanotowane.pldoc.pisz.plpdf.pisz.plalbionteam.htw.pl
zanotowane.pldoc.pisz.plpdf.pisz.plcichooo.htw.pl
|
|
|
|
