Тема: Spoj Robotic Sort
Помогите пожалуйста решить http://www.spoj.pl/problems/CERC07S/. Я знаю, что можно решить декартовым деревом, но как это сделать не приходит в голову. Подскажите идеи.
Re: Spoj Robotic Sort
А в чём проблема, ведь как делать неявным декартовым деревом reverse на отрезке, описано в статье?
Можно даже обойтись без явных поисков минимума: заранее перенумеровать все числа, и для каждого числа запомнить указатель на его вершину в дереве. Тогда на i-ом шаге мы должны взять вершину, соответствующую числу i, найти её номер в массиве (это делается так: поднимаемся от вершины по предкам до корня, прибавляя каждый раз всё, что оставляем слева от себя), ну и потом просто сделать reverse на соответствующем префиксе (а само число i удалить из дерева вообще, зачем оно нам потом нужно).
3 2011-11-22 12:06:14 Отредактировано Hack-Yer (2011-11-22 12:07:59)
Re: Spoj Robotic Sort
Пожалуйста посмотрите мой код.
На инпуте :
6
3 4 5 1 6 2У меня выходит RE. Это из-за того, что процедура push была не во всех вершинах.
На 3-ем шагу дерево должно быть:
6
/ \
1 5
\ /
2 4
/
3 А у меня выходит:
6
/ \
1 5
\ \
2 4
/
3 Re: Spoj Robotic Sort
Я просмотрел бегло, но думаю, что проблема в том, как ты ищешь ind: ведь в дереве могли быть непропушенные флаги rev, а ты просто поднимаешься до корня и суммируешь. Мне кажется, самый простой способ - дважды пройти путь до корня: первый раз вызывая push вдоль всего пути, и лишь второй раз насчитывая ind.
Re: Spoj Robotic Sort
Пытаюсь сдать эту задачу на spoj.pl никак не получается уложиться в тл, на локальном компьютере работает очень быстро, можно ли как нибудь ускорить алгоритм, делаю в точности то, что написано выше?
Re: Spoj Robotic Sort
Забавно, что именно сегодня я тоже сдавал эту задачу на тренировке 
Не знаю, как там на spoj, но у меня проблем с TL не было. Выложи куда-нибудь код, может, там есть какой-нибудь косяк.
Re: Spoj Robotic Sort
http://pastebin.com/AHJLPeYi вот здесь код)
Re: Spoj Robotic Sort
Хм, ну с виду всё нормально. Разве что можно отказаться от динамического выделения памяти в insert(), просто сделав глобальный массив node'ов.
Re: Spoj Robotic Sort
Не помогло вот с заменой на массив http://pastebin.com/qk34VMFs. Нет сохранилось ли у тебя решение этой задачи, чтоб заслать ее на spoj? Или не знаешь ли других проверяющих систем с этой задачей?
Re: Spoj Robotic Sort
Да уж, позапихивать пришлось так ещё
Вот мой код: http://pastebin.com/Gr2EAHwV, даёт 1.40 сек.
Из хаков:
Не хранить в дереве уже отсортированные вершины, т.е. на i-ом шаге в дереве хранятся только n-i+1 вершин (у теории - улучшает примерно в два раза).
Ручной ввод-вывод, вместо обычных scanf/printf: оперировать только с gets/puts (без этого у меня тоже не проходило, так что достаточно важно).
А вот при подсчёте номера вершины и раскручивании предков, как оказалось, вполне можно использовать рекурсию вместо хранения предков в массиве: в данном случае рекурсия почти не сказывается на времени работы.
Интересно отметить, что на SPOJ'е суммарное N по всем тестам около 200 тыс., т.к. получается примерно 0.7 сек на 100 тыс. сложных операций с декартовым деревом: вот такое оно медленное.
11 2012-04-14 10:36:44 Отредактировано KADR (2012-04-14 10:37:10)
Re: Spoj Robotic Sort
Я кодил ее давно и декартово дерево написано ужасно криво, но кроме ввода никаких хаков не делал. Правда, работает оно 1.85 секунд. Кстати, выводил я не puts, а обычным printf.
Re: Spoj Robotic Sort
Спасибо сдал, еще одной моей проблемой кажется самой большой было то, что я использую 5 вызовов split и merge вместо 3, для того, чтобы поставить следующее число на свое место. Т.е. получается что 5 * n * logn TLE, а 3 * n * logn АС, грубо говоря.
до
inline void swapper(int l, int r)
{
pnode L,MID,R;
split(T,L,R,l);
split(R,MID,R,r - l + 1);
if (MID) MID -> rev ^= true;
merge(T,L,MID);
merge(T,T,R);
split(T,L,T,1);
}после
inline void swapper(int l, int r)
{
pnode L,MID,R;
split(T,L,R,r);
split(R,MID,R,1);
if (L) L -> rev ^= true;
merge(T,L,R);
}