Теория игр и системы рекомендаций: участники о задачах на VK Cup 23
Финалисты чемпионата по программированию от VK рассказывают, как решали задачи от «Почты», «Дзена» и «ВКонтакте».
Финалисты чемпионата по программированию от VK рассказывают, как решали задачи от «Почты», «Дзена» и «ВКонтакте».
Вторая задача — более интересная и трудная. Нужно было прочитать файлы с большим количеством чисел и отсортировать, либо оставить только уникальные значения. Это задача на правильную работу с памятью и машинными ресурсами.
Чисто алгоритмическая задача, нужно уметь разве, что с файлами работать.
Если уникальных чисел мало можно использовать counting sort для сортировки, да и для уникальных значений годится.
Если уникальных значений много или точно неизвестно: сортировка с помощью external sort на основе merge sort, для уникальных значений - ещё раз пробежаться по отсортированному файлу.
Можно ускорить сортировку если реализовать n way слияние на основе priority queue, а priority queue реализовать с помощью heap.
Ещё внешнюю сортировку с помощью bucket sort можно реализовать, но тут надо иметь преставление о распределении данных. Распределение можно оценить если к примеру прочитать тысячу чисел из рандомных мест файла.
Насколько помню, основная сложность задачи была в том, что оперативной памяти на машине не хватало для того, чтобы полностью прочитать файлы размером в несколько ГБ, и нужно было это учитывать при планировании вычислений.