26

(8 ответов, оставленных в Problems)

Известно в этой задаче какое максимальное количество студентов может быть ?

27

(8 ответов, оставленных в Problems)

Ограничения хоть бы написал.

28

(12 ответов, оставленных в Algo)

"если n>=m бин коэф делится на M"    Не похоже что правда. С[1000000000][999999999] = 1000000000

29

(12 ответов, оставленных в Algo)

Привет

Что у нас есть из алгоритмов что б найти  (C[n, k])  для K <= N < 10^9
по _не простому_ модулю M < 10 ^ 5

?

30

(2 ответов, оставленных в Algo)

http://e-maxx.ru/forum/viewtopic.php?id=269

31

(4 ответов, оставленных в Problems)

Идея с минимального контролирующего множества провалилась. sad Пошло бы если бы бомбой уничтожали только ряд или только колонку.
Сдал перебором всех возможных колонок.  Интересно как ее за 22ms решили.

32

(4 ответов, оставленных в Problems)

Думай в сторону графов и минимального контролирующего множества.

33

(4 ответов, оставленных в Feedback)

смотри ниже. Там cnt используется и для других целей.

34

(6 ответов, оставленных в Problems)

Это я про 1/4финальное условие - "фактически циклический сдвиг на к - это и есть поменять две соседние подстроки"

Для этого условия сместить вначале на a потом на b =   сместить один раз на (a + b) (по модулю)

35

(4 ответов, оставленных в Problems)

Я решал с помощью treap + binary search.  Зачем массив на N для сбалансированного дерева ?

36

(2 ответов, оставленных в Algo)

4n действительно грубовато но и 2n мало.
тут надо 2 * (min k такое что 2^k >= n)

например для стандартного N <= 100000 хватит
int t[1 << 18]

А вообще пора http://e-maxx.ru/algo/segment_tree переписывать smile Когда дерево выровнено по 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

(6 ответов, оставленных в Problems)

В такой постановке задачи - когда идут только циклические сдвиги на K, нам достаточно иметь один счетчик и прибавлять это K к нему.

38

(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

(3 ответов, оставленных в Problems)

Неужели так лень гуглянуть на эту же фразу "метода отжига решить задачу о ферзях" ???
с первых ссылок и описание найдешь и визулиализатор.

40

(3 ответов, оставленных в Problems)

Решил SKYLINE деревом отрезков. Кроме height еще сохраняй minValue и maxValue.
Скопировал в http://ideone.com/Njt4I если не разберешься.

41

(2 ответов, оставленных в Problems)

Толи что-то с тестами, толи так и задумано, но тупой O(2 ^ N * N * N) прошел.

Посмотрел внимательнее - оказалось такое время получилось когда я свой BigInteger прицепил к темплейтам. На long long  сдавалась за 0.29.

Так что вроде все не так и плохо. smile

43

(3 ответов, оставленных в Algo)

Да на самом деле умножений тут ровно столько же кроме случая когда n == 1.  просто пользуемся фактом что перед нечетным всегда четное.

С ним есть определенные непонятки -
пытался его сдать в

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

45

(14 ответов, оставленных в News)

Спасибо! smile

46

(3 ответов, оставленных в Feedback)

Спасибо,  все как всегда очень толково smile

Небольшая опечатка в

new_d[ i ][j] = min (d[ i ][j], d[ i ][k] + d[k][k])

47

(14 ответов, оставленных в News)

Может в chm есть какой конвертер ? От туда легче было бы копировать. :-)

А в целом, конечно, огромное спасибо, некоторые вещи кроме как у тебя больше нигде не найти.

48

(4 ответов, оставленных в Problems)

Думаю самое быстрое решение - разделить все камни пополам (в каждой не больше 10)   в каждой из половинок перебрать все подмножества отсортировать и найти лучшую комбинацию ~ O(2^(N / 2) )

49

(3 ответов, оставленных в Feedback)

Есть предложение в старом добром Флойде (http://e-maxx.ru/algo/floyd_warshall_algorithm) убрать
d2 что б новичков не пугать smile  так намного красивее и чуть быстрее.

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

(10 ответов, оставленных в Feedback)

Кстати такой lcp подсчет сейчас уже не модный все равно smile

На 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;
}