Доброго времени суток.
Авторы задач сегодняшнего раунда – Михаил Мирзаянов и я. Хочу сказать спасибо Дмитрию Левшунову за техническую помощь в организации контеста, а так же Геральду Агапову и Николаю Кузнецову за написание альтернативных решений.
Желаю всем удачи!
UPD: Контест закончился, всем спасибо за участие.
- Задачи
- Результаты
- Победитель: marek.cygan
нет
what sahould i do????????????????
i run this program correctly
I'm also very interested about this verdict.
А то условие то вроде понятно... а вот откуда там 12 в выходе не пойму)))
Походу чего-то не заметил)))
Well, but why does my gcc-4.4.3 work with "%lld" just fine?
sorry for my bad English
them like if the shotest path go through according edge. So update cost for any query is O(N^2)
First, see if this new road is actually better than the shortest path from u to v. It may not be :)
Assuming it's an improvement, set a[u][v] = a[v][u] = d. Then, run Floyd-Warshall to update the shortest distances. Normally this would be O(n^3), but because only the distance between u and v changed, it suffices to use only u and v as midpoints, reducing the time to O(n^2). Given 300 roads, the total runtime is 300 * O(n^2) ~= 300^3 which is quite fine.
I got a PE for problem D!!!! Is there something wrong with the judge?
"=" means assignment, so your expression can be written this way:
col = Used[i1];
if (col ){...}
col will equal Used[i1] and thereafter
1. проверяем не являются ли какие строки подстроками других строк. если это так - лишние строки выкидываем, ясно почему так можно сделать
2. склеиваем особым образом все оставшиеся строки во всевозможных порядках. например, чтобы склеить 3 строки a, b, c (в данном порядке) надо из c выкинуть наибольший префикс, совпадающий с суффиксом b, а затем из b поибольший префикс, совпадающий с суффиксом a и только после этого замерить длину a+b+c (+ - это контатенация). собственно, для нахождения наибольшего префикса (за линейное время, желательно) и нужны КМП или хэши.
- кидаем все слова в бор (тоже самое что суфф.дерево, только добавляем не все суффиксы, а только слова целиком).
- затем просчитываем переходы на этом дереве, например если стаю в какой-то вершине, то в какую вершину перейду если допишу определенную букву ( алгоритм Ахо-Карасика), это похоже на КМП на дереве, если можно так сказать.
- для каждого состояния я буду знать какие из данных слов входят в текущий "спуск" ("спуском" можно названть строка от корня до текущей вершины, не знаю как правильно это назвать).
- очередь по этому дерево и по переходам которые я просчитал, с запоминанием состояния (i,j) - был ли я в i вершине с набором j (набор двоичное представление какие строки я уже собрал какие нет, то есть от 0 до 7 включительно)
Граф не взвешен поэтому мне надо найти первое состояние когда я пришел в (i, 7).
З.Ы. наверное очень непонятно, но как есть, заранее извиняюсь за незнание терминологии.
thank you !
const int N = 310;
int main() {
int n;
scanf("%d", &n);
int g[N][N];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
scanf("%d", &g[i][j]);
assert(g[i][j] <= 1000); // runtime error...
}
}
А ошибка была другая — есть функция string press(string a, string b), которая решает задачу для двух строк. Однако я смотрел вариант press(a, press(b, c)), но забыл про press(press(a, b), c)).
Thanks
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
Using KMP, it's easy to find for 2 given strings the longest suffix of the first one that is a prefix for the second one.
After that you simply try all posible permutations of the 3 strings given in the problem(watching for degenerate cases, when one of the strings is a substring of one of the other two..).
Спасибо.
К сожалению, эта информация меня еще больше запутала:
Дело в том, что на втором сэмпле моя программа возвращает ( у меня дома)
1
3 1 1 4
(Я считаю, что это правильный ответ:
Разорван цикл 1231, оставшиеся цепочки 123 и 4567 соединины ребром (1-4). В итоге получается цепочка 3214567 из 6 ребер, соединяющих все вершины.)
Программа выдает неправильный ответ на втором тесте (=втором семпле):
1. Предложеный ответ (1 \ 3 1 1 4) не является правильным. ( почему?)
2. Программа возвращает другой ответ
а) неправильный формат вывода
(после количества дней и четверок городов ставлю перенос строки. После последнего числа в строке пробела нет.)
б) программа работает по-другому (??!!)
3 ...
Честно говоря хотелось бы разобратся в чем причина. Другие идеи приветствуются.
Зараннее спасибо.
vanjonito.
б)
Проверил в Visual Studio 2005 - точно так же