Вчера вечером дочка попросила помочь с задачей из экзамена ЕГЭ по информатике, к которому она готовится. В школе никто из них не смог, преподаватель сказал что-то умное — и его никто не понял. Язык — Python. Я сначала воспринял задачу на слух и решил "другую". Потом все же внимательно прочитал и начал решать. Решил, но что-то сложно получалась для экзамена, где около 30 заданий (это конечно одно из самых сложных и за него дается 4 балла). К тому же закралось сомнение в правильности гипотезы, которую я положил в основу решения. Только я решил ее доказывать, как сразу нашел нормальное решение... Дочка сказала, что я монстр, и я был этим очень доволен...
Предлагаю для разминки. Естественно, интересен только вариант Б. Вполне подходит для собеседований.

Для заданной последовательности неотрицательных целых чисел необходимо найти максимальное произведение двух её элементов, номера которых различаются не менее чем на 8. Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000.
Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов. Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе.
 
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования. Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла.
 
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
 
Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
Обязательно укажите, что программа является решением задания Б.
Максимальная оценка за правильную программу, эффективную по времени и по памяти — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
 
Входные данные представлены следующим образом. В первой строке задаётся число N — общее количество элементов последовательности. Гарантируется, что N > 8. В каждой из следующих N строк задаётся одно неотрицательное целое число – очередной элемент последовательности.
Пример входных данных:
10
100
45
55
245
35
25
10
10
10
26
Программа должна вывести одно число — описанное в условии произведение. Пример выходных данных для приведённого выше примера входных данных: 2600.

UPDATE
Решение дал watchmaker. Желающие сделать сами — не смотрите его сообщение

Здравствуйте, Serg27, Вы писали:
S>

S>Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
 
S>Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.

Казалось бы, за один проход находим 9 самых больших чисел с их позициями, ну а дальше тупо перебираем 36 пар?

Здравствуйте, Erop, Вы писали:

E>Казалось бы, за один проход находим 9 самых больших чисел с их позициями, ну а дальше тупо перебираем 36 пар?

Это и был мой второй вариант. Для этого нужно уметь делать списки из кортежей (дочка впервые услышала про tuple от меня), введение списка 9 самых больших чисел требует либо сложной логике по его обновлению, либо знания, что списки можно сортировать (что тоже дочка не знала) и т.п. Кроме того я задумался — верна ли посылка о 9 самых больших числах с позициями и начал искать контр-примеры... Но тут я и придумал более простое решение.

Здравствуйте, Serg27, Вы писали:

S>Для заданной последовательности неотрицательных целых чисел необходимо найти максимальное произведение двух её элементов, номера которых различаются не менее чем на 8

Если есть такая пара с индексами i<j, то произведение пары с индексами k,j, где k < i, будет не больше. То есть достаточно просто хранить максимум из уже просмотренных элементов и умножать только на него. Естественно с задержкой 8.

int solve() {
    const int d = 8;
    int b[d] = {0};
    int n = get_next_int();
    int r = 0;
    int m = 0;
    for (int i = 0; i < n; ++i) {
        int& e = b[i % d];
        m = max(m, e);
        e = get_next_int();
        r = max(r, m * e);
    }
    return r;
}

Здравствуйте, watchmaker, Вы писали:


W>Если есть такая пара с индексами i<j, то произведение пары с индексами k,j, где k < i, будет не больше. То есть достаточно просто хранить максимум из уже просмотренных элементов и умножать только на него. Естественно с задержкой 8.

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

Здравствуйте, Serg27, Вы писали:


S>Это и был мой второй вариант. Для этого нужно уметь делать списки из кортежей (дочка впервые услышала про tuple от меня), введение списка 9 самых больших чисел требует либо сложной логике по его обновлению, либо знания, что списки можно сортировать (что тоже дочка не знала) и т.п. Кроме того я задумался — верна ли посылка о 9 самых больших числах с позициями и начал искать контр-примеры... Но тут я и придумал более простое решение.

А что такое "более простое"?
Вот смотри, пишу из головы:

struct xxxFinder {
    enum { maxDist = 8 };
    std::vector<std::pair<int, int>>data;
    int curPos;

    xxxFinder() : curPos( 0 ), data(std::pair<int, int>(0, 0), maxDist + 1 ) { };

    void pushNumber( int n )
    {
        curPos++;
        if( n > data[0].first ) {
            int i = 0;
            while( i < maxDist && data[i+1].first < n ) {
                data[i] = data[i+1];
                i++;
            }
            data[i].first = n;
            data[i].second = curPos;
        }
    }
    int maxProd()
    {
        int res = 0;
        for( int i = 0; i < data.size(); i++ ) {
            for( int j = i + 1; j < data.size(); j++ ) {
                if( abs( data[i].second - data[j].second ) > minDist && data[i].first * data[j].first > res ) {
                    res = data[i].first * data[j].first > res ;
                }
            }
        }
        return res;
    }
};

Оно, по идее, и решение и простое.

Здравствуйте, Erop, Вы писали:

E>Оно, по идее, и решение и простое.
Да, оно и решение и простое. Но решение, которое дал watchmaker проще — кода меньше, затраты времени и памяти меньше.
Конечно если говорить о production то эти решения равнозначны — главное написать их правильно...

Здравствуйте, Serg27, Вы писали:

S>Да, оно и решение и простое. Но решение, которое дал watchmaker проще — кода меньше, затраты времени и памяти меньше.
S>Конечно если говорить о production то эти решения равнозначны — главное написать их правильно... Правда отличия могут проявится если будет число не 8, а скажем 100000000.

Ну это всегда так, если решение есть, а нужно "другое, но лучше", при этом не понятно чем лучше, то трудно придумать, так как не понятно о чём думать

Здравствуйте, Serg27, Вы писали:

S>Предлагаю для разминки. Естественно, интересен только вариант Б. Вполне подходит для собеседований.

Им бы гвоздь в голову забить за упоротые бюрократизмом формулировки. Решение вполне очевидно: скользящее окно по максимум 8 элементов с их позициями.

s = [10, 100, 45, 55, 245, 35, 25, 10, 10, 10, 26]

buffer = [(0, 0)]
result = 0

for i in range(len(s)):
  candid = s[i] * max(map(lambda p: p[1], filter(lambda p: i - p[0] > 8, buffer)), default=0)

  if candid > result:
    result = candid

  if s[i] > max(map(lambda p: p[1], buffer)):
    buffer.append((i, s[i]))

  buffer = buffer[0:8]


print(result)

S>Решение дал watchmaker. Желающие сделать сами — не смотрите его сообщение
Задача С4.
Если сделать А — тоже пойдет.
Б — это практически вопрос на собеседовании в компьютерную контору...

Здравствуйте, pestis, Вы писали:

P>Им бы гвоздь в голову забить за упоротые бюрократизмом формулировки. Решение вполне очевидно: скользящее окно по максимум 8 элементов с их позициями.
Идея решения та же что у Егора и что мой "второй вариант". Реализация чуть другая — поиск максимума делается сразу в цикле прохода. Недостаток тот же — реализация сложнее (чем у watchmaker), больше расходы на вычисления и памяти.
Видно, что такое решение скорее всего и будет реализовано — сразу пришло в голову 3 человекам (я, Егор и Вы) из 4.

Здравствуйте, Serg27, Вы писали:

S>Идея решения та же что у Егора и что мой "второй вариант". Реализация чуть другая — поиск максимума делается сразу в цикле прохода. Недостаток тот же — реализация сложнее (чем у watchmaker), больше расходы на вычисления и памяти.

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

S>Видно, что такое решение скорее всего и будет реализовано — сразу пришло в голову 3 человекам (я, Егор и Вы) из 4.

Логично. В условиях экзамена стрейтфорвард решения рулят. Хотя экзамены уже давно стали не те что прежде. Лет 10 назад попался мен под руку вариант вступительных в топовый местный вуз, так я их за 20 минут решил в уме абсолютно не напрягаясь. В мое время народ по полгода интенсивно готовился, прорешивал по 100 задач в день и все равно большинство не могло осилить 5 задач из билета за отведенное время.

Здравствуйте, Serg27, Вы писали:

S>Я сначала воспринял задачу на слух и решил "другую".

Про поиск максимума среди чисел, отличающихся по расстоянию не БОЛЕЕ чем на 8?
Тогда это элементарно, скользящее окно, шириной 8.

Или про среди чисел, отличающихся по ЗНАЧЕНИЮ?


Имхо, простое решение вот какое.
1. Пусть у нас нет ограничений по расстоянию (точнее, расстояние не менее 1). Тогда берём две порядковые статистики, m1 = max(A) и m2 = max(A\{m1}), и очевидно, что максимум произведения равен m1*m2.
2. Пусть расстояние не менее 2. Тогда, если m1 и m2 соседи, мы не можем их взять. Но возьмём m3. Из набора {m1,m2,m3} выберем наибольшую пару, которая не является соседями, и вуаля.
8. Пусть расстояние не менее 8. Тогда, очевидно, возьмём 8 порядковых статистик (и, разумеется, запомним их координаты).

Теперь надо лишь аккуратно это закодировать.

import heapq # для 8 элементов можно было бы и вручную запилить приоритетную очередь, даже без кучи

def read_int():
  return int(raw_input())

W = 8
N = read_int()
assert N > W

H = [] # куча (приоритетная очередь) пар (значение,индекс)
for i in range(N):
  if i > W:
    heapq.heappop(H) # младшенького долой!
  heapq.heappush(H, (read_int(),i))
  assert len(H) == min(i+1, W)

assert len(H) == W

# ну а теперь - танцы! танцуют все со всеми, потому что сортировать и оптимизировать лень! O(W*W) = O(1), ибо константа же
print max(a*b for a,i in H for b,j in H if abs(i,j)>=W)

E>Ну это всегда так, если решение есть, а нужно "другое, но лучше", при этом не понятно чем лучше, то трудно придумать, так как не понятно о чём думать
Там написано, чем: памятью и скоростью.
Квадратичный алгоритм с массивлвм на все числа — это минимально допустимый вариант решения.
Если в нем нет ошибок, то получишь 2 сырых балла.
Если улучшаешь, то получаешь 3 или даже 4 сырых балла — максимум.

Здравствуйте, LaptevVV, Вы писали:

LVV>Квадратичный алгоритм с массивлвм на все числа — это минимально допустимый вариант решения.
Я дал алгоритм линейный по времени и константный по памяти. Вся потребная память -- массив из 9 пар интов...
Альтернативное решение содержит массив из 9 интов и не содержит финального забега по 36 парам. Этим он лучше.

LVV>Если в нем нет ошибок, то получишь 2 сырых балла.
LVV>Если улучшаешь, то получаешь 3 или даже 4 сырых балла — максимум.
Почему?

Здравствуйте, Кодт,

К>Про поиск максимума среди чисел, отличающихся по расстоянию не БОЛЕЕ чем на 8?
К>Тогда это элементарно, скользящее окно, шириной 8.

Только один я читаю в исходном сообщении треда?

....необходимо найти максимальное произведение двух её элементов, номера которых различаются не менее чем на 8.

LVV>>Квадратичный алгоритм с массивом на все числа — это минимально допустимый вариант решения.
E>Я дал алгоритм линейный по времени и константный по памяти. Вся потребная память -- массив из 9 пар интов...
E>Альтернативное решение содержит массив из 9 интов и не содержит финального забега по 36 парам. Этим он лучше.
Ну так это и есть оптимальный.
За него получаешь 4 балла, если нет ошибок — они прописаны в инструкциях для эксперта.
LVV>>Если в нем нет ошибок, то получишь 2 сырых балла.
LVV>>Если улучшаешь, то получаешь 3 или даже 4 сырых балла — максимум.
E>Почему?
Квадратичный алгоритм с массивом на все числа — это решение задачи А.
Ее улучшение — это решение задачи Б.
За задачу Б максимум 4 балла, если нет ошибок.

Здравствуйте, Vlad_SP, Вы писали:

К>>Про поиск максимума среди чисел, отличающихся по расстоянию не БОЛЕЕ чем на 8?
К>>Тогда это элементарно, скользящее окно, шириной 8.

V_S>Только один я читаю в исходном сообщении треда?
V_S>

V_S> ....необходимо найти максимальное произведение двух её элементов, номера которых различаются не менее чем на 8.

Только один ты не читаешь предыдущую строчку:
S>Я сначала воспринял задачу на слух и решил "другую".

Вот мне и стало интересно, какую другую задачу решал Serg27

Здравствуйте, Кодт, Вы писали:

К>Только один ты не читаешь предыдущую строчку:
S>>Я сначала воспринял задачу на слух и решил "другую".

К>Вот мне и стало интересно, какую другую задачу решал Serg27
Да, именно другую — по расстоянию не БОЛЕЕ 8.

Здравствуйте, LaptevVV, Вы писали:

LVV>Ну так это и есть оптимальный.
Ну так в теме сравнивают два таких решения