Недавно был проведён первый отборочный тур Олимпиады Университета Иннополис.

К сожалению, я не смог решить D и E на полный балл, а разборы авторов меня не удовлетворили из-за отсутствия доказательств корректности. По этому, прошу всех тех, кто сдал эти задачи и при этом понимает, почему то, что он отправил работает, отозваться на мольбы и написать разбор с доказательством.

Условия

Если же вы раньше не видели эти задачи, но интересно попробовать их решить, возможно вам помогут следующие материалы:

Разбор на D, которые оставили автора:

"Выгодно брать только v, 0, s mod v. O(n^2)"

Я понимаю, как это написать, но не понимаю, почему это правильно.

На задачу Е создатели решили разбор не оставлять (то есть я даже не представляю как она делается).

Возможно, помогут авторские исходники:

Код авторского решения на D

Код авторского решения на E

Решение на С++: 46178226

Решение на С++: 46178084

Решение на С++: 46178118

Решение на С++: 46178228

Решение на С++: 46178239

Решение на С++: 46178244

I got two solutions for http://codeforces.com/contest/1036/problem/F

First one: 42893786 Second one: 42893945

First solution gets MLE, though it differs from second one only in line 81. On this line in first approach I try to use precalculated values from the array, instead of calculating them anew.

Can someone explain how a person can get MLE because of trying to get a value from an array?

I tried to test perfomance of different approaches to build and use trie data structure.

I used 706D - Vasiliy's Multiset to test my versions of tries on it.

The question is: Why does approach with pointers takes 2 times more memory than one with static array? As I know, a pointer stores an address of a variable, so it shouldn't take that much memory.

Here are my submissions:

Pointer approach: 40063381

Static array approach: 40063561

Any suggestions are welcomed!

Доброго времени суток!

Недавно я решал задачи с ХХХ Всероссийской олимпиады школьников по информатике. Меня весьма поразило авторское решение задачи 6 (подобный метод я не встречал нигде).

Может ли кто-либо объяснить мне почему авторское решение на 100 баллов корректно? А именно, почему метод построения обратной перестановки и решение задачи "наоборот" работает? Связано ли это с какими-то особыми свойствами обратной перестановки? Могу ли я подобный метод использовать для любых задач на перестановки (строить обратную данной и решать задачу с конца, заменив все действия обратными им)?

Условие задачи: http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf

Разбор: http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-analysis.pdf