Возможно ли за 5 дней догнать тех, кто соревновался целый месяц? Недавно я решил проверить это на CodeRun Boost Challenge — месячном марафоне по программированию от Яндекса. Я присоединился к соревнованию, когда до его завершения оставалось меньше недели, и поставил себе дерзкую цель: прорваться в топ.

Суть челленджа

CodeRun Boost Challenge — это не просто набор задач. Это целая история, где мы помогаем виртуальному коту Кодеруну спасти его мир от "Великого Стирания". Каждый день появлялась новая, всё более сложная задача, а за скорость решения начислялись бонусные баллы. Борьба в лидерборде была нешуточной.

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

Пример задачи: Восстановление данных

Одна из последних задач была особенно интересной. Представьте, что из-за системного сбоя у вас есть перемешанный список слов: половина из них — полные версии, а другая половина — их укороченные копии (префиксы). Нужно было восстановить исходные пары.

Например, из ["abac", "abacab", "aba", "abaa"] нужно было собрать пары ("aba", "abaa") и ("abac", "abacab").

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

  1. Сортировка по длине: Все слова сортируются по длине в порядке убывания.

  2. Поиск от длинного к короткому: Я начал обрабатывать самые длинные слова. Каждое такое слово, для которого еще нет пары, — это "полная версия", ожидающая свой префикс.

  3. Эффективное сопоставление: На каждом следующем шаге (для слов покороче) я быстро проверял, не является ли текущее слово префиксом для одного из "ожидающих" длинных слов. Для этого идеально подошли словари (хэш-мапы).

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

Python

# Демонстрация логики на Python
from collections import defaultdict

def solve_word_pairs(n: int, words: list[str]) -> list[list[int]]:
    groups = defaultdict(list)
    for i, word in enumerate(words):
        groups[len(word)].append(i + 1)
    
    sorted_lengths = sorted(groups.keys(), reverse=True)
    
    final_pairs = []
    unmatched_long_word_indices = []

    for length in sorted_lengths:
        current_word_indices = groups[length]
        long_words_by_prefix = defaultdict(list)

        for long_idx in unmatched_long_word_indices:
            prefix = words[long_idx - 1][:length]
            long_words_by_prefix[prefix].append(long_idx)
            
        newly_unmatched_indices = []
        for short_idx in current_word_indices:
            short_word = words[short_idx - 1]
            if short_word in long_words_by_prefix and long_words_by_prefix[short_word]:
                long_idx = long_words_by_prefix[short_word].pop()
                final_pairs.append([short_idx, long_idx])
            else:
                newly_unmatched_indices.append(short_idx)

        unmatched_long_word_indices = []
        for key in long_words_by_prefix:
            unmatched_long_word_indices.extend(long_words_by_prefix[key])
        unmatched_long_word_indices.extend(newly_unmatched_indices)

    return final_pairs

Результаты спринта

Тактика сработала. Несмотря на то, что я пропустил более 20 дней соревнования, мой финальный рывок принес впечатляющие результаты. Я активно использовал Rust и Go, чтобы максимизировать шансы в разных языковых зачетах.

Итог моего пятидневного марафона:

  • 🏆 71 место во всеобщем рейтинге.

  • 🦀 19 место в лидерборде по Rust.

  • 🧠 26 место в лидерборде по Go.

Эта история — доказательство того, что даже с поздним стартом можно достичь высоких результатов, если выбрать правильную стратегию и выложиться на полную. Огромное спасибо Яндексу за челлендж, который заставил мозг работать на пределе!