English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
A NIE, TO iostreams, MOŻNA SIĘ ROZEJŚĆ.
Potwierdzam i dziękuję Kacprze, ino mi 17 sekund działa :P
Jest to pewnie zamierzchłość z czasów gdy istniały tylko grupy A i B, co powodowało że ostatni dzień składał się z 4 zadań. Najwidoczniej ktoś zapomniał poprawić :(
potwierdzam testy Kacpra
potwierdzam
Proszę bardzo @Marcin.
https://drive.google.com/file/d/1AwLg0_6z4sP3d5ESrZfayJxXpJ12vftt/view?usp=sharing
https://drive.google.com/file/d/1AwLg0_6z4sP3d5ESrZfayJxXpJ12vftt/view?usp=sharing
Co do powyższych pytań o poprawność, to pozwolę sobie wspomnieć niezwykle pomocne stwierdzenie, że jak się zrozumie o co chodzi z tym wypukłym DP, to oba te claimy są oczywiste xD
Potwierdzam, ale jak ktoś zrobi większy test, to jeszcze chętniej przyjdę i potwierdzę.
@Jakub Kądziołka
> dlaczego zbiór wartości k, dla których odpowiedź <= x, jest przedziałem
Niech f(k) będzie funkcją wyniku od k. Gdybyśmy nie zwracali uwagi na k, to optymalnie jest wziąć tańszy obraz z każdej pary - powiedzmy, że w takiej sytuacji wybralibyśmy k0 obrazów Alicji. Twierdzimy teraz, że f(k) jest nierosnąca dla k <= k0 i niemalejąca dla k >= k0. Dlaczego jest nierosnąca dla k <= k0? Jeśli mamy optymalny ciąg dla f(k) dla k < k0, to na pewno możemy zamienić w nim jeden obraz Boba na tańszy obraz Alicji (bo wzięliśmy k obrazów alicji, a jest k0 par z tańszymi od Boba). Jeśli go podmienimy to dostaniemy niegorsze rozwiązanie dla k+1, zatem f(k) >= f(k+1) dla każdego k <= k0. Dla k >= k0 analogicznie. W takim razie jak binsearchujemy, to przedział wartości k będzie spójny.
> dlaczego rozwiązanie zachłanne działa
Nie mam tu szybkiego argumentu niestety, wyszło po dłuższym kminieniu że "powinno być OK", więc naklepałem go w O(n^2 log n) i sprawdziłem, że działa xd.
> dlaczego zbiór wartości k, dla których odpowiedź <= x, jest przedziałem
Niech f(k) będzie funkcją wyniku od k. Gdybyśmy nie zwracali uwagi na k, to optymalnie jest wziąć tańszy obraz z każdej pary - powiedzmy, że w takiej sytuacji wybralibyśmy k0 obrazów Alicji. Twierdzimy teraz, że f(k) jest nierosnąca dla k <= k0 i niemalejąca dla k >= k0. Dlaczego jest nierosnąca dla k <= k0? Jeśli mamy optymalny ciąg dla f(k) dla k < k0, to na pewno możemy zamienić w nim jeden obraz Boba na tańszy obraz Alicji (bo wzięliśmy k obrazów alicji, a jest k0 par z tańszymi od Boba). Jeśli go podmienimy to dostaniemy niegorsze rozwiązanie dla k+1, zatem f(k) >= f(k+1) dla każdego k <= k0. Dla k >= k0 analogicznie. W takim razie jak binsearchujemy, to przedział wartości k będzie spójny.
> dlaczego rozwiązanie zachłanne działa
Nie mam tu szybkiego argumentu niestety, wyszło po dłuższym kminieniu że "powinno być OK", więc naklepałem go w O(n^2 log n) i sprawdziłem, że działa xd.
Osobiście wolę format jedna paczka z testami - jeden temat.
Można też na samym początku wykonać transformację, która (troszkę) ułatwia tego dynamika.
Całe to zadanie odbywa się w grupie addytywnej mod p, więc zastosowanie dowolnego automorfizu tej grupy na początku nie zmienia odpowiedzi. Możemy w szczególności zrobić tak (przykład dla p=11):
0 -> 0
2 -> 1
4 -> 2
6 -> 3
8 -> 4
10 -> 5
1 -> 6
3 -> 7
5 -> 8
7 -> 9
9 -> 10
To przekształcenie to po prostu x -> (6*x) % 11 czyli w jakims sensie x -> x/2 i po jego wykonaniu parzyste liczby przechodzą na <= 5, a nieparzyste na > 5. Dostajemy nowe zadanie, w którym zamiast o parzyste przedziały pytamy o <= 5 i to jest trochę mniej zamotane.
Całe to zadanie odbywa się w grupie addytywnej mod p, więc zastosowanie dowolnego automorfizu tej grupy na początku nie zmienia odpowiedzi. Możemy w szczególności zrobić tak (przykład dla p=11):
0 -> 0
2 -> 1
4 -> 2
6 -> 3
8 -> 4
10 -> 5
1 -> 6
3 -> 7
5 -> 8
7 -> 9
9 -> 10
To przekształcenie to po prostu x -> (6*x) % 11 czyli w jakims sensie x -> x/2 i po jego wykonaniu parzyste liczby przechodzą na <= 5, a nieparzyste na > 5. Dostajemy nowe zadanie, w którym zamiast o parzyste przedziały pytamy o <= 5 i to jest trochę mniej zamotane.
Potwierdzam, również widzę dodatkowy in o nazwie ".in"
Potwierdzam, ale albo to ja mam zwidy, albo tu jest 30 001 in'ów (jeden dodatkowy bez numerka o nazwie ".in").
Potwierdzam
Potwierdzam