Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Temat: [BAK] Ubogie testy
https://easyupload.io/72s7c1
Paczka z pięcioma folderami - g1, g2, g3, g4, g6 odpowiadającym kolejno testom spełniającym warunki wymienione w subtaskach o odpowiadających numerach. Po 100 testów w każdej paczce. Potwierdzać można oczywiście jakieś podzbiory
Paczka z pięcioma folderami - g1, g2, g3, g4, g6 odpowiadającym kolejno testom spełniającym warunki wymienione w subtaskach o odpowiadających numerach. Po 100 testów w każdej paczce. Potwierdzać można oczywiście jakieś podzbiory
Potwierdzam
Potwierdzam i dorzucam dwa testy z samymi znakami zapytania. Częściowo ukryłem output.
N=M=25 https://pastebin.com/1qBpLLPW
output:
53...43/6...
N=M=200 https://pastebin.com/NWdv6iJF
output:
79...57/1...
N=M=25 https://pastebin.com/1qBpLLPW
output:
53...43/6...
N=M=200 https://pastebin.com/NWdv6iJF
output:
79...57/1...
Potwierdzam nowe testy :D
Nie ma to jak zbugować kod po wygenerowaniu poprawnych outów na forum xddd. Nawet nie wiem co mogłem zrobić aby tak zwalić, ale RIP 2 punkty
Mój proces rozwiązywania zadania:
Po dobrym zrozumieniu procesu narysowałem sobie na kartce 14 drzew, które rozróżniały sąsiadów pola, któremu liczę wynik. Każde drzewo jest postaci np. T(2, {T(3, {T(4), T(3, {...})})}) czyli "wierzchołek stopnia 2 z nieśmiertelnym ojcem oraz dzieckiem stopnia 3, które ma jedno dziecko stopnia 4 i jedno dziecko stopnia 3, które ...". Kod to łączył w około 60 możliwych drzew z dodatnim wynikiem dla korzenia - gdzie już korzeniem jest pole, którego wynik dodam do globalnego wyniku. Po żmudnej implementacji miałem około 180k bitowych patternów pustych i zakazanych pól, co dawało złożoność O(N*M*180'000) i wystarczało tylko dla N, M <= 25. Szybko poprawiłem do 60k patternów i utknąłem na wiele godzin. Po zrobieniu kilku innych zadań wróciłem w niedzielę wieczorem do BAK i udało mi się zmergować podobne patterny, by mieć niecałe 7k przez Wiele godzin nie umiałem poprawić, ale w końcu pomergowałem jakieś podobne patterny i mam niecałe 7k, śmiga (na SIO 1.5s preprocessing i drugie tyle na przejście grida 200x200). Okropne zadanie, bardzo fajnie mi się nad nim pracowało.
Po dobrym zrozumieniu procesu narysowałem sobie na kartce 14 drzew, które rozróżniały sąsiadów pola, któremu liczę wynik. Każde drzewo jest postaci np. T(2, {T(3, {T(4), T(3, {...})})}) czyli "wierzchołek stopnia 2 z nieśmiertelnym ojcem oraz dzieckiem stopnia 3, które ma jedno dziecko stopnia 4 i jedno dziecko stopnia 3, które ...". Kod to łączył w około 60 możliwych drzew z dodatnim wynikiem dla korzenia - gdzie już korzeniem jest pole, którego wynik dodam do globalnego wyniku. Po żmudnej implementacji miałem około 180k bitowych patternów pustych i zakazanych pól, co dawało złożoność O(N*M*180'000) i wystarczało tylko dla N, M <= 25. Szybko poprawiłem do 60k patternów i utknąłem na wiele godzin. Po zrobieniu kilku innych zadań wróciłem w niedzielę wieczorem do BAK i udało mi się zmergować podobne patterny, by mieć niecałe 7k przez Wiele godzin nie umiałem poprawić, ale w końcu pomergowałem jakieś podobne patterny i mam niecałe 7k, śmiga (na SIO 1.5s preprocessing i drugie tyle na przejście grida 200x200). Okropne zadanie, bardzo fajnie mi się nad nim pracowało.