Известно в этой задаче какое максимальное количество студентов может быть ?
27 2010-12-17 17:22:00
Re: NP-полная задача (8 ответов, оставленных в Problems)
Ограничения хоть бы написал.
28 2010-12-17 17:19:45
Re: Большой Биномиальный коэффициент (12 ответов, оставленных в Algo)
"если n>=m бин коэф делится на M" Не похоже что правда. С[1000000000][999999999] = 1000000000
29 2010-12-16 21:29:21
Тема: Большой Биномиальный коэффициент (12 ответов, оставленных в Algo)
Привет
Что у нас есть из алгоритмов что б найти (C[n, k]) для K <= N < 10^9
по _не простому_ модулю M < 10 ^ 5
?
30 2010-12-15 00:31:38
Re: lcp в суффиксном массиве (2 ответов, оставленных в Algo)
31 2010-11-20 14:42:50
Re: acm.sgu.ru #527-Explode 'Em All (4 ответов, оставленных в Problems)
Идея с минимального контролирующего множества провалилась. Пошло бы если бы бомбой уничтожали только ряд или только колонку.
Сдал перебором всех возможных колонок. Интересно как ее за 22ms решили.
32 2010-11-19 21:14:38
Re: acm.sgu.ru #527-Explode 'Em All (4 ответов, оставленных в Problems)
Думай в сторону графов и минимального контролирующего множества.
33 2010-11-06 23:33:15
Re: Суффиксный массив (4 ответов, оставленных в Feedback)
смотри ниже. Там cnt используется и для других целей.
34 2010-10-20 08:53:18
Re: какая структура данных? (6 ответов, оставленных в Problems)
Это я про 1/4финальное условие - "фактически циклический сдвиг на к - это и есть поменять две соседние подстроки"
Для этого условия сместить вначале на a потом на b = сместить один раз на (a + b) (по модулю)
35 2010-10-18 15:00:45
Re: 1439 timus (4 ответов, оставленных в Problems)
Я решал с помощью treap + binary search. Зачем массив на N для сбалансированного дерева ?
36 2010-10-11 11:53:37
Re: Дерево отрезков - память (2 ответов, оставленных в Algo)
4n действительно грубовато но и 2n мало.
тут надо 2 * (min k такое что 2^k >= n)
например для стандартного N <= 100000 хватит
int t[1 << 18]
А вообще пора http://e-maxx.ru/algo/segment_tree переписывать Когда дерево выровнено по 2^k все намного удобнее - можно легко определить за какой сегмент t[ i ] отвечает, легче делать Update и Build - без рекурсии.
Вот мой шаблон:
template <class T>
struct SegmentTree
{
SegmentTree(const T* begin, const T* end)
{
int sz = end - begin;
Create(sz);
copy(begin, end, values + dx);
for (int i = dx - 1; i >= 1; i--)
{
values[i] = values[i * 2] + values[i * 2 + 1];
}
}
SegmentTree(int sz)
{
Create(sz);
}
void Create(int sz)
{
dx = 1;
while (dx < sz)
dx *= 2;
values = new T[dx * 2];
memset(values, 0, sizeof(T) * dx * 2);
}
~SegmentTree()
{
delete[] values;
}
void Update(int pos, T value)
{
pos += dx;
values[pos] = value;
while (pos > 1)
{
pos /= 2;
values[pos] = values[pos * 2] + values[pos * 2 + 1];
}
}
T GetSegment(int l, int r, int pos, int tl, int tr)
{
if (l == tl && r == tr)
return values[pos];
int m = (tl + tr) / 2;
if (r <= m)
return GetSegment (l, r, pos * 2, tl, m);
if (l >= m)
return GetSegment (l, r, pos * 2 + 1, m, tr);
return GetSegment (l, m, pos * 2, tl, m) + GetSegment (m, r, pos * 2 + 1, m, tr);
}
T GetSegment(int l, int r)
{
return GetSegment(l, r, 1, 0, dx);
}
T* values;
int dx;
};
int a[] = {1,2,3,4};
SegmentTree<int> tree(a, a + 4);
int res = tree.GetSegment(0, 4); // r - как и в stl указывает на следующий за последним.
37 2010-10-11 11:40:20
Re: какая структура данных? (6 ответов, оставленных в Problems)
В такой постановке задачи - когда идут только циклические сдвиги на K, нам достаточно иметь один счетчик и прибавлять это K к нему.
38 2010-10-10 10:41:08
Re: MinCostFlow (10 ответов, оставленных в Problems)
Такой подход точно не корректен.
Меняй network следующем образом:
1. ужимаешь координаты в набор s = x0 < x1 < x2 < x3 .. xn = t (не больше 400)
2. между xi -> xi+ 1 ребро стоимостью =0, cap = m
3. между x(ai) ->x(bi) ребро стоимостью = -hi, cap = 1
39 2010-10-10 09:57:00
Re: Метод отжига (3 ответов, оставленных в Problems)
Неужели так лень гуглянуть на эту же фразу "метода отжига решить задачу о ферзях" ???
с первых ссылок и описание найдешь и визулиализатор.
40 2010-09-30 13:50:29
Re: Singapore 2007 (3 ответов, оставленных в Problems)
Решил SKYLINE деревом отрезков. Кроме height еще сохраняй minValue и maxValue.
Скопировал в http://ideone.com/Njt4I если не разберешься.
41 2010-09-21 15:53:39
Re: Eventown Problem (2 ответов, оставленных в Problems)
Толи что-то с тестами, толи так и задумано, но тупой O(2 ^ N * N * N) прошел.
42 2010-09-17 23:26:00
Re: Эффективные алгоритмы факторизации: under investigation (4 ответов, оставленных в Algo)
Посмотрел внимательнее - оказалось такое время получилось когда я свой BigInteger прицепил к темплейтам. На long long сдавалась за 0.29.
Так что вроде все не так и плохо.
43 2010-09-17 23:21:12
Re: двоичное возведение в степень (3 ответов, оставленных в Algo)
Да на самом деле умножений тут ровно столько же кроме случая когда n == 1. просто пользуемся фактом что перед нечетным всегда четное.
44 2010-09-15 08:29:48
Re: Эффективные алгоритмы факторизации: under investigation (4 ответов, оставленных в Algo)
С ним есть определенные непонятки -
пытался его сдать в
https://www.spoj.pl/problems/FACT0/
решает на long long в 2.13
хотя простенький python
def pollard_rho(n, iterations_count):
b0 = random.randint(0, n - 1)
b1 = b0
b1 = mulmod(b1, b1, n)
b1 += 1
if (b1 == n):
b1 = 0
g = gcd(abs(b1 - b0), n)
count = 0
while (count < iterations_count and (g == 1 or g == n)):
count += 1
b0 = mulmod (b0, b0, n)
b0 += 1
if (b0 == n):
b0 = 0
b1 = mulmod (b1, b1, n);
b1 += 1
b1 = mulmod (b1, b1, n);
b1 += 1
if (b1 == n):
b1 = 0
g = gcd (abs (b1 - b0), n)
return g
справился за 1.05
46 2010-09-10 08:38:55
Re: Еще предложения :) (3 ответов, оставленных в Feedback)
Спасибо, все как всегда очень толково
Небольшая опечатка в
new_d[ i ][j] = min (d[ i ][j], d[ i ][k] + d[k][k])
47 2010-09-10 08:31:03
Re: Оффлайн-версия сайта (14 ответов, оставленных в News)
Может в chm есть какой конвертер ? От туда легче было бы копировать. :-)
А в целом, конечно, огромное спасибо, некоторые вещи кроме как у тебя больше нигде не найти.
48 2010-09-09 20:34:52
Re: Timus 1005 (4 ответов, оставленных в Problems)
Думаю самое быстрое решение - разделить все камни пополам (в каждой не больше 10) в каждой из половинок перебрать все подмножества отсортировать и найти лучшую комбинацию ~ O(2^(N / 2) )
49 2010-09-08 22:51:11
Тема: Еще предложения :) (3 ответов, оставленных в Feedback)
Есть предложение в старом добром Флойде (http://e-maxx.ru/algo/floyd_warshall_algorithm) убрать
d2 что б новичков не пугать так намного красивее и чуть быстрее.
for (int k=0; k<n; k++)
{
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
d[ i ][j] = min (d[ i ][j], d[ i ][k]+d[k][j]);
}
И кстати алгоритм http://e-maxx.ru/algo/palindromes_count называется "Algorithm Manacher" описан в Jewels of Stringology.
50 2010-09-07 20:40:25
Re: Наибольший общий префикс двух подстрок (10 ответов, оставленных в Feedback)
Кстати такой lcp подсчет сейчас уже не модный все равно
На http://citeseerx.ist.psu.edu/viewdoc/do … p;type=pdf описан очень простой O(N) алгоритм для построения lcp из уже найденного suffixArray.
Как-то так:
void calcLcp()
{
int q = 0, j;
for(int i = 0; i < N; i++)
{
if(buckets[ i ]==0)
continue;
j = suffixarray[buckets[ i]-1];
while(s[i+q] == s[j+q])
q++;
lcp[buckets[ i ]-1] = q;
if (q > 0) q--;
}
return;
}