ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1743. Сортировка домино

Algo
Послано Zayakin Andrey[PermSU] 24 янв 2010 00:35
What is your comlexiety of your algo?
my O(n^2) solve this.
Re: Algo
Послано Lezhankin Petr [Ufa] 25 янв 2010 20:13
Do u claim that u've got AC with solution in O(n^2)? (n is up to 100000)
Re: Algo
Послано Zayakin Andrey[PermSU] 26 янв 2010 16:14
Build all 2*n pairs of numbers, sort this(firstly by first numbers by non-decreasing order, if first number is equal - sorted by second numbers by non-increasing order). And using greedy build sequence with length equal N start with a[0], if we don`t find solution, start with a[1] and so on, if we have solution we stop algo.
Sory for my english.
Re: Algo
Послано ilucian1 2 фев 2010 15:33
his algorithm is very good but I think its complexity actually is n*log(n) (sorting) + n (finding the solution)
Re: Algo
Послано svr 3 фев 2010 11:04
I suggest math righ algo;
Let a:[1..n]->{0,1} - rotate or not.
(i,j)- red if must a[i]!=a[j]
(i,j)- blue if must a[i]=a[j]
Blue connections- equality relation and we form m classes
If inside some class there is a red edge- "NO"
BFS in superGraph of classes
If find not even cicle "NO"- edge along level of graph
Rotate classes on even levels.
12 tests Ok test13 TL

Edited by author 03.02.2010 16:59

Edited by author 03.02.2010 16:59
Re: Algo
Послано Vladislav 21 сен 2011 20:39
The complexity can be O( n*log(n) ). Sort the 2n pairs as described(increasing by first, decreasing by second) and start from a[0]. The greedy alg. is as follows: go throught a1,a2... , when we find something which we can include and haven't included, include it. It is correct, because for a0 we can only put it in the begining or (inversed) at the end. But if we put it in the end, we can invert the whole sequence and get a solution with it at the begining and so on. So a0 will always give a solution (if possible) and we need one pass.