When we log in into the Yandex contest, we get the following message: "You are not allowed to view this contest"
Is anyone else having the same problem?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
When we log in into the Yandex contest, we get the following message: "You are not allowed to view this contest"
Is anyone else having the same problem?
Название |
---|
Same
Login?
saratov24
Fixed
If someone has the .pdf with tasks, please share, so we can at least start solving. Thanks
Login?
zagreb04
Fixed
Same (spbifmo151)
Foxed
Thanks!
Our login is zagreb02
Fixed
Thank you very much dear friend
!!
same (zagreb03)
Fixed
Same (login: belgrade01)
Fixed
Thanks
same(login: zagreb01)
Fixed
When opencup div 2 is going to start?
Fix please: Login: kharkiv03
It seems that there is a bug with automatical (or ever mass) addition for several sectors on the Yandex.Contest. So please write down your logins and they will be added manually
Fix please: zagreb03
spbifmo151
Our login also doesn't work: munich01
fixed
Thanks!
kharkiv03
Fixed
jagiellonian10
Fixed
lviv07
Fixed
kharkiv11
Same(yerevan01)
Fixed
Let's upvote all replies by snarknews
login: kharkiv11
Fixed
Login: nnovg04
How to solve problems 3 and 9?
9: Build a suffix array for $$$s + * + t$$$, then you will decrease $$$k$$$ from $$$min(n, m)$$$ to $$$1$$$. It`s pretty easy to maintain groups of suffixes with a common prefix of length $$$\leq$$$ $$$k_{current}$$$, processing events like "a suffix appears because of its length becomes exactly $$$k_{current}$$$" or "unite two groups into one", and to recalculate answer iteratively after every change of structure
Okay, so you tell me that Russia didn't have timezones change xd? Yeah, I knew that, but it came rather as a surprise to is today xd
I never thought fflush is that slow and inconsistent. We literally TLed problem 8 with c++17 and got like 1100 ms with c++11.
Our solution written on Java works for 4300ms. I thought it would work much faster, but it seems that without buffering input/output any interaction becomes very slow.
BUT they said:
So even if interaction is fast, their interactor may work slower than expected because of changing the array.
There is a very simple randomized solution, which we decided to cut off. Basically, go through the array, while maintaining two minimal elements. When you take a new element, compare it to the second minimum, and if it is less, then compare to the first minimum. With a preliminary random shuffle, the second comparison is needed in only about $$$\ln N$$$ cases on average. In order to cut it off, we set very strict query limit $$$N + 20$$$. However, the solution can check how many queries it has made and simply return the current answer if queries are depleted. The probability that those few unprocessed elements at the end of the array are important is very small.
The interactor checks that every element took part in at least one comparison. If some element was not touched, then it can be the sought-for second minimum in some array, probably not the one jury intended initially, so interactor returned WA in such case. This hack allowed us to cut off randomized solution, but we had to add this sentence, so that contestants could understand why their randomized solution does not pass.
P.S. Yes, flushes are expensive. Interaction with its context switches is expensive too. Moreover, interactive problems show wildly different performance on different machines, OS-es and testing systems. We even get noticeable deviation when rejudging the same solution many times in a row.
What is the purpose of $$$N \leq 10^5$$$?
I've seen this exact problem some time ago (sadly, cannot find a link) but with $$$N \leq 10^3$$$, general solution in $$$N + log_2 N$$$ queries was exactly the same but setting this limit resolves all issues with slow interactions.
Yeah, it is brand new problem
Our randomized solution was accepted. If n <= 20 one can ask n — 1 queries to find first minimum, erase it from array and then ask n — 2 queries to find second minimum which will be the answer. If n > 20 one can keep array b of size 20, which will contain (not for 100% but with high probability) first minimum and second minimum. We assume first and second minimums are somewhere in first 20 indices, and then starting from 21-th element for every index i we randomly choose ind such that 0 <= ind < 20 and compare b[ind] with a[i] and if a[i] < b[ind] we replace b[ind] with a[i]. This process will take n — 20 queries and after it we solve for case n = 20 with algorithm I described before.
Выкладываю описания решений "от жюри" (какие нашёл):
Я подумал над задачей, и на мой взгляд, я знаю линейное решение даже для случая с диагональю.
Если конкретно, есть матрица N x N, и в ней стоят числа. При этом N чисел встречаются в матрице ровно по одному разу (для диагонали), а ещё N*(N-1) разбиваются на пары одинаковых (для парных по симметрии элементов). Нужно за минимальное количество swap-ов сделать симметричную матрицу.
Во-первых, заметим, что диагональные элементы точно должны попасть на диагональ, причём в любом порядке. Буду дальше называть диагональные элементы "дырками", по сути они все взаимозаменяемы. Тогда: 1) Дырки, которые уже на диагонали, трогать не следует. (смотрим на цикл этой дырки: следующий элемент в цикле тоже на диагонали -> можно убрать дырку из цикла, будет на 1 swap меньше) 2) Есть K дырок вне диагонали, и K недырок на диагонали. Утверждается, что достаточно их как-то друг другу сопоставить и сделать по этому сопоставлению K swap-ов изначально, а потом решить задачу без задействования диагонали. (смотрим на цикл с произв. дыркой: видим, что можно сделать swap её со следующим элементов в цикле, что ислючает её из цикла и делает неподвижной)
Теперь разберёмся, как решать задачу без диагонали. У нас есть N*(N-1)/2 пар симметричных клеток. Очевидно, какая клетка снизу диагонали, а какая сверху, значения не имеет: т.е. это неупорядоченные пары. Давайте числа в клетках считать вершинами графа, а симметричные пары — неориентированными рёбрами графа. Получается, что конфигурация матрицы определяет граф, в котором у всех вершин степень 2, а значит он является набором независимых циклов. Следует заметить, что эти циклы уже не то же самое, что обычные циклы в перестановках. Они, например, неориентированные =)
Так вот: минимальное количество swap-ов равно (V — С), где V — количество вершин, а C — количество циклов (включая петли). Видимо, лучше всего это доказывать так, как предлагал Лёша, т.е. так же как это делают на лекциях по алгебре для перестановок. Нужно доказать, что один swap произвольной пары элементов не увеличить количество циклов больше, чем на один. Я попробовал, у меня получилось так: 1) Если делать swap клеток из разных циклов, то эти циклы сливаются (C -= 1). 2) Если делать swap клеток из одного цикла, то либо часть цикла разворачивается (C не изм), либо цикл разбивается на два (C += 1). Это позволяет легко решить задачу без диагонали.
Теперь вспомним про диагональ, однако будем считать, что её нет =) Просто есть K пустых мест в нашей бездиагональной матрице, и K недостающих элементов, которые мы должны расставить по пустым местам перед решением основной задачи. Естественно, эта начальная расстановка потребует от нас K операций, но это число никак не зависит от того, что куда мы поставим, так что в начальной расстановке у нас полная свобода. Нужно выбрать, что куда ставить, так, чтобы максимизировать количество циклов в нашем графе.
Если смотреть на рёбра графа, то они делятся на три типа: 1) Полностью определённые рёбра между двумя конкретно заданными вершинами. 2) Полуопределённое ребро из конкретной вершины в пока непонятно какую: какое число мы воткнём в соотв. пустую клетку матрицы, такой и будет второй конец этого ребра. 3) Неопределённые рёбра, у которых не указана ни одна из концевых вершин — это симметричная пара пустых клеток. Начальное распихивание K недостающих элементов в пустые клетки матрицы соответствует доопределению концов всех рёбер таким образом, чтобы у каждой вершины была степень 2. При этом нам хочется максимизировать количество циклов после доопределения.
Если смотреть на вершины, они могут иметь степени 0, 1 или 2. По вершинам можно сказать, что граф состоит из: 1) Циклы. С ними ничего делать нельзя и не надо. 2) Цепи. При этом каждый конец цепи может быть одного из двух типов: а) с выходящим полуопределённым ребром (т.е. заканчивается на симметричной паре с пустой клеткой) б) без выходящего полуопределённого ребра (заканчивается на симметричной паре без пустых клеток, но дальше продолжить нельзя) В частности, бывают цепи из одной вершины.
Если немного подумать, то становится ясно, что надо делать так: 1) Все цепи с полуопределённым ребром на одном конце надо замкнуть на себя — для этого надо закинуть в пустую клетку недостающее число. 2) Каждую цепь с полуопределённым ребром на обоих концах надо соединить с цепью без полуопределённых рёбер на концах. При этом образуется цикл. Можно понять, что таких цепей одинаковое количество, а что к чему прицеплять значения не имеет.
Короче это всё очень много мутного текста, но решение на самом деле простое.
Заметим, что Олмек всегда разрушает клетки одного ряда. Это означает, что можно опустошать каждый слой заданного прямоугольника независимо от остальных (в порядке сверху вниз, конечно). Самое главное — научиться опустошать отрезок [L;R) в массиве клеток (т.е. решать задачу при H = 1).
Можно пользоваться такой жадной стратегией опустошения отрезка [L;R). Начинаем в точке x = L. Пока x < R: если клетка [x; x+1) пуста, то перемещаемся из x в x+1 (без затрат) если клетка [x; x+1) полная, то перемещается из x в x+K (потратив одно падение) — т.е. выполняем падение в отрезок [x; x+K] Заметим, что алгоритм строго детерминированный, и проходит по некоторым состояниям x строго по возрастанию.
Рассмотрим граф, в котором вершины — это все состояния x, а рёбра — это описанные выше переходы двух типов. Естественно, все переходы идут строго вправо, и из каждой вершины ровно один переход — то есть это корневое дерево. Весь этот граф можно легко предподсчитать за линейное время. Задача опустошения отрезка [L;R) в терминах графа звучит так: нужно идти из L по переходам, пока не окажешься в R или правее ответом будет количество помеченных переходов на этом пути (т.е. переходов с падением)
Такую задачу можно решать методом двоичного подъёма (примерно как в LCA). Предподсчитаем: A[x,s] = <y,d> для всех 0 <= x <= W и всех 0 <= s <= log W Если выполнить из состояния x ровно 2^s шагов, то мы окажемся в состоянии y, затратив d падений. Имея эту информацию, можно найти бинарным поиском: сколько нужно шагов, чтобы добраться от L до R, и сколько при этом тратится падений.
Затраты: память: O(H * W log W) время : O(H * (W log W + Q log W)) При желании можно сделать O(H * W + W log W) памяти, если прочитать сразу все запросы и решать слои по порядку.
Раз надо сравнивать подстроки, то очевидно нужен суффиксный массив. Прежде всего построим суффиксный массив для S = A#B Имея суффиксный массив, будем работать с суффиксами обеих строк, упорядоченными сверху вниз (условно).
Для начала наивно предположим, что все подстроки различны. Будем перебирать K в порядке убывания от max(M, N) до 1. В каждый момент времени суффиксы длиной меньше K будем называть "мёртвыми", а длиной K или больше — "живыми". Нужно для каждого K узнать количество пар (живой суффикс A, живой суффикс B), таких что суффикс A выше суффикса B.
Можно это количество пар поддерживать и обновлять по ходу уменьшения числа K. Изначально оно равно нулю. На каждом новом K оживает один или два суффикса. Если оживает суффикс A, то надо прибавить к ответу количество живых суффиксов B ниже его. Если оживает суффикс B, то надо прибавить к ответу количество живых суффиксои A выше его. Чтобы быстро определять добавляемое количество, достаточно завести одно или два дерева Фенвика с ноликами/единичками.
Однако если предполагать, что все подстроки различны, то незачем вообще подстроки брать, всё по первой букве определяется; и даже суффиксного массива не надо =) Если же подстроки могут быть одинаковыми, то надо поддерживать дополнительно количество пар суффиксов A/B, у которых первые K символов совпадают. Более того, количество пар на 'меньше' надо периодически уменьшать, т.к. по мере обрезания символов какие-то суффиксы переходят из категории 'меньше' в категорию 'совпадают'.
Чтобы это всё пересчитывать, будем отслеживать множества живых суффиксов, которые совпадают по первым K символами. Каждое такое множество в суффиксном массиве всегда будет отрезком, причём периодически соседние отрезки будут объединяться. Чтобы понять, когда объединения когда происходят, надо посчитать lcp-массив — это lcp между соседними суффиксами в массиве. Для каждого положения, в котором lcp соседей равно K, надо объединить отрезки сверху и снизу от этого положения. В отрезке будет хранить количество суффиксов из A и из B (все суффиксы в отрезке всегда живые).
Итак, в общем случае наши действия на шаге K таковы: 1) Обработать ожившие суффиксы (те, у которых длина равна K): а) для каждого сделать запрос в дерево Фенвика на выше/ниже, добавить полученное количество к ответу б) добавить в дереве Фенвика единичку к позициям оживших суффиксов в) создать для каждого суффикса новый отрезок из одного элемента 2) Объединить соседние отрезки: для каждого места, в котором значение lcp-массива равно K: а) посмотреть на отрезки сверху от него и снизу б) посчитать произведение количества A-суффиксов в верхнем отрезке на количество B-суффиксов в нижнем отрезке (эти пары теперь равны) б) отнять от ответа 'меньше' это произведение, и прибавить его к ответу 'совпадают' в) объединить эти соседние отрезки
Общее время работы: O(N log N)
В задаче про строки можно построить суффиксное дерево для этой пары строк и "сканировать" его сверху вниз, поддерживая в дереве отрезков последовательность упорядоченных лексикографически подстрок, которые имеют длину k вместе с их числом вхождений в первую и вторую строку.
The teams from Cambridge also had the same problems (logins cambridge01 — cambridge04) and we saw this post just now. Could you fix for upsolving? Thanks!