ПК
Вход — пиксели (0 или 1), выход — буквы, полный двудольный граф
Size: a a a
2020 July 30
VD
Кажется, будет выдавать много false-positive результатов, но попробую реализовать, спасибо
Мб вертексный шрифт скейлить до размера области и сравнивать
VD
Отрендерить его и сравнить
/¯
Ну т.е. можно это определять без нейросетей со скрытыми слоями?
можно SVM'ом со скрытыми переменными
ПК
Где можно почитать про этот вид SVM?
VD
Где можно почитать про этот вид SVM?
https://en.wikipedia.org/wiki/Support_vector_machine
Думаю это оно
Думаю это оно
/¯
Где можно почитать про этот вид SVM?
простите http://oneweirdkerneltrick.com
/¯
Где можно почитать про этот вид SVM?
просто надо будет ядро придумывать
2020 July 31
DK
А можно как-то за O(log n) в онлайне отвечать на запрос: сколько отрезков из n отрезков полностью лежат в [l;r]? Я придумал только для оффлайна в сканлайне считать с мапами
Ш
А можно как-то за O(log n) в онлайне отвечать на запрос: сколько отрезков из n отрезков полностью лежат в [l;r]? Я придумал только для оффлайна в сканлайне считать с мапами
а l, r до какого ?
MB
А можно как-то за O(log n) в онлайне отвечать на запрос: сколько отрезков из n отрезков полностью лежат в [l;r]? Я придумал только для оффлайна в сканлайне считать с мапами
Мб можно и проще, но вот это должно работать.
Отрезок [L, R] лежит в отрезке [X, Y] если X <= L && R <= Y
Это стандартный запрос на прямоугольнике, вида "дана точка, сколько точек лежат правее и ниже?" (мы ставим отрезку [A, B] точку с координатами (A, B))
Отвечать на запросы к прямоугольникам онлайн можно, например, построив лес персистентных ДО (одно на каждый горизонтальный уровень, которое для каждой вертикальной полосы хранит количество точек в этой полосе, ниже этого уровня)
Отрезок [L, R] лежит в отрезке [X, Y] если X <= L && R <= Y
Это стандартный запрос на прямоугольнике, вида "дана точка, сколько точек лежат правее и ниже?" (мы ставим отрезку [A, B] точку с координатами (A, B))
Отвечать на запросы к прямоугольникам онлайн можно, например, построив лес персистентных ДО (одно на каждый горизонтальный уровень, которое для каждой вертикальной полосы хранит количество точек в этой полосе, ниже этого уровня)
K
А можно как-то за O(log n) в онлайне отвечать на запрос: сколько отрезков из n отрезков полностью лежат в [l;r]? Я придумал только для оффлайна в сканлайне считать с мапами
я тоже первым делом про оффлайн подумал
K
онлайн нужен?
MB
Если офлайн, то можно взять ту же фигню с прямоугольниками, но вместо леса перс-до обычный сканлайн с обычным ДО
ПК
А можно как-то за O(log n) в онлайне отвечать на запрос: сколько отрезков из n отрезков полностью лежат в [l;r]? Я придумал только для оффлайна в сканлайне считать с мапами
Ну, вроде можно деревом отрезков:
Храним в каждой вершине помимо ответа количество отрезков с левой границей в соотв. вершине отрезке и с правой границей в каждом из соседних справа отрезках.
Получать ответ так: ответ в левом ребёнке + ответ в правом ребёнке + количество отрезков с левой границей в левом ребёнке и правой границей в правом ребёнке (это, кажется, можно посчитать рекурсивно).
Храним в каждой вершине помимо ответа количество отрезков с левой границей в соотв. вершине отрезке и с правой границей в каждом из соседних справа отрезках.
Получать ответ так: ответ в левом ребёнке + ответ в правом ребёнке + количество отрезков с левой границей в левом ребёнке и правой границей в правом ребёнке (это, кажется, можно посчитать рекурсивно).
KK
Можно еще за log^2 c добавлением отрезков совсем тупо: в вершине ДО храним концы всех вершин, начинающихся в пределах данной, к примеру, в дерамиде. Теперь спускаемся в какую-то конечную вершину и проверяем сколько вершин находится слева
DK
Можно еще за log^2 c добавлением отрезков совсем тупо: в вершине ДО храним концы всех вершин, начинающихся в пределах данной, к примеру, в дерамиде. Теперь спускаемся в какую-то конечную вершину и проверяем сколько вершин находится слева
Судя по тому, что он спрашивает именно про log, а не квадрат, то он знает это
CC
Мб можно и проще, но вот это должно работать.
Отрезок [L, R] лежит в отрезке [X, Y] если X <= L && R <= Y
Это стандартный запрос на прямоугольнике, вида "дана точка, сколько точек лежат правее и ниже?" (мы ставим отрезку [A, B] точку с координатами (A, B))
Отвечать на запросы к прямоугольникам онлайн можно, например, построив лес персистентных ДО (одно на каждый горизонтальный уровень, которое для каждой вертикальной полосы хранит количество точек в этой полосе, ниже этого уровня)
Отрезок [L, R] лежит в отрезке [X, Y] если X <= L && R <= Y
Это стандартный запрос на прямоугольнике, вида "дана точка, сколько точек лежат правее и ниже?" (мы ставим отрезку [A, B] точку с координатами (A, B))
Отвечать на запросы к прямоугольникам онлайн можно, например, построив лес персистентных ДО (одно на каждый горизонтальный уровень, которое для каждой вертикальной полосы хранит количество точек в этой полосе, ниже этого уровня)
Что значит офлайн и онлайн в данном случае?
KK
Что значит офлайн и онлайн в данном случае?
Все запросы сразу предоставлены или постепенно приходят
CC
Все запросы сразу предоставлены или постепенно приходят
Ааа, спс