И в сличае с n^2... 
2 2011-08-17 13:19:04
Re: Алгоритм прима (4 ответов, оставленных в Feedback)
на результат это не повлияет..
А вот с выводом похоже надо
if (min_e[v] != -1)
cout << v << " " << min_e[v] << endl;
поменять на
if (sel_e[v] != -1)
cout << v << " " << sel_e[v] << endl;
3 2011-06-29 21:19:30
Re: Сложность алгоритма (3 ответов, оставленных в Problems)
Сдалась с таким же решением но на segment tree.
4 2011-06-29 13:33:43
Re: Сложность алгоритма (3 ответов, оставленных в Problems)
декартово дерево добавляет большую константу. Попробуй с помощью segment tree.
5 2011-06-10 08:23:33
Re: Задача "Кодовый замок" (12 ответов, оставленных в Problems)
Красиво. Вроде должно работать
Только с левой нижней надо аккуратнее проверять что б не пропустить перевернутую T - как-то
if (y < 0 || y == 0 && x < 0) return
6 2011-06-09 23:26:31
Re: Задача "Кодовый замок" (12 ответов, оставленных в Problems)
Сначало генерируй один длины 1 из них прибавлением всех возможных соседей по ребрy длины 2. итд
на каждом шаге убирай дубликаты. На размер поля на этом шаге не смотри - потом готовые замки двигать будешь
7 2011-06-09 23:19:56
Re: Двухменый segment_tree (4 ответов, оставленных в Feedback)
Не. Тоже так нельзя
Вот такой прходит:
void update_y (int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, int new_val) {
if (ly == ry) {
if (lx == rx)
t[vx][vy] = new_val;
else
t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
return;
}
else {
int my = (ly + ry) / 2;
if (y <= my)
update_y (vx, lx, rx, vy*2, ly, my, x, y, new_val);
else
update_y (vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
}
t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
}Тестировал на
void Test()
{
N = 20;
M = 20;
memset(t, 0, sizeof(t));
vector<vector<int> > c(N, vector<int>(M, 0));
for (int nTest = 1; nTest <= 20000; nTest++)
{
int x = rand() % M;
int y = rand() % N;
int val = rand() % 1000;
update_x(1, 0, M - 1, x, y, val);
c[y][x] = val;
int tx = rand() % M;
int lx = rand() % (tx + 1);
int ty = rand() % N;
int ly = rand() % (tx + 1);
val = 0;
for (int x = lx; x <= tx; x++)
{
for (int y = ly; y <= ty; y++)
val += c[y][x];
}
int val2 = sum_x(1, 0, M - 1, lx, tx, ly, ty);
assert (val == val2);
}
}8 2011-06-09 20:11:20
Re: Задача "Кодовый замок" (12 ответов, оставленных в Problems)
Нормальная задачка...
Сдалась с такой идеей - сначала генерирую всевозможные замки с длиной K (для K = 10 их не больше 40000)
Для каждого из замков проверяю куда его можно пропихнуть.
9 2011-06-05 13:54:55
Тема: Двухменый segment_tree (4 ответов, оставленных в Feedback)
Есть подозрение что на странице http://e-maxx.ru/algo/segment_tree в update_y пропущен
t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1]);
для случай ly != ry
10 2011-03-06 00:55:41
Re: округление после преобразования фурье (2 ответов, оставленных в Algo)
+1. Тоже сегодня это заметил... -6.99 например плюс +0.5 станет -6...
@a13n значит с fft она всетаки должна пройти...
11 2011-02-21 21:18:11
Re: STL (7 ответов, оставленных в Problems)
На практике лучше просто обрезать по int/long long (что по сути тот же модуль) так будет быстрее и больший диапозон хешей.
12 2011-02-21 15:56:28
Re: STL (7 ответов, оставленных в Problems)
В этом то и фишка хеша что нам не надо его полностью вычислять достаточно обрезать по int/long long или по модулю большого числа. Вероятность ошибок остается мизерной.
Алгоритм http://e-maxx.ru/algo/rabin_karp продолжает работать даже при строках в N = 100000.
Еще раз перечитай http://e-maxx.ru/algo/string_hashes.
14 2011-01-25 23:17:19
Re: UVa 606 - Keeps Going and Going and ... (9 ответов, оставленных в Problems)
Неизвестно. Но нам его выводить и не надо.
15 2011-01-24 21:07:17
Re: UVa 606 - Keeps Going and Going and ... (9 ответов, оставленных в Problems)
В третем примере нас просят узнать элементы Z с первого по десятый (считать нужно с 0)
например ищем Z[1]
Z = zip Z S
значит Z[1] = S[0]
S = 4 3 2 1 A
значит S[0] = 4 и Z[1] = 4.
etc.
16 2011-01-22 20:23:51
Re: UVa 606 - Keeps Going and Going and ... (9 ответов, оставленных в Problems)
Оно тебе надо? Если месяц не понять условие задачи может проще перейти к следующей? :-)
17 2011-01-20 16:32:04
Re: Загадочное число (3 ответов, оставленных в Problems)
Длина N <= 4 - можно легко пересмотреть все варианты разбиений и проверить есть ли такие ki.
18 2011-01-10 21:02:46
Re: UVa 606 - Keeps Going and Going and ... (9 ответов, оставленных в Problems)
Вкраце - в первых N строчках объявляются списки
В следующих M - вопросы найти элементы одного из списков с "s" по "e".
N и M в первой строчки
19 2010-12-22 10:22:19
Re: Большой Биномиальный коэффициент (12 ответов, оставленных в Algo)
Все получилось. Спасибо большое
20 2010-12-20 19:03:32
Re: Большой Биномиальный коэффициент (12 ответов, оставленных в Algo)
Не получилось.
В формуле ошибка при группировке (1*2*.. * (p-1)) и ((p + 1)*(p + 2)...
так как мы вычисляем по модулю (p ^ q) -> p + 1 != 1)
например p = 3, q = 2 у нас не получится сгруппировать (1 * 2) и (4 * 5)
Пробую группами не по p а по p^q тоже фигня получается.
21 2010-12-19 23:49:43
Re: NP-полная задача (8 ответов, оставленных в Problems)
Рекурсия / бектракинг / перебор / динамику тут можно сделать если бы точно можно было бы сказать что студентов не больше 20. А так - даже не знаю
22 2010-12-19 23:46:52
Re: Большой Биномиальный коэффициент (12 ответов, оставленных в Algo)
Спасибо, Ярослав. Буду пробовать.
23 2010-12-19 12:40:00
Re: Большой Биномиальный коэффициент (12 ответов, оставленных в Algo)
То что Китайская теорема работает это ясно - я имел ввиду что подсчитать коэффициент по модулю pi^qi не сильно нам упростит жизнь если хоть у одного qi >1.
как мы например будем считать коэффициент по модулю 16...
24 2010-12-19 12:35:43
Re: NP-полная задача (8 ответов, оставленных в Problems)
Вроде http://e-maxx.ru/algo/johnson_problem_2 твой случай.
25 2010-12-18 21:42:28
Re: Большой Биномиальный коэффициент (12 ответов, оставленных в Algo)
Так тоже не получится. разложить на простые и восстановить получится только если M "square-free".