Olimpiada Informatyczna - prośba o rozwiązanie Różnorodności (nie kod, "sposób")

pytanie zadane 19 stycznia 2018 w C i C++ przez yossarian22 Początkujący (340 p.)
edycja 19 stycznia 2018 przez yossarian22

Witam, czy jest ktoś w stanie opisać sposób rozwiązania, obserwacje itd, dla zadania Różnorodność z tegorocznej OI https://szkopul.edu.pl/problemset/problem/eHGwrk9xShVF-z_2f7K4Yyb_/statement/

Z góry dziękuję, pozdrawiam

komentarz 19 stycznia 2018 przez Przemysław Obywatel (1,510 p.)

Rozumiesz polecenie i nie wiesz jak je zaprogramować, czy nie rozumiesz polecenia?

komentarz 19 stycznia 2018 przez yossarian22 Początkujący (340 p.)

Rozumiem polecenie i nie wiem jak zaprogramować w najlepszej możliwej złożoności czasowej przy podanym zakresie pamięci.

1	komentarz 19 stycznia 2018 przez yossarian22 Początkujący (340 p.) Na ten moment próbowałem dwóch sposobów: Lecenie "wężykiem" każdego kwadraciku, oraz lecenie "kolumnami". Żadne nie spełnia wymogów czasowych.

1 odpowiedź

odpowiedź 19 stycznia 2018 przez Przemysław Obywatel (1,510 p.)

Cześć :)
Sprawa wygląda tak:

Masz tablicę n na m i w niej wycinek k na k. Obliczenie różnorodności konkretnego wycinka jest raczej proste: lecisz kolejno po jego wszystkich polach, i jeśli wartość tego pola jest różna od wszystkich poprzednich wartości w tym wycinku, to zwiększasz różnorodnośc o 1.

Ale jak wyznaczyć wycinek z największą różnorodnością?
Po pierwsze powinieneś najpierw przyjąć, że max_różnorodność = różnorodnośc_pierwszego_wycinka, a później dla każdego wycinka sprawdzać czy jego różnorodność jest większa niż max_różnorodność. Jeśli tak to max_różnorodność = różnorodność_tego_wycinka.

Ale jak przelecieć pętlą po WSZYSTKICH możliwych wycinkach?
Hmmm... wiem jak to zrobić, ale strasznie ciężko mi zebrać myśli, żeby ci to wytłumaczyć ;)
Pomyśl sam, jak masz jakiś pomysł to napisz i spróbujemy ;)