Тренировочный контест — бэкенд
басталуы:

Тренировочный контест

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

Решение задач должно быть в виде файла на языках Python, C++, Java, Go, PHP, C#, Kotlin, Scala, JavaScript без использования подключаемых библиотек.

Если вы первый раз сталкиваетесь с тестирующей системой, попробуйте свои силы на вкладке «Пробный контест».

Значение ошибок можно посмотреть в соответствующем разделе.

Вопросы задавайте на intern@yandex-team.ru.

Желаем удачи!

Далее идет расширенная инструкция по работе с Яндекс Контестом.

Данная инструкция написана авторами соревнования на основе множества вопросов, сложных подходов и ошибок, которые встречались у участников.

Содержание

1. Краткая (не очень) инструкция.

1.0. В каком порядке надо решать задачи?

1.1. Что является решением задачи и как его отправить?

1.2. Данные - откуда читать, куда писать?

1.3. Как тестируется решение?

1.3.1. ВАЖНО: ограничения на входные данные - гарантии участнику

1.3.2. Возможные вердикты тестирования

1.4. Задачи решил, что дальше?

1.5. Что можно изучить перед соревнованием?

2. Ответы на самые-самые часто задаваемые вопросы.

2.1. “Я прочёл задачу, но не понял …”

2.2. “Я уверен в том, что ваше условие / примеры / пояснение содержат ошибку!”

2.3. “Локально тесты из условия работают, но при отправке на тестах из условия получаю…”

2.3.1. Ошибка компиляции (CE)

2.3.2. Ошибка выполнения (RE)

2.3.3. Неправильный ответ (WA)

2.3.4. Дополнительные специфичные для языков проблемы

2.3.4.1. С++

2.3.4.2. Golang

2.3.4.3. Java

2.4. “А можно ли использовать pandas / numpy / boost / другую дополнительная супер-пупер библиотеку?”

2.5. “Мое решение не проходит тесты в системе, но я всё-всё-всё перепроверил по 10 раз”

2.5.1. “Уверен, что у вас некорректный тест!”

2.5.2. “Как я должен искать ошибку, если не вижу ваш тест?”

2.5.3. “Решение прошло первые Х тестов, а дальше никак. Что же там за тест?”

2.5.4. “Я уверен, что мое решение работает максимально эффективно. Но система продолжает выдавать вердикт TL”.

2.5.5. “Да что такое этот ваш вердикт ML?!”.

2.5.6. “Впал в уныние, получив вердикт RE. Не знаю, что и делать”

2.5.7. “Моя программа выполняется на 0.002 секунды дольше / испольует на 0.1 МБ больше, чем разрешено. Да как же так?!”

2.5.8. “Да как у меня может быть вердикт WA? Я же всё делаю правильно!”

3. Важная информация для различных языков

3.0. Общие концепции и идеи

3.0.0. Переполнение целочисленного типа

3.0.1. Буферизованный ввод/вывод

3.0.2. Работа с таблицей символов

3.0.3. Возможности стандартной библиотеки языка

3.1. C++

3.2. Python

3.3. Java

3.4. Golang

3.5. PHP

3.6 C#

1. Краткая инструкция

1.0. В каком порядке надо решать задачи?

Задачи можно читать и решать в любом порядке. Более того, можно делать попытки по разным задачам “вперемешку”.

Мы постарались выстроить задачи в порядке возрастания сложности, но помните, что эта оценка очень субъективна.

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

1.1. Что является решением задачи и как его отправить?

Решением задачи является исходный код (программа) на одном из разрешенных в соревновании языков программирования.

Отправить решение в систему можно двумя способами (можно пользоваться и тем, и тем):

  • скопировать сам текст программы и вставить в соответствующее окошко

  • отправить файл с кодом (расширения .cpp, .java, .py и аналогичные).

Код, разделенный на несколько отдельных файлов, отправлять нельзя. Исполняемые файлы (.jar, .exe и т.д.) НЕ являются решением задачи.

1.2. Данные - откуда читать, куда писать?

Решение должно считывать данные из стандартного потока ввода (консоли) ИЛИ из файла ‘input.txt’. Аналогично решение должно выводить данные в стандартный поток вывода (консоль) ИЛИ в файл ‘output.txt’.

Выбор, откуда читать / куда писать - полностью на усмотрение участника.

Примеры ввода/вывода на разных языках: стандартный поток и файлы.

Важно: любой не относящийся к ответу вывод делает весь ответ неверным. Примеры таких выводов:

  • “Введите число Х:”

  • “Ответ равен:”

Решение должно выводить только то, что просят по условию задачи.

1.3. Как тестируется решение?

Автоматически происходят следующие вещи: - решение компилируется;

  • решение вызывается по очереди на наборе заранее заготовленных тестов;

  • на каждом тесте (независимо) решение должно уложиться в отведенные ограничения на время выполнения / использованную память;

  • ответ на каждый тест проверяется на корректность (в случае, если уложились в ограничения времени/памяти).

Если решение не проходит тест - вы получаете соответствующий вердикт и дальнейшая проверка данного решения останавливается.

Важно: в условии задачи представлены лишь первые тесты (именно первые). Всего тестов намного больше.

Решение считается верным только, если оно проходит ВСЕ тесты.

1.3.1. ВАЖНО: ограничения на входные данные - гарантии участнику

Мы не раз наблюдали следующую ситуацию. Участник читает ограничения на входные данные и начинает писать громоздкий код, чтобы их проверить у ввода.

Это всё НЕ НУЖНО делать!

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

Более того, все тесты проверяются автоматически при подготовке задачи. Так что мы уверены в том, что все тесты корректны.

Важный пример: входные данные в задаче содержали даты в формате “год месяц день”. В условии были заданы ограничения:

  • день от 1 до 31;

  • месяц от 1 до 12;

  • год от 1950 до 2022;

  • даты являются корректными календарными датами (то есть не будет 30 февраля).

Мало того, что участник решил проверить все эти ограничения (что уже потребовало немало дополнительного кода с использованием календаря в языке).

Главная проблема - участник неверно записал проверки корректности, поэтому ловил неправильный ответ и не мог понять, что не так с его алгоритмом решения (с самим решением без проверок всё было ок).

1.3.2. Возможные вердикты тестирования

Детальная информация по всем возможным вердиктам расположена по ссылке “Значения ошибок”

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

1.4. Задачи решил, что дальше?

Итоговым результатом участника является количество задач, по которым он получил вердикт ОК (хотя бы раз за время соревнования).

После завершения соревнования анализируется ваш результат, резюме и другие факторы (авторам соревнования неизвестные). По итогам с вами свяжутся - вероятнее всего в течение недели.

Если вам кажется, что уже пора бы получить ответ, а его нет - пишите или на почту intern@yandex-team.ru, или в вопросы соревнования (лучше на почту).

1.5. Что можно изучить перед соревнованием?

Самые частые темы, которые могут встретиться на соревновании и последующих собеседованиях:

Возможности стандартной библиотеки

  • базовая работа со строками и символами;

  • сортировка и компараторы (функции сравнения объектов);

  • списки (на массиве и связные);

  • множества и словари (хеш-таблицы и деревья поиска);

  • стек и очередь;

  • очередь с приоритетом (обычно на основе кучи);

  • встроенный двоичный поиск;

Базовые алгоритмы

  • двоичный поиск (когда не хватает встроенного);

  • префиксные суммы;

  • два указателя;

  • сортировка событий;

  • двоичные деревья (не поиска, просто деревья);

Базовые алгоритмы, но для искушенных

  • динамическое программирование

  1. одномерное (зайчик);

  2. двумерное (черепашка);

  3. рюкзак;

  • основы теории графов:

  1. хранение;

  2. поиск в глубину;

  3. поиск в ширину;

  4. топологическая сортировка;

  5. кратчайшие пути.

Советуем изучить тренировки Яндекса 1.0, 2.0 и 3.0 для лучшего ознакомления.

2. Ответы на самые-самые часто задаваемые вопросы.

2.1. “Я прочёл задачу, но не понял …”

Мы рассчитываем, что вы изучили все разделы условия:

  • легенда;

  • описание входных данных;

  • описание выходных данных;

  • примеры тестов (да, это тоже часть условия);

  • пояснения к примерам.

Мы постарались написать пояснения к примерам максимально подробно.

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

2.2. “Я уверен в том, что ваше условие / примеры / пояснение содержат ошибку!”

Вкратце - нет, мы уверены, что всё в порядке.

Да, точно в порядке. Вот точно-преточно.

Вероятно, вы что-то не так прочитали или поняли. Перечитайте условие.

Другой хороший способ - попробуйте составить четкие аргументы, почему что-то неверно. Найдите цитаты из условия, подтверждающие вашу точку зрения. Вероятнее всего, в процессе вы найдете, что именно вы читали / понимали не так.

2.3. “Локально тесты из условия работают, но при отправке на тестах из условия получаю…”

Первым делом проверьте, что вы выбрали именно ту задачу, которую хотите сейчас сдать.

Важно: убедитесь, что ваш случай не попадает под особый случай для вашего языка (все детали для языков ниже).

Тесты в условии являются первыми тестами при проверке. Да, ровно в том порядке, в котором они указаны в задаче.

Вот несколько дополнительных возможных причин:

2.3.1. Ошибка компиляции (CE)

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

Откройте “отчет” - там будет написано сообщение об ошибке, выданное компилятором.

2.3.2. Ошибка выполнения (RE)

Проверьте, что вы читаете данные в корректном формате. Да, именно в том формате, который указан в примерах ввода.

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

2.3.3. Неправильный ответ (WA)

Вы точно локально выводите правильный ответ?

Вы точно выводите данные в том же формате, что и в задаче? Это может быть критично.

Вы точно не выводите НИЧЕГО лишнего? Прям точно-преточно? В том числе проверьте, не выводите ли вы непечатаемые символы.

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

2.3.4. Дополнительные специфичные для языков проблемы (для проблем с тестами из условия)

Если у вас ошибки на тестах НЕ из условия - изучите пункт 2.5.

2.3.4.1. C++

Неопределенное поведение (undefined behaviour, UB)

Подробнее об этом на Википедии.

  • Неинициализированные переменные;

Ваша среда разработки может обнулять переменные (особенно в debug-режимах), поэтому вы можете не замечать проблемы. В системе же в данных переменных может лежать “мусор”.

  • Выход за границы массива;

Зачастую компиляторы не кидают ошибку (хотя бы в debug), но просто разрешают программе прочитать / записать в “не ту” память. В системе это может приводить к ошибкам и некорректным значениям.

  • Переполнение целочисленного типа;

Проверьте переполнение целочисленного типа. (Например, если умножить 100 000 на 100 000 на С++, то получится 1410065408).

Использование чистого fstream

Если вы хотите работать с файлами через fstream, то используйте конкретные реализации ifstream и ofstream.

Создание просто fstream без доп. настроек не гарантирует, что он будет работать именно на ввод/вывод, как вы этого можете ожидать.

2.3.4.2. Golang

Совместное использование fmt.Scan / fmt.Fscan и bufio.Reader

Никто не гарантирует синхронизированность разных способов ввода.

Локально они могут работать, в системе - чаще всего нет.

Если вы получаете WA 1, хотя локально всё работает - используйте только один из двух способов (желательно bufio.Reader).

2.3.4.3. Java

Ваше решение НЕ должно содержать package. Вообще никакой. Удалите, если он есть.

Иначе вы получите RE 1, так как ваш класс не будет найден при запуске.

2.4. “А можно ли использовать pandas / numpy / boost / другую дополнительная супер-пупер библиотеку?”

Нет, нельзя. Даже если задача очень круто решается этой библиотекой - всё равно нельзя.

Вам доступны только библиотеки / модули, входящие в стандартную поставку компилятора.

К примеру, модуль “algorithm” в С++ или “collections” в Python доступны.

Кстати, все авторские решения не содержат каких-то зубодробительных алгоритмов и структур данных на 200+ строк.

2.5. “Мое решение не проходит тесты в системе, но я всё-всё-всё перепроверил по 10 раз”

Данный пункт достаточно объемный, поэтому мы разобьём его на несколько подпунктов.

2.5.1. “Уверен, что у вас некорректный тест!”

Мы уверены, что все тесты корректные.

При подготовке задачи используется автоматическая валидация тестов. Так что всё точно корректно, мы уверены.

Обратите внимание, что тесты удовлетворяют ТОЛЬКО ограничениям, описанным в условии и никаким другим.

И почти наверняка все ограничения, описанные в условии, будут достигнуты в том или ином тесте.

Пример: как-то раз в одной из наших задач вводились фамилии.

На фамилии было наложено ограничение “состоят из строчных и заглавных латинских букв”.

Некоторые участники считали, что первая буква фамилии всегда заглавная (это же фамилия), из-за чего ловили ошибку.

2.5.2. “Как я должен искать ошибку, если не вижу ваш тест?”

Да, тесты недоступны для просмотра участником (кроме тестов в условии). Нет, мы их не покажем точно.

В то же время эти тесты точно-преточно удовлетворяют ограничениям, описанным в “формат входных данных”.

И поэтому вы вполне можете сгенерить сами локально тест. Даже если это будет случайный тест - вероятнее всего что-то вы найдете.

Если не нашли - то проверьте крайние случаи (минимальные / максимальные значения или другие экстремумы в данных).

Может быть у вас падает, если количество элементов массива равно 1? Или может быть программа не работает, когда число - степень двойки?

В реальной работе вам тоже придется придумывать тесты для своего кода (юнит-тестирование), а также не всегда вы сможете легко посмотреть, на чем же “падает” ваш код в продакшене.

2.5.3. “Решение прошло первые Х тестов, а дальше никак. Что же там за тест?”

Повторимся: все тесты точно-преточно удовлетворяют ограничениям, описанным в “формат входных данных”.

Вероятнее всего, ваше решение “споткнулось” об тесты с максимальными значениями / количествами входных данных.

Да-да, если в задаче написано “N <= 200 000”, то там будут тесты с “N = 200 000”. И, вероятнее всего, таких тестов как раз будет большинство.

Если вы видите, что ваше решение сначала работало быстро, а потом резко начало работать долго и, возможно, еще и неправильно - это как раз начались ОЧЕНЬ большие тесты после нескольких мелких.

2.5.4. “Я уверен, что мое решение работает максимально эффективно. Но система продолжает выдавать вердикт TL”.

Первым делом проверьте советы для вашего языка (см. содержание) - возможно у вас недостаточно эффективный ввод/вывод.

Оцените асимптотику (количество операций) вашего решения. Вероятнее всего, совсем “втупую” решение не подразумевается (иначе в чём смысл).

Ограничения выставлены таким образом, что авторские решения укладываются в 2-3 раза от выставленных ограничений.

В среднем языки типа C++ или Go выполняют порядка нескольких сотен миллионов (10^8) операций в секунду. Остальные языки в среднем помедленнее, но в задачах специально выставлены разные ограничения для разных языков.

Пример Допустим, что в задаче N < 300 000. Если ваша программа выполняет O(N^2) операций, то это порядка (3 * 10^5) в квадрате ~ (10^11) операций. Как видите, тут очень далеко от 10^8 (даже от 10^9), поэтому это не залезет ни в секунду, ни в две, ни в десять.

2.5.5. “Да что такое этот ваш вердикт ML?!”.

Две основные причины:

  • вы пытаетесь выделить слишком большой массив.

Пример Массив / вектор из 10^9 интов (4-байтного целого типа) занимает 4 Гигабайта. Подумайте о том, насколько это много, учитывая ограничения по памяти в 256 или 512 мб в задачах.

  • вы вошли в бесконечный цикл, который расширяет какую-то структуру данных. По сути между вердиктами TL и ML была гонка.

2.5.6. “Впал в уныние, получив вердикт RE. Не знаю, что и делать”.

Иногда под вердиктом RE скрывается вердикт ML: при попытке выделить очень большой массив некоторые языки выбрасывают исключение, которое интерпретируется системой как RE, хотя по факту проблема именно в превышении лимита по памяти.

Зачастую всего RE сигнализирует о следующих проблемах:

  • Неверный тип данных при чтении.

Например, вы пытаетесь прочесть строчку как число.

Или вы пытаетесь впихнуть слишком большое число в недостаточно большой тип.

  • Выход за границы массива.

Например, ваш код пытается взять первый и второй элементы массива, а в нём всего лишь один элемент (вот это поворот!)

  • Деление на ноль.

Ну тут комментарии излишни)

  • Обращение к null (Java, Kotlin, C# и др.) / None (Python).

Общий смысл таков - вы пытаетесь обратиться к данным, которых там нет по определению.

  • (С++ специфично) Обращение к “мусорным данным” - использование неинициализированных значений массива / end()-итератор.

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

2.5.7. “Моя программа выполняется на 0.002 секунды дольше / испольует на 0.1 МБ больше, чем разрешено. Да как же так?!”

На самом деле это косяк интерфейса Яндекс.Контеста.

То число, что вы видите - это не время / память вашего решения. Это те время / память, при которых выполнение вашей программы было остановлено. Да-да, никто не будет ждать конца завершения программы, уже превысившей ограничения.

Вероятнее всего ваше решение потребляет НАМНОГО больше времени / памяти, чем нужно (как мы писали, авторские решения используют, как правило, в 2-3 раза меньше ресурсов, чем заданные ограничения).

2.5.8. “Да как у меня может быть вердикт WA? Я же всё делаю правильно!”

Очевидно, что самая вероятная причина - у вас ошибка в логике / коде. И тут мы не можем ничего поделать.

Но вот несколько советов, которые могут помочь:

  • Перечитайте условие. Вы точно не пропустили важную деталь? (“выведите ответ в сортированном порядке” или “числа могут повторяться”).

  • Проверьте переполнение целочисленного типа. (Например, если умножить 100 000 на 100 000 на С++, то получится 1410065408).

3. Важная информация для различных языков

Здесь мы постарались собрать известные нам оптимизации или просто полезные советы по решению задач на том или ином языке.

3.0. Общие концепции и идеи

3.0.0. Переполнение целочисленного типа

Статья на Википедии.

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

Пример: если умножить 100 000 на 100 000 на С++, то получится 1410065408.

Способ решения по сути один: хотя бы один из двух операндов должен быть большого (обычно 8-байтного типа).

3.0.1. Буферизованный ввод/вывод

Большинство языков программирования имеют стандартные средства ввода/вывода, связанные с консолью.

Зачастую данные средства недостаточно эффективны при вводе и выводе (особенно при выводе) больших объемов данных.

Чаще всего к этому приводит частое обращение к данным на диске (вне оперативной памяти).

Для ускорения используют буферизованный ввод/вывод. В таком случае данные читаются / пишутся на диск не поэлементно, а сразу большим куском. Такой подход позволяет уменьшить количество обращений к внешней памяти, что и ускоряет программу.

3.0.2. Работа с таблицей символов

Не раз в решениях, где надо было как-то соотносить позицию латинской буквы с её номером в алфавите (в ту или иную сторону), мы наблюдали аккуратно записанные 26 символов в правильном порядке “ABCDE…XYZ”.

Так НЕ НАДО делать!

Любой язык содержит операции для преобразования символов в их коды (ASCII или Unicode) и обратно.

Изучите их и пользуйтесь - ваш код станет намного удобнее и проще.

Пример: один участник получил вердикт “неправильный ответ”, так как при записи алфавита вместо буквы “J” записал второй раз букву “G”.

3.0.3. Возможности стандартной библиотеки языка

Чаще всего какой-либо алгоритм или структуру данных, которую нужно использовать в решении, уже реализовали в языке программирования (часто, но не всегда).

Изучите заранее возможности стандартной библиотеки вашего языка.

Особенно сделайте упор на следующие пункты:

  • сортировка и компараторы;

  • динамические массивы на массиве;

  • множества и словари (хеш-таблицы и деревья поиска);

  • встроенный двоичный поиск;

  • связный список (для особых ценителей);

  • стек и очередь;

  • очередь с приоритетом (обычно на основе кучи).

Маленькая деталь про хеш-таблицы

Хеш-таблицы не гарантируют по умолчанию какой-то определенный порядок итерации.

Точнее, есть фиксированная зависимость порядка итерации от данных, определенная для фиксированного компилятора и его версии.

Если вам нужен какой-то специфичный порядок итерации, то

  • возможно вам нужны деревья поиска;

  • возможно вам достаточно порядка итерации в порядке вставки (OrderedDict в Python / LinkedHashSet и LinkedHashMap в Java).

3.1. C++

Компиляторы

Для С++ доступны компиляторы CLang и GNU C++.

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

Ускорения ввода-вывода

При сомнениях в скорости ввода/вывода через cin/cout можете попробовать использовать следующее ускорение:

// пишем один раз в main перед использованием cin
ios::sync_with_stdio(false);
cin.tie(nullptr);

(вызывается в начале выполнения программы) Этот код отключает синхронизацию с printf/scanf и синхронизацию потоков cin/cout между собой.

Также напоминаем, что endl вызывает внутри себя flush, что может негативно сказаться на скорости выполнения работы программы (рекомендуется использовать \n при необходимости)

Работа с кодами символов

Тип char является целочисленным, поэтому:

  • (ch - ‘a’) или (ch - ‘A’) - номер символа ch в алфавите (зависит от регистра);

  • char(pos + ‘a’) или char(pos + ‘A’) - символ по номеру pos в алфавите (зависит от регистра);

Возможности стандартной библиотеки языка

Очевидно, что это не все возможности, просто элементы из пункта 3.0.3.

  • sort (принимает два итератора);

  • vector (динамический массив) и list (связный список);

  • set/map - деревья поиска; unordered_set/unordered_map - хеш-таблицы;

  • lower_bound / upper_bound;

  • queue, deque;

  • priority_queue (на максимум).

3.2. Python

Компиляторы

Для Python доступны компиляторы PyPy и Python 3. PyPy соответствует Python 3.7.

Важно: в большинстве случаев PyPy выполняет программы быстрее, поэтому авторы задач рекомендуют его для использования.

Но вы можете использовать любой из двух компиляторов. Иногда Python 3 (не PyPy) выполняет некоторый код эффективнее PyPy (но редко). Еще реже у данных компиляторов случается разница в поведении, которая может быть вам критична.

Никакого штрафа за переотправку решения под другим компилятором нет.

Ускорения ввода-вывода

Рекомендуется рассмотреть возможность вывода данных с помощью комбинации:

  • сбор всех результирующих данных в один массив

  • приведение элементов данного массива к строкам:

  • “скрепление” данных строк с помощью функции “join” у выбранного разделителя

Пример: вывод массива целых чисел “ans” в формате “каждое число на новой строке”:

# если ans = [1, 3, 5], то map(str, ans) сделает "1", "3", "5"
ans_str = "\n".join(map(str, ans))
print(ans_str)

Работа с кодами символов

  • ord(ch) - ord(‘a’) или ord(ch) - ord(‘A’) - номер символа ch в алфавите (зависит от регистра);

  • chr(pos + ord(‘a’)) или chr(pos + ord(‘A’)) - символ по номеру pos в алфавите (зависит от регистра);

Возможности стандартной библиотеки языка

Очевидно, что это не все возможности, просто элементы из пункта 3.0.3.

  • sort / sorted;
  • list (динамический массив);
  • set / dict - хеш-таблицы;
  • модуль bisect;
  • модуль collections: deque, defaultdict;
  • модуль heapq.

3.3. Java

ВАЖНО: Не используйте package

Заголовок говорит сам за себя. Удалите package, если он есть в первой строке вашего решения.

Решения с package будут ловить RE 1 при отправке в систему, так как класс не будет найден для запуска.

Ускорения ввода

На больших объемах данных Scanner начинает проседать по производительности.

Рекомендуется рассмотреть возможность использования BufferedReader (возможно вам еще приглянется класс StringTokenizer).

Пример ввода с BufferedReader есть в справке Яндекс.Контеста

Ускорения вывода

В случае необходимости ускорения вывода можно использовать любой буферизованный вывод (PrintWriter / BufferedWriter). Единственное условие - не забудьте закрыть поток после вывода (операция close) или используйте конструкцию try-with-resources.

Работа с кодами символов

  • (ch - ‘a’) или (ch - ‘A’) - номер символа ch в алфавите (зависит от регистра);

  • (char)(pos + ‘a’) или (char)(pos + ‘A’) - символ по номеру pos в алфавите (зависит от регистра);

Возможности стандартной библиотеки языка

Очевидно, что это не все возможности, просто элементы из пункта 3.0.3.

  • Arrays.sort / Collections.sort;

  • Comparable / Comparator;

  • ArrayList (зачастую хватает простого массива);

  • HashSet/HashMap - хеш-таблицы; TreeSet/TreeMap - деревья поиска;

  • Arrays.binarySearch / Collections.binarySearch;

  • ArrayDeque;

  • PriorityQueue.

ВАЖНО: не совсем очевидное сравнение wrapper-класса Integer

Если элементы типа Integer принадлежат отрезку [-128..127], то они представляются одним и тем же объектом в памяти.

Если же элементы типа Integer вне заданного отрезка, то каждое значение представляется своим собственным объектом, поэтому сравнение на == скажет, что они различны (так как различны ссылки).

Пример:

// a, b в отрезке
Integer a = 123;
Integer b = 123;
System.out.println(a == b); // true

// c, d вне отрезка
Integer c = 234;
Integer d = 234;
System.out.println(c == d); // false

// e, f в отрезке, но созданы через new
Integer e = new Integer(123);
Integer f = new Integer(123);
System.out.println(e == f); // false

3.4. Golang

ВАЖНО. Оптимизация ввода

Среди кандидатов на Golang популярно использовать связку двух способов:

  • fmt.Scan;

  • bufio.Reader вместе с fmt.Fscan.

НЕ ИСПОЛЬЗУЙТЕ ИХ ВМЕСТЕ! В системе они рассинхронизированы, ваша программа будет читать ввод очень неправильно.

  • Читайте только через bufio.Reader - он быстрее (буферизованный как-никак).

  • Используйте ОДИН bufio.Reader на весь ввод.

  • По возможности вводите массивы поэлементно - примерно так: fmt.Fscan(in, &arr[i]) в цикле по i.

  • Если вдруг вы решили считывать строку целиком - используйте ReadString(), а не ReadLine (а вообще лучше прочтите документацию и узнайте про отличия, плюсы и минусы).

3.5 PHP

Количество доступной памяти и вердикт RE

В компиляторе PHP есть внутренние ограничения на количество доступной оперативной памяти (меньше задуманных нами).

Если ваша программа превышает эти ограничения, то вы получите вердикт RE.

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

<?php
ini_set('memory_limit', '512M');
(далее ваше решение)
?>

512M - это пример, выставляйте ту величину, которая указана в ограничениях по памяти для вашего компилятора.

3.6 C#

Компиляторы

Для C# доступны компиляторы MS .NET и Mono.

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

Работа с кодами символов

  • (ch - ‘a’) или (ch - ‘A’) - номер символа ch в алфавите (зависит от регистра);

  • (char)(pos + ‘a’) или (char)(pos + ‘A’) - символ по номеру pos в алфавите (зависит от регистра);