e-olymp 5282. Седловые точки

Задача. Седловые точки

Задана матрица $K$, содержащая $n$ строк и $m$ столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.
Найдите количество седловых точек заданной матрицы.

Входные данные

Первая строка содержит целые числа $n$ и $m$. $(1 \leq n, m \leq 750)$. Далее следуют $n$ строк по $m$ чисел в каждой. $j$-ое число $i$-ой строки равно $k_{ij}$. Все $k_{ij}$ по модулю не превосходят $1000$.

Выходные данные

Выведите количество седловых точек.

Тесты

Ввод Вывод
1 2 2
0 0
0 0
4
2 2 2
1 2
3 4
1
3 5 5
100 -100 100 1000 110
10 -1000 100 -1000 110
100 -1000 100 100 110
1000 -1000 1000 1000 100
1000 -1000 1000 1000 -1000
1
4 4 4
1000 1000 100 100
1000 1000 1000 1000
100 100 100 1000
100 1000 1000 1000
4
5 2 3
1 -1 1
0 -1 0
2
6 5 1
-1
0
-1
0
-1
2
7 4 2
1 2
-2 1
-1 2
-2 -1
1
8 3 3
5 1 3
3 1 2
1 1 2
3
7 3 3
5 2 3
3 4 2
1 8 2
0

Решение

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

Вариант решения за $O\left(n^2\right)$

Для этого мы просто сравниваем каждый максимум с каждым минимумом и считаем их совпадения. В этом случае алгоритм будет выполнятся за $O(n^2)$, где $n$ это наибольшая из длин массивов. Это значит что при достаточно больших массивах программа будет работать непозволительно долго. Но такой подход достаточно прост в реализации и интуитивно понятен.

Вариант решения за $O\left(n\log n\right)$

В этом случае мы сортируем массивы, для установления взаимосвязи между элементами в них. А далее заведя два указателя на элементы массивов проверяем на равенство только не меньшие элементы от текущих в разных массивах. Если равных элементов окажется несколько подряд, то их количество будет равно произведению количества их повторений в каждом из массивов. Дойдя до конца одного из них нужно не забыть проверить остались ли в другом массиве равные последнему в пройденном элементы. Проверять стоит лишь не меньшие элементы. Таким алгоритмом мы проверяем совпадения линейно за $O(n)$, где $n$ это наибольшая из длин массивов, но для него необходимо отсортировать оба массива за $O(n\log n)$. Таким образом мы получаем вычислительную сложность $O(n\log n)$, что уже быстрее предыдущего варианта.

8 thoughts on “e-olymp 5282. Седловые точки

  1. Правильно ли вы асимптоты написали? Для первого наверно было бы правильно написать [latex]O(nm)[/latex], а во втором у вас сортировка слиянием для массива длинной [latex]n[/latex], так что у вас асимптота второго кода будет ну как минимум [latex]O(n\log n)[/latex], если я не прав прошу вас предоставить анализ времени работы.

    • Большое спасибо Руслан, соглашусь во втором случае оценка будет $O(n\log n)$, давайте попробуем порассуждать.
      Насколько я помню оценка делается с точностью до константы.
      В первом случае, выполнив оценку сверху и выбрав за $n$ максимум из $n$ и $m$, имеем вычислительную сложность $O(n^2)$.
      Во втором случае вычислительная сложность будет $O(n\left(\log n + 1\right) + m\left(\log m + 1\right))$. Из $n$ и $m$ выберем максимум и обозначим за $n$, имеем:
      $O(n\left(\log n + 1\right) + n\left(\log n + 1\right)) = O(2n\left(\log n + 1\right))$.
      Отбросив константы имеем $O(n\log n)$.
      Возможно в этих рассуждениях я допустил ошибку, подскажите, где?

  2. Поскольку у вас нет возможности корректировать свои комментарии, я позволил себе внести исправления. Нужно так — \log n, а не logn. Иван, исправьте, пожалуйста в тексте работы.
    Слитно или раздельно? И Иван и Руслан сделали по ошибке на эту тему. Посмотрите пожалуйста эту и эту статьи.

Добавить комментарий