Недавно был проведён первый отборочный тур Олимпиады Университета Иннополис.
К сожалению, я не смог решить D и E на полный балл, а разборы авторов меня не удовлетворили из-за отсутствия доказательств корректности. По этому, прошу всех тех, кто сдал эти задачи и при этом понимает, почему то, что он отправил работает, отозваться на мольбы и написать разбор с доказательством.
Если же вы раньше не видели эти задачи, но интересно попробовать их решить, возможно вам помогут следующие материалы:
Разбор на D, которые оставили автора:
"Выгодно брать только v, 0, s mod v. O(n^2)"
Я понимаю, как это написать, но не понимаю, почему это правильно.
На задачу Е создатели решили разбор не оставлять (то есть я даже не представляю как она делается).
Возможно, помогут авторские исходники:
Научимся решать, для начала, случай x = 2.
Тогда при n ≤ k, если запустить наивное решение, которое перебирает пару чисел и бежит по битам, то оно будет работать за
, что при n ≤ k есть 
.
В противном случае, давайте рассмотрим
, по всем k, что 2k входит в двоичную запись ксора.
Тогда
это 
по всем упорядоченным парам степеней двоек x, y что и 2x, и 2y входит в ксор.
Тогда давайте зафиксируем упорядоченную пару x, y и посчитаем, сколько пар чисел содержит в ксоре обе эти степени двойки. Для этого можно для фиксированных значений этих бит в числе, посчитать сколько есть чисел с такими значениями. А затем перемножить количества, где не совпадают значения по обоим битам.
Это будет работать за O(nk2), что при n > k есть
.
Таким образом, случай x = 2 мы научились решать за
.
При n ≤ k можно воспользоваться битовым сжатием, написав свой битсет, если сохранить для каждого элемента в массиве, значение в битсете (можете посмотреть на это в авторском решении).
При n > k также можно воспользоваться битовым сжатием, если сохранить для каждого бита и значения, в битсете множество индексов чисел, с таким значением этого бита (на это также можно посмотреть в авторском решении).
Таким образом, x = 2 мы научились решать за
.
При x = 3 решить за
не получится, но можно решить за 
, перебрав три бита, и сделав все аналогично. Тогда если запускать первое решение при n ≤ k2, а второе при n > k2, решение будет работать за 
.
Итого, получается решение за
.
TL; DR Top 10 optimizations 2017 — (collectors edition)
Спасибо большое за развёрнутый разбор задачи Е. Я всё понял.
Может быть, вы могли бы мне и D рассказать? :)
А где вы нашли разбор?
Он автор (если вы конечно говорили про Ильдара))
Если нет, то на сайте: https://olymp.innopolis.ru/ooui/informatics/archive/ . Решение лежит в Documents
я тоже заинтересован ,интересно узнать как решается задача D .
Далее диалог 2 людей по поводу доказательства задачи Д:
В: Предположим, что существуют два элемента не ноль и не v
В: Если они не соседние, очевидно один из них можно догнать до v, а другой уменьшить
В: иначе пусть наши неравные нулю и v соседние элементы — это x и y
В: Слева от x — a, справа от y — z, b — t
В: тогда у нас последовательность a, x, y, b
В: коэф между a и x — w, x и y — z, y и b — t
В: И нам нужно минимизировать функцию
awx + xyz + b
причем x + y = p
y = p — x
Д:
[Ответ на сообщение]
В:
причем x + y = p
Что такое p?
В: да, не уточнил
В: Мы пытаемся найти противоречие
В: В чем может быть противоречие?
Д: Существует меньшее значение?
В: Да
В: при такой же сумме всех элементов
Для упрощения мы будем менять только x и y
нам хватит
так вот
итого нам нужен минимум
awx + (p — x)xz + bt(p — x)
-z * x^2 + x * (wx + pz — bt) + btp
Д: Ага
Но это парабола, ветви вниз, не ограничена снизу
А нам нужен минимум
Минимум тогда на границах области определения
Вы немного ошиблись, это не разбор задач, это служебные файлики, которые мы использовали при подготовке и не удалили, когда выкладывали архив. Рады, что они вам помогли решить задачу.
Кстати, контест в тренировках: Отборочный этап Олимпиады Университета Иннополис. Первый тур. 2018-2019
Ну.. У меня получилось решить Д, но у меня нет 100% доказательств.. Для меня просто стало очевидно, что когда мы заполняем печи, мы должны заполнять их полностью т.е. если мы где то в 2 местах заполним печи не полностью, то почему бы нам просто не перенести скажем из той, где хуже влияет на результат, в то место, где лучше.. т.е. будем заполнять полностью. Теперь сделаем динамику с 2 сторон где мы будем заполнять печи только полностью. Осталось перебрать только остаток (s%v) т.е. возможное его расположение и для каждого за О(1) будем смотреть что получится, минимизируя ответ. Если есть логические ошибки в моем доказ-ве или просто что то не понятно, то напишите =) Я просто сам не уверен, что это так то норм доказ-во.