Тренировки от Yandex 9.0

Прошел уже девятый сезон тренировок от Yandex. В этот раз изменили формат: раньше на целую неделю давалось ~10 задач на одну тему, которые можно было решать в любое время. Сейчас каждую неделю выделяли четыре слота по часу вечером, в каждом по две задачи. Такой формат ближе к спортивному программированию и собеседованиям. Дополнительно каждую неделю предлагался набор задач вне конкурса.

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

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

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

Для меня самым полезным оказалось порешать задачи на префиксные суммы и стек рекордов. Концепцию префиксных сумм понять несложно, но применять их последовательно в одной задаче трудновато. Каноничный пример, посчитать сумму произведений по всем тройкам индексов: ∑_i<j<k a_i·a_j·a_k.

Решение можно построить за линейное время за три цикла. Считаем сначала суффикс сумм p_sum от n до 0. Вторым шагом используя посчитанный суффикс для подсчета второго, как p_mul_i = p_mul_i+1 + p_sum_i+1· a_i, так же идя в обратном направлении. Последним шагом идем в прямом направлении и все суммируем, домножая на a_i.

Чтение данных

Самая полезная функция на контесте – это считывание данных. В C++ все просто работает через <</>>, в Rust приходится городить буфер и самому разделять по пробелам:

fn get_ints<T: std::str::FromStr>(n: usize) -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.split_whitespace()
        .take(n) // можно убрать, если нужно считать все до конца строки без указания количества
        .map(|w| w.parse().ok().unwrap())
        .collect()
}
let [n, k] = get_ints::<usize>(2).try_into().unwrap();
let v = get_ints::<usize>(n);

// Считывание строки тоже пригождается
let mut s = String::new();
std::io::stdin().read_line(&mut s).unwrap();
let s = s.trim_end();

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