а ирл такое хоть когда-нибдуь нужно?

кроме клика мышью по экрану... )))

оч маловероятно

а ирл такое хоть когда-нибдуь нужно?

да. Поэтому и спрашиваю

в реальной жизни всем надо сайты и игры)))))

оч маловероятно

у коллеги такая таска

Ну просто если не забивать, то быстрее квадрата не посчитаешь, потому что для формирования ответа уже квадрат по времени нужен.

забей на это.

да #pragma once

Сможет разрулить разве?

а ирл такое хоть когда-нибдуь нужно?

Выделение объектов рамкой на рабочем столе? Как пример задачи

на практике явно слонжность не будет првоеряться %)

ибо кейс экрана 16m на 16m вряд ли будет :)

Задача: есть N прямоугольников, заданные координатами своих углов. Требуется для каждого прямоугольника найти все прямоугльники, внутри которых он находится полностью. Оффлайн задача. Требуется решение быстрее, чем за N^2

Есть алгоритм, который проверяет принадлежность точки многоугольнику

Есть алгоритм, который проверяет принадлежность точки многоугольнику

не то

не то

Ок

Ну, строго говоря, асимптотику лучше квадрата в худшем случае ты не получишь. Потому что если в первом квадрате лежат все, во втором - все, кроме первого, в третьем - все, кроме первого и второго, итд, то ответ будет иметь размер N-1 + N-2 +... + 1 + 0 = (N-1)*(N)/2. Вот такая печаль

Задача: есть N прямоугольников, заданные координатами своих углов. Требуется для каждого прямоугольника найти все прямоугльники, внутри которых он находится полностью. Оффлайн задача. Требуется решение быстрее, чем за N^2

Ну, строго говоря, асимптотику лучше квадрата в худшем случае ты не получишь. Потому что если в первом квадрате лежат все, во втором - все, кроме первого, в третьем - все, кроме первого и второго, итд, то ответ будет иметь размер N-1 + N-2 +... + 1 + 0 = (N-1)*(N)/2. Вот такая печаль

так, я понимаю это

IRL такого не будет

А если хочется в среднем, то стоит указать, какие именно средние варианты нужны.

/2

А если хочется в среднем, то стоит указать, какие именно средние варианты нужны.

Так, хорошо. Мне нужно что-то порядка (N+Ans)*logN, где N - кол-во прямоугольников, Ans - количество вложенных прямоугольников в другие, N » Ans

Ключевое: N много больше Ans. Требуется улучшение асимптотики с квадрата до чего-нибудь быстрее

Да вижу

N*Ans не устроит?)

N*Ans не устроит?)

а умеешь?

N*Ans не устроит?)

устроит

Скорее, имелось в виду Ans << N^2

Скорее, имелось в виду Ans << N^2

да, именно. Ты прав

очепятка

Решено

2 dimensional interval tree

это для проверок вложенности

также стояла задача поиска всех прямоугольников, к оторые пересекаются друг с другом - это решается обычным сканлайном

Задача: есть N прямоугольников, заданные координатами своих углов. Требуется для каждого прямоугольника найти все прямоугльники, внутри которых он находится полностью. Оффлайн задача. Требуется решение быстрее, чем за N^2

помечаем все вершины одного прямоугольника одной буквой, например первый прямоугольника все вершины А, второй Б и так далее. Потом отмечаем на каждой оси проекции этих вершин. Должны получиться последовательности типа АБВВВБАА на каждой их оси. Дальше теорема, один прямоугольника включается в другой тогда и только тогда, когда проекции его вершин лежат между двумя крайним проекциями другого прямоугольника на обоих осях

помечаем все вершины одного прямоугольника одной буквой, например первый прямоугольника все вершины А, второй Б и так далее. Потом отмечаем на каждой оси проекции этих вершин. Должны получиться последовательности типа АБВВВБАА на каждой их оси. Дальше теорема, один прямоугольника включается в другой тогда и только тогда, когда проекции его вершин лежат между двумя крайним проекциями другого прямоугольника на обоих осях

Мне стоит писать, почему это квадратное решение?

Сделайте вектор самых левых X координат, отсортируйте его и делайте обход по отсортированному вектору.

Мне стоит писать, почему это квадратное решение?

Да

Не должно зайти. Обход все равно останется квадратичным по сложности

Сделайте вектор самых левых X координат, отсортируйте его и делайте обход по отсортированному вектору.

За четыре обхода решается но с n^2 по памяти

за сколько там N^2 памяти выделяется? Не за О(N^2) ли случайно?)

за сколько там N^2 памяти выделяется? Не за О(N^2) ли случайно?)

а с каких пор мы стали учитывать в асимптотику выделение памяти?

Автор же нашел решение

Автор же нашел решение

Если есть проще...

а с каких пор мы стали учитывать в асимптотику выделение памяти?

Ладно, но это смотря с какой стороны посмотреть) В терминах математики выделение памяти это константа

Ладно, но это смотря с какой стороны посмотреть) В терминах математики выделение памяти это константа

а я программированием занимаюсь

ну да

Сейчас решение Михаила гляну. Скорее всего, я неправильно понял его мысль

На практике каких значений достигает N?

Не должно зайти. Обход все равно останется квадратичным по сложности

Нет там квадрата обхода.

На практике каких значений достигает N?

Не знаю. Потенциально порядки тысяч-десятков тысяч

Всем привет. В 20:00 кину задачу на C++. Задача интересная, поэтому просьба - не спойлерить! Ответы слать мне в личку. Я напишу в этот чат никнеймы тех, кто решил задачу правильно. Задача является разновидностью известной задачи "циклическая космическая станция", но с дополнительными ограничениями, которые заставляют напрячь не столько общую логику, сколько опыт программиста.

Всем привет. В 20:00 кину задачу на C++. Задача интересная, поэтому просьба - не спойлерить! Ответы слать мне в личку. Я напишу в этот чат никнеймы тех, кто решил задачу правильно. Задача является разновидностью известной задачи "циклическая космическая станция", но с дополнительными ограничениями, которые заставляют напрячь не столько общую логику, сколько опыт программиста.

а в чем профит? зачем тратить на нее время?

а в чем профит? зачем тратить на нее время?

Некоторые любят напрячь мозги, когда есть свободное время.

а в чем профит? зачем тратить на нее время?

А в чем профит читать техническую литературу в нерабочее время, а в чём профит делать свои игрушечные проекты, за которые тебе не платят?

Задача: есть N прямоугольников, заданные координатами своих углов. Требуется для каждого прямоугольника найти все прямоугльники, внутри которых он находится полностью. Оффлайн задача. Требуется решение быстрее, чем за N^2

Можно kdtree заюзать, будет что-то типа O(nlogn)

А в чем профит читать техническую литературу в нерабочее время, а в чём профит делать свои игрушечные проекты, за которые тебе не платят?

Ты читаешь\делаешь проект потому что тебе ТЕМА ИНТЕРЕСНА и ты меняешь время на знания, которые ты хочешь получить.

Можно kdtree заюзать, будет что-то типа O(nlogn)

я так и не понял, как там kdtree заюзать. А вот как заюзать 2 dimensional interval tree - знаю

но тут прокатит и решение проще, которое Михаила

http://ideone.com/q7d6yl #CircularStationTask #Задача

Необходимо дописать код в функцию Task::explore(). Функция должна выйти после того, как весь свет на станции выключен.

Можно использовать for, но нельзя использовать локальные переменные?

Да. Локальные переменные запрещены.

То есть только for без счетчика

http://ideone.com/q7d6yl #CircularStationTask #Задача

std::vector<bool>? Прикольно ?

Не придумывается, как без счетчика сделать :(

http://ideone.com/q7d6yl #CircularStationTask #Задача

Task() { std::mt19937 generator((std::random_device()())); lights.resize(size_t(STATION_SIZE)); for (int i = 0; i < STATION_SIZE; ++i) { lights[i] = std::uniform_int_distribution<>(0, 1)(generator) != 0; } room = 0; } Можно моднее сделать: Task() : lights(STATION_SIZE), room() { std::mt19937 generator((std::random_device()())); std::generate(std::begin(lights), std::end(lights), std::bind(std::uniform_int_distribution<>(0, 1), std::ref(generator))); }

Можно, но задача в другом :)

Да я так, просто, не смог пройти мимо :)

Первое корректное решение - @AndreiKr .

а в чем профит? зачем тратить на нее время?

На собственный апгрейд)

Первое корректное решение - @AndreiKr .

я не удивлен)

Первое корректное решение - @AndreiKr .

Тот самый Андрей, которого я знаю?)

тут есть кто в sql шарит?

Тот самый Андрей, которого я знаю?)

Мне казалось, что нет.

Тот самый Андрей, которого я знаю?)

Видимо, тот самый.

я не удивлен)

Почему? Остальные 1013 мемберов данного чата не любят задачки? :)

Почему? Остальные 1013 мемберов данного чата не любят задачки? :)

да не. все всё любят

Видимо, тот самый.

Привет)

да не. все всё любят

многие просто еще на работе)

Добрый вечер :)

да не. все всё любят

Сам то решишь?

Сам то решишь?

не хочу, я ща работаю. и да, лучше пометить тегами задачки, чтоб потом проще было искать

не хочу, я ща работаю. и да, лучше пометить тегами задачки, чтоб потом проще было искать

Плюсую насчёт тегов.

Пометил. CircularStationTask.

Сам то решишь?

Просто некоторые пока что на рабо те работу работают)

Пометил. CircularStationTask.

и просто тегом "задача" тогда

Сделал.

Сделал.

благодарю

Сам то решишь?

Провокаторша :) Задача не на время, совсем. Нечего людей дразнить. У кого будет желание, а главное, время - те и покумекают :)

Задача: есть N прямоугольников, заданные координатами своих углов. Требуется для каждого прямоугольника найти все прямоугльники, внутри которых он находится полностью. Оффлайн задача. Требуется решение быстрее, чем за N^2

Вот у тебя N вложенных друг в друга прямоугольников. Один вывод ответа займет квадрат времени

Но если тебе просто дерева вложенности хватит, то можно за NlogN

Блин. Самое сложное - сформулировать условия задачи. Нашёлся умный человек :) В общем, статические переменные тоже нельзя.

А монады можно?

Хочу видеть.

А, ну я задачу не прочитал — просто подумал, что что-то, в чем надо обойтись без локальных переменных и вспомнил монады :)

Блин. Самое сложное - сформулировать условия задачи. Нашёлся умный человек :) В общем, статические переменные тоже нельзя.

Почему нельзя статические переменные

Почему нельзя статические переменные

Всё, что можно, перечислено в строке 40. // Use only 'next()', 'previous()', 'isLightEnabled()', 'toggleLight()', 'do', 'for', 'if', 'while' and 'return'