English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
potwierdzam to, co napisał Grzegorz.
Jak dla mnie testy nie1 oraz nie2 są niepoprawne. Np. w teście nie1 pierwszy samochód to (2,0),(3,2) (wymiary 1x2), a w końcowym ustawieniu to już (0,0),(1,1) (wymiary 1x1). Po przeparkowaniu zmienił swój rozmiar, a tak chyba nie powinno być czy czegos nie ogarniam?
Czy ktos mogłby pokazać prawidłowe rozwiazanie dla testu 32 ?
10 10
5 2
0 6
5 2
1 3
4 3
3 8
8 5
0 2
5 2
9 0
?
10 10
5 2
0 6
5 2
1 3
4 3
3 8
8 5
0 2
5 2
9 0
?
potwierdzam testy z tymi 37 zmianami. W kolejności po kolei te testy które nie przechodzą, a nie alfabetycznie (zastanawiałem się o co chodzi, że mi 32 nie działa a wam od 1000+ zaczynają nie działać :D)
32
35
139
267
306
425
470
522
703
1114
1160
1223
1338
1405
1516
1556
2221
2761
2827
2882
3086
3110
3116
3131
3407
3519
3650
3701
3818
4183
4237
4267
4315
4399
4421
4527
4897
32
35
139
267
306
425
470
522
703
1114
1160
1223
1338
1405
1516
1556
2221
2761
2827
2882
3086
3110
3116
3131
3407
3519
3650
3701
3818
4183
4237
4267
4315
4399
4421
4527
4897
Mój program potwierdza :)
Witam, przesyłam 6 małych testów poprawnościowych napisanych ręcznie. Testy dają taką odpowiedź, jaką mają nazwę.
http://speedyshare.com/w6US6/small.zip
Sprawdźcie, czy są dobre.
http://speedyshare.com/w6US6/small.zip
Sprawdźcie, czy są dobre.
@Krzysztof Wicher również potwierdzam :D
A też sobie potwierdzę i podobnie jak reszta mam 37 różnic na testach Grześka.
@Krzysztof Wicher
Albo mam dobre, albo nie niszczy :P
Albo mam dobre, albo nie niszczy :P
Mi to wszystkie heury niszczy:
2 100
98 1
97 96
TAK
2 100
99 98
2 1
TAK
2 100
99 97
5 1
TAK
2 100
98 1
97 96
TAK
2 100
99 98
2 1
TAK
2 100
99 97
5 1
TAK
Mógł by ktoś podzielić się rozwiązaniem testu 1628 z paczki Grzegorza
Mnie też nie udało się wpaść na rozwiązanie z grafem :)
Szukam najtańszej bazy przestrzeni Z_2^n, tak jak wyżej piszecie. Pierwszy brut to Gauss, O(n^5). Potem zacząłem trzymać zbiór wektorów taki, że żadne dwa nie zaczynają się w jednym punkcie - to daje chyba O(n^3), w każdym razie przechodzi już testy (chociaż ja miałem taki test, że działało u mnie w 4s). Ale można zrobić jeszcze tak, że również żadne dwa nie kończą się w jednym punkcie. Wtedy można pokazać, że nowy wektor jest liniowo zależny od tego "kanonicznego zbioru wektorów" tylko wtedy, jeśli jest sumą kilku rozłącznych elementów tego zbioru (tzn. np. [3,7] = [3,5] + [6,6] + [7,7]). A to można sprawdzać w O(1) jak się zrobi prostą strukturę, której wyliczenie zajmuje O(n), więc można ją przeliczać po każdym wstawieniu wektora. Łącznie mamy O(sort + n^2) ;)
TL;DR: przekombinowałem
Szukam najtańszej bazy przestrzeni Z_2^n, tak jak wyżej piszecie. Pierwszy brut to Gauss, O(n^5). Potem zacząłem trzymać zbiór wektorów taki, że żadne dwa nie zaczynają się w jednym punkcie - to daje chyba O(n^3), w każdym razie przechodzi już testy (chociaż ja miałem taki test, że działało u mnie w 4s). Ale można zrobić jeszcze tak, że również żadne dwa nie kończą się w jednym punkcie. Wtedy można pokazać, że nowy wektor jest liniowo zależny od tego "kanonicznego zbioru wektorów" tylko wtedy, jeśli jest sumą kilku rozłącznych elementów tego zbioru (tzn. np. [3,7] = [3,5] + [6,6] + [7,7]). A to można sprawdzać w O(1) jak się zrobi prostą strukturę, której wyliczenie zajmuje O(n), więc można ją przeliczać po każdym wstawieniu wektora. Łącznie mamy O(sort + n^2) ;)
TL;DR: przekombinowałem
Potwierdzam wszystkie testy (z 37 poprawkami).
Potwierdzam ;_;