1085. Jesienne porządki [ETI07E5]

[marian_sof]

Witam. Otóż mam taki problem. Ni diabła nie mogę się zmieścić w czasie od drugiej próby. Dla pierwszej próby jest limit czasu 1s, mieszczę się bez problemu, natomiast w pozostałych próbach, gdzie limit czasu wynosi 3s, nie daje rady. Co ciekawe, nie ważne jakbym optymalizował kod, wymyślał różne sposoby, czas nie zmienia się nawet o 0.01s. I wynosi dla 2 - 2,99s, a dla 3 i 4 - 6,98s. Nie wiem widocznie idę w złym kierunku, albo w którymś momencie sie zapętla, ale to wtedy chyba nie było by podanych tych wyników? Jak to z tym wszystkim jest? Czy ktoś rozwiązywał te zadanie i może mi dać jakieś małe wskazówki? Pozdrawiam i czekam na odpowiedzi

[gribnick]

Dla pewności: Czy w tym zadaniu wynik, a dokładniej współrzędna x ma być liczbą całkowitą?

[neo_cocacola_sof]

przeszedl mi 2 pierwsze testy,ale nastepne 2 bledna odpowiedz;/ z czym moze byc problem?

[phson175]

Heh, ja mam dobre wyniki dla przykładowych testów i tych w tym temacie, ale mam tylko zaliczony jeden test ;/.
Moje rozwiązanie jest bardzo proste, ale nie wiem czy poprawnie zakładam, że najkrótsza droga będzie wtedy gdy współrzędna x ogniska będzie jedną ze współrzędnych x punktów wprowadzonych na wejściu.
Algorytm sprowadza się do obliczania sum dróg względem każdego x zbioru punktów na wejściu i wybraniu najmniejszej.

[phson175]

Można prosić o jakieś testy.

[narbej]

Revive this topic?

The last reply to this topic is now over 2042 days old. Your reply will bump the topic to the top of its list and notify anyone previously involved in the conversation.

Are you sure you want to continue this old conversation?

Nie jestem pewny czy chcę/powinienem kontynuować, ale... pojawił się nowy komentarz pod zadaniem. Oto wszystkie ye komentarze [zostaną tam, pod zadaniem, skasowane] :

2015-09-01 02:30:50 Adrian Szewczyk
@Arkadiusz Nowaczynski bez sortowania da się dość prawie do 0.00 ; )

Ostatnio edytowany: 2015-09-01 02:37:33
2014-03-10 23:34:46 Arkadiusz Nowaczyñski
Chciałem zrozumieć i wysłać liniowy algorytm do tego zadania, ale okazało się że logarytmiczne sortowanie dało mi prawie najlepszy czas
2012-02-24 15:13:22 Micha³ ¯muda
Podejrzewam, że liczy się tylko droga pokonana, gdy Jasio porusza się z ładunkiem na taczce.
2011-05-31 22:35:34 Lupus Nocawy
W szczególności ani treść ani przykłady nie precyzują jak należy rozwiązać taki test:
2
0 1
0 2
Aby sędzia zaakceptował rozwiązanie, należy dla takiego testu wypisać:
0 3
2011-05-31 22:35:06 Lupus Nocawy
To zdanie jest trochę niejednoznacznie sformułowane.
Już po przykładzie widać, że coś jest nie tak.

Rozwiązanie nie ma nic wspólnego z długością drogi, którą Jaś musi pokonać.
Żeby rozwiązać to zadanie, należy znaleźć punkt na głównej alei, którego suma odległości od wszystkich kopców jest najmniejsza, oraz tą sumę.
(Odległości rozumiane oczywiście w metryce rzeki).

Przykładowo, dla testu:
2
0 1
2 1
rozwiązaniem jest:
0 4
Natomiast najkrótsza droga jaką musiałby przebyć Jaś, gdyby mógł poruszać się jedynie po alejkach, ma długość 5 (Jaś startuje w punkcie (2,1), wędruje do punktu (2,0), następnie do punktu (0,0), następnie do (0,1) i z powrotem do (0,0)).

No chyba że Jasiu potrafi się teleportować do kupek liści i musi przebywać drogę jedynie w jedną stronę...

Ostatnio edytowany: 2011-05-31 23:10:57
2010-07-12 13:26:40 Micha³ Wo¶
Jasiu odwiedza kolejne kupki liści po kolei tak jak podane na wejściu? czy po kolei, tak jak idzie?

Ostatnio edytowany: 2010-07-13 21:55:33

[narbej]

2015-09-01 02:30:50 Adrian Szewczyk
@Arkadiusz Nowaczynski bez sortowania da się dość prawie do 0.00 ; )

Prawie dojść a dojść to nie to samo. W zadaniach tego typu ranking jest prawie doskonały, ale uwzględnia tylko pierwsze zgłoszenie [danego uzera] najwyżej punktowane - tu max 100 pkt. Jednak jest już co najmniej jeden wynik nie prawie ale dokładnie 0.00:
http://pl.spoj.com/status/ETI07E5,narbej/ id zgłoszenia: 15032990
Jednak uzyskałem taki czas nie sortowaniem ani nie algorytmem liniowym [jest taka możliwość?], tylko jednym z tu wymienionych, chociaż to też prawie sortowanie:
http://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/Selekcja
http://edu.i-lo.tarnow.pl/inf/alg/001_search/0042.php
+fast i - fast o

[przemek625]

Jak wyznaczyć punkt ogniska?

Wpadłem na pomysł aby patrzeć tylko na współrzędną x oraz ustalić liczbę k-współrzędna szukanego ogniska k należy do przedziału podanych współrzędnych x. czyli jak np: współrzędne x_{i} dla kolejnych par to:1,2,3,5. to k należy do przedziału od 1 do 5.

Sprowadza się to do policzenia min(|x_{1}-k|+...|x_{n}-k|). Czyli dużo roboty, bo trzeba po koli każdą liczbę z przedziału k sprawdzać i wsadzać do jakiegoś wektora potem wybrać min.

Czy jest to poprawny sposób rozwiązania tego zadania? Czy da się to jakoś szybciej zrobić? Jakieś pomysły?

[narbej]

W prawym górnym rogu okna są cztery ikony. Druga od lewej - lupa, służy do wyszukiwania, a okazuje się, że jest tu już wątek o tym zadaniu z cennymi podpowiedziami.