Sheephard

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

Т.е. вам надо найти путь из одной клетки в другую, пройдя по как можно меньшему количеству клеток. Можно ходить в 8 направлений - если пересечь угол, то можно за одну точку на ломаной перейти по диагонали.

Немного порисовав вы поймёте, что ответ - миксимум из горизонтального и вертикального расстояний между начальной и конечной клетками.

Надо только аккуратно разобрать случаи, если начальная или конечная точка лежит на границе клетки.

Если я правильно понял задачу, то надо подсчитать для каждого i
sum_{j=1..n} (i%j?1:0) % 2.

Или - есть n ламп в ряд изначально не горящих. Переключаются каждая первая, каждая вторая, третья и т.д. Вопрос - а какие лампы горят в конце.

Разверните условие. Не переключайте каждую 1-ую, 2-ую и т.д. лампу, а подсчитайте для каждой лампы, сколько раз она будет переключена (потому что переключать их все по одной - это медленно. Надо как-то агрегировать вычисления)?

Лампа будет переключена ровно столько раз, сколько делителей у ее номера. Иными словами - вам надо понять, четное ли количество делителей у каждого числа. Вспоминаем, что любое число представимо в виде разложения на простые множители: p1^k1*p2^k2* ... pm^km. Можно подсчитать количество делителей - это будет (k1+1)(k2+1)...(km+1), ведь каждое простое число может входить в делитель в степени от 0 до ki включительно.

Теперь, в каком случае это число будет нечетным? Только если все ki четные. А это значит, что число - полный квадрат (все степени четные же. Берем корень, делим степени пополам, получаем целое число).

Итого ответ - проставить true в массиве по всем индексам i*i.

Будет достаточно, если я приведу тест, на котором ваша программа ошибается?
вот такой тест:
4
1 2 1 3
правильный ответ: 1
ответ вашей программы: 2
P.S. ладно, ошибка в этой части: or (l[i] == vmin and l[imax] > vmin)

Похоже, на строке "abcdef" у вас выдаст d=0, а может и вообще d не напишет.

Проблема в том, что вы пытаетесь считать параллельно для правой и левой половины. Логично, коэффициенты там симметричные будут, но можно сделать ошибку. И ускорения ваша оптимизация практически не несет. В 2 раза меньше итераций, делающих в 2 раза больше + дополнительная проверка каждый раз. На компилируемых языках может быть еще и медленнее наивного цикла от 0 до n-1. В питоне - не знаю. Уж точно не в 2 раза быстрее, как можно было бы подумать.

Еще, я бы вместо последовательного обновления коэффициента в previous считал его явно. i-ый символ встречается ровно в (i+1)*(n-i) подстроках.