Как найти лямбда максимум

Как рассчитать x, в котором функция получает максимальное значение, используя python функцию lambda.
Например, l = [1, 5, 4, -1], функция x ^ 2. 5 — это x, в котором функция получает максимальное значение.

задан 17 ноя 2017 в 20:11

user274622's user avatar

1

Можно воспользоваться функцией max():

In [315]: l = [1, 5, 4, -1]

In [316]: def func(x):
     ...:     return x**2
     ...:

In [317]: max(l, key=func)
Out[317]: 5

или:

In [321]: max(l, key=lambda x: x**2)
Out[321]: 5

ответ дан 18 ноя 2017 в 0:18

MaxU - stand with Ukraine's user avatar

Можно так:

from functools import reduce

X = [1, 5, 4, -1]
max_x = reduce(lambda a, b: a if a**2 > b**2 else b, X)

Ну а вообще для такой функции как x^2 очевидно, что максимальное значение будет у максимального X, а для этого достаточно просто на списке с вашими значениями использовать max()

ответ дан 17 ноя 2017 в 21:19

Игорь Игоряныч's user avatar

Игорь ИгорянычИгорь Игоряныч

1,8934 золотых знака12 серебряных знаков27 бронзовых знаков

Источник

Here is an example:

library(glmnet)

n <- 500L

x1 <- rnorm(n, 2.0, 0.5)
x2 <- rnorm(n, -1.0, 2)
y <- factor(rbinom(n, 1L, plogis(-0.6 + 1.0 * x1 - 0.8 * x2)))

X <- matrix(c(x1, x2), ncol = 2)

mod <- glmnet(X, y, "binomial")

Now you can see the degrees of freedom and corresponding lambda by simply:

> print(mod)

Call:  glmnet(x = X, y = y, family = "binomial") 

      Df       %Dev   Lambda
 [1,]  0 -1.026e-14 0.149300
 [2,]  1  3.314e-02 0.136000
 [3,]  1  6.073e-02 0.123900
...

So in this case the coefficients are all 0 when lambda is 0.149300 (or higher). To confirm:

> coef(mod, s = 0.149300)
3 x 1 sparse Matrix of class "dgCMatrix"
                   1
(Intercept) 1.688296
V1          .       
V2          .     

> coef(mod, s = 0.136000)
3 x 1 sparse Matrix of class "dgCMatrix"
                      1
(Intercept)  1.64233062
V1           .         
V2          -0.04946726

Note that the vectors for the degrees of freedom and lambda can also be accessed via mod$df and mod$lambda, and you can also change the values of lambda which glmnet tries (if say you wanted to home in on «lambda_max») using for example:

mod <- glmnet(X, y, "binomial", lambda = seq(0.149, 0.151, by = 0.0001))

Источник

Учитывая список пользовательских объектов, найдите максимальное и минимальное значение поля среди пользовательских объектов, используя поток в Java.

1. Использование Stream.max() метод

Идея состоит в том, чтобы преобразовать список объектов в поток объектов, а затем использовать Stream#max() метод, который принимает Comparator для сравнения объектов на основе значения поля и возвращает Optional содержащий максимальный объект в потоке.

Точно так же мы можем использовать Stream#min() метод поиска минимального объекта в потоке.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

import java.util.Arrays;

import java.util.Comparator;

import java.util.List;

// Класс `User`, имеющий приватные поля `name` и `age`

class User

{

    private String name;

    private Integer age;

    public User(String name, Integer age)

    {

        this.name = name;

        this.age = age;

    }

    public Integer getAge() {

        return age;

    }

    // другие геттеры и сеттеры

    @Override

    public String toString() {

        return «[« + name + «, « + String.valueOf(age) + «]»;

    }

}

// Находим максимальное и минимальное значение поля среди пользовательских объектов

// использование потока в Java 8 и выше

class Main

{

    public static void main(String[] args)

    {

        List<User> users = Arrays.asList(new User(«George», 15),

                                        new User(«Tom», 10),

                                        new User(«Mike», 12));

        // получаем пользователя с минимальным возрастом

        User user1 = users.stream()

                        .min(Comparator.comparingInt(User::getAge))

                        .get();

        System.out.println(«User with minimum age: « + user1);

        // получаем пользователя с максимальным возрастом

        User user2 = users.stream()

                        .max(Comparator.comparingInt(User::getAge))

                        .get();

        System.out.println(«User with maximum age: « + user2);

    }

}

Скачать  Выполнить код

результат:

User with minimum age: [Tom, 10]
User with maximum age: [George, 15]

 
Мы также можем передать лямбда-функцию в качестве компаратора, как показано ниже:

// получаем пользователя с минимальным возрастом

User user1 = users.stream()

                .min((x, y) -> x.getAge() — y.getAge())

                //.min((x, y) -> Integer.compare(x.getAge(), y.getAge()))

                .get();

// получаем пользователя с максимальным возрастом

User user2 = users.stream()

                    .max((x, y) -> x.getAge() — y.getAge())

                    //.max((x, y) -> Integer.compare(x.getAge(),y.getAge()))

                    .get();

Скачать  Выполнить код

2. Использование коллекторов

Мы также можем использовать Collectors чтобы найти максимальный или минимальный объект в списке.

Collectors#maxBy() возвращает Collector который производит максимальный объект в соответствии с заданным Comparator. Сходным образом, Collectors#maxBy() возвращает Collector который производит минимальный объект в соответствии с заданным Comparator.

// получаем пользователя с минимальным возрастом

User user1 = users.stream()

                .collect(Collectors.minBy(Comparator.comparingInt(User::getAge)))

                .get();

// получаем пользователя с максимальным возрастом

User user2 = users.stream()

                .collect(Collectors.maxBy(Comparator.comparingInt(User::getAge)))

                .get();

Скачать  Выполнить код

 
Мы также можем передать лямбда-функцию в качестве компаратора, как показано ниже:

// получаем пользователя с минимальным возрастом

User user1 = users.stream()

                .collect(Collectors.minBy((x, y) -> x.getAge() — y.getAge()))

                .get();

// получаем пользователя с максимальным возрастом

User user2 = users.stream()

                .collect(Collectors.maxBy((x, y) -> x.getAge() — y.getAge()))

                .get();

Скачать  Выполнить код

3. Использование Stream.reduce() метод

Мы также можем выполнить операцию редукции над элементами потока, используя метод Stream.reduce() метод, возвращающий Optional описывающий редуцированный объект.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

import java.util.Arrays;

import java.util.List;

// Класс `User`, имеющий приватные поля `name` и `age`

class User

{

    private String name;

    private Integer age;

    public User(String name, Integer age)

    {

        this.name = name;

        this.age = age;

    }

    public Integer getAge() {

        return age;

    }

    // другие геттеры и сеттеры

    @Override

    public String toString() {

        return «[« + name + «, « + String.valueOf(age) + «]»;

    }

}

// Пользовательский класс

class Compare

{

    public static User min(User a, User b) {

        return a.getAge() < b.getAge() ? a : b;

    }

    public static User max(User a, User b) {

        return a.getAge() > b.getAge() ? a : b;

    }

}

// Находим максимальное и минимальное значение поля среди пользовательских объектов

// использование потока в Java 8 и выше

class Main

{

    public static void main(String[] args)

    {

        List<User> users = Arrays.asList(new User(«George», 15),

                new User(«Tom», 10),

                new User(«Mike», 12));

        // получаем пользователя с минимальным возрастом

        User user1 = users.stream()

                .reduce(Compare::min)

                .get();

        System.out.println(«User with minimum age: « + user1);

        // получаем пользователя с максимальным возрастом

        User user2 = users.stream()

                .reduce(Compare::max)

                .get();

        System.out.println(«User with maximum age: « + user2);

    }

}

Скачать  Выполнить код

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

// получаем пользователя с минимальным возрастом

User user1 = users.stream()

                .reduce((a, b) -> a.getAge() < b.getAge() ? a : b)

                .get();

// получаем пользователя с максимальным возрастом

User user2 = users.stream()

                .reduce((a, b) -> a.getAge() > b.getAge() ? a : b)

                .get();

Скачать  Выполнить код

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

// получаем пользователя с минимальным возрастом

User user1 = users.stream()

                .reduce(new User(«Dummmy», Integer.MAX_VALUE),

                        (a, b) -> a.getAge() < b.getAge() ? a : b);

// получаем пользователя с максимальным возрастом

User user2 = users.stream()

                .reduce(new User(«Dummmy», Integer.MIN_VALUE),

                        (a, b) -> a.getAge() > b.getAge() ? a : b);

Скачать  Выполнить код

Вот и все, что касается поиска максимума и минимума пользовательских объектов в Java.

Источник

В этой статье мы научимся находить максимальное значение в списке на Python. Для всестороннего понимания вопроса мы рассмотрим использование некоторых встроенных функций, простые подходы, а также небольшие реализации известных алгоритмов.

Сначала давайте вкратце рассмотрим, что такое список в Python и как найти в нем максимальное значение или просто наибольшее число.

В Python есть встроенный тип данных под названием список (list). По своей сути он сильно напоминает массив. Но в отличие от последнего данные внутри списка могут быть любого типа (необязательно одного): он может содержать целые числа, строки или значения с плавающей точкой, или даже другие списки.

Хранимые в списке данные определяются как разделенные запятыми значения, заключенные в квадратные скобки. Списки можно определять, используя любое имя переменной, а затем присваивая ей различные значения в квадратных скобках. Он является упорядоченным, изменяемым и допускает дублирование значений. Например:

list1 = ["Виктор", "Артем", "Роман"]
list2 = [16, 78, 32, 67]
list3 = ["яблоко", "манго", 16, "вишня", 3.4]

Далее мы рассмотрим возможные варианты кода на Python, реализующего поиск наибольшего элемента в списке, состоящем из сравниваемых элементов. В наших примерах будут использоваться следующие методы/функции:

  1. Встроенная функция max()
  2. Метод грубой силы (перебора)
  3. Функция reduce()
  4. Алгоритм Heap Queue (очередь с приоритетом)
  5. Функция sort()
  6. Функция sorted()
  7. Метод хвостовой рекурсии

№1 Нахождение максимального значения с помощью функции max()

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

В приведенном ниже примере список передается функции max в качестве аргумента.

list1 = [3, 2, 8, 5, 10, 6]
max_number = max(list1)
print("Наибольшее число:", max_number)



Наибольшее число: 10

Если элементы списка являются строками, то сначала они упорядочиваются в алфавитном порядке, а затем возвращается наибольшая строка.

list1 = ["Виктор", "Артем", "Роман"]
max_string = max(list1, key=len)
print("Самая длинная строка:", max_string)



Самая длинная строка: Виктор

№2 Поиск максимального значения перебором

Это самая простая реализация, но она немного медленнее, чем функция max(), поскольку мы используем этот алгоритм в цикле.

В примере выше для поиска максимального значения нами была определена функция large(). Она принимает список в качестве единственного аргумента. Для сохранения найденного значения мы используем переменную max_, которой изначально присваивается первый элемент списка. В цикле for каждый элемент сравнивается с этой переменной. Если он больше max_, то мы сохраняем значение этого элемента в нашей переменной. После сравнения со всеми членами списка в max_ гарантировано находится наибольший элемент.

def large(arr): 
    max_ = arr[0]
    for ele in arr:
        if ele > max_:
           max_ = ele
    return max_ 


list1 = [1,4,5,2,6]
result = large(list1)
print(result)  # вернется 6

№3 Нахождение максимального значения с помощью функции reduce()

В функциональных языках reduce() является важной и очень полезной функцией. В Python 3 функция reduce() перенесена в отдельный модуль стандартной библиотеки под названием functools. Это решение было принято, чтобы поощрить разработчиков использовать циклы, так как они более читабельны. Рассмотрим приведенный ниже пример использования reduce() двумя разными способами.

В этом варианте reduce() принимает два параметра. Первый — ключевое слово max, которое означает поиск максимального числа, а второй аргумент — итерабельный объект.

from functools import reduce


list1 = [-1, 3, 7, 99, 0]
print(reduce(max, list1))  # вывод: 99

Другое решение показывает интересную конструкцию с использованием лямбда-функции. Функция reduce() принимает в качестве аргумента лямбда-функцию, а та в свою очередь получает на вход условие и список для проверки максимального значения.

from functools import reduce


list1 = [-1, 3, 7, 99, 0]
print(reduce(lambda x, y: x if x > y else y, list1))  # -> 99

№4 Поиск максимального значения с помощью приоритетной очереди

Heapq — очень полезный модуль для реализации минимальной очереди. Если быть более точным, он предоставляет реализацию алгоритма очереди с приоритетом на основе кучи, известного как heapq. Важным свойством такой кучи является то, что ее наименьший элемент всегда будет корневым элементом. В приведенном примере мы используем функцию heapq.nlargest() для нахождения максимального значения.

import heapq


list1 = [-1, 3, 7, 99, 0]
print(heapq.nlargest(1, list1))  # -> [99]

Приведенный выше пример импортирует модуль heapq и принимает на вход список. Функция принимает n=1 в качестве первого аргумента, так как нам нужно найти одно максимальное значение, а вторым аргументом является наш список.

№5 Нахождение максимального значения с помощью функции sort()

Этот метод использует функцию sort() для поиска наибольшего элемента. Он принимает на вход список значений, затем сортирует его в порядке возрастания и выводит последний элемент списка. Последним элементом в списке является list[-1].

list1 = [10, 20, 4, 45, 99]
list1.sort()
print("Наибольшее число:", list1[-1])



Наибольшее число: 99

№6 Нахождение максимального значения с помощью функции sorted()

Этот метод использует функцию sorted() для поиска наибольшего элемента. В качестве входных данных он принимает список значений. Затем функция sorted() сортирует список в порядке возрастания и выводит наибольшее число.

list1=[1,4,22,41,5,2]
sorted_list = sorted(list1)
result = sorted_list[-1]
print(result)  # -> 41

№7 Поиск максимального значения с помощью хвостовой рекурсии

Этот метод не очень удобен, и иногда программисты считают его бесполезным. Данное решение использует рекурсию, и поэтому его довольно сложно быстро понять. Кроме того, такая программа очень медленная и требует много памяти. Это происходит потому, что в отличие от чистых функциональных языков, Python не оптимизирован для хвостовой рекурсии, что приводит к созданию множества стековых фреймов: по одному для каждого вызова функции.

def find_max(arr, max_=None):
    if max_ is None:
        max_ = arr.pop()
    current = arr.pop()
    if current > max_:
        max_ = current
    if arr:
        return find_max(arr, max_)
    return max_


list1=[1,2,3,4,2]
result = find_max(list1)
print(result)  # -> 4

Заключение

В этой статье мы научились находить максимальное значение из заданного списка с помощью нескольких встроенных функций, таких как max(), sort(), reduce(), sorted() и других алгоритмов. Мы написали свои код, чтобы попробовать метод перебора, хвостовой рекурсии и алгоритма приоритетной очереди.

Источник

Лямбда-оптимизация

Лямбда-оптимизация (также известная как aliens trick, дискретный метод множителей Лагранжа, WQS Binary Search, Lagrangian Relaxation и т.д.) — очень мощная и красивая идея оптимизации динамики, которая стала широко известна после IOI 2016. Позже выяснилось, что подобная задача уже встречалась ранее (к примеру, в 2012 году на зимних петрозаводских сборах, в более ранних китайских олимпиадах и даже в одной научной статье 1992 года), однако действительно популярна эта оптимизация стала именно после 2016 года. Так как это новая и сложная в деталях тема, то вокруг нее есть множество мифов и заблуждений. В этой статье я попытался собрать исчерпывающий источник всей информации, которая известна про лямбда-оптимизацию. Если вы знаете какую-то идею, которая здесь не упоминается, напишите, пожалуйста, об этом мне в телеграме.

Кроме того, часто так случается, что лямбда-оптимизация внутри себя использует Convex Hull Trick, поэтому если вы с ним не знакомы, рекомендуется сначала изучить его перед прочтением этой статьи.

Идея на примере задачи

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

Задача:
Дан массив неотрицательных чисел $a$ длины $n$. Назовем мощностью подотрезка квадрат суммы его элементов. Необходимо разбить массив $a$ на $k$ подотрезков таким образом, чтобы минимизировать сумму мощностей подотрезков разбиения. Иными словами, выделить такие $k — 1$ чисел (границы подотрезков разбиения) $i_1$, $i_2$, $ldots$, $i_{k — 1}$, чтобы

$$(a_1 + a_2 + ldots + a_{i_1 — 1})^2 + (a_{i_1} + a_{i_1 + 1} + ldots + a_{i_2 — 1})^2 + ldots + (a_{i_{k — 1}} + ldots + a_{n})^2$$

было минимально.

Собственно, лямбда-оптимизация обычно и применяется в подобных задачах, где нужно как-то разбить массив на $k$ подотрезков оптимальным образом.

Давайте придумаем какое-нибудь решение. Построим двумерную динамику $dp[i][c]$ размера $n times k$, которая будет равна минимальной стоимости разбиения первых $i$ элементов массива на $c$ подотрезков. Ответ на задачу, соответственно, будет храниться в $dp[n][k]$.

Чтобы пересчитать эту динамику, нужно перебрать позицию $j$, в которой будет заканчиваться предыдущий отрезок разбиения:

$$dp[i][c] = min limits_{j < i} dp[j][c — 1] + (a_{j + 1} + a_{j + 2} + ldots + a_i)^2$$

Такую динамику в самом простом случае можно считать за $O(n^3 k)$ или $O(n^2 k)$, если насчитывать сумму $a_{j + 1} + ldots + a_i$ налету или же заметить, что она равна $pref[i] — pref[j]$, где $pref$ — массив префиксных сумм массива $a$.

После чего стандартные оптимизации динамики типа разделяй и властвуй, оптимизации Кнута — Яо или Convex Hull Trick могли бы попробовать уменьшить асимптотику этого решения до $O(n k log n)$, $O(n^2)$ или $O(nk)$.

Давайте для примера рассмотрим, как решать эту задачу при помощи Convex Hull Trick. Это решение понадобится нам далее.

Перепишем формулу через префиксные суммы:

$$dp[i][c] = min limits_{j < i} dp[j][c — 1] + (pref[i] — pref[j])^2$$

Раскроем скобки:

$$dp[i][c] = min limits_{j < i} dp[j][c — 1] + pref[i]^2 — 2 cdot pref[i] cdot pref[j] + pref[j]^2$$

Вынесем за знак минимума фиксированный член $pref[i]^2$:

$$dp[i][c] = pref[i]^2 + min limits_{j < i} dp[j][c — 1] — 2 cdot pref[i] cdot pref[j] + pref[j]^2$$

И перегруппируем:

$$dp[i][c] = pref[i]^2 + min limits_{j < i} (-2 pref[j]) cdot pref[i] + (dp[j][c — 1] + pref[j]^2)$$

Получилось, что нужно найти минимум линейных функций вида $(-2pref[j]) cdot x + (dp[j][c — 1] + pref[j]^2)$ в точке $x = pref[i]$. Тогда получается, что эту динамику можно считать по слоям (по возрастанию $c$) за $O(n k log n)$ при помощи Convex Hull Trick. Можно заметить, что так как элементы массива неотрицательны, то $pref[i]$ не убывают, поэтому можно воспользоваться методом двух указателей вместо бинпоиска внутри Convex Hull Trick и уменьшить время работы до $O(n k)$.

Однако что делать, если ограничения на $n$ и $k$ очень большие? К примеру, $n, k le 10^5$. Тут уже точно никак не обойтись этой динамикой, потому что ее размер слишком большой. В этот момент к нам на помощь как раз таки и приходит лямбда-оптимизация. Ее идея заключается в том, что мы избавимся от второй размерности в динамике. Тогда новая динамика $dp[i]$ будет просто минимальной стоимостью разбить первые $i$ элементов массива на сколько-то подотрезков без ограничения на их количество. Ее формула пересчета будет выглядеть следующим образом:

$$dp[i] = min_{j < i} dp[j] + (pref[i] — pref[j])^2$$

Однако очевидно, что в этом случае оптимальное разбиение разделит наш массив на $n$ подотрезков длины $1$, потому что именно в таком случае стоимость будет минимальна.

Чтобы этого избежать, мы будем штрафовать за каждый новый подотрезок, который мы берем. Давайте введем константу $lambda$ (лямбда), и тогда стоимость подотрезка будет равна не $(pref[i] — pref[j])^2$, а $(pref[i] — pref[j])^2 + lambda$. Формула пересчета динамики поменяется от этого совсем не сильно:

$$dp[i] = min_{j < i} dp[j] + (pref[i] — pref[j])^2 + lambda$$

Теперь давайте подумаем, что будет происходить с ответом при разном выборе константы $lambda$. Если лямбда равна нулю, то эта динамика ничем не отличается от динамики без штрафа. В оптимальном решении мы выберем разбиение на $n$ подотрезков. Если же мы будем постепенно увеличивать лямбду, то стоимость использования большего количества отрезков будет возрастать, и мы постепенно будем использовать все меньше и меньше подотрезков. В пределе при очень больших лямбдах (к примеру, $10^{100}$), стоимость использования еще одного подотрезка будет уже больше, чем вся стоимость разбиения, поэтому оптимальное разбиение будет использовать всего один подотрезок, в котором будут лежать все элементы массива.

После всех этих рассуждений последняя идея уже совсем очевидна: давайте запустим бинпоиск по лямбде и найдем такую лямбду, для которой в оптимальном разбиении будет ровно $k$ подотрезков, Тогда если ответ на задачу со штрафом равен $dp[n]$, то ответ на изначальную задачу — это $dp[n] — lambda k$, потому что надо вычесть стоимость $k$ подотрезков, на которые мы разбиваем наш массив. Остается лишь заметить, что формула нашей динамики с лямбдой практически такая же, как в двумерной динамике, поэтому ее можно насчитывать за $O(n log n)$ или даже $O(n)$ при помощи Convex Hull Trick (в отличие от динамики по слоям, здесь пересчет динамики происходит через себя, поэтому прямые нужно добавлять по ходу подсчета динамики, но их угловые коэффициенты убывают, так что это можно без проблем делать), и итоговая асимптотика решения задачи будет равна $O(n log C)$, где $C$ — разность левой и правой границы для лямбды в бинпоиске.

Таким образом, изначальную динамику за $O(n^3 k)$ мы смогли соптимизировать до $O(n log C)$. Невероятно!

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

В принципе, нельзя сказать, что этот алгоритм какой-то особенно сложный, однако с ним часто возникают проблемы при реализации. Первый вопрос, который, возможно, уже пришел к вам в голову: а точно ли необходимая лямбда найдется? Не может ли быть такой ситуации, что для какой-то конкретной $lambda$ оптимальное количество подотрезков разбиения — это $k + 1$, а для $lambda + 1$ ответ уже $k — 1$, и нигде не достигается ровно $k$ подотрезков? Давайте разберемся в этом вопросе!

Определим $f(c)$ как ответ на изначальную задачу для $c$ подотрезков (то есть $dp[n][c]$ в нашей изначальной двумерной динамике). Тогда оптимальный ответ при штрафе $lambda$ будет равен $min_{c} f(c) + c cdot lambda$. Так как это минимум линейных функций, давайте изобразим это в виде прямых на плоскости (идея, схожая с Convex Hull Trick).

test

Тогда алгоритм коректен, если для каждого $c$ есть такая точка $x = lambda$, что в этой точке минимум достигается именно для $c$ подотрезков. То есть, иными словами, на картинке представлен корректный Convex Hull Trick, и никакую прямую из него не надо выкинуть. В каком же случае это будет верно? Давайте посмотрим на точки пересечения соседних прямых (для $c$ подотрезков и $c + 1$ подотрезка). Тогда необходимо, чтобы эти точки пересечения возрастали.

Чему равна точка пересечения этих прямых? Это точка, в которой $f(c) + cx = f(c + 1) + (c + 1) x$. Это можно переписать как $x = f(c) — f(c + 1)$. Мы хотим, чтобы эти точки убывали по $c$, то есть, иными словами, $f(c — 1) — f(c) > f(c) — f(c + 1)$. Возможно, вы уже поняли, что это означает. Это свойство функции называется выпуклостью (или выпуклостью вверх).
Тогда если наша функция $f$ удовлетворяет этому свойству, то лямбда-оптимизация будет работать. Заодно мы поняли, что бинпоиск можно запускать только по целым числам. Действительно, ведь точки пересечения имеют вид $f(c) — f(c + 1)$, что является целым числом, ведь сами значения функции $f$ — это целые числа (стоимости разбиений на $c$ подотрезков).

test

Здесь есть одна маленькая тонкость. Пусть $f(c — 1) — f(c) + 1 = f(c) — f(c + 1)$, то есть точка пересечения $c$-й прямой с $c + 1$-й на единицу больше, чем точка пересечения $c — 1$-й прямой с $c$-й. Тогда может возникнуть такая ситуация, что при $lambda = f(c — 1) — f(c)$ мы выберем ответ, в котором будет $c — 1$ отрезков, а для $lambda = f(c) — f(c + 1)$ мы уже выберем ответ с $c + 1$ отрезками, и тогда $c$ отрезков нигде не будет достигаться.

Эта проблема решается одним очень простым приемом: при подсчете динамики давайте не просто минимизировать стоимость, но и при равных стоимостях давайте минимизировать количество используемых подотрезков. От этого подсчет динамики не станет сильно сложнее. Тогда в точке $f(c + 1) — f(c)$ оптимальное разбиение разобьет наш массив как раз ровно на $c$ подотрезков.

Аналогично, лямбда оптимизация работает, если выполняется обратное условие: $f(c — 1) — f(c) > f(c) — f(c + 1)$. Это условие называется выпуклостью (или выпуклостью вверх). Как мы поняли, лямбда-оптимизацию можно применять, если функция является выпуклой или вогнутой. Иногда эти условия так же называются условиями строгой выпуклости или вогнутости. Однако на практике так получается, что почти никогда функции не удовлетворяют этим условиям.
Обычно функции удовлетворяют условиям нестрогой выпуклости и вогнутости, которые формулируются следующим образом:

$$f(c — 1) — f(c) ge f(c) — f(c + 1)$$

или

$$f(c — 1) — f(c) le f(c) — f(c + 1)$$

И на самом деле, функция $f$ из нашей задачи тоже удовлетворяет именно условию нестрогой вогнутости. Это можно заметить на примере массива $[0, 0, 0]$. Для него стоимость разбиения на любое количество подотрезков равна нулю, поэтому $f(1) — f(2) = f(2) — f(3)$.

Замечание:
Пока что мы не доказываем, что в нашей задаче функция $f$ нестрого вогнутая, потому что это чаще всего совершенно не тривиальный факт. Мы докажем его (а также дадим инструмент для доказывания этого в других задачах) чуть позже. Однако обычно при написании решения этот факт просто берется на веру и не доказывается.

Что же делать, если наша функция нестрого выпуклая? В этом случае все еще существует оптимальное число $lambda$, однако может возникнуть такая ситуация, что в одной точке пересекается сразу несколько прямых. К примеру, прямые для $c — 1$, $c$ и $c + 1$. Тогда в этой точке оптимальное разбиение будет использовать $c — 1$ подотрезков, а в следующей уже $c + 1$ подотрезка, и так получается, что прямая для $c$ нигде не доминирует.

test

Однако это не проблема! Мы все так же можем бинпоиском найти лямбду, в которой разбиение на $k$ отрезок будет оптимальным (это наибольшая лямбда, в которой в оптимальном разбиении не более $k$ подотрезка). Однако если нам вернули, что в этой точке оптимально использовать $c$ подотрезков, и стоимость равна $Y$, то стоимость разбиения на $k$ подотрезков без штрафа будет попросту равна $Y — k lambda$, ведь через точку $(lambda, Y)$ проходит прямая $f(k) + xk$. Обратите внимание, что мы вычитаем из $Y$ именно $k lambda$, а не $c lambda$. $Y — c lambda$ — это стоимость оптимального разбиения массива на $c$ подотрезков, а нам нужно $k$.

Применение лямбда-оптимизации вне динамического программирования

Идею лямбда-оптимизации необязательно использовать именно для задач динамического программирования. Давайте познакомимся с примером такой задачи.

Задача:
Дан граф с весами на ребрах. Необходимо найти вес минимального остовного дерева, в котором степень первой вершины равна $k$.

В этой задаче можно ввести число $lambda$ и прибавить его к весам всех ребер, инцидентных первой вершине, после чего найти в получившемся графе остов минимального веса. Если лямбда — большое отрицательное число, то всегда выгодно брать ребра из вершины $1$, и в оптимальном остове будет максимальное их количество. Если же лямбда — большое положительное число, то брать ребра из вершины $1$ очень невыгодно, и в оптимальном ответе будет только одно такое ребро.

Осталось лишь запустить бинпоиск по лямбде и найти такую лямбду, при которой в оптимальном ответе степень первой вершины будет равна $k$.

Упражнение:
Дано дерево с весами на ребрах. Найдите в нем паросочетание размера $k$ минимального веса.

Восстановление ответа

Мы научились находить оптимальную стоимость разбиения массива на $k$ подотрезков при условии, что функция стоимости $f(k)$ является нестрого выпуклой. Теперь давайте поймем, как восстанавливать ответ. То есть как находить то самое оптимальное разбиение, если это спрашивается в задаче. В случае строгой выпуклости это очень просто: у нас есть конкретное $lambda$, при котором мы разбили наш массив на $k$ подотрезков. Необходимо просто в конце запустить еще раз подсчет динамики для оптимального $lambda$ и при подсчете поддерживать предков как в любой обычной динамике.

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

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

Хранение минимального и максимального количества подотрезков в оптимальных разбиениях

Мы уже и так храним не только значение динамики, но и минимальное количество подотрезков, на которые можно разбить массив, чтобы достигался оптимальный ответ. Давайте хранить не только минимальное количество подотрезков, но и максимальное! Назовем эти значения $l[i]$ и $r[i]$: минимальное и максимальное количество подотрезков, на которые можно разбить первые $i$ элементов массива с данным штрафом $lambda$, чтобы стоимость разбиения была оптимальна. Мы уже знаем, что чем больше лямбда, тем меньше отрезков нам надо использовать, и если при одной и той же лямбде можно оптимально разбить массив и на $l[i]$ подотрезков, и на $r[i]$, то можно за ту же стоимость разбить его и на любое количество подотрезков между ними.

Теперь мы можем идти с конца и постепенно восстанавливать ответ. Мы знаем, что $l[n] le k le r[n]$, потому что $k$ подотрезков дают оптимальный ответ для данной лямбды. Теперь мы будем перебирать позиции по убыванию, пытаясь найти позицию $j$, через которую мы могли бы оптимально пересчитать значение динамики для $n$. Для этого должно, во-первых, выполняться, что $dp[n] = dp[j] + (pref[n] — pref[j])^2 + lambda$, а во-вторых, должно быть возможно разбить массив до позиции $j$ оптимальным образом ровно на $k — 1$ подотрезков (чтобы с добавлением еще одного весь массив разбился ровно на $k$ подотрезков), то есть должно быть выполнено: $l[j] le k — 1 le r[j]$. Когда мы нашли такое $j$, то мы знаем, что последний подотрезок разбиения — это $[j + 1, n]$, и можем продолжать процесс поиска следующего подотрезка. Так мы за $O(n)$ сможем восстановить необходимое разбиение.

Второй бинпоиск для уточнения $k$

Пускай мы уже нашли лямбду, для которой $k$ подотрезков являются оптимальными, но минимальное количество подотрезков в оптимальном разбиении меньше $k$. Тогда запустим еще один бинпоиск уже при фиксированной лямбде, который попытается сделать разбиение ровно с $k$ подотрезками. Раньше при равной стоимости мы минимизировали количество подотрезков в разбиении, а теперь введем константу $mid$, такую что для индексов, меньших $mid$, мы будем брать большее количество подотрезков в разбиении при равной стоимости, а для индексов, не меньших $mid$, будем брать меньшее количество подотрезков в разбиении при равной стоимости. При $mid = 0$ мы всегда выбираем меньшее количество подотрезков и получим разбиение, в котором не больше $k$ подотрезков, а при $mid = n$ мы всегда предпочитаем большее количество подотрезков и получим разбиение, в котором не меньше $k$ подотрезков. Тогда мы можем запустить бинпоиск по константе $mid$ в надежде, что найдется такая константа, для которой в оптимальном разбиении будет ровно $k$ подотрезков. Разумеется, то, что такая константа найдется, не гарантируется.

Тогда мы сначала запускаем наше обычное решение без восстановления ответа, находим оптимальную лямбду, и уже для оптимальной лямбды запускаем бинпоиск по $mid$. Асимптотика этого решения — $O(n (log C + log n))$.

Комбинация двух путей

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

Доказательство выпуклости функции $f$

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

Пока что мы принимали на веру, что функция $f(k)$ для нашей задачи является выпуклой или вогнутой. И чаще всего при решении вы и не будете это доказывать. Вы либо просто верите в это, либо, возможно, интуитивно понимаете, что стоимость перехода от решения с $k$ подотрезками к решению с $k + 1$ подотрезками убывает или возрастает ($f(k) — f(k + 1)$ убывает или возрастает). Иными словами, можно это понимать так: если есть решения для $k + 1$ и $k — 1$, то из них можно переконструировать два решения для $k$, и тогда одно из них будет иметь вес, не больший среднего арифметического $f(k + 1)$ и $f(k — 1)$.

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

Сведение к mincost-k-flow

Пререквизиты: знание стоимостных потоков.

Стандартная задача, в которой ответ выпуклый, — это mincost-k-flow. Пусть дана сеть со стоимостями на ребрах. Определим $f(k)$ как минимальную стоимость потока величины $k$ в этой сети. Тогда утверждается, что $f(k)$ — выпуклая функция. Действительно, давайте вспомним, как ищется поток минимального веса. Чтобы перейти от потока величины $k$ к потоку величины $k + 1$, мы находим кратчайший путь в остаточной сети и пускаем по нему единицу потока. Стоимость этого увеличения как раз равна длине кратчайшего пути. Но ведь длина кратчайшего пути не убывает при возрастании $k$, поэтому $f(k + 1) — f(k)$ не убывает. Что и требовалось доказать.

То есть если ответ на нашу задачу можно выразить как стоимость минимального потока в какой-то сети, то функция $f$ будет являться выпуклой, а значит, мы можем применять в этой задаче лямбда-оптимизацию. Обратите внимание, что размер сети может быть сколь угодно большой, ведь мы не собираемся реально решать нашу задачу при помощи mincost-а. Мы лишь хотим доказать, что это можно сделать. Решать же задачу мы будем лямбда-оптимизацией.

Давайте рассмотрим пример задачи, в которой можно доказать выпуклость функции $f$ сведением к mincost-у.

Задача:
Дан массив $a$ длины $n$. Необходимо выбрать $k$ непересекающихся пар соседних элементов этого массива и закрыть их доминошками так, чтобы сумма всех оставшихся чисел была максимальна.

Давайте сначала заметим, что сумма всех оставшихся чисел — это сумма всех чисел минус сумма закрытых чисел, так что нам надо минимизировать сумму закрытых чисел. Во-вторых, можно заметить, что каждая доминошка закрывает ровно одну ячейку массива на четной позиции и ровно одну на нечетной. Поэтому если мы рассмотрим двудольный граф, в одной доли которого будут четные индексы, а в другой — нечетные, и между индексами $i$ и $i + 1$ для всех $i$ будет проведено ребро веса $a_i + a_{i + 1}$, то нам нужно просто в этом двудольном графе найти паросочетание размера $k$ минимального веса.

Но ведь поиск минимального паросочетания можно легко свести к поиску потока минимального веса. Необходимо лишь ориентировать ребра паросочетания слева направо и поставить на них пропускную способность $1$, а также добавить сток и исток и провести из истока ребра нулевого веса и единичной пропускной способности во все вершины левой доли, а из всех вершин правой доли провести ребра нулевого веса и единичной пропускной способности в сток. Тогда минимальный вес потока величины $k$ в этом графе будет как раз таки равен ответу для $k$ доминошек для нашей изначальной задачи, а значит, мы можем решать ее при помощи лямбда-оптимизации.

Неравенство четырехугольника

Если наша задача заключается в разбиении массива на $k$ подотрезков, то ее квадратичную динамику можно представить в таком виде:

$$dp[i][c] = min limits_{j < i} dp[j][c — 1] + w(j, i)$$

Тогда верно следующее утверждение:

Предложение:
Если функция $w$ удовлетворяет неравенству четырехугольника, то есть для любых $a le b le c le d$ выполнено

$$w(a, c) + w(b, d) le w(a, d) + w(b, c)$$

Тогда функция $f(c) = dp[n][c]$ является нестрого выпуклой (если неравенство в обратную сторону, то вогнутой).

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

Доказательство:
Полностью доказывать это утверждение мы не будем, потому что это весьма объемный труд. Ознакомиться с ним можно во второй части этой статьи.

Если коротко, то доказательство состоит из последовательной проверки следующих фактов:

  1. Если есть два оптимальных разбиения на отрезки $P$ и $Q$, и в $P$ один из отрезков — это $[a, b]$, а в $Q$ один из отрезков — это $[c, d]$, и выполняется $a le c le d le b$, то эти два отрезка можно поменять на $[a, d]$ и $[c, b]$, а также поменять местами концы путей $P$ и $Q$ после точек $d$ и $b$, и полученные пути тоже будут оптимальными. Этот факт понять весьма легко. Получившиеся пути будут тоже являться некоторыми разбиениями, однако сумма их длин будет не больше, чем сумма длин изначальных путей, по неравенству четырехугольника. Тогда если изначальные были оптимальными, то на самом деле достигается равенство, и два новых пути также являются оптимальными.

  2. Для любых двух оптимальных разбиений, таких что в одном из них хотя бы на $m$ отрезков больше, чем в другом, есть такая пара отрезков, как в прошлом факте, что если отрезок $[a, b]$ является $i$-м в первом разбиении, то отрезок $[c, d]$ является $i+m$-м во втором разбиении. Доказывается этот факт индукцией по обеим длинам путей.

  3. И тогда совмещая два предыдущих факта, можно понять, что если есть два оптимальных пути длины $k_1$ и $k_2$, то для любого числа $k$ между ними есть оптимальный путь длины $k$.

  4. Из чего в конечном итоге и следует, что $f(c)$ является выпуклой.

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

Несложно проверить, что неравенство четырехугольника выполняется и для многих других задач на лямбда-оптимизацию. К примеру, накрыть точки на прямой $k$ отрезками, минимизировав сумму квадратов их длин, или разбить массив на $k$ подотрезков, максимизировав сумму побитового «или» подотрезков, и так далее. Кажется, большинство задач на лямбда-оптимизацию удовлетворяют этому свойству.

Применение 1D1D-оптимизации

И на самом деле это полезно не только с теоретической точки зрения! Наша формула для одномерной динамики при фиксированной лямбде выглядит следующим образом:

$$dp[i] = min limits_{j < i} dp[j] + w’(j, i)$$

где $w’(j, i) = w(j, i) + lambda$. Если $w$ удовлетворяет неравенству четырехугольника, то и $w’$ тоже ему удовлетворяет, потому что лямбды в неравенстве сокращаются. А одномерную динамику такого вида, в которой функция пересчета удовлетворяет неравенству четырехугольника, можно считать при помощи 1D1D-оптимизации. Поэтому на самом деле комбинация лямбда-оптимизация + 1D1D-оптимизация решает практически все задачи на лямбда-оптимизацию.

Восстановление ответа при условии неравенства четырехугольника

При доказательстве выпуклости функции $f$ одним из промежуточных фактов мы доказали следующее утверждение:

Лемма:
Для любых двух оптимальных разбиений, таких что в одном из них хотя бы на $m$ отрезков больше, чем в другом, есть такая пара вложенных отрезков $[a, b]$ и $[c, d]$, что если отрезок $[a, b]$ является $i$-м в первом разбиении, то отрезок $[c, d]$ является $i+m$-м во втором разбиении.

И в таком случае мы поняли, что ребра $[a, b]$ и $[c, d]$ можно заменить на $[a, d]$ и $[c, b]$, а также поменять концы двух путей, и тогда если один путь имел длину $k_1$, а другой — $k_2$, то итоговые пути будут иметь длины $k_2 + m$ и $k_1 — m$. То есть если взять правильное $m$, то мы можем построить путь любой длины между $k_1$ и $k_2$.

Тогда при условии верности неравенства четырехугольника можно восстанавливать ответ следующим способом. Пусть мы уже нашли оптимальную лямбду, и для нее минимальное количество подотрезков в оптимальном разбиении — это $l$, а максимальное — это $r$. Тогда восстановим ответы для $l$ и $r$ (максимизируя/минимизируя количество подотрезков разбиения при равной стоимости), после чего используя эти два пути восстановим путь длины $k$ ($l le k le r$). Необходимо просто идти по отрезкам разбиения двумя указателями и проверять, не нашли ли мы такую пару вложенных отрезков, что индекс первого в первом разбиении на $k — l$ меньше, чем индекс второго во втором разбиении. И в этом случае нужно взять префикс первого пути, суффикс второго и объединить их ребром. Вот и получился оптимальный ответ для разбиения на $k$ подотрезков.

Задача линейного программирования

Для прочтения этого раздела не обязательно быть знакомым с задачей линейного программирования, но это точно сильно облегчит понимание.

В данном разделе мы рассмотрим максимально общую задачу, к которой можно сводить изначальную, чтобы ответ был выпуклым.

На самом деле нам подходят ограниченные задачи целочисленного линейного программирования, в которых переход к вещественными числам не добавляет новых базовых решений. Давайте разбираться, что все это значит.

Определение:
Сформулируем задачу линейного программирования. Есть набор переменных $x_1$, $x_2$, $ldots$, $x_n$. Имеется набор $m$ условий:

$a_{i, 1} x_{i, 1} + a_{i, 2} x_{i, 2} + ldots + a_{i, j_i} x_{i, j_i} le b_i$

А также линейная функция $f(x_1, x_2, ldots, x_n) = c_1 x_1 + c_2 x_2 + ldots + c_n x_n$. Необходимо найти значения переменных $x_i$, которые удовлетворяют всем условиям и максимизируют (или минимизируют) функцию $f$.

Если $x_i$ должны быть целыми, то эта задача называется задачей целочисленного линейного программирования.

Обозначим за $b$ вектор, состоящий из $b_i$. Обозначим за $g_r(b)$ тот самый максимум функции $f$ при данных ограничениях для задачи линейного программирования, а за $g(b)$ обозначим максимум функции $f$ при данных ограничениях для задачи целочисленного линейного программирования.

Без труда можно понять, что $g_r(b)$ является вогнутой функцией. Давайте возьмем $b_1$ и $b_2$, а также $0 le t le 1$. Пусть $x^1$ максимизирует $f$ при ограничениях $b_1$, а $x^2$ максимизирует $f$ при ограничениях $b_2$. $x = t x^1 + (1 — t) x^2$. Тогда раз $x^1$ и $x^2$ удовлетворяют всем ограничениям, то и $x$ как их линейная комбинация с суммой коэффициентов $1$ удовлетворяет им. А также $f(x) = t f(x^1) + (1 — t)f(x^2) = tg_r(b_1) + (1-t)g_r(b_2) le g_r(tb_1 + (1-t)b_2)$, потому что $f$ — линейная функция. Что и требовалось доказать.

Однако из того, что $g_r$ является вогнутой, не следует, что $g$ обязательно является вогнутой. Ведь может так получиться, что $g(b) le g_r(b)$. Однако иногда все таки верно, что $g(b) = g_r(b)$. И тогда мы как раз можем с уверенностью сказать, что функция $g$ тоже выпуклая. А именно, это выполняется, если любое $x$, удовлетворяющее условиям, можно выразить как афинную комбинацию (линейную комбинацию с суммой коэффициентов, равной единице) каких-то целочисленных $x^j$, удовлетворяющих условиям. В таком случае мы можем записать, что $f(x)$ равно линейной комбинации $f(x^1)$ с суммой коэффициентов $1$ (то есть некоторой средневзвешенной сумме), поэтому $f(x) le max_j f(x^j) le g(b)$. Что и требовалось доказать.

Если область $mathbb{R}^n$, где верны все условия, является ограниченной (какой-то $n$-мерный многогранник), то любая точка внутри него является какой-то афинной комбинацией вершин этого многогранника. Поэтому на самом деле нам достаточно проверить, что все вершины являются целочисленными. Иными словами, если некоторые неравенства обращаются в равенство таким образом, что все переменные можно однозначно восстановить.

К примеру, можно без труда доказать, что нашу задачу про сумму квадратов сумм элементов в подотрезках можно выразить как задачу линейного программирования, а потом проверить, что все вершины являются целочисленными. Введем $n + C_n^2$ переменных $x_1$, $x_2$, $ldots$, $x_n$, $d_{i, j}$ ($1 le i < j le n$), где $x_i$ — номер отрезка, которому принадлежит $i$-й элемент, а $d_{i j}$ говорит о том, лежат ли $i$-й и $j$-й элементы в одной группе. Мы введем следующие ограничения:

$$1 le x_1 le x_2 le ldots le x_n le k$$

$$0 le d_{i j} le 1$$

$$1 — (x_j — x_i) le d_{i j}$$

И тогда линейная фунция $f(x_i, d_{ij}) = sum_{i = 1}^{n} a_i^2 + sum_{i < j} 2 d_{i j} cdot a_i cdot a_j$ как раз таки и будет равна ответу на нашу задачу, если мы рассматриваем целочисленную версию задачи линейного программирования. На самом деле $d_{i j}$ может быть равно единице даже если $x_i$ и $x_j$ лежат в разных блоках, но от этого $f$ только увеличится, поэтому это не точка оптимума. Теперь остается лишь проверить, что если некоторые неравенства обратились в равенства так, что все переменные восстанавливаются однозначно, то решение будет целочисленным. Это останется читателю в качестве упражнения.

Также можно заметить, что на самом деле задача поиска mincost-k-flow также является частным случаем этого метода. Можно заметить, что все ограничения в потоках выражаются в виде таких неравенств, а стоимость потока — линейная функция от них. Остается лишь вспомнить, что мы знаем, что если пропускные способности всех ребер целые, то и в оптимальном ответе по всем ребрам текут целые величины потоков.

Источники

  • Хорошая статья на английском языке
  • Восстановление ответа в лямбда-оптимизации
  • Собрание задач и источников
  • О сведении к задаче линейного программирования
  • Связь с методом множителей Лагранжа
  • Альтернативный способ понимания необходимости выпуклости фукнции $f$
  • Статья 1995 года, в которой доказывается выпуклость при условии неравенства четырехугольника
  • Статья 1992 года, использующая схожую идею

Задачи

  • Базовый пример задачи
  • Базовый пример задачи 2
  • Решить задачу для бóльшими ограничениями лямбда-оптимизацией
  • Применение лямбда-оптимизации не в задаче оптимизации динамики
  • Еще одно применение лямбда-оптимизации не в задаче оптимизации динамики
  • USACO 2017 January Contest, Platinum, Problem 2. Building a Tall Barn
  • ОСТОРОЖНО!!! СПОЙЛЕРЫ К IOI!!! Задача с IOI2016

Источник

Понравилась статья? Поделить с друзьями:

Не пропустите также:

  • Код ошибки 0x4004f00d office 2013 как исправить
  • Кроссаут ошибка 10011 как исправить
  • Как исправить оценки до конца года
  • Шайтан как найти надо
  • Как найти высоту конуса вписанного в сферу

    • 0 0 голоса
    Рейтинг статьи
    Подписаться
    Уведомить о
    guest

    0 комментариев
    Старые
    Новые Популярные
    Межтекстовые Отзывы
    Посмотреть все комментарии