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

Обсуждение задачи 1741. Монстр общения

CRACKED
Послано liuexp 1 ноя 2009 16:03
1.can a cracked one installed on alicensed one?
2.can a licensed one installed ona cracked one if it has never been pirated before?
Re: CRACKED
Послано r1d1 1 ноя 2009 17:10
1.YES
2.YES
Re: CRACKED
Послано liuexp 1 ноя 2009 19:05
But my shortest path algorithm still failed....
I first encode the vertice of pirated into 3*i
and the vertice of cracked into 3*i+1,
and the vertice of licensed into 3*i+2,
then construct the graph according to the input, and after that I use a DFS() to take away the edge that comes with a licensed one and is after a pirated one.
Finally I run the SPFA(), is there anything wrong?

I constructed several simple datas to test the DFS() AND SPFA(), it works all right.
Re: CRACKED
Послано r1d1 1 ноя 2009 19:49
hm... I use DP and all work
Re: CRACKED
Послано 2rf [Perm School #9] 1 ноя 2009 21:52
liuexp писал(a) 1 ноября 2009 19:05
I first encode the vertice of pirated into 3*i
and the vertice of cracked into 3*i+1,
and the vertice of licensed into 3*i+2,

?? You can have only licensed or pirated vertices; not cracked!

And, btw, singular for "vertices" is "vertex" not "vertice".

Edited by author 01.11.2009 22:23
Re: CRACKED
Послано 2rf [Perm School #9] 1 ноя 2009 23:47
What is your DP solution? Obviously, we have weighted graph in this problem and we want to know shortest path from one vertex to another. So, it's Dijkstra algorithm, but I'm not sure if you can call it DP... Did you use some special algo?
Re: CRACKED
Послано Lebedev_Nicolay[Ivanovo SPU] 2 ноя 2009 00:18
We need to find shortest path in DAG! So we need not Dijkstra, we need other algo. This algo very same with DP.
Re: CRACKED
Послано 2rf [Perm School #9] 2 ноя 2009 00:41
Oops, didn't see xi<yi in statement =) Anyway, I used Dijkstra and got AC.
Re: CRACKED
Послано Lebedev_Nicolay[Ivanovo SPU] 2 ноя 2009 00:52
How did you use Dijkstra (N = 10000)?
Did you use heap or priority queue?
Re: CRACKED
Послано 2rf [Perm School #9] 2 ноя 2009 01:39
O(N^2). It worked even though N=20000 actually(having cracked and licensed vertex for each version). Time was ~0.7 sec.