|
|
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
mayton Над параллелизмом думал? А что там думать, трясти надо. Если на 4 части резать, то: 1) для каждого из 4 квадратов решаем немного измененную задачу со срезающими ячейками только по 2 внешним сторонам (результат не подсчитываем), 2) объединяем соседние решения по 2, запуская процедуру среза и примыкающих ячеек, 3) объединяем половинки, запуская процедуру среза и примыкающих ячеек. 4)считаем результат Но мне интереснее отжать текущую реализацию без разрезаний. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 12:42 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov 3) объединяем половинки, запуская процедуру среза и примыкающих ячеек. Если ячейка из середины одной секции имеет выход в океан через пару других секций? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 12:47 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov mayton Над параллелизмом думал? А что там думать, трясти надо. Если на 4 части резать, то: 1) для каждого из 4 квадратов решаем немного измененную задачу со срезающими ячейками только по 2 внешним сторонам (результат не подсчитываем), 2) объединяем соседние решения по 2, запуская процедуру среза и примыкающих ячеек, 3) объединяем половинки, запуская процедуру среза и примыкающих ячеек. 4)считаем результат Но мне интереснее отжать текущую реализацию без разрезаний. Хорошо. Отжимай. Я попробую на этих выходных что-то написать. Неделька выдалась бешеная. Этой задаче я мог эпизодически уделять по 5 мин времени в сутки. +У меня еще штук 5 интересов "около" этого. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 12:49 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
iOracleDev Твой я не понимаю, за счет чего он должен выбираться из кратеров? Ты для каждой плитки ищешь выход в океан? Как определяешь что не попал в loop по плиткам? Как выходишь за пределы стены кратера, при условии неограниченной вложенности кратеров и их уровней? Сколько проходов по каждой плитке и от чего зависит, какая временная сложность алгоритма? 1. Выход из кратера за счет того, что его "берега" выше "долины", значит, они будут помечены как точки среза, от которых потом будут образованы новые срезы. 2. Зацикливания нет, т.к. мы все время идем в сторону увеличения уровня при вызове процедуры среза и внутри нее. 3. Выход за пределы стены с помощью стены, т.к. новый срез образуется из нее. 4. Один проход по каждой плитке (1 срезание), хотя проверок от соседей может быть больше. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 12:56 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov А что там думать, трясти надо. Если на 4 части резать, то: 1) для каждого из 4 квадратов решаем немного измененную задачу со срезающими ячейками только по 2 внешним сторонам (результат не подсчитываем), 2) объединяем соседние решения по 2, запуская процедуру среза и примыкающих ячеек, 3) объединяем половинки, запуская процедуру среза и примыкающих ячеек. 4)считаем результат 3 четвертинки придется пересчитывать по уровню затопления, когда будем объединять. То есть ничего не выигрываем в данном случае. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 13:00 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
iOracleDev Aleksandr Sharahov 3) объединяем половинки, запуская процедуру среза и примыкающих ячеек. Если ячейка из середины одной секции имеет выход в океан через пару других секций? Для моего алгоритма это не важно. Все возможные срезы для каждой части были сделаны независимо, теперь надо выполнить их диффузию в соседние части. Я не утверждаю, что это быстро, но это даст правильный результат. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 13:01 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
iOracleDev Сколько проходов по каждой плитке и от чего зависит, какая временная сложность алгоритма? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 13:04 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, а я и утверждаю, что будет выигрыш. Например, со спиралькой ваще кранты ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 13:04 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Давайте я в топике, как архивариус соберу различные маргинальные тест кейсы "острова". Мы подыщем для них картинки и будеем использовать как 1. Синтетические тесты.
При любых профилях карты океан всегда омывает и затапливает крайние пиксели по бордюру. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 14:29 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Со ссылкой на голосование У кого какое разрешение моника . Большинство мембером имеют моник Full-HD и я надеюсь что они нормально отображают на скрине картинку с разрешением 1024х1024 на уровне пиксельной точности. Выше создавать нет смысла т.к. она будет либо не кратная степени двойки либо будет отфильтрована фильтрами низкой частоты что сведет на нет ваши усилия по расчету конкретных отдельно стоящик пикселов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 15:41 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 iOracleDev Сколько проходов по каждой плитке и от чего зависит, какая временная сложность алгоритма? Не совсем так. O(n*ln(n)) - это только на этапе сортировки сравнениями. Если подойдет подсчет или радикс, то O(n). На остальных этапах - O(n), т.к. количество заходов в каждую ячейку фиксировано. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 15:49 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov Имя пользователя1, а я и утверждаю, что будет выигрыш. Например, со спиралькой ваще кранты а я и НЕ утверждаю, что будет выигрыш. Например, со спиралькой ваще кранты ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 15:53 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Более упрощенная задача проскакивала на хабре, более того, там было решение в 1 проход, сдесь немного сложнее, как минимум грани и мерность другая https://habr.com/ru/post/200190/ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 17:23 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Мда. Монотонность "слева". Пересекается с монтонностью "справа". И получаем ответ для 1-мерного массива высот. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 17:58 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov 2. Зацикливания нет, т.к. мы все время идем в сторону увеличения уровня при вызове процедуры среза и внутри нее. 3. Выход за пределы стены с помощью стены, т.к. новый срез образуется из нее. Площадка ниже остаточного уровня воды в кратере который ниже уровня подъема воды, однако этот кратер внутри дургого кратера, т.е. сначала подъем на стену, потом спуск и снова подъем, который уже выше уровня подъема воды, т.е. все что внутри должно оказаться сухим. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 18:16 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
mayton При любых профилях карты океан всегда омывает и затапливает крайние пиксели по бордюру. Я бы делал не так, собственно и сделал не так, остров имеет высоту от 0 до 255, при этом остаточный уровень воды может быть выше 0, т.е часть острова может остаться затопленной полностью. Ячейки на одном уровне с уровнем океана после отлива сухие. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 18:19 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
iOracleDev mayton При любых профилях карты океан всегда омывает и затапливает крайние пиксели по бордюру. Я бы делал не так, собственно и сделал не так, остров имеет высоту от 0 до 255, при этом остаточный уровень воды может быть выше 0, т.е часть острова может остаться затопленной полностью. Ячейки на одном уровне с уровнем океана после отлива сухие. Я не то имел в виду. Если вы пойдете на хитрость и создадите "куб" c высотой 255 и размерами например 1024х1024 а уровень океана поднимем на высоту например 300 то по идее ваш куб должен быть затоплен сверху. Эдакий себе всемирный потоп. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 18:28 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
iOracleDev Aleksandr Sharahov 2. Зацикливания нет, т.к. мы все время идем в сторону увеличения уровня при вызове процедуры среза и внутри нее. 3. Выход за пределы стены с помощью стены, т.к. новый срез образуется из нее. Площадка ниже остаточного уровня воды в кратере который ниже уровня подъема воды, однако этот кратер внутри дургого кратера, т.е. сначала подъем на стену, потом спуск и снова подъем, который уже выше уровня подъема воды, т.е. все что внутри должно оказаться сухим. Алгоритм пометит высокие ячейки как новые точки среза, но срезать по ним не будет, так как обход будет завершен досрочно на ячейке с высотой меньше уровня прилива. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 18:29 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
[quot mayton#22084832] iOracleDev Я не то имел в виду. Если вы пойдете на хитрость и создадите "куб" c высотой 255 и размерами например 1024х1024 а уровень океана поднимем на высоту например 300 то по идее ваш куб должен быть затоплен сверху. Эдакий себе всемирный потоп. В исходной постановке и был всемирный потоп, потом добавили произвольный уровень максимального подъема воды, а я еще добавил и уровень океана, который после отлива может быть выше какой то части острова. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 18:38 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Я хотел достигнуть договоренностей о краевых условиях алгоритма. Тоесть когда океану нет места на карте - океан считается пограничными пикселями с координанами например (-1,-1), (+1024,+1024) для моей карты. Иначе алгорим может не сработать или вам придётся вводить в него кучу поправок на края. Это - нудотсво. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 18:42 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
mayton, Остров ограничен краями прямоугольника, снаружи только океан, внутри все считается островом, но он может быть под водой, например уровень океана 1, минимальная высота плитки острова 0, часть острова навсегда останется под водой. Т.е. я к тому что уровень океана тоже можно двигать, как и уровень наводнения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 18:49 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
[quot iOracleDev#22084843] mayton пропущено... В исходной постановке и был всемирный потоп, потом добавили произвольный уровень максимального подъема воды, а я еще добавил и уровень океана, который после отлива может быть выше какой то части острова. На мой взгляд, уровень отлива - лишнее условие, т.к. оно равносильно тому, что все "краевые" точки острова и их соседи (и соседи соседей...) приподнимаются до уровня отлива, если их не считать точками острова. А если считать, то и дно океана надо считать. К тому же это можно свести к разности 2х задач с 2 разными приливами. В общем, пусть при отливе вода уходит туда, откуда пришла - в минус бесконечность. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 18:52 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
Я вообще не понимаю зачем вы различаете уровень океана и прилива или наводнения. По мне это - одно и тоже в топике. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 18:53 |
|
||
|
Задачка про остров
|
|||
|---|---|---|---|
|
#18+
mayton Я вообще не понимаю зачем вы различаете уровень океана и прилива или наводнения. По мне это - одно и тоже в топике. Ну ты склеротик: 22077662 )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 19:06 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=39929626&tid=1339799]: |
0ms |
get settings: |
10ms |
get forum list: |
13ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
142ms |
get topic data: |
10ms |
get forum data: |
3ms |
get page messages: |
66ms |
get tp. blocked users: |
1ms |
| others: | 13ms |
| total: | 266ms |
| 0 / 0 |
