|
|
|
|
|
|
|
Вернуться
| 1 Тер-Саркисов Богдан Олегович, 02 декабря 2021 г. 23:19:11 | |
Составим уникальный список из x и y значений по всем n точкам. Далее построим двудольный граф, где вершинами в первой доле будут координаты x, вершинами во второй доле будут координаты y, а точки будут задавать ребра x-y. Требуется отметить наименьшее число ребер так, чтобы каждая из вершин долей графа была концом хотя бы одного отмеченного ребра.
Пусть мы сначала отметили некоторые ребра произвольным образом так, чтобы никакая пара ребер не была смежной и чтобы при этом нельзя было отметить еще одно несмежное ребро. То есть построили какое-то максимальное паросочетание. Пусть количество этих ребер равно Z, а размеры долей графа равны X и Y соответственно. Тогда количество вершин, которые не являются концами ребер паросочетания, для первой доли равно X-Z, а для второй доли Y-Z. Далее требуется отметить ребра, концами которых являются неиспользованные вершины, а каждая такая вершина требует ровно одно ребро, поскольку использовать сразу две вершины при использовании одного ребра уже нельзя. Получается, что мы отметили Z+(X-Z)+(Y-Z)=X+Y-Z ребер. Далее заметим, что величина X+Y в этом выражении постоянна, а значение X+Y-Z требуется минимизировать. Получается, что нужно максимизировать значение Z, что сводит эту задачу к поиску наибольшего паросочетания (или максимального по размеру паросочетания). Существует алгоритм для поиска наибольшего паросочетания с асимптотикой O(E*sqrt(V)), где E - количество ребер, V - количество вершин. В нашем случае O(E) = O(V) = O(n), то есть задача решается за O(n*sqrt(n)).
|
|
|
| 2 Терентьев Михаил Павлович, 08 октября 2021 г. 14:21:41 | |
А если задачу свести к такой: Есть двудольный граф. Требуется удалить из него максимальное количество ребер, чтобы для каждой вершины этого графа существовало инцидентное ребро.
Это решается с помощью паросочетаний?
Или, например, можно какой-то dfs запустить, отмечая ребра через одно преимущественно.
Или запустить обход графа по фронту вершин, в текущий момент поддерживая список вершин из одной доли (соответственно, из этих вершин можно попасть во множество вершин второй доли среди необработанных вершин и тд). И начать такой обход нужно с вершин, у которых не более 1 соседа, потому что инцидентные ребра для этих вершин должны быть помечены 100%. А ребра будут отмечаться по мере необходимости. Например, 1-2-3-4-5-6. Ребро 1-2 должно быть отмечено в любом случае, иначе вершина 1 не будет инцидентна ребру. Далее ребро 2-3 не будем помечать. А вот 3-4 уже придется, потому что вершину 3 другим способом не отметишь.
|
|
|
| 3 Черепанв Иван це эс шст шст пят сбк пе эм тчк эм е, 06 октября 2021 г. 21:25:54 | |
|
Так ведь cnt(x)+cnt(y)-1 это не ответ а ключ для сортировки.
|
|
|
| 4 Меньшиков Фёдор Владимирович, 06 октября 2021 г. 19:29:18 | |
|
А вот есть ли тест, заваливающий формулу max(cnt(x), cnt(y))?
|
|
|
| 5 Меньшиков Фёдор Владимирович, 06 октября 2021 г. 19:26:05 | |
|
Иван, такой тест: квадрат 5 на 5 точек, всего 25, горизонталей 5, вертикалей 5. Ответ тоже 5 - можно взять 5 точек по диагонали. Совершенно не cnt(x)+cnt(y)-1=9.
|
|
|
| 6 Черепанв Иван це эс шст шст пят сбк пе эм тчк эм е, 05 октября 2021 г. 23:51:37 | |
|
Я плохо выразился. Нужна не сумма координат x+y а сумма количества точек для данных x и y, cnt(x)+cnt(y)-1
|
|
|
| 7 Меньшиков Фёдор Владимирович, 05 октября 2021 г. 21:45:29 | |
|
Чем-то напомнило задачу 573 НЛО. Та решается через паросочетания.
|
|
|
| 8 Терентьев Михаил Павлович, 05 октября 2021 г. 21:29:47 | |
Например, тест: n=3, p = {(0, 1), (1, 0), (1, 1)}.
Если сортировать по невозрастанию x+y, то отметится сначала точка 3, потом точка 1, потом точка 2.
Но оптимальным решением будет отметить только точки 1 и 2 - через точку 3 станут проходить уже созданные прямые.
Я думал над другим решением:
1) Сначала отметить те точки, которые должны быть отмечены в любом случае. Это "одинокие" точки по x или y. То есть нет других точек с тем же x или y.
2) Среди оставшихся точек отметить те, у которых вертикальная и горизонтальная прямые еще не были нарисованы. Эта жадность ничем не доказывается, а лишь содержит идею о том, что каждый раз будет отмечаться наибольшее количество прямых (вертикальная и горизонтальная), и потребуется в итоге меньше точек, чтобы нарисовать все прямые.
3) Среди оставшихся точек отметить те, у которых ровно одна прямая нарисована.
В некоторых случаях дает правильный ответ, а где-то нет.
|
|
|
| 9 Черепанв Иван це эс шст шст пят сбк пе эм тчк эм е, 05 октября 2021 г. 21:13:49 | |
|
Да, примерно так. Нужно несколько сортировок массива из 1e5 елементов. Зто можно сделать за 1 секунду на языке С. А оптимальность, особенно доказанную,, можно искать годами.
|
|
|
| 10 Терентьев Михаил Павлович, 05 октября 2021 г. 20:58:37 | |
Как я понял, вы предлагаете для каждой точки посчитать:
1) количество точек, у которых такое же значение x
2) количество точек, у которых такое же значение y
3) указатель на первую точку с текущим x в отcортированном списке по x (указатель на точку с тем же x и с наименьшим y)
4) указатель на первую точку с текущим y в отсортированном списке по y (указатель на точку с тем же y и с наименьшим x)
Затем отсортировать точки по x+y и просматривать по уменьшению x+y. А уже зачеркнутые вы имеете в виду те, через которые уже были проведены обе прямые, созданные ранее в результате выделения каких-то точек.
Наверное, всё то же самое можно сделать одной сортировкой: по первому ключу x+y, по второму x или y.
Но будет ли такой алгоритм оптимальным?
|
|
|
| 11 Черепанв Иван це эс шст шст пят сбк пе эм тчк эм е, 05 октября 2021 г. 20:25:13 | |
Считать точки в массив. В этом же массиве хранить прочие аттрибуты точек.
Создать массив указателей на точки и отсортировать его по x. Это позволяет найти, какие точки имеют одинаковый x. Для каждой точки в главном массиве записать число обших точек и указатель на первую из них.
Сделать то же самое по y.
Создать массив указателей на точки и отсортировать его по x+y.
Отмесать точки с наибольшим x+y, пропуская уже зачеркнутые.
|
|
|
| 12 Терентьев Михаил Павлович, 05 октября 2021 г. 19:07:34 | |
|
Имеется n точек на плоскости. Некоторые точки можно выделять. Если точка выделяется, то через неё рисуются вертикальная и горизонтальная прямые. Требуется отметить наименьшее количество точек, чтобы в результате через каждую из точек проходила и вертикальная, и горизонтальная прямые. Ограничения: n < 30000, координаты точек целочисленные, все точки различны.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
