В этой задаче нужно было взломать сортировку, разумеется приведенный алгоритм был неправильным. Однако он верно работал для массивов длины n < = 2. В остальных случаях можно было привести в качестве контр-примера последовательность n, n–1, ..., 1. Чтобы исправить данную сортировку, нужно во втором цикле бежать не от i, а от 1.
Заметим, что с помощью приведенной операции всегда можно получить n–1 одинаковое число. Для этого будем всегда приравнивать первые n–1 чисел, а n-ое число будем произвольно уменьшать или увеличивать вместе с ними. Однако после приведенных действий весь массив может оказаться равным. Это происходит в том случае, если сумма всех элементов делится на n. Таким образом, в данной задаче ответ либо n, либо n–1.
Данная задача была скорее математической. Правильным решением в ней является следующий выбор: сначала возьмем все n элементов по разу, затем возьмем максимальный элемент и вместе с ним произвольный, затем два максимальных и с ними произвольный, затем три максимальных и произвольный и так далее. Всего получится ровно столько наборов, сколько требовалось в условии. Нетрудно проверить, что все суммы окажутся различными.
Данную задачу можно решать так: построим новый граф, вершинами в котором будут являться цвета исходного графа. Ребро между двумя вершинами u и v будет в том случае, если в исходном графе существует ребро, соединяющие вершины a и b такие, что c[a] = u и c[b] = v. Тогда ответом на задачу является такой цвет k, минимальный по номеру, что степень вершины k в новом графе максимальна (без учета кратных ребер). Такое решение можно реализовать за O(M·log(N)).
246E - Братья по крови возвращаются
Задача была немного похожа на задачу 208E - Братья по крови. В комментариях к той задаче было описано решение при помощи структуры deque (массив, в который можно добавлять и удалять элементы с обеих сторон). Теперь применим эту структуру в этой задаче.
Для начала все различные имена переведем в различные числа и для каждой вершины v запомним, какие запросы у нее были. Далее для каждой вершины, которая является корнем некоторого дерева запустим dfs, в качестве параметров передадим ему вершину v и deque< set > z. Этот deque будет для каждой глубины i в поддереве вершины v хранить set — различные имена (числа) на глубине i.
Пересчитать его просто. Посмотрим на всех сыновей вершины v и посчитаем для них такой же deque. Очевидно, что размер нашего deque z будет максимальным из всех deque-ов потомков. Далее пройдем по всем deque-ам и объединим соответствующие set-ы чисел. Причем, разумеется, будем меньший set присоединять к большему. После этого нужно в начало нашего deque z вставить set размера 1 — цвет вершины v.
После этого сразу же можно ответить на запросы этой вершины. Ответ либо 0, если потомков на такой глубине нет, либо размер z[k], поскольку это как раз множество различных имен на глубине k от вершины v. Известно, что такой подход работает за хорошую асимптотику, в частности авторское решение работало около секунды. Если быть конкретнее, асимптотика решения O(N·log2(N)).
В качестве пояснения к этой задаче хочу отметить, что реализовывать ее нужно аккуратно. Нужно избегать копирований deque-ов и set-ов. Нужно делать swap меньшего и большего set-a или deque-а без копирования всех элементов, а затем всегда меньший присоединять к большему.
Хммм, а я в задаче А выводил такую последовательность : 2, 3, 1, ... n. Заметим, что после того как мы поменяем 3 и 1 местами, единица уже никогда не встанет на свое место)
Заметим, что нам подойдет любая последовательность, где единица изначально стоит не первой и не второй. Тут просто приведен один из возможных вариантов.
в D есть решение, которое на мой взгляд проще. мы просто заведем массив set`ов и если у нас есть ребро uv и c[u] != c[v], то в c[u]-й set будем складывать c[v], а в c[v] — c[u]. таким образом мы получим, что размер i-го сета == количеству цветов, которые являются смежными с i-ым. а потом уже просто найти максимум. главное здесь, если у нас максимум оказался 0, просто найти минимальный цвет, который у нас есть
Так ведь там именно это и написано)
по сути естественно да, но я про реализацию)
ребро 2-3 и 7-5. Получаем что цвет 3 имеет соседей 1 и 2. Цвет 1 имеет соседей 3, цвет 2 имеет соседа 3. Максимум цвет 3
спасибо большое
Не понимаю, вот два решение задачи С. Первое которое получает TL на 12 тесте Your text to link here... и второе которое получает АС Your text to link here.... Изменена строчка continue на break, и условие поднято выше.. Помогите разобраться
Я особо в решение не вникал, но мне однако кажется, что в первом случае находились бы все возможные варианты сумм, даже если нам надо меньше. А во втором решении находилось ровно столько, сколько надо.
да-да, спасибо... Я уже нашёл косяк:-)
В задаче С проходит полностью рандомный выбор набора солдат и запись полученных сумм в массив. Для повышения степени рандомности можно вначале сделать некоторое количество рандомных свапов.
Но почему???
Учитывая, что все числа различны, рандом на больших массивах даст уникальную сумму с большой вероятностью, а на маленьких не страшно и лишку погенерировать — не много и надо.
Кто-нибудь может описать идею решения последней задачи?
Можно делать так:
Для каждой высоты в дереве будем хранить вектор вершин, находящихся на данной высоте(высота — расстояние от корня), в порядке их обхода.
Теперь для каждого запроса мы можем бинпоиском найти границы отрезка в векторе вершин, внутри которого лежат потомки данной вершины(при помощи времен входа — выхода).
Теперь задача сведена к поиску количества разных строк на отрезке. Это можно сделать персистентным деревом отрезков (ответ будет за log N на запрос).
Итого имеем O((N + M) * log N) времени и O(N * log N) памяти.
Спасибо! Буду пробовать реализовать :-)
Зачем нужна персистентность? Тут и дерева Фенвика вроде хватит.
В offline задачах обычно вместо персистентного дерева отрезков таки используют обыкновенное + метод сканирующей прямой.
Ведь так и можно, и короче, и быстрее, правда? :-)
Самая классная фраза во всём разборе "Известно, что такой подход работает за хорошую асимптотику". Практически эквивалент "Очевидно, что <какая-то_муть>".
problem E: we can also use BIT to solve this problem. first we should read all the queries and change every query (v,k) into (depth , left , right) :depth is the depth of the k sons of v,left and right are the indexes of vector W[d](it saves all the nodes with depth of d),then we can answer all the queries in the same depth together . So we transform the problem to another simple problem ,how many distinct values in an interval .it's easy to solve it just use BIT (off line ). here is my submission
Any idea how to calculate on-line the number of distinct values in an interval? Thx
I think we can use a segment tree whose nodes store all distince values of an interval. The complexity is O(Nlog(N)^2) which is slower than offline solution.
Please correct me if I'm wrong.
I'm not sure that this works. When you have a query on the segment tree, you will have to merge all the sub-intervals your interval is made up of. I can not see how you can do this better than O(n).
Please describe more of your solution if you think it works.
You're right. I'd try another approach. Let p[i] is the smallest number such that
a[p[i]] = a[i]andp[i] > i(nearest occurrence to the right, if there is no such number p[i] = N + 1). Then the queries boil down to count how many elements there are from p[L] to p[R] which are greater than R. Building a segment tree whose nodes store all sorted values of p[] in an interval, this can be done by binary search.Indeed, this solution works:) Thank you
As I know, offline solution works in O(NlogN). Do you mean "is higher (bigger, more, worse) than offline solution"?
P.S. This online algorithm can be bit modified to O(logN) per query. You should go throw segment tree from up to down, in root use binary search [O(logN)] and each lower vertex gets link from its parent to right position in array [O(1)].
Sorry, my typo. It should be "slower".
HolkinPV, If we do DFS n times, that will take O(N^2) time, wont it? Can you please explain me how to do it properly? that would be a great helo.
may somebody explain problem E with a little more description? I can't understand why we are using deque and even can't completely understand the algorithm explained in the editorial
Let Q[depth] be a vector<set<string> >. Strings in sets in Q[depth] are the strings that are searched by now.When we are just starting search node v, and if we need to calculate queries (v,k1), (v,k2), ..., (v,kn) , we should record the end of Q[depth of v + ki] as cur[i]. When we are ending searching node v, the answer to query (v,ki) can be calculated. It equals to the number of distinct strings in Q[depth of v + ki][cur[i]+1] to Q[depth of v + ki][the end of Q[depth of v + ki]. See my code here(2624164) if you still do not understand.
in problem 246D — Colorful Graph We don't need to create new graph.
it is solvable brute force in O(n+m) my submission
Your solution seems to be O(n * m). It's really strange that it gets AC.
my code got AC because the complexity of my code is O(N+M) NOT O(N * M)
It's O(N*M) because of the memset. I think the memset line is not necessary. You can change it with an integer array to keep tracks that a color is already inserted to other color set, so you can increment the set size.
For question E,
Consider a connected tree where every node has 1 son exactly except for the last one which has 0 sons. ( so the graph is just a line )
Then if there are 100000 nodes, and you store the deque for every node, then you store 100000 deques with their lengths being 1,2,...100000 which is 5000050000 elements. wouldn't that be time out?
When we merge the deques, we don't create a new deque for every vertex. We can use one of the deques (the largest one) from the sons. Answers for the sons will be already calculated at this moment, so we don't care about them anymore :)
In your case, only one deque will be created in the entire program — it will travel from children to parents.
So we don't keep the deques for every vertex? then how do you answer queries if you only have one deque for the root of every tree?
Or are you saying to pass the deque from the son to the parent by reference so it doesn't need to be deep copied? But if you do that then you will modify the son's deque so queries to that son will be incorrect.
Edit: NVM, didn't read your post in entirety. Thanks I understand now
We do offline algorithm: for every vertex store all queries that rever to it. Then, it dfs, after the merge, then the deque is correct for the current vertex, answer all queries for this vertex and step out from dfs. Next step this deque, of course, may become incorrect — but all the answers for the children are already stored.
In problem 246D — Colorful Graph, we can just create for each different color a balanced search tree (map or set). If you want to count the neighbouring color diversity of a specific color, just for every edge containing one node of that color, check if the other node's color being connected was already counted or not with the balanced search tree. You can see my simple implementation.
Exactly! Don't get how that problem is rated 1700 lol
It's 1600 btw
I solved it before the rating were recalculated.
В C рандомное решение работает 31 миллисекунду)
Заведем сет куда будем складывать разные суммы. Возьмем какую-то перестановку солдат и будет брать 1, 2, 3... первых и смотреть на сумму, если новая — выводим текущий ответ.
Делаем рандом шафл и описанное действие до тех пор, пока не получим нужное количество разных сумм)
Every daym shufflin'
Why is the asymptotic O(Nlg^2(N))? I know one of the lg is because of the set, But why always merging the small one into the big one is NlgN? I don't really know how to calculate this type of asymptotic. Could someone teach me, Thank you.
yin wei xiao ji he bu chao guo yi ban (o4
hi, for problem D 246D — Colorful Graph this is my submission the idea is to build for each colour k set of integers Q[k] as described in the problem statement, i need to know the complexity of my solution i think it's O((n+m)lgn) is this true ?
I see that many solutions with worst case O(N^2) complexity have passed. those solutions simply added all the k-th sons to a set and found the size of the set. ideally they shouldnt have passed :/. It would easily fail on a test where all nodes are attached to 1 and the query repeatedly asks about direct sons of 1.
I also thought they should TLE but those are actually correct solutions. These guys are big-brain. Note that they actually store the solution for the same set of sons. It can be proved that the total size of these sets is at most $$$O(n\sqrt{n})$$$. Consider a node $$$u$$$. Let $$$p_1,p_2,\dots,p_k$$$ be its ancestors, where $$$p_i$$$ is $$$u$$$'s $$$i$$$-th ancestor. Then $$$u$$$ is in the set of queried sons if and only if we are querying ($$$p_i,i$$$). We claim that there are only $$$O(\sqrt{n})$$$ possible outcomes of these sets.
Observe that the $$$(i+1)$$$-the son query of $$$p_{i+1}$$$ is strictly larger than the $$$i$$$-the son query of $$$p_{i}$$$ if and only if $$$p_{i+1}$$$ has a $$$(i+1)$$$-th son which is not a $$$i$$$-th son of $$$p_i$$$. This means it has a different branch with depth at least $$$(i+1)$$$. Therefore the subtree rooted at $$$p_{i+1}$$$ is at least $$$(i+1)$$$ larger than the subtree rooted at $$$p_i$$$. So the "size increase" of query outcome can happen at most $$$O(\sqrt{n})$$$ times because the tree size would exceed $$$n$$$ otherwise. Apply the same argument for every node we can conclude that the total size of these query outcomes is at most $$$O(n\sqrt{n})$$$.
I don't understand why this solution gives TLE, it should pass IMO, I've used a similar approach as in the editorial. Please help.
Link: 28072464
E can be solved using DSU on trees too. See this blog.
can someone help what's wrong with my solution of problem D. I do simply dfs and store all the diverse neigh. solution
Refer this