Wataru

Никак не ускорить. Сортировка пузырьком - медленная. Имеет квадратичное время выполнения. для 100000 элементов там будет 5 миллиардов сравнений в худшем случае. Для случайных массивов в пару раз меньше в среднем. С учетом, что это питон - вам этих 2х миллиардов операций придется ждать минуту. А с учетом 10 повторений - все 10 минут.

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

Вы генерируете перестановки по одной, пока не отсчитаете k. Это медленно, потому что k может быть очень большим. Перестановок-то n! - это дофига много.

Надо генерировать ее сразу по номеру.

Посмотрите на первый элемент. У первых (n-1)! перестановок там 1, у следующих (n-1)! - там 2, потом идет группа, начинающихся с 3 и т.д.

Уже вы можете понять в какой группе искомая k-ая перестановка. Тупо floor(k/(n-1)!) (если нумерация с 0 и перестановок и групп). Фактически, формула для первого элемента - a[0] = (k-1)/(n-1)! + 1.

Дальше вы можете выкинуть из рассмотрения первый элемент. Сфокусируйтесь на группе с заданным известным первым элементом. Какой номер искомая перестановка имеет среди этих (n-1)!? Надо из k вычесть количество перестановок c меньшими первыми элементами (их (a[0]-1)*(n-1)!. Потом задача сводится к преведущей - сгенерировать k-ую перестановку среди оставшихся n-1 элементов.

Если использовать какое-нибудь дерево отрезков, чтобы быстро искать j-ый пока не занятый элемент, то все решение будет за O(n log n). Если делать совсем просто - двумя циклами - то будет O(n^2). Гораздо быстрее вашего O(n!).

Надо только аккуратно обработать случаи, когда (n-1)! слишком большое. Фактически, вам надо найти максимальный факториал, который меньше k. Пока не спуститесь до этого момента нужно сразу брать первый незанятый элемент и не считать факториал вообще.

Надо обязательно массив массивов? Или подойдут кортежи? Так-то есть zip.

А дальше можно через np.asarray и map преобразовать массив touples в массив массивов.

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

Везде, где вы читаете из файла делайте:

l = f.readline()
print("The line is: \""+l+"\"")
n = int(l)

Тогда сразу станет очевидно, что не так с файлом или кодом.

Кодировка исходного файла не та.

Откройте исходник в блокноте - сохранить как - и выбирайте разную кодировку под именем файла. Если появились кракозябры, измените их на русские да/нет и сохраните файл. Повторите операцию для разных кодировок, пока не сайт не примет.

Нет.

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

Это даже в C++ сделать нельзя, не говоря уже о питоне.

Edit: Вообще говоря в C++ есть realloc, Но оно не гарантирует расширение существующей области памяти. Ибо она может быть занята чем-то еще.

Во-первых, в вашем алгоритме цикл while вообще не нужен. Сколько нужно операций +1, чтобы из a получить a+12345? Ровно 12345. Вам надо просто вычесть одно число из другого.

Далее, мысль должна быть такая: Вот вы знаете, сколько нужно операций, чтобы все числа в массиве привести к X. Вопрос: сколько операций вам понадобится для приведения всех чисел к X+1? (Подсказка - если число было меньше X, то теперь понадобится на 1 операцию больше. Если число было больше X - то понадобится на 1 операцию меньше).

Теперь вам надо посмотреть, подумать и выбрать оптимальное X, которому вы будете приводить все числа. Ваш вариант с max/2 не оптимален.

Бинарный поиск.
Можно реализовать без if-ов вообще.
Суть в том, что у вас есть текущий отрезок. Находите середину, спрашиваете про нее. Получаете ответ R = 0 или 1. Потом прибавляете половину отрезка к левой границе, умноженную на R и вычитаете ее из правой границы, умноженную на 1-R. Таким образом сдвинется только одна граница. Остается вопрос, что делать с выходом из цикла. Там же внутри if запрятан.

Можно или скопировать код 7 раз (2^7 > 100), или иметь бесконечный цикл, который будет сравнивать границы и вызвать одну из двух функций в массиве на 2 элемента. Одна из функций выведет ответ и завершит работу программы через exit. Вторая - не будет делать ничего.

Список/массив на n элементов.