Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Разбор задач заочной олимпиады по программированию

Задача 1 - Управление памятью

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

Данные о блоке памяти - номер и время последнего запроса к нему - будем хранить в структуре Block:

class Block
{
    private final int num;
    private int time;
    
    public Block(int num, int time)
    {
        super();
        this.num = num;
        this.time = time;
    }
    
    /* getters and setters */
    /* ... */
}

Ссылки на все имеющиеся блоки будем хранить в массиве blocks, для того чтобы за O(1) получать блок по номеру. Также заводим 2 упорядоченных множества:

  • множество свободных блоков freeblocks (упорядочено по возрастанию номера блока)
  • множество занятых блоков allocatedblocks (упорядочено по возрастанию времени последнего запроса к блоку)

Вставка нового элемента в эти множества должна осуществляться за время O(log N). Это можно реализовать, например, с помощью деревьев двоичного поиска.
Изначально помещаем во freeblocks ссылки на все блоки.

 

class MemoryManager
{

    private final int T;
    private final int capacity;
    
    private Block[] blocks;
    
    //внутренняя структура TreeSet в Java - двоичное дерево, вставка элемента осуществляется за O(log N)
    
    private TreeSet<Block> freeblocks =
            new TreeSet<Block>(new ByNumComparator());
            
    private TreeSet<Block> allocatedblocks =
            new TreeSet<Block>(new ByTimeComparator());
    
    public MemoryManager(int capacity, int lt)
    {
        T = lt * 60;
        this.capacity = capacity;
        blocks = new Block[capacity];
        for (int num = 1; num <= capacity; num++)
        {
            Block block = new Block(num, 0);
            blocks[num-1] = block;
            freeblocks.add(block);
        }
    }

Далее будем последовательно обрабатывать запросы из входного файла.
Перед выполнением каждого запроса проводим следующую проверку: просматриваем последовательно блоки из allocatedblocks, и если время "простоя" блока превышено, перемещаем его во freeblocks. Проверка заканчивается при обнаружении первого блока с неистекшим временем "простоя" (т.к. у всех следующих время последнего доступа гарантированно больше).

    /* параметр time - текущее время */
    private void preopcheck(int time) // O(N * log N)
    {
        while (!allocatedblocks.isEmpty())
        {
            Block block = allocatedblocks.first(); // O(1)
            if (block.getTime() <= time - T)
            {
                freeblocks.add(block); // O(log N)
                allocatedblocks.pollFirst(); // O(1)
            }
            else break;
        }
    }

С помощью этой операции мы гарантируем, что перед выполнением запроса все "устаревшие" блоки освобождены.
Для выделения блока (allocate) берем первый блок из множества свободных, устанавливаем новое время последнего запроса и перемещаем его в множество занятых:

    /* параметр time - текущее время */
    /* возвращаем номер выделенного блока или -1, если нет свободных */
    public int allocate(int time) // O(N * log N)
    {
        preopcheck(time); // O(N * log N)
        Block block = freeblocks.pollFirst(); // O(1)
        if (block == null)
        {
            return -1;
        }
        block.setTime(time);
        allocatedblocks.add(block); // O(log N)
        return block.getNum();
    }

Для доступа к блоку по номеру проверяем, есть ли он в множестве занятых, и если это так, обновляем время последнего запроса:

    /* параметр time - текущее время, num - номер запрашиваемого блока */
    /* возвращаем true, если обращение было успешным, false в противном случае */
    public boolean access(int time, int num)  // O(N * log N)
    {
        preopcheck(time); // O(N * log N)
        if (num > capacity)
            return false;

        Block block = blocks[num-1]; // O(1)
        if (allocatedblocks.contains(block)) // O(log N)
        {
            allocatedblocks.remove(block); // O(log N)
            block.setTime(time);
            allocatedblocks.add(block); // O(log N)
            return true;
        } else
            return false;
    }

Таким образом, мы выполняем K операций за время порядка O(N * log N) каждую, и общее время выполнения программы порядка O(K * N * log N). На самом деле,это довольно завышенная оценка, т.к. редко возникает ситуация, когда в списке занятых блоков находится N "просроченных" блоков (за счет ограничений минимального времени "простоя", максимального текущего времени и количества запросов; точную оценку участникам предлагается провести самостоятельно)
Соответственно, время выполнения операции preopcheck в большинстве случаев имеет порядок O(log N), что дает приемлемую оценку для времени выполнения программы K * log N ~ 10^6.

Задача 2 - Менеджер пакетов

В задаче требуется реализовать алгоритм топологической сортировки графа с проверкой на ацикличность.
Пример реализации приведен на языке Java.

Для хранения зависимостей пакетов используем отображение (хэш-таблицу) имен пакетов в списки имен их зависимостей:

public class PackageManager
{

    private Map<String, List<String>> db;

    public PackageManager(Map<String, List<String>> db)
    {
        super();
        this.db = db;
    }

Отображение формируется при чтении входных данных. Доступ к списку зависимостей по имени пакета осуществляется за время порядка O(1).

Рекурсивный алгоритм топологической сортировки реализуется следующим образом. Для каждого пакета, входящего в обрабатываемый запрос, вызывается метод processPackage, в котором проверяется, не был ли пакет обработан ранее. Если пакет встречается впервые, он помещается в множество обработанных, после чего метод рекурсивно вызывается для всех пакетов, от которых он зависит. После этого имя пакета добавляется в список-результат. Таким образом, мы получаем список, в котором имя каждого пакета стоит строго после имен его зависимостей.
Если представить пакеты и их зависимости в виде ориентированного графа, в котором ребра направлены от каждого пакета к пакетам, от которых он зависит, то описанный алгоритм аналогичен алгоритму поиска в глубину на графе.
Для обнаружения циклических зависимостей следует модифицировать алгоритм, введя глубинную нумерацию на графе. Введем глобальную переменную number с начальным значением 1 и отображение dfnumber, сопоставляющее каждому пакету его глубинный номер. При каждом вызове метода processPackage для ранее не обработанного пакета глубинный номер устанавливается равным текущему значению number, после чего number увеличивается на 1. Если при следующих вызовах processPackage некоторый пакет встречается повторно, и его глубинный номер меньше текущего, значит имеет место циклическая зависимость - в графе обнаружено ребро (обратная дуга), идущее от потомка к предку. После обработки всех зависимостей пакета его глубинный номер устанавливается в 0, чтобы отличать обратные дуги от поперечных (соединяющих различные подграфы). Подробную информацию об описанных алгоритмах можно найти в книге  А. Ахо, Д. Хопкрофт, Д. Ульман "Структуры данных и алгоритмы" , с. 203-209.

Ниже предложена реализация класса Processor и метода processPackage:

    private class Processor
    {

        // список обработанных пакетов
        private Set<String> processed = new HashSet<String>();
        
        // результат
        private LinkedList<String> resolution = new LinkedList<String>();
        
        // отображение, сопоставляющее пакету его глубинный номер
        private Map<String, Integer> dfnumber =
                new HashMap<String, Integer>();
                
        // текущий глубинный номер
        private int number = 1;
        private final int NOT_IN_CYCLE = 0;

        public void processPackage(String pkg)
                throws CyclicDependencyException
        {
            if (!processed.contains(pkg))
            {
                // добавляем пакет в обработанные
                processed.add(pkg);
                
                // назначаем глубинный номер
                dfnumber.put(pkg, number);
                
                // увеличиваем текущий глубинный номер
                number++;
                
                List<String> list = db.get(pkg);
                for (String dep : list)
                {
                    // рекурсивный вызов для зависимостей
                    processPackage(dep);
                }
                
                // после обработки всех зависимостей помечаем пакет как не создающий цикла
                dfnumber.put(pkg, NOT_IN_CYCLE);
                
                // добавляем имя пакета в результат
                resolution.add(pkg);
                
            } else if (dfnumber.get(pkg) != NOT_IN_CYCLE
                    && dfnumber.get(pkg) < number) // условие для обратной дуги
            {
                throw new CyclicDependencyException();
            }
        }

        public List<String> getResolution()
        {
            return resolution;
        }
    }

В случае, когда число зависимостей (дуг в графе) L превышает число пакетов (вершин графа) N, данный алгоритм работает за время порядка O(L). Имея N запросов, получаем общее время выполнения программы порядка O(L*N). В условиях задачи L*N = 75 000 000, что укладывается во временные ограничения на современных процессорах.

Задача 3 - Взлом пароля

Данная задача вызвала множество вопросов со стороны участников олимпиады. Поэтому сначала небольшой обзор того, как эту задачу стоило понимать. Смотрим на вопрос в задаче - какова вероятность успеха. В общем случае вероятность какого-то события это отношение количества случаев, где это данное событие выполняется к общему числу случаев. Таким образом, для решения задачи нужно выяснить два числа, которые участвуют в упомянутом отношении. Проще всего с общим количеством случаев - в нашем примере это общее количество паролей. Смотрим на секцию "Входные данные". Комментарий к параметру К дает исчераывающий ответ - пароль это К цифр. Теперь перейдем к "успешным" случаям. Из задачи мы знаем, что успешность как-то связана с суммой цифр пароля. Таким образом у нас есть два варианта:1) "Успешный" случай ровно один - некий набор цифр, которые в сумме равны Q. Но получается, что в нашем решении не используется число Q. А значит оно уже почти наверняка неправильное. Это проверяется на примере. Если входные данные 18 и 50, то вероятность считается как 1/(9^18) (где 1 это количество "успешных паролей", а 9^18 это количество всех паролей). Убеждаемся, что мы не правильно поняли задачу и переходим ко второму варианту.2) "Успешных" случаев много. Много это сколько? В задаче  есть только условие, что сумма цифр равна Q. Наверное любой пароль в котором сумма цифр равна Q успешный. Пишем отдельную программу, которая, например перебором, считает количество паролей, которые состоят из 18 цифр и имеет сумму 50. Проверяем и убеждаемся, что в данном случае вероятность получается именно та, которая требуется- 0,00003293.Теперь когда понятно что нам требуется найти можно начинать решать задачу.

Есть два подхода к решению - математический и программистский.
Начнем с первого: просто порешать задачу на бумаге и выяснить математическую формулу, которая выражает искомую вероятность. Некоторые участники так и поступили. Они успешно справились с задачей.
Второй подход: использование такого приема как динамическое программирование.Представим себе таблицу в которой 300 строчек и 2700 столбцов. На пересечении K строчки и Q столбца стоит вероятность, которая требуется в условии.Наша задача заполнить эту таблицу (назавем ее chance).Начнем с первой строчки. Несложно понять, что строка имеет вид:1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 0 0 0 0 ... 0 Нули символизируют то, что вероятность того, что сумма цифр пароля длиной в 1 символ не может равнятся 10, 11 и прочим.Теперь подумаем как же нам заполнить все последующие строки.Пойдем слева-направо, сверху вниз по ячейкам таблицы. Пусть нам нужно заполнить ячейку chance[a,b]. Подразумевается, что все строчки с номерами меньшими a мы уже заполнили. Строим формулу chance[a,b] = (1/9)*(chance[a-1,b-1]) + (1/9)*(chance[a-1,b-2]) + ... + (1/9)*(chance[a-1,b-9]). Она значит следующее:мы пытаемся определить вероятность того, что пароль длины a имеет сумму b. С вероятностью 1/9 первая цифра этого пароля 1, тогда для оставшегося пароля (длиной a-1) сумма должна быть равна b-1. Второе слагаемое - с вероятностью (1/9) первая цифра будет 2, тогда оставшийся пароль должен давать в сумме b-2. И так далее для 9 слагаемых.

Пример реализации на C#.

class Program
    {
        private static readonly double[,] data = new double[301, 2701];

        private const int K = 18;
        private const int Q = 50;

        private const int T = 9;

        private static double GetData(int i, int j)
        {
            return ((i <= 0) || (j <= 0)) ? 0 : data[i, j];
        }

        static void Main(string[] args)
        {
            StartFill();
            ProgressFill();
            Output(K, Q);
        }

        private static void Output(int k, int q)
        {
            Console.WriteLine("{0:0.00000000}", GetData(k, q));
        }

        private static void ProgressFill()
        {
            for (var i = 2; i < 301; i++)
                for (var j = i; j < T * 300; j++)
                {
                    var chance = 0.0;
                    for (var k = 1; k < T + 1; k++)
                        chance += (1.0 / T) * GetData(i - 1, j - k);
                    data[i, j] = chance;
                }
        }

        private static void StartFill()
        {
            for (var i = 1; i < T + 1; i++)
            {
                data[1, i] = 1.0 / T;
            }
        }
    }

Задача 4 - Строки Фибоначчи

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

Авторское решение работало следующим образом:

Рассчитаем длины строк до N включительно.  Далее последовательно будем определять по номеру символа в  строке К и длине строк Ln-1 и Ln-2 номер в предыдущей строки(n-1 или n-2) и номер символа в этой строке. Если K > Ln-2, то понятно, что искомая буква находится в n-1-м слове и является в нем K-Ln-1-м символом. Иначе символ находится в n-2-м слове и является там K-м символом.  Будем повторять эти действия пока не дойдем до начальных строк(к примеру, в этой задачи до “a” или “b”). Чтобы данный алгоритм работал с большими числами необходимо реализовать длинную арифметику.

Реализация алгоритма на языке С:

while (n > 1) // нумерация началась с 0
    {
        if (max_of_two(&Num[n - 2], &K) == 1) n -= 2; // изменяем текущий номер на n-2
//max_of_two – ф-я сравнивающая два числа, возвращающая 1, если K > Ln-2 иначе 0
    else
        {
            sub(&K, &Num[n - 2]);// вычитаем из K Ln-2
            n -= 1;//изменяем номер текущей строки на n-1
        }
    }

 

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика