Wataru

Доказательство не верно из-за индуктивного перехода. Вы рассматриваете только уже отсортированные наборы задач. Не ясно, что добавляя задачи в другом порядке вы получаете варианты не лучше. Вы так же не показали, что вот эти 2 варианта дают оптимальное время для k+1 задачи.

Правильное доказательство весьма простое и без индукции. Общее время будет

Max(sum{i-начальнику}(bi), max{i - подчиненным}(ai))

.
Отсюда видно, что если вы какую-то задачу дали подчиненному, то все задачи с меньшим A нет смысла давать начальнику. Ведь второе слагаемое-максимум от этого не изменится, но первое увеличится. Можно "бесплатно" выполнить эти задачи подчиненными. Поэтому в оптимальном ответе вы даете какое-то множетсво минимальных A подчиненым, а остальные начальнику. Иначе можно какие-то задачи перекинуть с начальника на подчиненного и уменьшить первое слагаемое не меняя второе, уменьшив таким образом ответ, т.е. в этом случае решение точно не оптимальное.
Чтобы все варианты возможных оптимумов перебрать надо отсортировать задачи по возрастанию A. Это код и делает. поддерживается сумма B у всех оставшихся задач, а от текущей берется A - который и будет максимумом для всех задач с меньшим A.

В такой реализации это плохо видно, но можно переписать основной цикл так:

j = Len(B)-1
for i in range(len(A)):
  while j >= 0 and A[i] + B[j] > c:
    --j;
  if A[i] + B[j] == c:
    found = True
    break

В этом случае после цикла while поддерживается инвариант, что a[i]+b[j] <= c и это максимальное такое j.
Ведь, если этот инвариант поддерживался для пердыдущей итерации, то у нас было a[i-1] +b[j] <=c и a[i-1]+b[j+1]>c. Отсюда получается, a[i]+b[j+1] >= a[i-1]+b[j+1] > c. Т.е. если мы уменьшим j в цикле while инвариант останется действовать - это будет самое большое j, т.ч. a[i]+b[j] <= c.

А этот инвариант гарантирует, что когда в цикле по i переберется значение из ответа, j гарантированно будет указываать на j из ответа. Потому что, если существуют i', j', т.ч. a[i']+b[j'] = c, то можно увеличить j' пока b там не меняется, т.ч. b[j']>b[j'], отсюда получается a[i']+b[j'] <=c и a[i']+b[j+1] > c - а это и есть наш инвариант. Т.е. на итерации i=i' найдется именно j=j'.

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

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

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

Поэтому время всегда случайная величина с весьма большим разбросом.

Единственный способ научиться решать задачи - решать задачи. Много и разных. Если задачи по програмированию, то прорешивайте какой-нибудь leetcode. Если минут за 5 вообще идей нет - смотрите подсказки. Еще через 10 - смотрите чужие решения. Важно только потом все равно эти решения самостоятельно написать потом сразу.

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

Это называется IPC (inter-process communication). Гуглите IPC + ваш язык программирования, что-то да найдете. Полно библиотек готовых. Есть способы по-производительнее сокетов (всякие отображаемые в память файлы, например), но велосипед тут переизобретать смысла нет, если это только не задание на курсе по программированию.

Еще можно пользоваться потоками ввода-вывода. В зависимости от платформы, при создании процесса вы можете получить дескрипторы входного и выходного потоков порожденного процесса. Туда вы можете писать, как в файл, и читать оттуда, как из файла. А дочерний процесс будет как-бы читать с экрана и выводить туда, как-будто он обычное консольное приложение.

Мешать можно. Особо память это не сократит, а реализацию сильно усложнит.

Выведите 6^2, 66^2 и так далее. N до 20 хотя бы. Посмотрите на числа. Можете ли вы угадать цифру на заданной позиции без подсчета всего числа?

Подсказка, вы получите вот такие вот числа:

36
4356
443556
44435556
4444355556
444443555556
44444435555556
4444444355555556
444444443555555556
44444444435555555556
4444444444355555555556
444444444443555555555556
44444444444435555555555556
4444444444444355555555555556
444444444444443555555555555556
44444444444444435555555555555556
4444444444444444355555555555555556
444444444444444443555555555555555556
44444444444444444435555555555555555556
4444444444444444444355555555555555555556

Этот паттерн можно и доказать. Надо лишь представить возводимое в квадрат число как (10**n-1)2/3 и применить чуть-чуть элементарной алгебры, вроде формулы квадрата разности.

Обычно берут тип данных с запасом так, чтобы переполнения не было.
Если же переполнение действительно может произойти, то есть несколько подходов:
- игнорировать переполнение. Иногда это подходящий вариант. Например какая-нибудь CRC сумма для проверки целостности.

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

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

- Wraparound. Часто вам не важно абсолютное значение счетчика. Нужно лишь знать, какое из двух значений больше. При этом вы знаете, что сравниваемые значения не могут быть слишком большими. Тогда очень маленькое значение будет считаться больше очень большого. Два примерно одинаковых будут сравниваться как обычные числа. Так можно делать, например, с sequence number пакетов. Если вы получите пакет с номером 0x02 после покета с номером OxFFF1, Можно с спокойно считать, что это номер после переполнения. Ну не будет сеть задерживать перетасовывать 65 тысяч пакетов.

У вас не самое эффективное решение. Что-то типа O(n sqrt(n)), когда как задачу можно решить за O(n).

Сначала решетом эратосфена найдите для каждого числа минимальный простой делитель. У меня даже статья про этот алгоритм есть с кодом и объяснением.

Потом, решение за O(n log n) - можно быстро найти все простые множители каждого числа используя массив с предущего шага. Считайте степени простых множителей и перемножайте их +1. Так 2^2*3^1 имеет (2+1)(1+1) = 3*2 = 6 делителей (включая 1 и 12. Если они не нужны, вычтите 1-2 в конце).

Но можно сделать еще быстрее. Фактически применив динамическое программирование. Во втором массиве посчитайте степень минимального простого делителя для каждого числа. Если мнимальный делитель (p[i]) для i равен мнимальному для i/p[i], то степень для i будет 1 + степень для i/p[i]. Иначе она будет 1. Так же посчитайте для каждого числа что там останется, если выкинуть все вхождения минимального делителя. Потом в другом массиве посчитайте для каждого числа количество делителей - это ответ для числа без всех вхождений минимального, умноженный на количество этих минимальных делителей +1. Ну а потом по этому массиву считайте сумму. Это будет работать за O(n).

Нарешаете много задач, научитесь в голове перебирать известные алгоритмы.

А так - на до сначала построить математическую модель задачи. Понять, на что эта модель похожа. Может, тут граф нарисовать можно? Какие алгоритмы на графы вы вообще знаете? Применимы ли они тут? Или это строка. Какие есть алгоритмы на строки? Смотрите еще ограничения. По ним обчно понятно, что тут нужно что-то за O(n), или за O(n log n) написать. Множество применымых алгоритмов еще больше уменьшается.

В задачах на оптимальность чего-то помогает рассуждение "рассмотрим ответ. Какие у него можно заметить свойства. Можно ли какой-то ответ немного поменять, не ухудшая его?" Так вы получите какое-то свойство, которое можно уже применять для построения ответа. Например в задачах на жадность так можно понять, что надо отсрортировать что-то.

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

Часть III. Структуры данных
Часть VI. Алгоритмы для работы с графами

Менее важные, но встречающиеся темы:
Глава 30. Полиномы и быстрое преобразование Фурье
Глава 31. Теоретико-числовые алгоритмы
Глава 32. Поиск подстрок
Глава 33. Вычислительная геометрия

Но лучше прочитать, таки, всю книгу. Вправляет мозги, учит строить математические модели задач, что в олимпиадах очень важно.