Форум программистов, компьютерный форум CyberForum.ru

Программа не проходит тесты по времени, посоветуйте как исправить - C++

Восстановить пароль Регистрация
 
R_e_n
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 34
26.12.2013, 12:48     Программа не проходит тесты по времени, посоветуйте как исправить #1
Добрый день, не могли бы вы подсказать по задаче. Имеется круг с целыми числами от 1 до n. Числа можно или занимать или освобождать если оно было занято. Во входном потоке задана последовательность запросов в виде чисел. Если число x > 0, то это запрос на занятие числа x на круге. Если число x уже занято, то берется следующее число по часовой стрелке, и выводится номер занятого по факту числа. Если все занято выводится -1. Если x < 0, тогда если число |x| занято оно освобождается и выводится 0. Если свободно, тогда выводится -2. Всего запросов m штук. В первой строке заданы n и m (от 1 до 100000), затем m запросов. Время одна секунда.
Пример.
3 6
1 1 1 1 -1 -1
1 2 3 -1 0 -2

Я реализовал двумя способами:
1) Дерево поиска, если пришел запрос x > 0. Я проверяю есть ли заданное число в дереве, если нет тогда я его туда добавляю, если есть увеличиваю на 1 и так максимум n раз. Если x < 0, тогда ищу в дереве |x| если есть удаляю.
2) Я завел булев массив, если число не занято, то на его месте true, если занято false.

Оба решения не проходят по времени. Тема до этого была деревья поиска. Но не факт, что в решении будет дерево.
Как вы думаете:
1) Тут другое решение или корявая реализация?
2) Имеет ли смысл переписывать рекурсивный поиск в дереве на не рекурсивный?
3) Имеет ли смысл написать процедуру, которая в начале ищет в дереве число, если нашла, то она начинает из данного узла искать следующее число и т. д.
4) Можете предложить еще какие-нибудь решения?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.12.2013, 12:48     Программа не проходит тесты по времени, посоветуйте как исправить
Посмотрите здесь:

C++ Как измерить, сколько времени считала программа?
C++ Программа не проходит тест на acmp.ru
Компиляция проходит, но программа работает неправильно C++
функции, указатели, пожалуйста, посоветуйте, как исправить C++
Программа на контестере проходит только 1 тест из 9. Можете объяснить, в чем моя ошибка и как ее исправить! C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
26.12.2013, 16:47     Программа не проходит тесты по времени, посоветуйте как исправить #2
R_e_n, Дай ссылку на задачу. Решу скажу как сделал (:
R_e_n
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 34
26.12.2013, 16:54  [ТС]     Программа не проходит тесты по времени, посоветуйте как исправить #3
Цитата Сообщение от outoftime Посмотреть сообщение
R_e_n, Дай ссылку на задачу. Решу скажу как сделал (:
Не, там закрытая регистрация, а свой логин пароль дать не могу, вдруг голову потом оторвут. Лучше посоветуйте как бы вы решали
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
26.12.2013, 17:01     Программа не проходит тесты по времени, посоветуйте как исправить #4
R_e_n, Мне кажется проще будет решить с другой структурой, не помню названия, там что-то о множестве. Толи система непересекающихся множеств или около того...

http://ru.wikipedia.org/wiki/%D0%A1%...81%D1%82%D0%B2 кажется оно

Суть в том что когда тебе приходит запрос установить флаг, ты ставишь его в булевом массиве и обновляешь представителей слева от себя. Сложность вставки\удаления должна получиться approx O(1).

Добавлено через 4 минуты
http://e-maxx.ru/algo/dsu тут как всегда описание лучше всех (:
http://habrahabr.ru/post/104772/ а на хабре можно в самом начале прочитать, как сказку на ночь (:
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
26.12.2013, 17:06     Программа не проходит тесты по времени, посоветуйте как исправить #5
Цитата Сообщение от R_e_n Посмотреть сообщение
1) Тут другое решение или корявая реализация?
В любом случае, перебор всех индексов начиная с данного даст квадратичную (в лучшем случае) ассимптотику.

Цитата Сообщение от R_e_n Посмотреть сообщение
2) Имеет ли смысл переписывать рекурсивный поиск в дереве на не рекурсивный?
Рекурсивность не важна.

Цитата Сообщение от R_e_n Посмотреть сообщение
3) Имеет ли смысл написать процедуру, которая в начале ищет в дереве число, если нашла, то она начинает из данного узла искать следующее число и т. д.
Да. Но она не должна проверять элементы последовательно.

Цитата Сообщение от R_e_n Посмотреть сообщение
4) Можете предложить еще какие-нибудь решения?
Да. Я знаю как решить правильно. Нужна ассимптотика O(m*lb(n)).

Цитата Сообщение от R_e_n Посмотреть сообщение
Не, там закрытая регистрация, а свой логин пароль дать не могу, вдруг голову потом оторвут.
Эм.. А почему собственно кто-то должен помогать тебе победить в каком-то конкурсе?

Цитата Сообщение от R_e_n Посмотреть сообщение
Лучше посоветуйте как бы вы решали
Не стану рассказывать решение - это нечестно.
И так много подсказок дал.

Добавлено через 2 минуты
Цитата Сообщение от outoftime Посмотреть сообщение
Толи система непересекающихся множеств или около того...
Допускаю, что её можно применить, но я бы использовал не её.

Цитата Сообщение от outoftime Посмотреть сообщение
Сложность вставки\удаления должна получиться approx O(1).
Нет. Логарифм от числа мест.
Кстати, DSU - это тоже логарифм.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
26.12.2013, 17:09     Программа не проходит тесты по времени, посоветуйте как исправить #6
Цитата Сообщение от Qwertiy Посмотреть сообщение
но я бы использовал не её
Почему?
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
26.12.2013, 17:24     Программа не проходит тесты по времени, посоветуйте как исправить #7
Цитата Сообщение от outoftime Посмотреть сообщение
Почему?
Хм.. Потому что когда-то решил эту задачу другим способом.
Кстати, что в DSU делать с разделением группы, когда машина уезжает?
А вообще, есть подозрение, что задача решаема с использованием стандартных классов.

Добавлено через 4 минуты
Цитата Сообщение от Qwertiy Посмотреть сообщение
Нет. Логарифм от числа мест.
Хотя, в моём вариатне не совсем от числа мест. Но от него в худшем случае.
R_e_n
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 34
26.12.2013, 17:31  [ТС]     Программа не проходит тесты по времени, посоветуйте как исправить #8
Да, спасибо вам большое. Думаю подсказок больше не надо. Больше всего хотелось убедится, что дело не в реализации, а в неправильном алгоритме. Я подумаю над вашими словами.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
26.12.2013, 17:32     Программа не проходит тесты по времени, посоветуйте как исправить #9
Qwertiy, а где ты ее решил? Я тоже решить хочу (:
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
26.12.2013, 20:29     Программа не проходит тесты по времени, посоветуйте как исправить #10
Цитата Сообщение от outoftime Посмотреть сообщение
а где ты ее решил?
На одном из контестов была)
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
26.12.2013, 20:32     Программа не проходит тесты по времени, посоветуйте как исправить #11
Qwertiy, а ссылку не дашь?
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
26.12.2013, 21:28     Программа не проходит тесты по времени, посоветуйте как исправить #12
Цитата Сообщение от outoftime Посмотреть сообщение
а ссылку не дашь?
Это внутренняя система, так что не могу. Да и сам не найду, скорее всего.

Задача формулировалось примерно так:
Есть стоянка с расположенными по кругу парковочными местами (n мест). К произвольному месту x подъезжает машина. Если место свободно, она встаёт на него, если нет, то проезжает по часовой стрелке до ближайшего свободного места и встаёт на него. Дана последовательность событий: положительное число x означает, что машина приехала к месту x, отрицательное число -x означает что машина покинула место x. На запросы первого типа ответить, на какое место встанет машшина (или -1, если все места заняты).
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
16.01.2014, 16:51     Программа не проходит тесты по времени, посоветуйте как исправить #13
R_e_n, ну как программа?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.01.2014, 17:03     Программа не проходит тесты по времени, посоветуйте как исправить
Еще ссылки по теме:

Программа проверяющая тесты C++
C++ Сортировка слиянием не проходит тесты массива 10^5
Конструктор копирования. Посоветуйте как исправить ошибку C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
R_e_n
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 34
16.01.2014, 17:03  [ТС]     Программа не проходит тесты по времени, посоветуйте как исправить #14
Цитата Сообщение от Qwertiy Посмотреть сообщение
R_e_n, ну как программа?
Да, все хорошо, спасибо, решил.
Yandex
Объявления
16.01.2014, 17:03     Программа не проходит тесты по времени, посоветуйте как исправить
Ответ Создать тему
Опции темы

Текущее время: 05:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru