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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
R_e_n
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 35
#1

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

26.12.2013, 12:48. Просмотров 463. Ответов 13
Метки нет (Все метки)

Добрый день, не могли бы вы подсказать по задаче. Имеется круг с целыми числами от 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     Программа не проходит тесты по времени, посоветуйте как исправить
Посмотрите здесь:

Программа на контестере проходит только 1 тест из 9. Можете объяснить, в чем моя ошибка и как ее исправить! - C++
Объясните, в чем моя ошибка в решении задачи. Условие: 103. Подсчет войск ограничение времени на тест: 0.5 сек. ...

Сортировка слиянием не проходит тесты массива 10^5 - C++
#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; int N; void Merge(vector &lt;int&gt; &amp;intVector,int first,int last) { ...

функции, указатели, пожалуйста, посоветуйте, как исправить - C++
Ввести 2 массива из N неотрицательных чисел разной размерности. Считать N≤100. Конец ввода элементов индицирует ввод отрицательного числа. ...

Конструктор копирования. Посоветуйте как исправить ошибку - C++
Пишет &quot;Нет подходящего конструктора копирования по умолчанию&quot;, задание было добавить конструктор копирования. я добавил с16 по 27 строку...

Программа проверяющая тесты - C++
Здравствуйте, обращаюсь к вам за помощью так как уже нет выхода):wall Надо написать программу которая будет проверять тест,вот даже не...

Программа не проходит тест на acmp.ru - C++
http://********/index.asp?main=task&amp;id_task=446 На хоккейном стадионе в одном большом городе расположено большое прямоугольное табло. Оно...

Как измерить, сколько времени считала программа? - C++
Запускается прога, запрашивает число (например 1000), включается таймер (или читается время из winXP), идёт расчёт (например сумма от 1 до...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
║XLR8║
508 / 430 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
26.12.2013, 16:47     Программа не проходит тесты по времени, посоветуйте как исправить #2
R_e_n, Дай ссылку на задачу. Решу скажу как сделал (:
R_e_n
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 35
26.12.2013, 16:54  [ТС]     Программа не проходит тесты по времени, посоветуйте как исправить #3
Цитата Сообщение от outoftime Посмотреть сообщение
R_e_n, Дай ссылку на задачу. Решу скажу как сделал (:
Не, там закрытая регистрация, а свой логин пароль дать не могу, вдруг голову потом оторвут. Лучше посоветуйте как бы вы решали
outoftime
║XLR8║
508 / 430 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
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
818 / 626 / 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║
508 / 430 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
26.12.2013, 17:09     Программа не проходит тесты по времени, посоветуйте как исправить #6
Цитата Сообщение от Qwertiy Посмотреть сообщение
но я бы использовал не её
Почему?
Qwertiy
818 / 626 / 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
Сообщений: 35
26.12.2013, 17:31  [ТС]     Программа не проходит тесты по времени, посоветуйте как исправить #8
Да, спасибо вам большое. Думаю подсказок больше не надо. Больше всего хотелось убедится, что дело не в реализации, а в неправильном алгоритме. Я подумаю над вашими словами.
outoftime
║XLR8║
508 / 430 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
26.12.2013, 17:32     Программа не проходит тесты по времени, посоветуйте как исправить #9
Qwertiy, а где ты ее решил? Я тоже решить хочу (:
Qwertiy
818 / 626 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
26.12.2013, 20:29     Программа не проходит тесты по времени, посоветуйте как исправить #10
Цитата Сообщение от outoftime Посмотреть сообщение
а где ты ее решил?
На одном из контестов была)
outoftime
║XLR8║
508 / 430 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
26.12.2013, 20:32     Программа не проходит тесты по времени, посоветуйте как исправить #11
Qwertiy, а ссылку не дашь?
Qwertiy
818 / 626 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
26.12.2013, 21:28     Программа не проходит тесты по времени, посоветуйте как исправить #12
Цитата Сообщение от outoftime Посмотреть сообщение
а ссылку не дашь?
Это внутренняя система, так что не могу. Да и сам не найду, скорее всего.

Задача формулировалось примерно так:
Есть стоянка с расположенными по кругу парковочными местами (n мест). К произвольному месту x подъезжает машина. Если место свободно, она встаёт на него, если нет, то проезжает по часовой стрелке до ближайшего свободного места и встаёт на него. Дана последовательность событий: положительное число x означает, что машина приехала к месту x, отрицательное число -x означает что машина покинула место x. На запросы первого типа ответить, на какое место встанет машшина (или -1, если все места заняты).
Qwertiy
818 / 626 / 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++
Задача: дан текстовый файл. в нем символы &quot;.&quot; и &quot;,&quot; заменить на &quot;тчк&quot; и &quot;зпт&quot; соответственно. ...

Сбор черники. Программа не проходит 11 тест - C++
Текст задачиСбор черники (Время: 1 сек. Память: 16 Мб Сложность: 17%) В фермерском хозяйстве в Карелии выращивают чернику. Она...

Программа выводит какуето абракадабру как исправить? - C++
Разработка программы для автоматизации перевода слов Структура «словарь» должна содержать 2 поля: слово на русском языке и его перевод на...

После выполнения алгоритма программа сразу закрывается - как исправить? - C++
дела такое: (циклический алгоритм, задача с матрицами) программа запускается в Win32 Console Application, но после выполнения алгоритма...

как исправить ошибку? (программа должна перевести двоичный код в десятичный) - C++
#include &lt;iostream.h&gt; #include &lt;string.h&gt; int atoi(char *s) { int chislo = 0; int razryad = 1; int len = strlen(s); ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru