Я студент и увидел, что Тинькофф выплачивает целых 25 тысяч рублей студентам каждый месяц, но надо пройти некий отбор. По описанию на сайте быстро становится понятно, что отбор на самом деле - некий аналог олимпиадных задач. Я в свое время решал немало подобных задач в Академии Яндекс.Лицея и участвовал в олимпиадах. Однако, дальше города я не проходил, по простой причине: цель была стать программистом, пишущим программы, а не знающим все используемые алгоритмы, в итоге я не сильно углублялся в тему.
Собственно, я подал заявку и по привычке пошел читать полное положение о отборе, в котором сказано, что надо быть не трудоустроенным. Я работаю программистом 2 года и увольняться ради стипендии не хочется. К тому же, как оказалось, стипендию получат только 85 человек из всех, подавших заявку. И тут я вспомнил про ChatGPT, и мне стало интересно, если бы я был практически полным нулем в программировании, смог бы я получить стипендию, используя ChatGPT?
Пройти тест можно в любое время в течении месяца. После начала теста система автоматически завершит его через 4 часа.
Решаем первую задачу
Всего надо решить 8 задач. Не сильно вчитываясь в условие, начинаю копировать текст:
Но вот прикол, Тинькофф позаботился с тем, чтобы нельзя было получить нормальный текст просто скопировав. При копировании появляются лишние символы и переносы. К примеру скопировав простое a1, a2, ... an получаем вот такой результат "�1,�2,...,��a1,a2,...,an", но каждый элемент на новой строчке, иногда несколько пустых строк (объединил для удобства). На Хабр, кстати, текст вставляется без переносов и практически без лишних символов.
В любом случае, такие запреты на копирование выглядят смешно. Я сделал фото и отправил его Яндексу, чтобы расшифровать, что написано. В итоге, подправив, получаем следующий текст.
Hidden text
У вас есть массив длины n из элементов a1, a2, …, аn. Каждый элемент можно не более одного раза заменить на любое целое число. Стоимость замены числа x на у равна (x-y)^2 монет. Элементы заменяются независимо, то есть, если ai = aj и меняются оба элемента, то заплатить придется ровно за две замены.
Чему равно минимальное количество монет, необходимое, чтобы сделать все элементы массиваравными?
Формат входных данных
В первой строке дано целое число п обозначающее длину массива. (1 <= n <= 100)) Во второй строке через пробел заданы п целых чисел а1, а2, … аn (-100 <=a <= 100).
Формат выходных данных
Выведите минимальное число монет, которое нужно потратить, чтобы сделать все элементы равными.
И вот такие тесты приводит Тинькофф:
Hidden text
Ввод:
2
10 2
Вывод:
32
Ввод:
3
-4 -6 -4
Вывод:
3
Ввод:
3
7 5 9
Вывод:
8
Просим нейросеть решить олимпиадную задачу и даем ей текст. На что ChatGPT генерирует описание как надо решить задачу
Hidden text
Для решения этой задачи можно заметить, что чтобы сделать все элементы массива равными, необходимо выбрать значение, которое будет наиболее часто встречаться в массиве, и заменить все остальные элементы на это значение. Таким образом, минимальное количество монет, необходимое для этого, будет равно сумме квадратов разностей между каждым элементом массива и этим выбранным значением.
Для реализации этой идеи, можно воспользоваться словарем, в котором будем хранить количество вхождений каждого элемента массива. Затем, найдя элемент с наибольшим количеством вхождений, можно заменить все остальные элементы на это значение и вычислить необходимое количество монет.
Приводит решение на python:
n = int(input())
arr = list(map(int, input().split()))
freq = {} # словарь для хранения количества вхождений каждого элемента
for num in arr:
freq[num] = freq.get(num, 0) + 1
most_freq_num = max(freq, key=freq.get) # находим элемент с наибольшим количеством вхождений
total_cost = 0 # общее количество монет
for num in arr:
if num != most_freq_num:
total_cost += (num - most_freq_num) ** 2
print(total_cost)
Но первый же тест и ответ неверный: он выводит 64, а должно быть 32. Я нажимаю кнопку "Regenerate response", но ничего не меняется. Тогда я кидаю эту же задачу еще раз, но уже с примером входных данных. Вот новое объяснение от нейросети
Hidden text
Для того, чтобы сделать все элементы массива равными, нужно найти значение, которое является наиболее часто встречающимся в данном массиве, так как замена каждого элемента массива на это значение потребует наименьшее количество монет.
Для решения этой задачи можно использовать следующий алгоритм:
Считываем длину массива и элементы массива.
Создаем словарь, в котором будем хранить количество вхождений каждого элемента в массиве.
Находим наиболее часто встречающийся элемент в массиве.
Для каждого элемента массива вычисляем стоимость замены на найденный элемент и добавляем эту стоимость к общей стоимости замен.
Выводим общую стоимость замен.
Вот реализация этого алгоритма на Python:
И код с входными данными:
Hidden text
n = int(input())
a = list(map(int, input().split()))
# Создаем словарь для подсчета количества вхождений каждого элемента в массиве
count = {}
for x in a:
count[x] = count.get(x, 0) + 1
# Находим наиболее часто встречающийся элемент
mode = max(count, key=count.get)
# Вычисляем общую стоимость замен
cost = sum((x - mode) ** 2 for x in a)
print(cost)
Входные данные:
2
10 2
Выходные данные:
32
Входные данные:
3
-4 -6 -4
Выходные данные:
-3
Но чуда не случается. Тогда я прямо пишу, что ошибка при определенном тесте. Привожу пример первого теста и ожидаемый ответ. Вот что ответила мне нейросеть:
Hidden text
Действительно, в данном случае минимальное количество монет для сделать все элементы массива равными должно быть равно 32, а не 64. При замене числа 10 на 2 стоимость будет (10-2)^2 = 64, а при замене числа 2 на 10 стоимость будет (2-10)^2 = 64. То есть общая стоимость замен будет 64, но если заменить 10 на среднее арифметическое 6 и заменить 2 на 6, то общая стоимость будет (10-6)^2 + (2-6)^2 = 16 + 16 = 32. Извините за путаницу, благодарю за замечание.
Но код мне не прислалали. Прошу исправить код с учетом замечания, вот код, который теперь работает правильно:
n = int(input())
arr = list(map(int, input().split()))
# Найдем среднее арифметическое
avg = sum(arr) // n
# Вычисляем количество монет для каждого элемента массива
coins = sum((i - avg)**2 for i in arr)
# Проверяем наличие другого возможного среднего
if coins > 0:
coins2 = sum((i - avg - 1)**2 for i in arr)
coins3 = sum((i - avg + 1)**2 for i in arr)
coins = min(coins, coins2, coins3)
print(coins)Итак, задачу мы решили. При этом я даже не знаю, что именно мы решали. Условия я прочитал только на следующий день
Решаем вторую задачу
По старому алгоритму получаем текст и тесты:
Hidden text
На бесконечной двумерной плоскости есть точка, координаты которой изначально равны (0, 0). Вам дана строка S длины Т. S состоит только из символов N, W, S, E. В течение n дней вы будете совершать операции с точкой. В день i вы должны:
• прибавить положительное вещественное число ко второй координате, если S; равен N;
• отнять положительное вещественное число от первой координаты, если Si равен W;
• отнять положительное вещественное число от второй координаты, если Si равен S;
• прибавить положительное вещественное число к первой координате, если Si равен Е.
Определите, возможно ли совершить операции в каждый из дней так, чтобы в итоге после всех n дней координаты точки снова стали равны (0, 0).
Формат входных данных
В единственной строке входных данных вам задана S(1 <= n <= 1000).
Формат выходных данных
Выведите Yes, если возможно каждому дню назначить некоторое положительное вещественное число, так, что в итоге координаты точки будут равны (0, 0). Если это невозможно, то выведите No
Примеры данных
Ввод:
WSEN
Вывод:
Yes
Ввод:
WEWWEW
Вывод:
Yes
Ввод:
WWSN
Вывод:
No
Ввод:
N
Вывод:
No
Первое решение от нейросети и сразу же неверное:
Hidden text
S = input()
sum_n = sum_s = sum_w = sum_e = 0
for s in S:
if s == 'N':
sum_n += 1
elif s == 'S':
sum_s += 1
elif s == 'W':
sum_w += 1
elif s == 'E':
sum_e += 1
if sum_n == sum_s and sum_w == sum_e:
print("Yes")
else:
print("No")Н
Нажимаю кнопку "Regenerate response" и так 3 раза, каждый раз получаю неверное решение. К этому моменту я уже прочитал условие, и задача оказалась очень простой. Я объясняю, что не так у ChatGPT:
Hidden text
Неправильно при таком вводе WEWWEW ответ будет "YES", суть в том, что прибавляется не 1, а любое число, надо просто проверить возможно ли тогда вернуться в (0, 0)
На что нейросеть извиняется и в коде просто заставляет пользователя вводить число, на которое продвинется пользователь
Hidden text
Извините, вы правы. Я неверно проинтерпретировал условие задачи. В таком случае, для решения задачи необходимо поддерживать две переменные - текущие координаты x и y точки. На каждой итерации необходимо изменять значение соответствующей координаты на заданное значение. Затем нужно проверить, равны ли текущие координаты точки (x=0 и y=0). Если хотя бы раз на этапе обработки итерации координаты выходят за границы (x < 0 или y < 0), то ответ на задачу будет "No". Иначе, ответ будет "Yes".
Вот пример кода, который решает эту задачу:
s = input().strip()
x = 0
y = 0
for i in s:
k = int(input().strip())
if i == "N":
y += k
elif i == "S":
y -= k
elif i == "E":
x += k
else:
x -= k
if x < 0 or y < 0:
print("No")
break
else:
if x == 0 and y == 0:
print("Yes")
else:
print("No")
Тут я приофигел и сам решил задачу, потому что она максимально простая. Думаю, любой человек, который умеет работать с условиями, сможет ее решить. Вот мое решение:
Hidden text
def func(s):
if "W" in s and "E" in s:
pass
else:
if "W" in s or "E" in s:
return "No"
if "S" in s and "N" in s:
pass
else:
if "S" in s or "N" in s:
return "No"
return "Yes"
s = input()
print(func(s))Решаем третью задачу
Текст и тесты:
Hidden text
У Ивана есть табличка, состоящая из H строк и W столбцов. Изначально в левом верхнем углу лежит камень. Иван хочет поэтапно переместить камень в правый нижний угол. На каждом шаге он может подвинуть камень на одну клетку влево, вверх, вправо или вниз (если после этого камень не выйдет за границу таблички). Допускается, что камень несколько раз окажется в одной клетке.
Иван сделал свои ходы дал вам табличку, состоящую из H строк и W столбцов. Обозначим за a[i, j] (1 <= i <= H, 1 <= j <= W) символ, находящийся в i-й строке сверху и j-м столбце слева. a[i, j] равен «#», если камень Ивана хотя бы раз побывал в клеточке, находящейся на пересечении і-й строки сверху и j-го столбца слева изначальной таблички. Если камня Ивана в этой клеточке не было, то а[i, j], равен «.». Определите, возможно ли такое, что Иван никогда не перемещал камень влево или вверх.
Формат входных данных
В первой строке вам через пробел даны целые числа Н и W (2 <= H, W <= 8). Дальше следуют H строк. В і-й записана строка a[i, 1], a[i, 2], …, a[i, W]
Формат выходных данных
Если возможно, что Иван использовал только перемещения вправо или вниз, то выведите «Possible» (без кавычек), иначе выведите «Impossible» (без кавычек).
Ввод:
3 4
##..
.##.
..##
Вывод
Possible
Ввод:
3 3
###
..#
.##
Вывод
Impossible
Ввод:
4 4
##..
.##.
.##.
..##
Вывод
Impossible
Кидаем задачу ChatGPT и получаем ответ:
Hidden text
Действительно, в этом примере ответ должен быть Impossible, но предложенный алгоритм не учитывает этот случай. В данном примере есть два возможных пути: идти сначала вправо, потом вниз; или идти сначала вниз, потом вправо. Оба пути необходимы, чтобы добраться до правого нижнего угла.
Для проверки этого условия нужно провести обход в глубину или в ширину по графу, где вершинами являются клетки таблицы, а ребра соединяют соседние клетки. Если из начальной клетки можно достигнуть конечную, используя только перемещения вниз и вправо, то ответ Possible, иначе Impossible.
Вот исправленный код, который использует поиск в глубину:
def dfs(table, i, j, visited):
if i == len(table) - 1 and j == len(table[0]) - 1:
return True
visited.add((i, j))
if i < len(table) - 1 and table[i + 1][j] == "#" and (i + 1, j) not in visited:
if dfs(table, i + 1, j, visited):
return True
if j < len(table[0]) - 1 and table[i][j + 1] == "#" and (i, j + 1) not in visited:
if dfs(table, i, j + 1, visited):
return True
return False
h, w = map(int, input().split())
table = [input() for _ in range(h)]
visited = set()
if dfs(table, 0, 0, visited):
print("Possible")
else:
print("Impossible")Здесь используется функция dfs для рекурсивного обхода в глубину. Если в конечной клетке (i=len(table)-1, j=len(table[0])-1) оказался камень, то функция возвращает True, иначе продолжает поиски вниз и вправо из текущей клетки. Кроме того, используется множество visited для отслеживания уже посещенных клеток и предотвращения зацикливания в случае, если в таблице есть циклы.
Падет второй тест, указываем на это нейросети и сразу просим исправить код. На что получаем правильный ответ:
Hidden text
h, w = map(int, input().split())
a = []
for i in range(h):
row = input()
a.append(row)
for i in range(h):
for j in range(w):
if a[i][j] == '#':
if i == 0 and j == 0:
continue
elif i == 0 and a[i][j-1] != '#':
print("Impossible")
exit()
elif j == 0 and a[i-1][j] != '#':
print("Impossible")
exit()
elif a[i-1][j] != '#' and a[i][j-1] != '#':
print("Impossible")
exit()
print("Possible")
Решаем четвертую задачу
Текст и тесты:
Hidden text
У вашего друга есть коллекция карточек, на каждой из которых написано целое число от 1 до n.
Карточек с числом і у него а[i] штук. Две карточки могут образовать пару, если модуль разности чисел на них не превосходит 1. Ваш друг хочет создать наибольшее количество пар из своих карточек так, чтобы выполнялось описанное условие. Каждая карточка может участвовать максимум в одной паре.
Помогите своему другу и найдите это количество.
Формат входных данных
В первой строке задано целое число n(1 <= n <= 105) Далее идут n строк из целых чисел. На i-й из них записано число а[i] (0 <= a[i] <= 109).
Формат выходных данных
Выведите число, равное максимальному количеству пар, на которое можно разбить карточки.
Ввод:
4
2
0
5
4
Вывод:
5
Ввод:
8
4
2
3
4
0
4
2
1
Вывод:
9
Первое решение от ChatGPT упало, я решил попробовать сгенерировать ответ еще раз. Второе решение тоже падало с ошибкой:
Hidden text
Второе решение:
Одно из возможных решений этой задачи - сначала отсортировать массив с количеством карточек, а затем пройтись по нему, пытаясь сформировать пары с соседними элементами.
Для этого можно пройтись по массиву, начиная с индекса 1 и сравнивая текущий элемент с предыдущим. Если модуль их разности не превосходит 1, то можно сформировать пару из этих элементов и увеличить счетчик пар на 1. При этом нужно уменьшить значения обоих элементов на 1, чтобы они больше не могли участвовать в других парах.
Если текущий элемент с предыдущим сформировать пару не удалось, то можно попытаться сформировать пару со следующим элементом (индекс i+1), если такой элемент есть и модуль разности между ними не превосходит 1.
В конце работы алгоритма нужно вернуть количество образованных пар.
Пример реализации на языке Python:
n = int(input())
a = list(map(int, input().split()))
a.sort()
pairs = 0
i = 1
while i < n:
if abs(a[i] - a[i-1]) <= 1:
pairs += 1
a[i] = 0
a[i-1] = 0
i += 1
elif i < n-1 and abs(a[i+1] - a[i-1]) <= 1:
pairs += 1
a[i+1] = 0
a[i-1] = 0
i += 2
else:
i += 1
print(pairs)
Время работы алгоритма составляет O(n log n), так как сначала выполняется сортировка, которая имеет сложность O(n log n), а затем проход по массиву, который имеет линейную сложность O(n).
Теперь я уже прочитал условие и посмотрел код, который за меня заботливо написали. Проблема была в том, что ChatGPT ждал входные данные в другом формате. По тестам Тинькофф каждое число на новой строке, а вот нейросеть ждала все в одной строке. Подправив чуть тесты, код отработал, но ответ был неверный.
Дальше я играл роль болванчика, который проверял код на тесты и выдавал вердикт ChatGPT о том, что его код не прошел такой-то тест и надо найти и исправить ошибку. Из интересного, один раз нейросеть написала код на Python 2.
Мы ходили по кругу, в первом тесте ответ был то 1, то 4, то снова 1 и даже 3. Я указывал на ошибки и ждал, когда наконец мне дадут верный код. И я таки дождался верного ответа. Я лишь немного изменил его для подходящих входных данных:
Hidden text
Извините за путаницу в ответах. Нужно изменить логику подсчета количества пар. Вместо того, чтобы просто складывать количество пар для каждого числа, мы должны на каждой итерации посмотреть, сколько пар можно сформировать из текущего числа и уже рассмотренных. Также мы должны учитывать, что число может остаться неиспользованным и быть использовано позднее.
Попробуйте следующий код:
n = int(input())
a = list(map(int, input().split()))
a.sort()
pairs = 0
used = [False] * n
for i in range(n):
if not used[i]:
used[i] = True
pairs_i = a[i]
for j in range(i + 1, n):
if not used[j] and abs(a[j] - a[i]) <= 1:
used[j] = True
pairs_i += a[j]
pairs += pairs_i // 2
print(pairs)
Теперь при вводе 4 2 0 5 4 вывод будет равен 5.
Решаем пятую задачу
Текст и тесты:
Hidden text
У вас есть строка А = А[1]А[2]...А[n], из строчных букв английского алфавита. Вы можете не более одного раза проделать следующую операцию: выбрать индексы i и j (1 <= i <= j <= n) и развернуть подстроку A[i]A[i+1]...A[j] (то есть заменить ее на A[j]A[j-1]...A[j];). Посчитайте количество различных строк, которые можно получить в итоге.
Формат входных данных
В единственной строке входных данных задана А состоящая из строчных букв английского алфавита (1 <= |A| <= 200000).
Формат выходных данных
Выведите искомое количество строк.
Ввод
llrr
Вывод:
5
Ввод
ffffffffff
Вывод
1
Ввод
цabacaba
Вывод
15
Скармливаем данные нейросети и получаем неправильный ответ. Указываем на ошибку при прохождении первого теста и после этого ChatGPT без проблем дает верное решение.
Hidden text
Для решения этой задачи можно построить все возможные строки, которые могут получиться после одной операции переворота, и посчитать количество уникальных строк среди них.
Для этого можно перебирать все возможные пары индексов i и j, в которых i <= j, и заменять подстроку A[i:j+1] на перевернутую версию. Затем добавить полученную строку в множество уникальных строк. В конце подсчитать размер этого множества.
Вот реализация на Python:
s = input()
n = len(s)
unique_strings = set()
for i in range(n):
for j in range(i, n):
new_s = s[:i] + s[i:j+1][::-1] + s[j+1:]
unique_strings.add(new_s)
print(len(unique_strings))Проверим работу решения на примере llrr. Вывод должен быть равен 5, так как возможны следующие строки:
llrr (исходная строка)
lrll
rlll
rlr
rrl
Решаем шестую задачу
Текст и тесты:
Hidden text
Вам даны n точек на плоскости. Координаты i-й из них равны (x[i], у[i]).
Будем делать следующую операцию, пока это возможно: выберем четыре целых числа а, b, c, d(a != c, b != d) так, что ровно на трех позициях из (a, b), (a, d), (c, b), (c, d) есть точка, и добавим точку на оставшуюся позицию.
Можно показать, что этот процесс конечен. Найдите максимальное количество раз, которое можно совершить описанную операцию.
Формат входных данных
В первой строке задано целое число nn(1 <= n < 10^5) Далее следуют n строк, на i-й из которых целые числа x[i] и у[i] через пробел (1 <= x[i]y[i] <= 10^5). Если і != j, то x[i] != x[j] или у[i] != y[j] то есть все точки различны.
Формат выходных данных
Выведите искомое максимальное число раз.
Ввод
3
2 2
3 2
3 3
Вывод
1
Ввод:
2
5 5
10 10
Вывод
0
Ввод
7
1 1
1 2
1 3
1 4
2 1
3 1
4 1
Вывод
9
Вот мы и дошли до второй задачи, которую не смог решить ChatGPT. К его чести будет сказано, что после более 10 правок я сам начал читать условие и не понял что требуется. Я понимаю, что нам вводят список координат. Но вот как операция с a, b, c, d должна работать с этими координатами мне вообще не понятно.
Можно написать в поддержку и уточнить условия, но тест я проходил ночью. Да и если бы я проходил днем, сомневаюсь, что мне бы ответили в течении хотя бы 4 часов. Собственно, это непродуманный момент со стороны Тинькофф.
Вот ответ, который прошел 2 теста из 3
Hidden text
from collections import defaultdict
n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]
x_count = defaultdict(int)
y_count = defaultdict(int)
for x, y in points:
x_count[x] += 1
y_count[y] += 1
result = 0
for x, y in points:
if x_count[x] > 1 and y_count[y] > 1:
result += 1
print(result)
Что самое интересное, каждый раз код то увеличивался, то уменьшался. А также он мне сгенерировал код на C++, хотя до этого я писал только на Python (изначально я не просил писать на определенном языке). А после того, как нажал "генерировать" еще раз, получил код на Arduino, но я даже не стал ждать завершения генерации и сразу прервал работу. Код на C++ не прошел тесты. Вот, кстати, он:
Hidden text
С++ код
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,cnt[N];
struct node{
int x,y;
}a[N];
bool cmp(node a,node b){
return a.x<b.x;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
for(int i=2;i<n;i++){
if(a[i-1].y<a[i].y&&a[i].y<a[i+1].y) cnt[a[i].x]++;
}
int ans=0;
for(int i=1;i<=N-5;i++){
ans=max(ans,cnt[i]+cnt[i-1]+cnt[i+1]);
}
cout<<ans;
return 0;
}
В какой-то момент я устал и начал читать условие, а после просто перешел к следующей задаче
Решаем седьмую задачу
Текст и тесты:
Hidden text
Дан массив а[1], а[2], ..., а[n], длины n и число k.
В a есть n*(n + 1)/2 подотрезков (непрерывных подпоследовательностей вида а[l], a[l+1], ..., а[r], где (1 <= l <= r <= n).
На скольких из этих подотрезков среднее арифметическое чисел не меньше k
Формат входных данных
В первой строке даны числа n и k через пробел. Далее следуют п строк на і-й из которых записано число а.
Все входные числа являются целыми. И выполняются следующие ограничения: n <= 200000, 1 <= k <= 10^9, 1 <= a[i] <= 10^9.
Формат выходных данных
Выведите единственное число - количество подотрезков массива, среднее арифметическое на которых не меньше k.
Ввод
3 4
5
3
5
Вывод
5
Ввод
1 8
7
Вывод
0
Ввод
9 52
20
40
60
80
100
80
60
40
20
Вывод
33
Залил все в нейросеть и получил 2 решения, но оптимизированный алгоритм к сожалению не дописал. А вот первый вариант прошел все тесты:
Hidden text
В данной задаче можно воспользоваться двухпроходным алгоритмом, который за линейное время посчитает ответ.
Первый проход: посчитаем префиксные суммы массива. Для этого заведем массив p[i], в котором p[i] = a[1] + a[2] + ... + a[i]. Тогда сумму элементов на подотрезке [l, r] можно посчитать как p[r] - p[l-1].
Второй проход: переберем все подотрезки и для каждого подотрезка вычислим его среднее арифметическое. Если оно не меньше k, увеличим счетчик на 1.
В итоге, ответом на задачу будет являться количество подотрезков среднее арифметическое чисел которых не меньше k.
Реализация на Python:
n, k = map(int, input().split())
a = list(map(int, input().split()))
# Вычисляем префиксные суммы
p = [0] * (n+1)
for i in range(1, n+1):
p[i] = p[i-1] + a[i-1]
count = 0
for i in range(1, n+1):
for j in range(i, n+1):
# Вычисляем среднее арифметическое элементов на подотрезке [i, j]
avg = (p[j] - p[i-1]) / (j - i + 1)
if avg >= k:
count += 1
print(count)
Этот алгоритм имеет временную сложность O(n^2), что не подходит для данной задачи при n <= 200000. Однако, можно заметить, что условие avg >= k эквивалентно условию p[j] - p[i-1] >= k*(j-i+1). Поэтому во втором проходе можно фиксировать правый конец подотрезка j, и двигать левый конец i от j до 1, и при этом поддерживать значение p[j] - p[i-1]. Если это значение становится больше или равно k*(j-i+1), то все подотрезки [i, j], [i+1, j], ..., [j, j] удовлетворяют условию, и мы можем увеличить счетчик на j-i+1.
Таким образом, оптимизированный алгоритм имеет временную сложность O(n). Реализация на Python:
n, k = map(int, input().split())
a = list(map(int, input().split()))
# Вычисляем префиксные суммы
p = [0] * (n+1)
for i in range(1, n+1):
p
Просим дописать оптимизированный алгоритм, но получаем код, который не проходит тесты. Сообщаем, что неоптимизированный алгоритм работает верно, а написанный им код не проходит тесты. В результате получаем правильное решение:
Hidden text
Изначально решение имеет временную сложность O(n^3), так как проходим по всем подотрезкам, а затем для каждого подотрезка проходим по всем элементам, чтобы вычислить среднее арифметическое.
Можно оптимизировать алгоритм, чтобы сократить время выполнения до O(n^2). Для этого можно использовать технику префиксных сумм. Создаем массив префиксных сумм, где каждый элемент представляет сумму всех элементов до данного индекса включительно. Таким образом, для каждого подотрезка можно вычислить сумму за константное время, используя префиксные суммы.
Теперь мы можем вычислить среднее арифметическое за константное время для каждого подотрезка, используя префиксные суммы. Если среднее арифметическое подотрезка больше или равно k, увеличиваем счетчик на 1.
Итоговый алгоритм:
n, k = map(int, input().split())
a = list(map(int, input().split()))
# Вычисляем префиксные суммы
prefix_sum = [0] * (n + 1)
for i in range(1, n + 1):
prefix_sum[i] = prefix_sum[i - 1] + a[i - 1]
count = 0
for i in range(1, n + 1):
for j in range(i, n + 1):
# Вычисляем сумму подотрезка за константное время, используя префиксные суммы
sum_subarray = prefix_sum[j] - prefix_sum[i - 1]
# Вычисляем среднее арифметическое подотрезка
avg_subarray = sum_subarray / (j - i + 1)
if avg_subarray >= k:
count += 1
print(count)
Решаем восьмую задачу
Текст и тесты:
Hidden text
Дано дерево из вершин n Вершина 1 является его корнем. Родителем вершины i(2 <= i <= n) является вершина р[i]. Кроме того дана последовательность неотрицательных целых чисел x[1], x[2], ..., x[n]. Вам нужно проверить, возможно ли раскрасить вершины дерева в черный или белый цвет и назначить каждой вершине неотрицательный целый вес так, чтобы для каждой вершины v выполнялось следующее: сумма весов вершин в поддереве вершины v с таким же цветом как y v равна х[v] (v в сумме тоже учитывается).
Формат входных данных
В первой строке задано натуральное число n(1 <= n <= 1000). Во второй строке
через пробел заданы натуральные числа p[2], p[3], ..., p[n] .(1<=p[i] <= i-1). В третьей строке через пробел заданы целые числа x[1], x[2], ..., x[n], (0 <= x[i] <= 5000)
Формат выходных данных
В единственной строке выведите строку POSSIBLE, если возможно каждой вершине назначить один из двух цветов и неотрицательный целый вес так, чтобы выполнялись все ограничения. Иначе выведите IMPOSSIBLE
Опять пришли к задаче, которую не получилось решить. Часто ChatGPT генерировал разные приколы в коде, вроде использования переменной, которой не существует. Или пробовал взять переменную из функции. Из непонятного было следующее: создавались функции, в которую прикидывали константное число; падали ошибки с выходом за границы списков и так далее. Я не пробовал разобраться в итогах работы черного ящика. Однажды нейросеть, видимо, поняла, что проблема с ней надолго и придумала название задаче "Веса и цвета". В общем, либо получался неверный ответ, либо вообще код падал.
Наконец, начал читать задание самостоятельно и должен признать, что над задачей надо хорошенько подумать. В то время времени было уже поздно, и я уже плохо соображал, а задача была непростая. На следующий день все равно не смог придумать решение, но и думал я не больше 15 минут. Так что причина сложностей нейросети понятна
Косяки Тинькофф
Я не пользовался поддержкой, но написано следующее, цитирую: "На вопросы отвечают авторы задач. В нерабочее время врем ответа может быть увеличено" (да, да, там написано с опечаткой). Время работы не указано вообще. Как быстро авторы ответят в рабочее время? Как быстро в нерабочее время? Если честно, я не совсем уверен, что мне бы ответили достаточно быстро. Даже на городских соревнованиях ответ от организаторов приходил не мгновенно и, как правило, сводился к тому, что нужно внимательно прочитать условия задачи.
Самая же большая проблема в том, что задачи одинаковые для всех (а пройти можно в любое время в течении месяца, на решение теста отводится 4 часа). На следующий день, чтобы сделать скрины я зашел в тест, и увидел, что он закрыт. Я не могу в него даже зайти. Создал временную почту, зарегестрировался, в поле телефон ввел первое что пришло в голову и аккаунт создался. Проверили только почту. Данную процедуру я повторил 3 раза, чтобы убедится что тест одинаковый для всех.
Это означает, что я могу скопировать себе все задачи, подумать над ними несколько дней или недель (можно не думать, а заставить поработать нейросеть или вообще купить решение), а потом закрыть тест за несколько минут. При этом я могу проверить решение даже на одном дополнительном аккаунте. Это позволяет пройти первый этап отбора, не имея особого знания предметной области.
Такой же прокол есть у Академии Яндекс.Лицея. С той лишь разницей, что у них есть несколько вариантов тестов, обычно 4. Тем не менее, ничто не мешает решить все 4 теста и вернуться через месяц с основным аккаунтом.
Конечно, я не считаю, что человек, ничего не знающий, сможет пройти все этапы отбора. Однако, при равных условиях преимущество будет у того, кто нашел подобные недочеты.
Собеседование с алгоритмами
После всего, что ChatGPT продемонстрировал, возникает вопрос: а насколько необходимы алгоритмические собеседования, если нейросети могут успешно решать подобные задачи? Может быть, стоит рассмотреть возможность найма ИИ вместе с тестировщиком и просто проверять результаты его работы. Если тесты не проходят, мы можем просто сообщить об этом нейросети и заставить генерировать новый код.
Я никогда не был поклонником алгоритмических собеседований. Как правило, они созданы, чтобы понять, выдает ли человек себя за того, кем является. По моему мнению, это не является показателем, потому что даже ChatGPT справляется с задачами и успешно их решает. Также и человек может натренировать скилл решения олимпиадных задач, но не уметь программировать в реальных проектах.
Всем спасибо за уделенное время, буду рад обратной связи
P.S. Статья вычитана с помощью ChatGPT
