Приглашаем посмотреть задания, которые мы использовали для онлайн-этапа отбора, а также решения для них.
В этом году количество желающих превзошло все предыдущие, и на нашей платформе тестирования было создано более 3700 учетных записей. Участникам предлагалось решить два задания, а на их решение мы выделяли две недели и 15 попыток проверки на каждое.
CheckUp
После заполнения анкеты проходит первый этап отбора на автоматизированной платформе тестирования CheckUp. Это собственный продукт, прототип которого был разработан учениками нашей Школы пару лет назад. С тех пор он постоянно поддерживается, обрастает новыми функциями и помогает нам организовывать отбор в Школу.
Часть интерфейса CheckUp
Он умеет хранить, обрабатывать и проверять решения участников, позволяет им тестировать решения собственными тестами, а также имеет чат для поддержки и выяснения спорных вопросов условий. Мы пользовались разными способами отбора, но в итоге пришли к выводу, что нужен свой и не ошиблись.
Числа
Только факты: из 3700 учетных записей лишь 1318 отправили на проверку хотя бы одно решение. С одним заданием справились 483 участника, а с обеими задачами 283.
Из людей, которые отправили хотя бы одно решение для первого задания справились с ним 35% участников, для второго задания этот процент гораздо выше почти 60%. Возможно это связано с тем, что первое задание кажется легче, и попробовать решить его проще.
В общей сложности системой было проверено 8986 решений, а нами и участниками написано 3720 сообщений в чате.
То, ради чего все пришли
Как мы и обещали в чате поддержки CheckUp, в этой статье я подробно разберу задания этого года и дам ссылки на тесты, которые мы использовали для проверки.
Преобразования слов
На вход подается 2 подстроки. Нужно определить, можно ли превратить первую во вторую, заменяя одни буквы на другие, с учетом следующих правил:
- участвуют только буквы русского алфавита а-я;
- все буквы в нижнем регистре;
- за один шаг нужно преобразовать все вхождения одной буквы в другую.
Например:
хабр бобр
здесь преобразование возможно (х б: бабр, а
о: бобр)корм кров
здесь тоже возможно, но, чтобы поменять
местами о и р понадобится дополнительная буква, не используемая в
подстроках (о я: кярм, р о: кяом, я р: кром, м в: кров)бобр добр
а здесь уже нет, потому что за шаг меняются
все вхождения, и б не сможет стать одновременно и д и б.Условие этого задания довольно простое, однако есть несколько тонкостей, которые нужно было учесть в решении, указаны ниже с пояснениями, перечислены по частоте ошибок в решениях.
1. Наш алфавит конечен
Во втором примере мы использовали дополнительную букву. Дело в том, что в нашем алфавите их всего 33, и если все они используются и в первой, и во второй подстроке нам негде взять букву для замены. Самый простой пример такого:
абвгдеёжзийклмнопрстуфхцчшщьыъэюя
бавгдеёжзийклмнопрстуфхцчшщьыъэюя
Здесь используются все 33 буквы и мы не можем поменять местами б и а.
2. Необходимо преобразовать слово только в одну сторону
Было несколько решений, которые использовали проверку слов на изоморфизм, но она избыточна третий пример преобразовать нельзя. А вот если поменять местами слова добр бобр, тут преобразование возможно.
3. Для замены хватит всего одной буквы
Из первого пункта может сложиться ощущение, что если в левой подстроке есть весь алфавит, то преобразование всегда невозможно, однако это неверное заключение. Если во второй строке используется не весь алфавит, можно использовать ту букву, которой там нет:
абвгдеёжзийклмнопрстуфхцчшщьыъэюя
бабгдеёжзийклмнопрстуфхцчшщьыъэюя
Здесь во второй подстроке, вместо буквы в стоит буква б, позволяющая сначала заменить а на в, а затем использовать освободившуюся а. (а в: вбв..., б а: вав..., в а: баб...)
4. Что делать со строками разной длины
На этот и следующий вопрос мы отвечали в чате, но их тоже укажу, на случай, если кому-то интересно.
Многие сообразили, что как ни преобразовывай буквы в таких строках, одинаковыми они не станут. Так и есть, для этих строк можно было сделать отдельную проверку и сразу возвращать 0. Фраза про строки разной длины в дополнительной информации к условию была добавлена для того, чтобы решения участников не падали с ошибкой на таких данных.
5. Изначально равные строки
Было несколько вопросов о том, возможно ли преобразование для строк, которые уже равны. Во-первых, 0 шагов это тоже действие. Во-вторых, в задании необходимо ответить на вопрос, можно ли превратить первую строку во вторую, то есть сделать их равными. Так как они уже равны, можно возвращать 1.
Если учесть всё это и вынести в отдельные условия, останется проверить только то, что каждой букве первой подстроки соответствует только одна буква второй.
Пример кода решения на Python:
def check_conversion(str_from, str_to): if str_from == str_to: # Если подстроки уже равны return 1 if len(str_from) != len(str_to) or len(set(str_from)) == len(set(str_to)) == 33: # Если длина подстрок не равна # Или количество уникальных букв в обеих подстроках равно 33 return 0 symbols_map = {} for symbol_from, symbol_to in zip(str_from, str_to): if symbols_map.get(symbol_from, symbol_to) != symbol_to: # Если мы пытаемся заменить одну букву на две разных return 0 symbols_map.update({ symbol_from: symbol_to }) return 1str_from, str_to = input().split()print(check_conversion(str_from, str_to))
Активные вакансии
Петя решил узнать, когда программисту выгоднее всего искать работу на hh.ru. Конечно, когда открыто больше всего вакансий.
Он выгрузил в текстовый файл время открытия и закрытия всех подходящих вакансий за 2019 год.
Теперь нужно определить период времени, когда открытых вакансий было больше всего.
Считаем, что:
- начальное и конечное время всегда присутствуют;
- начальное время всегда меньше или равно конечному;
- начальное и конечное время включены в интервал.
Например:
1
1 5
Здесь всего одна вакансия, соответственно, период, когда вакансий было больше всего тоже один, и занимает он все время жизни вакансии 5 секунд, ответ
1 5
.2
1 3
2 4
Здесь чуть посложнее, с 2 по 3 секунду были активны обе вакансии, такой интервал один, его длина 2 секунды, ответ
1
2
.2
1 2
3 4
Здесь вакансии не пересекались, то есть максимальное количество вакансий одна, однако интервалов, в которые была активна одна вакансия два. Несмотря на то, что в дискретном понимании, все 4 секунды вакансии существовали, непрерывным такой интервал не является, ответ
2 4
.Это задача на то, чтобы представить, как и в каком порядке происходили события. По сути, всё сводится к тому, чтобы собрать время начала и окончания всех вакансий, отсортировать его по возрастанию и пройтись по получившимся моментам времени, с каждой остановкой увеличивая или уменьшая количество активных вакансий, в зависимости от того, начальный это или конечный момент времени.
При этом, после изменения количества необходимо сравнить его с текущим максимальным и обновить максимальное, если текущее его превысило. Если сохранить информацию о том, в какой момент времени это произошло, её можно использовать для вычисления суммарной длительности.
Из тонкостей этого задания можно выделить две:
1. Данные на входе могут быть не отсортированными.
Условия не гарантируют сортировку входных данных, об этом нужно было позаботиться в решении, и это является, по сути, ключом к нему.
2. Данных может быть много, а потому лишние действия могут привести к превышению лимита времени или памяти.
В нашем большом тесте для этой задачи 100 000 вакансий, то есть 200 000 временных точек, что требует от решения быть максимально оптимальным и не использовать лишнего.
Пример кода решения на Python:
vacancies_count = int(input())time_points = []for moment in range(vacancies_count): start, end = input().split() # Добавляем информацию о начале и конце активности вакансии, и флаг, # свидетельствующий о том, является ли этот момент концом активности. # Флаг понадобится для сортировки и выяснения максимального количества вакансий time_points.append([int(start), False]) time_points.append([int(end), True])# Учитывая особенности сортировки Python для совпадающих по времени # моментов первым будет начало интервала, а вторым конец (False < True)time_line = sorted(time_points)max_vacancy_count = 0current_vacancy_count = 0for point_index in range(len(time_line)): # Если текущий момент - это начало активности вакансии, добавляем, # если конец - отнимаем current_vacancy_count += -1 if time_line[point_index][1] else 1 if current_vacancy_count > max_vacancy_count: max_vacancy_count = current_vacancy_count # Предыдущий список максимальных, если он был, заменяется новым max_vacancies_points = [point_index] elif current_vacancy_count == max_vacancy_count: # Если количество вакансий снижалось, а затем снова выросло, # интервалов с максимальным количеством вакансий # будет больше, чем 1, их индекс добавляется в массив max_vacancies_points.append(point_index)total_time = 0for point_index in max_vacancies_points: # Для интервалов с максимальным количеством вакансий между открытием # и закрытием не будет других моментов, то есть # time_line[point_index + 1] - это конец интервала # Добавляем 1, потому что начальное и конечное время включены в интервал total_time += 1 + time_line[point_index + 1][0] - time_line[point_index][0]print(len(max_vacancies_points), total_time)
Ссылка на репозиторий, в котором лежат решения для всех трёх языков и наши закрытые тесты: github.com/gooverdian/school-2020-tasks
Мы знаем, что вы сделали...
Не могу не упомянуть несколько огорчающий факт. В этом году было гораздо больше списанных решений. Уже через две недели после старта набора, в двадцатых числах августа, стали появляться первые дубли решений с одним и тем же источником, причем автором этих решений стал таинственный добрый самаритянин, не принимавший участия в школе (или использовавший другие решения для своей учетной записи). Также было много попыток купить решения для наших задач, что уже совсем расстраивает. Итоговое количество списавших в этом году перевалило за 50. Поначалу, мы приглашали таких участников на интервью в обычном режиме, однако, быстро стало понятно, что абсолютному большинству из них не хватает знаний. В итоге, мы приняли решение перенести собеседования с такими участниками на более поздние сроки.
Если вдруг в этом разделе вы узнали себя: пожалуйста, знайте, что после онлайн-этапа с автоматической проверкой всегда будет оффлайн с живым интервью. Используйте свои навыки программирования, а не поиска решений в интернете. Подготовьтесь лучше, и вы справитесь самостоятельно.
Всем ещё раз большое спасибо за участие!