Size: a a a

2016 November 01

A

Alex Ф-ф-фэils!🌠︙ in pro.algorithms
#welcome Приветствуем нового участника! Хотим сразу предупредить вас, что если вы не разбираетесь в теме чата, то лучше пройдите в чат для новичков: https://telegram.me/joinchat/BYlFbD3eN3JMaG34hyh96w
Также ознакомьтесь с описанием группы и помните, что при нарушении правил вас могут забанить
источник

G

Group Butler [beta] in pro.algorithms
Alex Ф-ф-фэils!🌠︙
#welcome Приветствуем нового участника! Хотим сразу предупредить вас, что если вы не разбираетесь в теме чата, то лучше пройдите в чат для новичков: https://telegram.me/joinchat/BYlFbD3eN3JMaG34hyh96w
Также ознакомьтесь с описанием группы и помните, что при нарушении правил вас могут забанить
Custom welcome message saved!
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺 in pro.algorithms
Есть идея ежедневно постить сюда задачи, с разбором на следующий день
источник

A

Alex Ф-ф-фэils!🌠︙ in pro.algorithms
гуд идея. Правда, у меня нет идей
источник

DS

Dumitru Savva in pro.algorithms
как-то так
источник

A

Aldar in pro.algorithms
Алоха)
источник

DS

Dumitru Savva in pro.algorithms
Там проще все
источник

A

Alex Ф-ф-фэils!🌠︙ in pro.algorithms
Прив) располагайся)
источник

DS

Dumitru Savva in pro.algorithms
Находишь позицию минимального элемента, вот тебе и граница
источник

DS

Dumitru Savva in pro.algorithms
Дальше два Бин поиска,
источник

DS

Dumitru Savva in pro.algorithms
Все )
источник

A

Aldar in pro.algorithms
Dumitru Savva
Находишь позицию минимального элемента, вот тебе и граница
с чего это
источник

A

Aldar in pro.algorithms
хотя да
источник

A

Aldar in pro.algorithms
а как найти минимальный элемент
источник

A

Aldar in pro.algorithms
не за линейное время
источник

DS

Dumitru Savva in pro.algorithms
Бин поиск))
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺 in pro.algorithms
#algorithm *Бинарный поиск*
Пусть есть некое условие p(i) и отрезок поиска [L, R].
Условие p монотонно - то есть, найдется такое x что оно выполняется для всех чисел <= x и не выполняется для чисел > x.
*Задача*: найти значение x.
*Решение*: будем считать что p(L-1) = true и p(R+1) = false.
Установим в начале l=L-1 и r=R+1 и будем поддерживать инвариант p(l)=true и p(r)=false внутри цикла.

int binarySearch(int L, int R, function<bool(int)> p) {

  int l = L-1, r = R+1;

  while (l + 1 < r) { // итерируемся пока l и r не будут соседними числами

    int mid = (l + r) / 2; // если l и r не соседи то mid != l, mid != r

    if (p(mid)) {

      l = mid;

    } else {

      r = mid;

    }

  }

  return l; // для i <= l p(i) == true, для i > l (i >= r) p(i) == false

}


*Примеры использования*:

_Дан отсортированный массив a = [a0, a1, .., an], все элементы различны. Найти в нем элемент k._
p(i) = a[i] <= k; L=0; R=n. На выходе получим максимальный индекс x такой, что a[x] <= k. Если k есть в массиве то a[x] == k.

_Дан массив a = [a0 > a1 > .. > an < b1 < b2 < .. < bm]. Найти индекс минимального элемента (an).
p(i) = a[i] < a[i+1]; L=0; R=len(a)-1.
На выходе получим максимальный индекс x такой, что a[x] < a[x+1] > a[x+2].
источник

DS

Dumitru Savva in pro.algorithms
Vladislav 🇺🇸🚜🇷🇺
#algorithm *Бинарный поиск*
Пусть есть некое условие p(i) и отрезок поиска [L, R].
Условие p монотонно - то есть, найдется такое x что оно выполняется для всех чисел <= x и не выполняется для чисел > x.
*Задача*: найти значение x.
*Решение*: будем считать что p(L-1) = true и p(R+1) = false.
Установим в начале l=L-1 и r=R+1 и будем поддерживать инвариант p(l)=true и p(r)=false внутри цикла.

int binarySearch(int L, int R, function<bool(int)> p) {

  int l = L-1, r = R+1;

  while (l + 1 < r) { // итерируемся пока l и r не будут соседними числами

    int mid = (l + r) / 2; // если l и r не соседи то mid != l, mid != r

    if (p(mid)) {

      l = mid;

    } else {

      r = mid;

    }

  }

  return l; // для i <= l p(i) == true, для i > l (i >= r) p(i) == false

}


*Примеры использования*:

_Дан отсортированный массив a = [a0, a1, .., an], все элементы различны. Найти в нем элемент k._
p(i) = a[i] <= k; L=0; R=n. На выходе получим максимальный индекс x такой, что a[x] <= k. Если k есть в массиве то a[x] == k.

_Дан массив a = [a0 > a1 > .. > an < b1 < b2 < .. < bm]. Найти индекс минимального элемента (an).
p(i) = a[i] < a[i+1]; L=0; R=len(a)-1.
На выходе получим максимальный индекс x такой, что a[x] < a[x+1] > a[x+2].
Офигеть, если знать такие формальности можно все что угодно написать быстро
источник

A

Aldar in pro.algorithms
источник

V🇺

Vladislav 🇺🇸🚜🇷🇺 in pro.algorithms
Dumitru Savva
Офигеть, если знать такие формальности можно все что угодно написать быстро
оно для того и придумано, мы использовали такую формализацию в нашей acm команде чтобы писать бинкоиск быстро и без багов
источник