Может быть я очень невнимательный, но пока что никто не создал блог для обсуждения регионального этапа 2020. А тем временем, если я правильно понимаю, первый тур прошел уже во всех регионах, так что задачи уже можно спокойно обсуждать (поправьте, если я неправ).
Предлагаю обсуждать здесь региональный этап, задачи, баллы, условия проведения в этом году в регионах и т.п.
UPD1: Результаты первого дня регионов, писавших на:
Яндекс.Контесте: результаты Я.К
Codeforces: результаты Сodeforces (Спасибо MikeMirzayanov)
Санкт-Петербурга: результаты СПб
Татарстана: результаты РТ (Спасибо ismagilov.code и kuzma)
Челябинска: результаты Челябинск (Спасибо kuzma)
UPD2: Второй тур уже почти закончился. Думаю, через 30-40 минут уже можно будет спокойно обсуждать задачи (если это не так, поправьте пожалуйста). Надеюсь, все (более-менее) довольны (более-менее) своими результатами).
UPD3: Результаты второго (и первого, местами) дня регионов, писавших на:
Яндекс.Контесте: результаты Я.К
Codeforces: результаты Сodeforces (Спасибо MikeMirzayanov)
Татарстана: результаты РТ (Спасибо psevdoinsaf)
Санкт-Петербурга: результаты СПб (Спасибо Hello_zoka)
Карелии: результаты Карелия (Спасибо ismagilov.code)
Дальнего Востока: Результаты ДВ (Спасибо ZloyNegr)
Москвы: Результаты Мск (Спасибо k291061)
Решение D:
Заметим, что если мы увеличиваем $$$z[i]$$$ на 1 (и при этом $$$z[i]$$$ < $$$m$$$), то количество строк со значением 1 или не меняется, или увеличивается на 1(так как все элементы во всех столбцах различны).
Из этого следует, что существует ответ такого вида: $$$[m, m, ...., m, x, 0, ...,0]$$$.
Теперь чтобы найти такой ответ, достаточно бинарного поиска по длине префикса $$$m$$$, а затем бинарного поиска по $$$x$$$.
Асимптотика $$$O(nm * (log(m) + log(n)))$$$
А можешь пожалуйста подробнее объяснить этот момент: "Из этого следует, что существует ответ такого вида: [m,m,....,m,x,0,...,0]?"
просит не совсем понимаю, как именно это вытекает.
Такой алгоритм: будем перебирать $$$i$$$ от $$$0$$$ до $$$n - 1$$$. Теперь увеличиваем $$$z[i]$$$ от $$$0$$$ до $$$m$$$. Понятно, что в какой-то момент у нас будет ровно $$$s$$$ единиц в значении строк и при этом наш массив всегда в процессе работы алгоритма имеет такой вид.
Это решение можно оптимизировать до $$$O$$$($$$nm$$$). Типо просто перебрать все ответы и пересчитывать за $$$O$$$($$$1$$$)
Простите, я слеповат. Это уже написали снизу)
Решение C:
Сначала для каждого элемента предпочитаем индекс первого элемента справа равного ему. Это можно делать например с помощью unordered_map.
Теперь для каждого элемента будем искать в скольких отрезках длины $$$1$$$, $$$2$$$, $$$3$$$.. он будет самым правым из чисел равных ему на отрезке. Очевидно, что если мы такое посчитаем для каждого элемента и каждой длины то мы получим ответ на задачу.
Рассмотрим пример
У нас массив {$$$2$$$, $$$3$$$, $$$1$$$, $$$4$$$, $$$6$$$, $$$4$$$, $$$3$$$, $$$3$$$, $$$1$$$, $$$57$$$} и мы рассматриваем первую единицу. Для каждой длины посчитаем в скольких отрезков этой длины содержится наше число
Колво: $$$1$$$ $$$2$$$ $$$3$$$ $$$3$$$ $$$3$$$ $$$3$$$ $$$2$$$ $$$1$$$ $$$0$$$ $$$0$$$
Длина: $$$1$$$ $$$2$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6$$$ $$$7$$$ $$$8$$$ $$$9$$$ $$$10$$$
Легко заметить что верхний массив для любого элемента и массива будет иметь вид {$$$1$$$ $$$2$$$ $$$3$$$ .... $$$x$$$ — $$$1$$$ $$$x$$$ $$$x$$$ $$$x$$$ ... $$$x$$$ $$$x$$$ $$$x$$$ — $$$1$$$ ... $$$3$$$ $$$2$$$ $$$1$$$} Это очевидным образом представляется в виде сумм и разностей арифметических прогрессий. Значит мы свели задачу к прибавлению арифметической прогрессии на отрезке. Эта задача может быть решена за линейное время.
Итоговая асимптотика: $$$O$$$($$$n$$$)
Может быть не очень читаемо(мой первый разбор)
Может быть не очень читаемоЯ всегда не очень хорошо понимаю другие разборы, так что у меня появились некоторые вопросы к твоему решению)) :
1) Как быстро посчитать массив
{1 2 3 .... x — 1 x x x ... x x x — 1 ... 3 2 1}для всех чисел в массиве, или представить их в виде арифметических прогрессий?2) Как это переходит в наш ответ, то есть как мы из наших прогрессий получим ответ?)
2) Ну просто сумма вроде, мы же считаем
в скольких отрезках длины 1, 2, 3.. он будет самым правым из чисел равных ему на отрезкеДругое (моё) решение C:
Давайте пойдем справа налево и будем поддерживать для каждого числа массива $$$1$$$ если число встречается впервые на данном суффиксе и $$$0$$$ иначе. Давайте посмотрим что у нас получится, если для всех суффиксов мы выпишем полученные последовательности $$$0$$$ и $$$1$$$ в таблицу. Например рассмотрим сэмпл (массив $$$1\,3\,2\,1\,2$$$):
Давайте заметим что $$$S_d$$$ это сумма на каком-то параллелограмме таблицы (мда). Для ясности, вот $$$S_3$$$ для нашего примера:
Ну, давайте посмотрим, как пересчитывается $$$S_{d+1}$$$ через $$$S_d$$$. Мы вычитаем верхнюю строку и добавляем справа диагональ. То есть примерно вот так (зеленое — удаляем, синее — добавляем):
Теперь, что нам надо сделать? Давайте посчитаем для каждого элемента, для каких длин $$$d$$$ он вносит вклад. Заметим, что элемент $$$i$$$ вносит вклад в длины не более $$$i$$$.
Кроме того, давайте посчитаем когда для этого элемента $$$1$$$ заменяется на $$$0$$$ (до этого момента во всех строках, в которые этот элемент входил, будет стоять $$$1$$$, а после — всегда $$$0$$$). Пусть это $$$when_i$$$ для $$$i$$$-ого элемента. Если же элемент до конца прохода будет первым на суффиксе среди равных ему, положим $$$when_i = -1$$$ (по сути это индекс ближайшего элемента равного ему, но стоящего левее). Тогда несложно заметить, что этот элемент вносит вклад во все длины не более $$$n - when_i$$$.
То есть нам нужно добавить, что элемент вносит вклад (увеличивает на 1) все длины от $$$1$$$ до $$$min(i, n - when_i)$$$, добавляясь как элемент на правой диагонали, прибавив $$$1$$$ на соответствующем отрезке. Это делается за линию префиксными суммами.
Теперь мы посчитали, по сути, для каждой длины сумму на последней диагонали. Теперь чтобы посчитать ответ для $$$S_d$$$, нужно в полученном массиве добавить к $$$d$$$-ому элементу $$$S_{d-1}$$$ и вычесть сумму на суффиксе длины $$$d$$$ (та самая верхняя строка). Первое мы уже посчитали, второе легко считается при проходе справа налево.
Снова другое решение на C (чем-то схожее с решением devid, если я случайно пересказал его, поправьте пж):
Заметим что все отрезки длины d состоят из какого-то отрезка d — 1 (в данном решении будет рассматривать, что это суффикc) и одного элемента слева.
Давайте подумаем как можно пересчитывать S(d) через S(d — 1):
По факту нам нужно просто не учитывать те элементы, которые уже были в d — 1, когды мы их добавили
Для этого давайте обозначим за next(i) = ближайщий справа элемент, равный a[i];
А pref(i) = количество различных на префиксе длины i;
Теперь S(d) = S(d — 1) — pref(d — 1) + кол-во элементов массива next от 0 до n — d — 1, больших d; pref(d — 1) мы вычитаем для того, чтобы не учитывать отрезок длины d — 1, являющий префиксом исходного массива(очевидно, что слева мы не можем добавить элементы). Считать мы его можем за n log n просто проходом сетом.
Как быстро считать третье слагаемое? Здесь я писал дд, мб можно что-то другое.
Давайте изначально добавим в дд все элементы массива next от 0 до n — 2.
Теперь будем искать кол-во элементов, больших 1 (можно просто сплитом);
После этого удаляем элемент на позиции n — 2;
Теперь ищем кол-во элементов, больших 2... Думаю алгоритм понятен.
Все значения записываем в массив. И теперь мы можем спокойно найти S(d) через S(d — 1)
S(0) = n, как база;
В этом году на Codeforces пишут 17 регионов. Вот результаты после первого тура: https://mirror.codeforces.com/spectator/ranklist/bbd85b80155bc7d5df6e5681729d7f27
Я пока не понял подробности, но меня попросили официально временно не публиковать эту ссылку. Извините, ссылка более недоступна.
Пожалуй добавлю парочку
Татарстан:
https://pcms.university.innopolis.ru/results/region/2020/regional-day1-20200116-sdffasklfuehf.html
СПБ:
http://neerc.ifmo.ru/school/spb/standings-2020-day1.html
Те, кто писал на яндексе:
https://contest.yandex.ru/news/?postId=911
http://neerc.ifmo.ru/school/spb/standings-spb-2020.html СПБ, 1+2 тур
Хабаровский край (классы: 11, 10) https://imcs.dvfu.ru/cats/main.pl?f=rank_table;cid=3033335;sid=;sites=1178986
Приморский край (классы:10, 11, 9, 10) https://imcs.dvfu.ru/cats/main.pl?f=rank_table;cid=3033335;sid=;sites=1175454
Камчатский край https://imcs.dvfu.ru/cats/main.pl?f=rank_table;cid=3033335;sid=;sites=1217892
Суммарная таблица по всем трём регионам за оба тура (11, 10, 9, 11, ?): https://imcs.dvfu.ru/cats/main.pl?f=rank_table;cache=1;clist=3033335,3033343;hide_ooc=1;hide_virtual=1;sid=
Элегантное (имхо) решение на С.
Пусть изначально все $$$S[i] = 0$$$, теперь найдём вклад каждого индекса в ответ.
Я утверждаю, что элемент $$$a[i]$$$ даёт вклад во все отрезки, в которых $$$i$$$ является первым вхождением этого элемента (иначе, впервые "открывает" этот элемент другой индекс, вклад принадлежит именно ему). Как это формализовать: все отрезки $$$[l, r]$$$, при $$$prev[a[i]] < l <= i$$$ и $$$i <= r < n$$$, нумерация с 0, $$$prev[x]$$$ — индекс предыдущего вхождения типа задания $$$x$$$.
Теперь понятно, как это делать за $$$O(n^3 log n)$$$, можно от лога избавиться если сжать координаты (отпадает необходимость в map).
Как это делать за квадрат? Давайте разберёмся, что же происходит. Мы итерируемся по $$$l$$$ от $$$prev[a[i]] + 1$$$ до $$$i$$$, включительно. На каждой итерации мы рассматриваем отрезки с правыми концами от $$$i$$$ до $$$n - 1$$$, крайние длины соответственно будут $$$i - l + 1$$$ и $$$n - i$$$. Это по сути, прибавление 1 на отрезке. Так как сначала идут все запросы, а потом нужно вывести значение, можно сделать прибавление за $$$O(1)$$$ — просто завести массив флажков $$$flag$$$, классический приём, кто не в курсе. Тогда для прибавления единицы на отрезке $$$[l, r]$$$, мы просто делаем
flag[l]++иflag[r + 1]--, потом уже проходимся по массиву, обновляем текущее значение на значение флажка в данном индексе, и это значение выходного массива $$$S$$$ в данном индексе.До фулла отсюда недалеко. Заметим, что все увеличения флажков на 1 (при каком-то $$$i$$$) находятся в подряд идущих индексах (очевидно, так как мы итерируем $$$l$$$ по одному). А поэтому, можно взять самые кратчайшие длины для левейшего и правейшего $$$l$$$, а также соответственные максимальные длины. Для первых мы делаем запрос на увеличение 1 на отрезке массива флажков (это важно, не конечного массива!!), аналогично с последними, только увеличение на -1. После этого мы восстанавливаем значения флажков, и уже с их помощью достраиваем массив.
в D есть решение за O(nm), по каждой строке можно построить дерево где val[2n-1] корень,а x[i]ые — листья. Отсортируем подсчётом столбцы, пусть изначально все z[i] = 0, будем увеличивать z[0] на 1 пока z[0] < m, z[1] и тд когда z[i] увеличится на 1 лист в некотором дереве станет 1(до этого он был 0), пойдём по дереву от листа изменяя значения в вершинах до первой 1 или до первой вершины с op = and у которого другой потомок равен 0, если мы дошли до корня значить количество True увеличилось на 1. Будем делать так пока кол-во true не станет равно s. В итоге по каждому ребру дерева будет не > 1 прохода, Увеличений z[i] будет не > mn.
Мне за последние 30 минут стало немного страшно за завтра. Это было запланировано?
upd. в случае падения тестирующей системы, продлят ли нам тур на время крэша? если нет, что будут делать в такой ситуации?
upd2. Прошу прощения за панику, тур прошёл великолепно :)
Не понял объясни)
Сайт по программированию под названием Codeforces прилег поспать примерно на полчаса.
А ты на кф писал? Если да расскажи как прошло)
Первый день очень круто прошел, очередей вообще не было. Посылки тестировались не больше минуты.
Круто! Рад что теперь можно нормально писать) Бтв на ejudge все тоже было прекрасно.
Можете пожалуйста объяснить решение задачи B на полный балл
По условию задачи, штраф выдают за максимальное превышение скорости на всей дороге. Отметим, что там также указано, что это превышение должно быть гарантированным, то есть мы не имеем права выписать штраф за превышение на $$$x$$$ м/с, если существует план поездки, где максимальное превышение меньше (иными словами, данные о въезде и выезде не дают нам право утверждать, что водитель гарантированно хотя бы в один момент превысил скорость на такую величину).
Окей, разобрались с формулировкой. Теперь поймем следующий полу-очевидный факт: в лучшем случае автомобилист двигался с одинаковым превышением по всей дороге. И только за это превышение мы сможем выписать штраф.
Нет смысла рассматривать планы поездки с неравномерным превышением, т.к. водитель мог сделать лучше, превышая меньше на участках с большим превышением и больше — на участках с меньшим. Таким образом, максимальное превышение в данных планах не является гарантированным.
Тогда понятно, что мы ищем некоторую величину, на которую превысил скорость в лучшем случае водитель во время поездки. О ней мы только знаем следующее: двигаясь с таким превышением, путь водителя займет в точности $$$t - s$$$ секунд.
С более высоким превышением водитель потратил бы меньшее время на путь, а с менее высоким — большее.
Таким образом, функция $$$T(up)$$$, где $$$up$$$ — это превышение, а $$$T(up)$$$ — время, затраченное на поездку, монотонно убывает. Это значит, что мы может найти требуемое $$$up' : T(up') = t - s$$$ с помощью двоичного поиска. На каждом раунде поиска мы можем честно посчитать, за сколько проедет водитель каждый участок дороги и просуммировать результаты.
Итак, получили $$$up'$$$. Еще одним бин. поиском по массивам $$$a$$$ и $$$f$$$ найдем, какой штраф за это придется выписать нарушителю (ведь превышения там отсортированы заранее по возрастанию).
UPD: снизу отметили, что можно сразу производить бинпоиск по позиции превышения в списке штрафов. Так код будет действительно выглядеть лаконичнее :)
Итоговая асимптотика: $$$O(q \cdot n \cdot \log m + m)$$$.
Второй бинпоиск не нужен же, и так нашли позицию превышения i, тогда f[i] — штраф
Согласен, абсолютно справедливо.
А можешь пояснить откуда появилось +m в асимптотике? (решение, кста, классное)
Как минимум надо считать 2*m-1 число)
Ребят, 2 года назад на всерос брали примерно: 120 из 11, 80 из 10 и 60 из 9
1 год назад примерно всех по 80,с чем это связано?
хм, взяли вроде 96 из 11 класса...
Такое ощущение, что в этому году 10 классу может не хватить и 650 баллов для отбора
Откуда такие догадки ?
D-шка, решившаяся примитивной динамикой на 53 балла, натолкнула на эту мысль. И действительно, 100-е место в мск — 630 баллов. 650 баллов, похоже хватит, но запас совсем крохотный.
Решения второго дня:
Очевидное свойство ответа: $$$\sum_{i=0}^{i = j}cnt[i] * a[i] < a[i + 1]$$$ для любого $$$i$$$.
Теперь время кукарека: мы можем просто идти с начала и брать $$$i$$$ купюру пока все свойство выполняется. Понятно, что мы можем проверять только одно из $$$n$$$ неравенств. Также надо в каждый момент времени проверять что $$$currentsum <= b$$$
Это решение за $$$O(n * q)$$$.
Как ускорить: заметим, что у нас для какого-либо префикса купюр взято максимальное количество каждой купюры, которое удовлетворяет свойству. Следующей после этого префикса купюры у нас взято максимальное число которое удовлетворяет $$$currentsum <= b$$$. Теперь мы можем для каждого префикса насчитать сумму и количество взятых купюр(в предположении $$$b = \infty$$$), а затем сделать бинпоиск.
Теперь решение работает за $$$O(n + q * log(n))$$$
Идея от fedoseev.timofey: у нас будет не более $$$log(maxval)$$$ значений сумм купюр для всех префиксов, поэтому решение можно написать за $$$O(n + q * log(log(maxval))$$$.
Будем писать ДО.
Для объединения двух отрезков достаточно хранить для каждого отрезка:
1) $$$ans[4][4]$$$, где $$$ans[i][j]$$$ это максимальная сумма если мы взяли префикс длины $$$i$$$ и суффикс длины $$$j$$$
2) $$$pref[4]$$$, где $$$pref[i]$$$ это сумма первых $$$i$$$ элементов на префиксе отрезка
3) $$$suff[4]$$$ — аналогично $$$pref$$$
Зная это мы можем объединять два отрезка за $$$O(4 ^ 4)$$$. Таким образом решение будет работать за $$$O(q * log(n) * 4 ^ 4 + n * log(n))$$$
Я писал в D корневую, не успел отдебагать :( Потом услышал, что она ни у кого не заходила. Получилось ли у кого-то все же запихнуть?
Да, насколько я знаю devid все-таки сдал(если это не так, поправьте пожалуйста).
Сдал). Если интересно — разбор ниже.
У меня корневая с первого раза зашла. Сливал за $$$O(4^3)$$$.
Ты очень крутой, мы все тобой гордимся.
А я сливал последние 2 часа, потому что руки из одного места
А как сливать за куб? Расскажи pls.
В разборе комментом ниже есть)
Ааа, спасибо)
Перебираем количество плакатов в начале первого блока, в конце первого $$$a$$$ и в конце второго, если хранить в блоке $$$dp[i][j]$$$ — ответ, если мы берем в начале не более $$$i$$$ и в конце ровно $$$j$$$, то нам не нужно перебирать количество в начале второго, а оно просто равно $$$4 - a$$$.
Мои решения, насколько я понимаю, отличающиеся от авторских(?):
Давайте заметим, что зная $$$a, b, c, n$$$ можно легко восстановить $$$d = \frac{ab-n}{c}$$$. Теперь заметим что $$$n>=a+b-1$$$, отсюда $$$a \leqslant n$$$ и $$$b \leqslant n$$$. Давайте переберем $$$a, b$$$ в $$$[1..n]$$$ и $$$c$$$ в $$$[1..a)$$$. Это решение за $$$\mathcal{O}(n^3)$$$.
Теперь заметим что $$$d=\frac{ab-n}{c}<b$$$. отсюда следует что $$$c>\frac{ab-n}{b}$$$. Теперь будем перебирать не от $$$1$$$, а от этого значения. При равном $$$a$$$ мы перебираем $$$b\in [1..n]$$$ и $$$c$$$ мы перебираем за $$$a-\frac{ab-n}{b}=a-(a-\frac{n}{b})=\frac{n}{b}$$$, что суммарно $$$\mathcal{O}(n^2 \ln{n})$$$
Давайте разомкнем цепь в начале побьем массив на корень блоков, в каждом по корню элементов. В каждом блоке посчитаем динамику $$$dp[x][y]$$$ — если в данном блоке возьмем $$$x$$$ элементов в начале и $$$y$$$ — в конце. Понятно, как ее посчитать. Теперь давайте заметим, что мы можем за $$$4^4$$$ слить ответы для двух отрезков.
Давайте теперь втупую при каждом запросе менять элемент в блоке, пересчитывать в блоке динамику и заново сливать ответ для всех блоков.
Проблема — это работает слишком медленно. Давайте для начала соптимизируем сливание отрезков. Для этого пусть теперь $$$dp[x][y]$$$ — если мы оставим не более $$$x$$$ в начале и $$$y$$$ в конце. Теперь нам ненужно перебирать одну из размерностей при сливании. Круто.
Но это все еще не заходит. Заметим, что из всего решения, только сливание имеет множитель $$$4^3$$$. Давайте соптимизируем количество сливаний. Для этого на массиве блоков напишем... корневую? Да! (мда). То есть побьем наш массив матриц $$$4 \times 4$$$ соответствующих блокам на $$$\sqrt{\sqrt{n}}=\sqrt[4]{n}$$$ блоков. Теперь мы легко можем пересчитать динамику, пересчитать ответ в блоке блоков и посчитать ответ по корневой написанной на корневой.
С несколькими всеми любимыми оптимизациями (как же я люблю оптимизации, вот они, слева направо: pragma GCC optimize, bump аллокатор, подбор констант, глобальные массивы, передача аргументов по ссылке — ♥♥♥), это
легкозаходит в ТЛ.Предварительные результаты:
А в Кемеровской области произошёл мем. Пошёл сильный снегопад и гибдд не разрешил детям ехать на автобусе в город, чтобы писать второй этап (дети для подготовки собираются в лагере за неделю до олимпиады). В итоге область пишет олимпиаду в понедельник с другими заданиями. Явно будут другие баллы, никаких равных условий. Дети будут сидеть в лагере еще два дня, откуда им взять еду и места жития, там же новые подъедут
Кто может объединить все результаты в одну табличку?
Пока всех нет — никто, но вчера вроде где-то объединяли все известные в табличку (по первому дню).
На московском сайте материалы выставили: https://olympiads.ru/moscow/2019-20/vsosh/region_start.shtml
Сюда свел оба дня многих регионов
https://docs.google.com/spreadsheets/d/1QrJ7RYvNthgGsyq1nE0DSziU402mloF6zusSIse1ypQ/edit#gid=574526530
Москвы естественно нет
Добавил еще несколько регионов, на данный момент находится здесь 3426 участников
https://docs.google.com/spreadsheets/d/1OEhriHiyopuMyuRjc8yIQ1f3ThStXEgggbAAZdfR8LU/edit?usp=sharing
UPD. Добавил Москву — итого 4236 участников
Будет совсем отлично, если еще колонку региона добавите
и класса плез)
Кто знает, когда будет дорешка?
Можно тут (Турнир "Краевая олимпиада 2020 (Дорешивание)"): https://imcs.dvfu.ru/cats/main.pl?f=contests;cid=500001;sid=
Такой подход позволит узнать ответ не только для $$$n$$$, но и для всех чисел до него. Далее в решении будет предполагаться, что полигон находится в нижнем левом углу участка.
Воспользуемся приемом динамического программирования. Пусть $$$dp[k][s]$$$ — это количество способов получить $$$k$$$ пустых клеток, если ширина участка зафиксирована и равна $$$s$$$.
Пересчёт. Заметим, что мы можем взять каждый способ получить $$$k - s$$$ пустых клеток и добавить вверх один пустой ряд. Значит, прибавим эту величину: $$$dp[k][s] += dp[k - s][s]$$$. Но мы не учли вариант, когда сверху находится всего лишь один пустой ряд.
Такая конфигурация не может получиться с помощью добавления одного пустого ряда вверх к корректному варианту из $$$k - s$$$ пустых клеток (т.к. в нем было бы сверху 0 пустых рядов, а это значит, что сторона участка равна стороне полигона, а это противоречит требованию из условия).
Таким образом, осталось разобрать только этот случай. Представим, что мы рассматриваем участок с одним пустым рядом сверху. Очевидно, что есть убрать этот ряд, то у нас получится прямоугольник, где левая часть занята полигоном, а правая — пустая и имеет площадь $$$k - s$$$, и каждой ширине правой части соответствует ровно один валидный набор данных (т.е. способ). Тогда количество таких способов в точности равно количеству делителей $$$k - s$$$, меньших $$$s$$$ — это будет как раз ширина правой части.
Финальное замечание: $$$k$$$ и, следовательно, $$$k - s$$$ при пересчете не превысит максимальное $$$n = 3000$$$, поэтому мы можем заранее любым способом получить делители чисел до $$$3000$$$, чтобы ими можно было воспользоваться в динамике. Итоговая асимптотика: $$$O(n \cdot n \log n)$$$, где $$$O(n \log n)$$$ — это сумма количества делителей всех натуральных чисел до $$$n$$$.
Для фиксированного $$$a < n$$$ на него делятся $$$\frac{n}{a}$$$ чисел до $$$n$$$. В итоге получается частичная сумма гармонического ряда до $$$n$$$, умноженная на $$$n$$$, а эта величина известна и имеет порядок $$$O(n \log n)$$$.
Непосредственно ответ получить легко: необходимо просуммировать все $$$dp[n][i]$$$ для $$$1 \le i \le n$$$. В подзадачах с дополнительным ограничением $$$x$$$ на длину стороны можно любым способом посчитать количество плохих вариантов и вычесть его из данной величины.
UPD: кстати, такое решение может работать и за $$$O(n^2)$$$, если заранее посчитать до максимального $$$n$$$, $$$cnt[i][j]$$$ — количество делителей $$$i$$$, меньших $$$j$$$. Тогда можно совершать переходы в основной динамике за $$$O(1)$$$.
Результаты Ижевска: https://bacs.cs.istu.ru/
Как думаете какой проходной балл у 11 класса в этом году?
644
Даже не мечтай! Всерос нас ждет!
Судя по резам мск — больше
Говорят для 11 660
есть основания для этого?
Да, конечно https://docs.google.com/spreadsheets/d/1ZdkXRIFRsVvWMXTMvMV-mrJrB11QxGorkyyXSKXZ5KM/edit#gid=0
А можно в табличке отразить всех участников не до 600+, а до 500+ баллов? Из девятых классов пока здесь попали 44 человека, и скорее всего, это не все, кто пройдет на ЗЭ. Очень интересно, как там дальше все выглядит.
Это точно со всех регионов?
Кто таблицу вбивал? У меня фамилия указана неверно. 187 место. ШаШушинский. Моя фамилия ШаРушинский.
простите ) ( я не знаю кто делал таблицу)
https://olympiads.ru/moscow/2019-20/vsosh/region_results.shtml москва
Результаты ЕКБ: https://docs.google.com/spreadsheets/d/1H21ygJthNHttLz7lKWJLFFmvsjyBXq-poen7mGceudU/edit?usp=sharing
Задачи доступны для дорешивания на Яндекс.Контесте:
Оба тура в Тренировках Codeforces:
UPD: Исправил доступ.
Нет доступа на просмотр соревнования :(
Спасибо, исправил.
А какой проход будет примерно по 9 классу
540-550
Результаты новосибирской области https://drive.google.com/file/d/1SRlD5QcucDz_hQPmm-tkbEV5afForm_6/view?usp=sharing
а я зделал 1 и 5 задачки и куснул 3 на 22 балла
Молодчина!
Официальные и окончательные результаты Челябинска: https://rcokio.ru/files/upload/olimp/vseros/itog_19-20/informatika.xlsx
Уже не знаю, насколько это актуально, но раз в "странных опросах" до сих пор обсуждают асимптотику к B2, представлю решение за $$$O(n \log ^2 n)$$$. Такую асимптотику можно получить несложной оптимизацией вышеописанного решения с ДП (достаточно только заметить, что полезных состояний для вычисления ответа всего $$$n \log n$$$).
Эта реализация позволяет получить ответ для $$$n = 4 \cdot 10^5$$$ за одну секунду:
Результаты в республике Адыгея
Проходные баллы: 9: 543, 10: 607, 11: 644