Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 38
1

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

26.12.2013, 12:48. Показов 1146. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.12.2013, 12:48
Ответы с готовыми решениями:

Не проходит тесты по времени
Здравствуйте. Вот сижу перебираю олимпиадные задачи, и столкнулся с такой проблемой: ...

Программа не проходит тесты
Здравствуйте, решаю задачу: Имеется список людей с указанием их фамилии, имени и даты рождения....

Программа не проходит определённые тесты
Вот такой вот вышел код для данной задачи но он почему-то не проходит выше второй группы хотя если...

Программа не проходит некоторые тесты
Доброго времени суток, друзья! Решаю задачу: вывод стандартный вывод Дана строка, состоящая...

13
║XLR8║
1210 / 907 / 270
Регистрация: 25.07.2009
Сообщений: 4,354
Записей в блоге: 5
26.12.2013, 16:47 2
R_e_n, Дай ссылку на задачу. Решу скажу как сделал (:
1
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 38
26.12.2013, 16:54  [ТС] 3
Цитата Сообщение от outoftime Посмотреть сообщение
R_e_n, Дай ссылку на задачу. Решу скажу как сделал (:
Не, там закрытая регистрация, а свой логин пароль дать не могу, вдруг голову потом оторвут. Лучше посоветуйте как бы вы решали
0
║XLR8║
1210 / 907 / 270
Регистрация: 25.07.2009
Сообщений: 4,354
Записей в блоге: 5
26.12.2013, 17:01 4
R_e_n, Мне кажется проще будет решить с другой структурой, не помню названия, там что-то о множестве. Толи система непересекающихся множеств или около того...

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

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

Добавлено через 4 минуты
http://e-maxx.ru/algo/dsu тут как всегда описание лучше всех (:
http://habrahabr.ru/post/104772/ а на хабре можно в самом начале прочитать, как сказку на ночь (:
1
829 / 637 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
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
║XLR8║
1210 / 907 / 270
Регистрация: 25.07.2009
Сообщений: 4,354
Записей в блоге: 5
26.12.2013, 17:09 6
Цитата Сообщение от Qwertiy Посмотреть сообщение
но я бы использовал не её
Почему?
1
829 / 637 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
26.12.2013, 17:24 7
Цитата Сообщение от outoftime Посмотреть сообщение
Почему?
Хм.. Потому что когда-то решил эту задачу другим способом.
Кстати, что в DSU делать с разделением группы, когда машина уезжает?
А вообще, есть подозрение, что задача решаема с использованием стандартных классов.

Добавлено через 4 минуты
Цитата Сообщение от Qwertiy Посмотреть сообщение
Нет. Логарифм от числа мест.
Хотя, в моём вариатне не совсем от числа мест. Но от него в худшем случае.
1
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 38
26.12.2013, 17:31  [ТС] 8
Да, спасибо вам большое. Думаю подсказок больше не надо. Больше всего хотелось убедится, что дело не в реализации, а в неправильном алгоритме. Я подумаю над вашими словами.
0
║XLR8║
1210 / 907 / 270
Регистрация: 25.07.2009
Сообщений: 4,354
Записей в блоге: 5
26.12.2013, 17:32 9
Qwertiy, а где ты ее решил? Я тоже решить хочу (:
0
829 / 637 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
26.12.2013, 20:29 10
Цитата Сообщение от outoftime Посмотреть сообщение
а где ты ее решил?
На одном из контестов была)
0
║XLR8║
1210 / 907 / 270
Регистрация: 25.07.2009
Сообщений: 4,354
Записей в блоге: 5
26.12.2013, 20:32 11
Qwertiy, а ссылку не дашь?
0
829 / 637 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
26.12.2013, 21:28 12
Цитата Сообщение от outoftime Посмотреть сообщение
а ссылку не дашь?
Это внутренняя система, так что не могу. Да и сам не найду, скорее всего.

Задача формулировалось примерно так:
Есть стоянка с расположенными по кругу парковочными местами (n мест). К произвольному месту x подъезжает машина. Если место свободно, она встаёт на него, если нет, то проезжает по часовой стрелке до ближайшего свободного места и встаёт на него. Дана последовательность событий: положительное число x означает, что машина приехала к месту x, отрицательное число -x означает что машина покинула место x. На запросы первого типа ответить, на какое место встанет машшина (или -1, если все места заняты).
0
829 / 637 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
16.01.2014, 16:51 13
R_e_n, ну как программа?
0
0 / 0 / 0
Регистрация: 30.07.2012
Сообщений: 38
16.01.2014, 17:03  [ТС] 14
Цитата Сообщение от Qwertiy Посмотреть сообщение
R_e_n, ну как программа?
Да, все хорошо, спасибо, решил.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.01.2014, 17:03

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

Программа не проходит все тесты на тестовой системе
Дано число K. Дальше следуют K блоков. В каждом блоке есть 4 числа a,b и c,d . Числа натуральные и...

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

Программа не проходит по времени
http://codeforces.com/problemset/problem/591/B - сама задача Я перепробовал много...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

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