Задачава не успеа никој од 150+ ученици да ја реши комплетно, дали ќе добиеме некој hint

Без мемоизација решението беше O(L * K * P), односно 2D sliding window со проверка на сите точки дали припаѓаат во опсегот [x, x+N] и [y, y+M]. Мене ми текна една идеја со DP матрица и услов "imaTochka(x1, y1, x2, y2) = (dp[x2][y2] - dp[x1][y1])>0" ама немав време да ја испробам.

This message was edited 3 times. Last update was at 28/02/2016 17:52:33

Решението со мемоизација со матрица ќе го надмине меморискиот лимит. Во најлош случај, ќе имаме 1*10^8 полиња, ако работиме со int матрица секое поле зафаќа 4 бајти меморија, па добиваме вкупна потрошена меморија од над ~381.5 мегабајти. Исто така се приметува дека за празна подматрица (односно подматрица во која нема погодувања) е многу лесно да се најдат сите можни комбинации, тоа може да се заврши во O(1) време со едноставна формула. Според ова, мојата идеја е да се подели матрицата на разделени интервали и да се најдат посебно за нив сите можни комбинации, па да се соберат. Секако, нема да ја чуваме во меморија целата N*M матрица, туку одвоените интервали. Останува уште да се напише кодот.

This message was edited 1 time. Last update was at 29/02/2016 14:41:50