Две красивые задачи по алгоритмам

[robofox]

Задача с таблицей решается методом градиентного спуска: наугад прыгаем в любую ячейку и движемся, выбирая соседние клетки с наименьшим значением. За линейное время мы окажемся в каком-нибудь локальном минимуме.

Если представить таблицу в виде плоскости, где числа — это высота участка, то нам надо найти в ней ямку (не обязательно самую глубокую). Мы помещаем шарик в любую точку, сила тяжести катит его вниз по склону. Рано или поздно он окажется в какой-нибудь ямке.

[winger]

Можно придумать тест, на котором градиентный спуск будет работать в среднем за Theta(n^2).

[robofox]

Значит не повезло. Можно придумать тест, в котором минимумов не будет вообще :)

[Mrrl]

Нельзя — все элементы в матрице разные.

[Mrrl]

Кстати, сама по себе непростая задача :) У меня получился пример, который требует около n^2/2 шагов.

[Sayonji]

~N^2/2 легко, а меньше невозможно.

[Colwin]

Например, можно пустить его по спирали :-)

[Mrrl]

Или змейкой. Но надо, чтобы он с неё не вырвался.

[Davidov]

А можно псевдокод? Исходя из вашего описания возникает ощущение, что все-таки Ω(n). Кажется, у меня есть решение, но оно O(log(n)) по памяти.

[alexanderskulikov]

Но где же \Omega(n)? Мы же просто ходим по массиву. Если уж быть совсем формальным, то приведённое в посте решение использует O(\log n) доп. памяти, да (на наши два-три указателя). Псевдокод лениво писать, но могу на вопросы ответить, если что-то всё же недосказанным осталось.

[robofox]

На 3 указателя требуется 3 ячейки памяти. Почему log(n)?

[Mrrl]

3*log(n) бита

[Davidov]

Если решение использует O(log(n)) по памяти, то можно просто завести переменную, в которой хранить встречался элемент или нет и каждый раз делать seen ^= 1<<a[i] и при сбросе бита выводить сообщение, что такой элемент был. По сути это то же самое, что массив.
Ок, вопрос, как будет вести себя алгоритм, если в массиве много хороших циклов вида:
2, 3, ..., k, 1?
Ведь мы должны как-нибудь переходить к следующему циклу, но при этом мы никак не можем отметить, что элементы 2, 3, 4… k мы уже посмотрели.

[Mrrl]

Такая переменная потребует n бит памяти. Это в лучшем случае O(n/log(n)) ячеек.
С циклами фокус в том, что ни один цикл не проходит через ячейку n+1: ведь числа, равного n+1, в массиве нет. Поэтому, начав с n+1, мы рано или поздно войдём в какой-нибудь цикл, но стартовая точка в этот цикл входить не будет. И на точку входа в цикл будет по меньшей мере две ссылки.

[Davidov]

Ок, был не прав. Спасибо. Я кажется понял, где произошло непонимание.

[robofox]

1. Cделаем n+1 шаг из вершины (n+1). После этого мы обязательно окажемся в вершине на цикле.
2. Запомним эту вершину и будем продолжать шагать, пока не вернёмся в неё. Тем самым узнаем длину цикла k.
3. Поставим два указателя в вершину (n+1). Первым указателем сделаем k шагов. После этого будем двигать каждый из указателей на один шаг вперёд, пока они не встретятся.

Сложность меньше чем 3*n.

[Mrrl]

Вторая задача

Будем ловить льва в пустыне делением её пополам.
Пусть n>2. Обозначим m=[(n+1)/2]. Сначала рассмотрим элементы M[m,k] и найдём среди них минимальный. Сравним его с элементами M[m-1,k] и M[m+1,k]. Если он меньше обоих — локальный минимум найден. Иначе будем работать с той половиной матрицы, где лежит меньший из этих двух элементов. Допустим, что это элемент a=M[m-1,k].
Теперь рассмотрим элементы M[j,m] для j=1..m-1 и найдём меньший из них.
Если этот элемент больше a, то возьмём ту четвертинку матрицы (M[1..m-1,1..m-1] или M[1..m-1,m+1..n]), в которой лежит a. Все смежные с этой четвертинкой элементы больше a. Значит, в этой четвертинке есть локальный минимум — и мы свели задачу от размера n к размеру n/2, затратив O(n) операций.
Если M[j,m]<=a, рассмотрим его соседей M[j,m-1] и M[j,m+1]. Меньший из этих элементов обозначим b.
Если b>M[j,m], то локальный минимум найден. В противном случае, все элементы, соседние с четвертинкой матрицы, содержащей b, больше b, и мы снова свели задачу к вдвое меньшей, затратив O(n) операций.
Общее число затраченных на весь поиск сравнений — 3*n+O(log(n)).

Мне эта задача показалась проще первой.

[evans2094]

Вам не кажется что найти минимальный элемент в матрице размером (n/2,n) методом «рассмотрения элементов» — это (n^2)/2 операций, так как нужно рассмотреть (n^2)/2 элементов? Что автоматом убивает любую оптимизацию.
«Градиентный спуск» из центра матрицы с приоритетом движения диагонали, а потом вдоль стороны ближе к реальному варианту, но там тоже можно тестовый пример придумать вида (см. ниже) и иди-броди ищи эту единичку. Если сделать обязательное требование что «для любой ячейки — значения 8 соседних ячеек не равны значению в ячейке, а так же неравны между собой» — тогда проще. А так остается только «поиск таракана на столе методом ощупывания».
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 1 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2

[Mrrl]

В условии явно сказано: «Дана матрица nxn, содержащая различные натуральные числа». Так что приведённый пример к задаче отношения не имеет. При чём здесь «найти минимальный элемент в матрице размером (n/2,n) методом «рассмотрения элементов»», тоже не очень понятно — в матрице (n/2,n) мне достаточно просмотреть n/2+2 элемента плюс время на поиск в матрице размером (n/2,n/2). То есть, задача (n,n) сводится к (n/2,n/2) за 3/2*n+4 обращения к матрице.

[evans2094]

Я привел пример матрицы в которой содержатся различные числа. 1 и 2. Этот пример соответствует условию. Ваш алгоритм не может найти дырку в столе, и к тому же некорректно описан. Вы или некорректно его себе представляете или так описываете что мне абсолютно непонятны ваши рассуждения. Попробуйте его оформить в коде.
Кстати рассечение матрицы на части вводит дополнительный геморрой с рассмотрением случаев внутренних границ.

[Mrrl]

Чтобы локальный минимум гарантированно существовал, нужно, чтобы элементы были попарно различными — иначе два минимальных значения можно поставить рядом, и построить вокруг них воронку из бОльших чисел.
А в коде… пожалуйста.

Правда, там слегка другой алгоритм - он работает за 4*N, а не за 3*N сравнений, но там чуть проще логика и меньше вариантов для перебора.

        static void FindLocMin(int[,] M,int N,out int x,out int y) {
            FindLocMin(M,0,N,0,N,out x,out y);
        }

        private static void FindLocMin(int[,] M,int x0,int lx,int y0,int ly,out int x,out int y) {
            for(;;) {
                if(lx<=2 || ly<=2) {
                    FindLocMinDirect(M,x0,lx,y0,ly,out x,out y); return;
                }
                int mx=lx/2,my=ly/2;
                int xmin=0,ymin=0;
                for(int i=1;i<lx;i++) {
                    if(M[x0+i,y0+my]<M[x0+xmin,y0+my]) xmin=i;
                }
                for(int i=1;i<ly;i++) {
                    if(M[x0+mx,y0+i]<M[x0+mx,y0+ymin]) ymin=i;
                }
                x=x0+mx; 
                y=y0+ymin;
                if(M[x-1,y]<M[x,y]) x--;
                if(M[x0+mx+1,y]<M[x,y]) x=x0+mx+1;
                int x1=x0+xmin,y1=y0+my;
                if(M[x1,y1-1]<M[x1,y1]) y1--;
                if(M[x1,y0+my+1]<M[x1,y1]) y1=y0+my+1;
                if(M[x1,y1]<M[x,y]) {
                    x=x1; y=y1;
                }
                if(x==x0+mx || y==y0+my) return;
                if(x>x0+mx) {
                    x0+=mx+1; lx-=mx+1;
                } else lx=mx-1;
                if(y>y0+my) {
                    y0+=my+1; ly-=my+1;
                } else ly=my-1;
            }
        }

        private static void FindLocMinDirect(int[,] M,int x0,int lx,int y0,int ly,out int x,out int y) {
            x=x0; y=y0;
            for(int i=0;i<lx;i++) for(int j=0;j<ly;j++) {
                    if(M[x0+i,y0+j]<M[x,y]) {
                        x=x0+i; y=y0+j;
                    }
                }
        }

[evans2094]

Первое. Элемент матрицы называется локальным минимумом, если он строго меньше, всех имеющихся у него соседей. В приведённом мной примере он есть.
Второе. С деловым видом проползти по диагонали — не оригинально и не надёжно. Минимумы не обязаны там сидеть.

[evans2094]

Черт. Автор таки дописал слово «попарно» к «различные числа». Теперь с вами не поспоришь :)

[Sayonji]

Интересно, а есть решение у той же задачи, только если матрицу считать тором?

[Mrrl]

Да точно так же: выбираем любую параллель и меридиан (они образуют границу будущего прямоугольника). Находим на них минимальный элемент. Если он — локальный минимум, то всё нашли. Иначе рядом с ним (не на границе) есть элемент меньше его — и меньше всех элементов границы — а значит, на прямоугольнике (N-1,N-1), полученном после вырезания границы, локальный минимум тоже есть. И можно пойти его искать, разрезая прямоугольник на половинки.
Собственно, основная идея: если в какой-нибудь области есть элемент, который меньше любого элемента, граничащего с этой областью, то в этой области есть хотя бы один локальный минимум.

[alexanderskulikov]

Бинго! =) Попроще первой, ога.

[Mrrl]

Кстати, моё решение неправильное. Можно найти контрпример размером 8х8. Но исправить решение не очень сложно.

[hacklex]

В решении первой задачи может помочь факториал.
Если известно, что в массиве из N элементов числа из интервала 1..N-1, то действовать можно так:
1) считаем факториал F = N!
2) если F не делится на A[i], повторяющийся элемент найден
3) иначе делим F на A[i] и проверяем следующий элемент.

Я подразумеваю, что N известно заранее, поскольку автор сказал «массив», а не «список».

[hacklex]

Я также понимаю, чем плохо решение через факториал (произведение быстро становится очень большим; разрядная сетка аккумулятора должна быть длиннее разрядной сетки элементов; перемножение очень больших чисел трудно называть операцией О(1)), но если всё же считать умножение целых чисел операцией O(1), то такое решение соответствует требованиям задачи: получение N! за линейное время, один проход по массиву, одна дополнительная переменная.

[Ogra]

Контрпример, на котором ваш алгоритм не найдет повторяющихся чисел:
N=8
7 2 3 3 2 4 5

[hacklex]

действительно, обшибся

[Mrrl]

Во-первых, N! сам по себе требует O(N) ячеек памяти.
Во-вторых, возьмите N=5 и массив 2,2,4,5,1.
120/2=60
60/2=30
30/4 не делится. Но повторяющийся элемент другой…

[Mrrl]

Конечно, массив 2,2,4,3,1

[hacklex]

угу, обшибся

[evans2094]

За N! можно совсем просто (причем необязательно уже натуральные значения и именно из интервала [1,n]).
Делаем обычный пузырек (как то так)

array a[0..n];
for i=0 to n
begin
for k=(i+1) to n
begin
if a[i]=a[k] then return (a[k]);
end;
end;

В результате за факториал находим все повторяющиеся элементы (и целочисленные, и дробные — без разницы).
Суть задачи имхо в том чтобы правильно воспользоваться целочисленностью и диапазоном значений элементов массива.

[hacklex]

Я ничего не понял. Рискну, однако, задать несколько вопросов:
1) где тут факториал в приведённом коде?
2) в задаче просили O(n), в коде вижу O(n²)…

… Суть задачи ухвачена верно.

[evans2094]

N! есть фаториал, то есть 1*2*..*N-1*N
В моем примере если бы я написал
for i=0 to n
begin
for k=0 to n
begin
if a[i]=a[k] then return (a[k]);
end;
был бы N^2 (N раз делаем N операций). А примере выше — факториал (N раз делаем от N операций до 1-й операции). Но зачем все варианты по два раза проверять? Но еще раз повторюсь. Это решение не учитывает ограничения задачи, позволяющие привести решение к обходу графа. Но зато совершенно не требует дополнительной памяти кроме как два счетчика циклов :)
В первый раз правда натупил с границами циклов, но фиг с ним. общий вид работы алгоритма нагляден.

[hacklex]

Ох…

Ещё раз, прочувствуйте разницу:

1) сложность О(n²), точное число итераций N*(N+1)/2

for i=1 to n
  for k=i to n
     -- итерация тут --

2) сложность О(n!):

for a[1]:=1 to n
  for a[2]:=a1 to n
    ...
     for a[n]:=a[n-1] to n
        -- итерация тут --

Количество for-циклов зависит от n. Вот тогда можно говорить «За факториал». Реализуются такие алгоритмы проще всего рекурсивно. В вашем случае факториал вообще был ни при чём, абсолютно.

[evans2094]

Ох… Чет я не то употребил вчерась. Вы совершенно правы. Мои извинения.

[fshp]

2) если F не делится на A[i], ...

То A[i] не из диапазона 1..n;

[hacklex]

Абсолютно не обязательно. Например, А = { 1, 2, 2 }. Но выше уже дано написали, что ничего не получится через факториал.

[alexanderskulikov]

В общем, как все уже поняли, факториал тут не особо поможет. Это мне напомнило почему-то теорему Вильсона. Она даёт необходимое и достаточное условие того, что число простое. Но алгоритмически её трудно использовать.

[kenoma]

Если массив разрешается портить, то можно было бы последовательно «расставлять» числа по соответствующим им ячейкам до тех пор, пока не будет совершена попытка записи числа n в ячейку n, где уже сидит число n.

[Mrrl]

Например, так:

  int rep(int A[],int N){
    int b=A[N+1];
    while(A[b]!=b){
       int c=A[b];
       A[b]=b;
       b=c;
    }
    return b;
}

[redax]

нет, контр пример:

1 3 2 2

[freopen]

Это решение делает ровно те же перемещения по массиву, что и авторское. Автор, впрочем, также предложил метод нахождения описанного вами места без непосредственной перезаписи.

[kenoma]

Абсолютно с этим согласен, хотел это добавить, но подумал, что это и так очевидно для тех, кто прочел статью.

[DrAlan]

Господа можете на примере например такого массива пошагово расписать как найти за О(n) повторяющийся элемент. Вот никак не могу сообразить.
1 2 3 3

[kenoma]

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

1. Берем «1», смотрим, на какой позиции она находится — она находится в ячейке с индексом «1». Оставляем ее как есть.
2. Переходим ко второму элементу массива «2», он тоже на своем месте.
3. Переходим к третьему элементу массива «3», он тоже на своем месте.
4. Переходим к четвертому элементу массива «3». А вот он не на своем месте, меняем его местами с тем элементом массива, что находится в ячейке с индексом «3». Постойте-ка, там уже записано то же самое значение, значит повтор найден.

Следует отметить, что в общем случае менять элементы массива местами нужно до тех пор, пока все участники операции не встанут на свои места, или не будет найден повтор.

[redax]

Просто из вашего комментария не сразу было понятно что вы предлагаете менять элементы местами.

[redax]

Если можно модифицировать массив, и диапазон значений элементов меньше чем N, я бы предложил что-нибудь такое:
for i=1 to N
A[A[i]] = A[A[i]]+(N+1).
Потом ответ — те i для которых A[i] / (N+1) > 1.

[redax]

Точнее A[(A[i] % (N+1))] = A[A[i]] + (N+1).

[freopen]

Фактически вы запихали дополнительный массив, описанный в начале решения внутрь основного. Такое решение никак не может считаться решением без дополнительной памяти.

[FireStorm]

По первой задачке: самое простое решение, если можно изменять массив — отсортировать его алгоритмом, не требующим дополнительной памяти, например, quicksort-ом. Если есть повторяющиеся элементы, они в отсортированном массиве обязательно будут стоять рядом.

[Mrrl]

quicksort требует O(N^2) времени. А надо уложиться в O(N).

[FireStorm]

Да, вы правы, с сортировкой в ограничение по времени не уложиться, я забыл про это. QuickSort имеет оценку O(N logN), но это несущественно, всё равно ни одна сортировка не имеет O(N).

Изначально я думал пойти по тому же пути, что предлагал kenoma, но это позволит лишь идентифицировать отдельные циклы, но это не нужно, т. к. нам достаточно найти именно тот цикл, в который можно прийти, начав путь в ячейке N+1.

[Mrrl]

Да, quicksort можно заставить гарантированно уложиться в O(N log(N)), но тогда он будет совсем не quick — константа там такая, что он окажется медленнее, чем heapsort. И по пути придётся вспоминать, как искать медиану 7 чисел за 10 сравнений.

[freopen]

А еще Quicksort требует O(log n) дополнительной памяти

[p53]

log n памяти вам и так понадобится, чтобы хранить число n

[Mrrl]

В таком случае, на quicksort понадобится log(N)^2 (если считать в битах)

[FireStorm]

Это верное замечание. Если учитывать расходы на стек, то наихудший случай при неудачном выборе срединного элемента даст нам аж O(N^2).

[freopen]

Это неверно. Мы не можем уйти в стек больше, чем на O(n). Кроме того, можно аккуратно раскрыть хвостовую рекурсию и гарантировать O(log n) для глубины стека в худшем случае.

[FireStorm]

Да, насчёт глубины вызовов O(N^2) — ошибка, правильно O(N).
По поводу «аккуратного раскрытия хвостовой рекурсии» прошу пояснить. Если меняется алгоритм выбора срединного элемента, то придётся учитывать собственно расходы на поиск оптимального элемента.

[Mrrl]

Когда мы делим массив на две части, то можем сначала рекурсивно вызвать qsort на более короткую часть, а вместо второго вызова организовать цикл.

void qsort(T *A,int N){
  while(N>1){
     int k=Split(A,N);  // разделить на две части, вернуть индекс разделяющего элемента
     if(k<N/2){
       qsort(A,k); 
       A+=k+1; 
       N-=k+1;
    }else{
       qsort(A+k+1,N-k-1);
       N=k; 
    }
  }
}

[FireStorm]

Восхитительно!
Если рисовать дерево рекурсивных вызовов этого решения, то получается, что вместо более длинной ветви (определяется по количеству элементов в части), уходящей вниз, здесь будет цикл, уходящий вправо, а от каждого шага цикла будут свои короткие ветви вниз.
Элегантный подход. Спасибо!

[vf1]

Интересно. Но как мы приняли решение:
Давайте встанем в вершину (n+1)
В реальности нам придется проверять все возможные циклы?
Тогда, например для случая: 1 2 3 4 5 6 7 8 8, давайте встанем на вершину 1 и сделаем n+1 переходов для поиска циклов, давайте встанем на вершину 2… и получится O(n*n).

[Mrrl]

Вершина n+1 отличается тем, что через неё циклы не проходят: по условию, все числа в массиве не больше n, и на n+1 переходов нет.
Если бы мы писали на С, то начинали бы с вершины 0.

[vf1]

Действительно, спасибо.

[dorne]

1 — XOR

[dorne]

Поксорить числа от 1 до N, а потом доксорить туда содержимое массива. Останется искомое повторяющееся число.

[Mrrl]

Там может повторяться больше, чем одно число. А некоторые числа могут быть пропущены.
А так можно было бы просто взять сумму. И вычесть N*(N-1)/2. Хотя пришлось бы бояться переполнений.

[dorne]

Сумма не будет линейной O(N), т.к. разрядность сложения нависит от N. В условии задачи сказано, что массив длины N+1 содержит натуральные числа от 1 до N. Это как-бы намекает, что там есть все числа из диапазона (потому что в условии про диапазон не сказано, сказано про числа), и только одно из них повторяется, иначе, это утверждение неверно, и автору стоит изменить условие задачи. Решение в статье считаю неверным, т.к. там решается другая задача и приведен пример не соответствующий условию.

[Mrrl]

После задачи написано:

Сразу поясню. В условии не говорится, что каждое число от 1 до n встречается в массиве, поэтому повторяющихся элементов там может быть сколько угодно (если бы все числа входили по разу, а одно — дважды, то задача была бы гораздо проще)

Так что менять ничего не надо.

[dorne]

О том что говорится и что не говорится в условии должно быть написано в условии а не постфактум. Ато, сформулируют так задачу на конкурсе, потом скажут, а на самом деле мы имели ввиду это. Так не делают. Надо менять условие.

[dorne]

Должен поправиться тут. Если N помещается в машинное слово, то сумма всех поместится в два, следовательно, суммирование будет таки — да линейным.

[Mrrl]

Кстати, тоже хорошая задача. Найти xor всех чисел от 1 до N за O(log N) операций.

[dorne]

В данном случае нет особого смысла, т.к. поиск ксора за линейное время не не влияет на сложность… А так — да.

[0leGG]

За O(1) же ищется, так как 2k XOR 2k + 1 == 1. И дальше считаем, 1 или 0 у нас получится в результате XOR пар (за одно деление/сдвиг) и делаем XOR с N, если N чётное

[Mrrl]

Да, как-то так.

(N&(-((~N)&1)))+((N>>1)&1)

[Mrrl]

Нет, скорее, (N&(-((~N)&1)))+((((N+1)>>1)&1)

[Chamie]

Не очень понимаю ограничение на память для первой задачи.
Можно ли просто завести массив битов длиной n и проходясь по исходному массиву ставить в битовый единичку в позицию, соответствующую значению числа, если там 0, а если там 1, то записывать число в список повторяющихся значений?

[sova]

картинка с графом кривая, да? стрелочки в цикле не туда идут. или я не прав?