Блог пользователя Yury_Bandarchuk

Автор Yury_Bandarchuk, 10 лет назад, По-русски

Всем привет!

Совсем скоро, 13-14 января, пройдут основные туры областной олимпиады в Беларуси.

Предлагаю после туров обсуждать задачи и делиться результатами здесь!

GL && HF!

UPD: Ну что, как вам задачки первого тура?

Краткие соображения по решению задач (SPOILER) :

1. Тут все ясно, просто массив на сто элементов.

2. Перебираем R до корня, затем бинарным поиском ищем максимальное C. Не забыть лонги.

3. Два указателя + добавить спереди нулей, чтобы числа были одной длины. Не забыть при выводе убрать лидирующие нули. Не забыть лонги [2].

4. Дп по дереву: dp[ver][0] — максимальный путь до какого-либо из листов + мы не снимали налог ни с одной дороги, за которые отвечает вершина ver. dp[ver][1] — то же самое, только мы уже сняли один налог. Затем просто два максимума по детям dp[ver][1] и dp[ver][0].

Надеюсь это должно работать =)

Условия первого дня здесь.

Второй тур завершен. Мне задачи понравились :)

Опять соображения :

1. Два указателя на концы строк и погнали.

2. Раскладываем на простые множители и каждый множитель доводим до степени, кратной трем. Это и будет ответ.

3. Посчитаем H[i][j] — количество спичек на одинаковых местах у чисел i и j.
Затем посчитаем такую динамику : dp[len][sum][eq], где len — длина префикса, который рассмотрели, sum — сумма спичек, которую набрали, eq — сколько на нормальных местах стоит, что не пришлось менять. Затем ответом будет просто сумма по всем dp[n][mySum][x], где mySum — x <= k. Ограничение по памяти не позволяло считать такую дп, поэтому считаем просто по слоям.

4. Первые 8 тестов — динамика за N^2 * K. Где dp[len][used] — минимальная стоимость, если мы уже набрали used групп, и последняя группа закончилась в позиции len. Предварительно нужно отсортить массив. 9-й тест — просто костыльный, там все тройки в инпуте. А в 10й написал жадность — сделал группы макс размера и следовательно остались ещё группы. Тогда уменьшаю самую большую группу и добавляю новую или добавляю в старую, но меньшего размера. Улучшаем пока улучшается.

Делитесь своими идеями и решениями, а я буду надеяться, что это все зайдет! =)

Кидайте резы по вашим областям мне в лс.

UPD: Есть резы Брестской, г. Минска, Гомельской области и Лицея БГУ и , скидывайте резы свои, жду!

Неполные результаты : Link.

UPD: Добавил Могилевскую область.

  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Всем Удачки ребзя!=)

»
10 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Выложите задачки первого тура, пожалуйста, если он уже закончился.

»
10 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
  1. Если позаниматься математикой, то можно находить maxC(R) за O(1)
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Тэги)

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится -22 Проголосовать: не нравится

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

Обожаю её!

»
10 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

В 4 задаче 2 дня можно проще. Сначала отсортируем работников по возрастанию a[i]. После этого будем пытаться набрать максимум людей в очередной проект(это количество будет равно минимуму из a[i], участвующих в проекте) Далее, до тех пор, пока мы можем это делать, будем находить проект с наибольшим количеством людей (1) и проект с наименьшим(2). После этого отправим одного человека из 1 в 2. Это можно сделать т.к финальное количество людей в 2 не будет превосходить 1. Продолжим делать это до тех пор, пока разница между наибольшим и наименьшим количеством не знанет <=1. Это значит, что мы нашли ответ.

Решение работает примерно за n^2(10 тест считало 30сек) и берет 100 баллов.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Когда будут общие результаты по областям?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У кого какие значения минимальных площадей в 4-ой задаче 2-ого дня получились?

»
10 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Сколько картошечки набрал автор? :)

»
10 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

Почти у всей Брестской области слетела 3 таска первого дня из-за лишнего пробела в конце. У кого-то еще была такая проблема?

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +33 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +30 Проголосовать: не нравится

      Писали аппеляцию по этому поводу ~7 человек. Все были отклонены.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    в минской области та же фигня с тестами.

    у нас допилили тестер, все прошло.

    хотя у Сазановича и так проходило)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Известны ли результаты каких-нибудь областей(отдельно)?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Юра, может скинешь результаты областей по отдельности, а потом, когда будут все, общие?

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Юра, можешь выложить хотя бы то, что есть?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Если можно поправьте в результатах имя 13 места на "Камеко Валерий".