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

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

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

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

26.12.2013, 12:48. Просмотров 484. Ответов 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) Можете предложить еще какие-нибудь решения?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.12.2013, 12:48
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Программа не проходит тесты по времени, посоветуйте как исправить (C++):

Программа на контестере проходит только 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 строку...

Программа с процедурами не проходит тесты - Delphi
Добрый день Пишу сюда, так как не могу найти ошибку самостоятельно. Код программы с процедурами(Первый раз использую) по синтаксису...

Числа Смита (Не проходит все тесты) - Free Pascal
Число Смита — такое составное число, сумма цифр которого равняется сумме цифр всех его простых сомножителей. Так, примером числа Смита...

13
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
26.12.2013, 16:47 #2
R_e_n, Дай ссылку на задачу. Решу скажу как сделал (:
1
R_e_n
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 35
26.12.2013, 16:54  [ТС] #3
Цитата Сообщение от outoftime Посмотреть сообщение
R_e_n, Дай ссылку на задачу. Решу скажу как сделал (:
Не, там закрытая регистрация, а свой логин пароль дать не могу, вдруг голову потом оторвут. Лучше посоветуйте как бы вы решали
0
outoftime
║XLR8║
510 / 432 / 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/ а на хабре можно в самом начале прочитать, как сказку на ночь (:
1
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,523
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 - это тоже логарифм.
1
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
26.12.2013, 17:09 #6
Цитата Сообщение от Qwertiy Посмотреть сообщение
но я бы использовал не её
Почему?
1
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,523
26.12.2013, 17:24 #7
Цитата Сообщение от outoftime Посмотреть сообщение
Почему?
Хм.. Потому что когда-то решил эту задачу другим способом.
Кстати, что в DSU делать с разделением группы, когда машина уезжает?
А вообще, есть подозрение, что задача решаема с использованием стандартных классов.

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

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

Задача преобразования XML не проходит все тесты - C#
Задача не проходит все тесты. Примеры, указанные в условии отрабатывают, а потом тестировщик пробует еще несколько различных вариантов...

ПК иногда не включается, проходит стресс-тесты, пробовал разные БП - Компьютерное железо
Привет всем. С компом странная проблема - после длительного нахождения в выключенном состоянии комп просто не включается, т.е. реакции на...

Оптимизация, алгоритм не проходит по времени - Pascal
Последовательность a1, a2, a3, … , an-1, an называется пилообразной, если она удовлетворяет одному из следующих условий: 1) a1 &lt; a2 &gt; a3...

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


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

Или воспользуйтесь поиском по форуму:
14
Yandex
Объявления
16.01.2014, 17:03
Ответ Создать тему
Опции темы

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