Ребята, а какая асимптотика будет у данного решения ?
https://www.hackerrank.com/challenges/the-grid-search/problem
Вообщем, имплементация следующая:
1. заполняю массив из хешей шаблона по строкам
2. делаю деревья символов, имеющие следующий вид:

struct Grid_Leaf {
   long n;
   long sum_last_n;
   bool is_root;
   int depth;
   Grid_Leaf* prev;
   Grid_Leaf* next;
   int row;
};

прохожу по всей матрице и создаю дерево, состоящее из n(кол-во строк в матрице) ветвей 1 уровня, корень - 0 уровня.
считаю хеши sum_last_n элементов
если она совпадает с хешем первой строки в паттерне, то записываю это как потеншиал матчер
и потом уже прохожу по всем потенциальным совпадениям и строка за строкой используя дерево сравниваю хеши в нужных столбцах

Насколько я понимаю, то асимптотика будет O(n * m + x * y), где n, m - это кол-во строк и столбцов в G, а x, y - кол-во столбцов и строк в шаблоне

Я правильно понимаю ?

не касаясь вопроса о практической применимости моделей МЛ к человеку - тезис опровергните

переделал кстати решение на хеши, намного красивей код получился.

почему ваше утверждение "надо учиться, играя с более сильным противником" не проходит проверку предсказанием?

тезис не имеет отношения к вопросу, значит нет необходимости в подтверждении или опровержении

имеет, это прямое следствие гипотезы "чтоб научиться играть в игру, надо играть против того, кто немного лучше тебя"

вот только не в тех условиях

так бывает, когда шуршишь бумажками и не научился ставить эксперименты

struct Grid_Leaf {
   long n;
   long sum_last_n;
   bool is_root;
   int depth;
   Grid_Leaf* prev;
   Grid_Leaf* next;
   int row;
};

вы делаете что-то безумно сложное, если вы хотите посчитать хеш прямоугольника, возьмите полиномиальный хеш, а поскольку он линеен, будет работать формула в духе префикс-суммы, связывающая хеш прямоугольника и хеши четырех "префиксов" от координат (0, 0)

к слову, обучение в играх с нулевой суммой с самим собой тоже подходит под определение, ведь учитывается обучение с обеих сторон

показывай свои эксперименты

мммм. можете объяснить ?
хеши четырех "префиксов" от координат (0, 0) ?

ну как hash(l..r) == hash(0..r) - hash(0..l-1) только в двумерном случае

hash(xl..xr, yl..yr) = hash(0..xr, 0..yr) - hash(0..xr, 0..yl-1) - hash(0..xl-1, 0..yr) + hash(0..xl-1, 0..yl-1)

сорри, а почему вы используете термин префикс ?

потому что это префикс

Что-то хакерранк с телефона не открыть (бросает на страницу авторизации быстрее, чем успеваю прочитать условие

просят искать подматрицу матрицы

как подстроку, только двумерный случай

а..... это из дискретной математики...