Ну может для этого есть отдельная группа, не привязанная к конкретному языку.

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

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

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

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

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

забей на это.

да #pragma once

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

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

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

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

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

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

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

Ок

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

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

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

/2

Да вижу

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

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

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

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

Да

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

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

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

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

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

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

ну да

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 вложенных друг в друга прямоугольников. Один вывод ответа займет квадрат времени

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

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

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

Хочу видеть.

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

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

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

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

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

Больше ничего. Вообще ничего. Только круглые, фигурные скобки и точки с запятой.

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

На операторы ограничений нет?

понял

На операторы ограничений нет?

Операторы, кроме (), тоже запрещены.

кстати. есть чат про алгоритмы. @proalgorithms

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

стоило бы добавить, что обращения к существующим переменным тоже запрещены)