UniLecs #141_1. Math Lottery
UniLecsЗадача: математики придумали свою версию лотереи. На лотерейном билете указана прямоугольная числовая матрица N*M, также есть скрытая часть, где указаны координаты ячейки X. Есть четыре возможных выигрышных направления: вверх/вниз и влево/вправо. Направление считается выигрышным, если все числа в этом направлении от ячейки X строго меньше числа в самой ячейке X. Если ячейка X находится на краю матрицы, то вы автоматически имеете выигрышное направление.
Необходимо выбрать такой лотерейный билет, ктр имеет максимальное общее кол-во выигрышных направлений для всех возможных игровых ячеек (определить только по исходной матрице, скрытая часть ест-но вам неизвестна).
Входные данные: arr - числовая матрицы N*M, эл-ты матрицы - натуральные числа от 1 до 10^3. N,M от 1 до 100.
Вывод: вывести общее кол-во выигрышных направлений для заданной таблицы.
Пример:
[ { 6, 4, 10, 11 },
{ 2, 9, 9, 3 },
{ 5, 4, 5, 4 } ]
Answer: 25
Реализация:
- @mrmeison, JS: 1 балл
Суть решения: Сначала пробигаемся с начала матрица до конца заполняя левое и верхнее направлевление для выйграша. Для этого сравниваем текущее и предыдущее значения по этому направлению и проверяем было ли предыдущее значение выиграшным по этому направлению. Если да, то проверять дальше бессмысленно, то что они в любом случае будут меньше текущего значения, иначе предверяем следующее число в том же направлении. После того как закончим прверять все верхнии и левые значения переходим к нижних правым. Для этого делаем тоже самое но в обратном направлении. Заодно и складываем сумму.
https://gist.github.com/MrMeison/66d6d9eb48b89a5a1414057be7914154
2. Andrew Bystrov, Java: 1 балл
Cамый топорный метод: мы просто идем и для каждой ячейки вычисляем, является ли она выигрышной или нет.
https://gist.github.com/AndrewBystrov/ddcf2d3127bc1991d94a94b0f37e956d
3. @akolosov364, JS: 1 балл
Для нахождения количества выигрышных направлений стоит хранить так же перевернутую матрицу для легкого доступа к массивам. Функция winnings подсчитывает количество выигрышных направлений для массива. Количество выигрышных направлений для ячейки будет равна сумме winnings двух направлений.
https://gist.github.com/KolosovAO/da85ae04702323c1010674260745c4d4
Test: https://repl.it/@AlieksieiKoloso/task141
4. Антон, Rust, Haskell, Python: 1.7 балла
Выделенное направление является для данной ячейки выигрышным, если все элементы при обходе от границы матрицы до данной ячейки строго меньше значения в данной ячейке. В силу транзитивности отношения порядка получаем, что данное направление является для данной ячейки выигрышным, если:
- В данном направлении нет других ячеек (т. е. ячейка на границе) , или
- Значение элемент в ячейке строго больше максимального значения по данному направлению.
Это даёт нам следующий алгоритм для определения количества ячеек, для которого данное направление является выигрышным:
- Положим текущее максимальное значение равным 0, количество ячеек с выигрышным направлением равным нулю.
- Проходим по данному направлению от границы и для каждой ячейки:
- Если значение в текущей ячейке больше текущего максимума, то приравниваем значение максимума этому элементу и инкрементируем количество выигрышных ячеек.
Для того, чтобы получить ответ для матрицы целиком, достаточно подсчитать это значение для каждой строки и каждого столбца (в обоих направлениях обхода) и просуммировать результаты.
https://gist.github.com/AnthonyMikh/603a065d26b62768d3dd645c69236cec
5. @Rusik666, С++: 1 балл
https://github.com/ruslan1979/unilecs/blob/master/task141.cpp
6. @R4PAAA, С++: 1 балл
Сначала считываем матрицу. Затем обрабатываем каждый её элемент. Для каждого элемента делаем 4 проверки в разные стороны. В каждой из проверок идём до тех пор, пока выполняется условие, что число строго меньше, чем число в ячейке. Если дошли до края, то это значит, что направление выйгрышное - увиличиваем счётчик.
https://repl.it/@KamilAkhmietzia/UniLecs141
7. @egormasharskii, С++: 1.5 балла
Метод 1. Для каждой ячейки матрицы проверяем все четыре направления на выигрышность. Итого O(N^3).
Метод 2. В предыдущем решении делаем лишнюю работу для каждого элемента марицы, а именно вычисляем выигрышность направления каждый раз сначала. Но вывод о выигрышности можно сделать и на основе выигрышности предыдущей ячейки в направлении. Соответственно получаем O(N*M).
https://gist.github.com/myegor/03b65dcacd7d998adbcba672c0c3372e
Test: http://cpp.sh/3dhya
8. @jinxonik, Python: 1.5 балла
МЕТОД 1. Перебор. Проходимся по всем элементам и проверяем каждое из 4-х направлений.
МЕТОД 2. Фиксация максимальных элементов по направлениям. Создаём два массива с копией исходного, в которых будем хранить максимальные значения сверху и слева (в одном массиве - максимум сверху, в другом - слева). Двигаемся слева направо и сверху вниз. Если текущее значение самое верхнее или больше значения сверху, добавляем к счётчику 1. Аналогично, если текущее значение самое левое или больше значения слева, так же добавляем 1. Далее записываем на место текущей ячейки максимум из текущей и соседней ячейки сверху (в один массив) или слева (в другой массив). Повторяем всё то же самое, двигаясь справа налево и снизу вверх и сравнивая элементы с соседними снизу и справа.
https://gist.github.com/jin-x/8ddf667a9e3b11bf38e7142f21a236bf
Test: https://repl.it/@jin_x/UniLecs-141-lotterypy
9. @LostInKadath, Python: 1.5 балла
Метод 1. Обычный вариант решения - в лоб. Методом грубой силы мы перебираем все клетки матрицы в цикле O(n*m). Для каждой клетки осуществляется проверка четырех направлений, по циклу O(n) или O(m) на каждое направление. Общая сложность алгоритма: O(n*m)*(2O(n) + 2O(m)) = 2O(n*n*m) + 2O(n*m*m) ~ O(n^3).
Метод 2. Второй вариант решения основывается на следующем факте: если все числа слева от заданного строго меньше заданного числа, то их максимум тоже строго меньше этого числа. Поэтому мы можем пройтись по строкам/столбцам, определяя каждый раз текущий максимум для данной строки/столбца. Если максимум изменился, значит, число в текущей клетке больше всех чисел, стоявших до него, и это направление является выигрышным. Алгоритм проходится по каждой строке в двух направлениях и по каждому столбцу в двух направлениях. Алгоритм не анализирует выигрышность направлений граничных клеток. Мы сами говорим, что по умолчанию любой лотерейный билет имеет количество выигрышных направлений, равное периметру матрицы. Общая сложность алгоритма: O(n * 2m) + O(m * 2n) = 2O(2*m*n) ~ O(n^2).Кода существенно больше, выглядит неприглядно, но алгоритм более эффективный. =)
https://gist.github.com/LostInKadath/b9c4aeb3d9968b7469e8be9680a41497
10. @kirillmotrichkin, Java: 1 балл
Пройдём с каждого края по каждому столбцу или строке и посчитаем количество ячеек, значения которых больше ТЕКУЩЕГО максимума. Значение максимума будем обновлять по мере продвижение по строке/столбцу. И делать +1 к результату при встрече числа больше максимума.
https://gist.github.com/superkiria/96c3f2f38955b72cf784a53d70f809f4
Test: https://repl.it/@superkiria/unilecs141java
11. @voodoo_woodpecker, JS, Python: 1.1 балла
Пробегаемся по матрице и из каждой точки "смотрим" в четыре направления, вверх, право, вниз, влево. Для этого двигаемся в этом правлаении пока имеет смысл -- мы не упёрлись в стенку и значения уменьшаются. Если второе условие нарушается, то считаем направление проигрышным и выходим.
https://gist.github.com/vwpkkr/f568fe5608a979410353f518803c53f6
Test Python: https://repl.it/@MikePeleah/UniLecs141Py