Реализация
Для каждого города определим: за кого он голосует. Просуммируем для каждого кандидата и определим победителя.
O(n * m)
Математика, разбор случаев
Поймем, какие ходы интересные. Заметим, что Андрею нет смысла делать ход, при котором |a–m| > 1 так, как мы можем увеличить вероятность победы, если подвинем число a ближе к m.
Таким образом, мы рассматриваем два варианта хода a = c–1 и a = c + 1. Вероятность победы в первом случае c / n, во втором (n–c + 1) / n. Выбираем наилучший вариант. Нужно помнить про случай n = 1.
O(1)
Разбор случаев, (возможно) структуры
Рассмотрим, как происходят замены. Если был отрезок из точек длины l, то мы потратим l–1 операцию и прекратим замены для этого отрезка. Если просуммировать длины всех отрезков и их количества, то ответ это суммарная длина минус количество отрезков.
После изменения одного типа символа длина изменятся на 1. Количество отрезков можно поддерживать при помощи массива. Рассмотрим события слияния, деление, появление и удаление отрезков.
Для слияния смотрим на правого и левого соседа. Если они являются точками, то произошло слияние и количество отрезков уменьшилось на 1. Остальные случаи аналогично можно разобрать.
O(n + m)
DFS, бинарный поиск
Запишем вершины в порядке DFS от корня для вершин каждой глубины отдельно, храним время входа/выхода из вершины в DFS. Все вершины находящиеся в поддереве v, в такой записи представляют отрезок. Теперь мы умеем получать все вершины в v на высоте h, в виде отрезка, делая два бинарных поиска.
Палиндром можно составить, если количество нечетных вхождений каждой буквы меньше 2. Эту функцию можно посчитать для каждого префикса в обходе на каждой глубине отдельно.
Для экономии памяти можно воспользоваться битовым сжатием, поняв, что нас интересует только четность и функция – это xor.
O(m * (logn + 26) + n) – времени O(n * 26) — памяти, существует оффлайн решение за O(m * 26 / 32 + n) и O(n * 26 / 8) памяти
ДП
Нас интересуют пути являющиеся палиндромами. Палиндром читается с начала и с конца одинаково. Воспользуемся этим. Считаем динамику от координат двух клеток, первой и последней в палиндроме.
Из каждого состояние есть 4 перехода (комбинации: первая клетка вниз/вправо и вторая клетка вверх/влево). Нас интересуют переходы только по равным символам, по свойству палиндрома. Заметим, что нас интересуют пары клеток находящихся на одинаковом расстоянии от начала и конца соответственно. Если у первой клетки координаты (x1;y1), у последней (x2;y2), то x1 + y1 = n + m - x2 - y2.
Чтоб сэкономить память воспользуемся идеей хранить 2 последних слоя. O(n3) – времени и O(n2) — памяти
Классные задачи.
Спасибо за быстрый разбор. D очень понравилась. :)
Что-то я не понял решение двух последних задач.
По D: объясните поподробнее, как мы можем получать все вершины поддерева V на высоте H? По E: Что хранит в себе динамика? Как её пересчитывать? Где лежит ответ?
D: Сначала заметим, что вершина U является сыном V если время_входа[V] <= время_входа[U] <= время_выхода[V]. Если вершины на высоте H отсортированы по времени входа, то границы можно найти бинарным поиском.
а разве не все поддерево вершины v лежит на отрезке [in[v],out[v]]?
Да, всё поддерево, но мы же рассматриваем все вершины на глубине H и выбираем из них те, что лежат в поддереве V, так как не все вершины на глубине H могут лежать в поддереве V.
Начинаем расширять палиндром из центра.
dp[сколько букв набрали в обе стороны относительное центра][номер клетки на идущей влево-вверх][номер клетки на идущей вправо-вниз]. для каждой пары клеток есть условия x1 + y1 = x2 + y2, из этого у нас O(n^3) состояний.
Переходов у нас 4, идем по равным клеткам из текущей пары по всем возможным направлениям.
Ответ лежит в dp[(n + m) / 2][(1;1)][(n;m)]
Auto comment: topic has been translated by josdas(original revision, translated revision, compare)
thanks for Editorial :)))
Can you explain Problem D in a bit more detail.What is meant by in and out time of vertex.What is bypass the prefix.Doesn't makes much sense to average people like me.
Some of my thoughts: we can firstly compute the depth of each vertex and use a list to record the order of vertices in each depth. Let's consider the mentioned example (see the problem). the order of vertices in each depth is:
Depth 1: 1
Depth 2: 2, 3, 4
Depth 3: 5, 6
This process can help us quickly find the vertices in depth h for the required vertex v in the following. Going on, after that, we use DFS to record the in-time and out-time of each vertex. For the given example, we have the DFS order as follows:
DFS order: 1, 2, 2, 3, 5, 5, 6, 6, 3, 4, 4, 1
This can be addressed by applying the following pseudo-code:
time = 1;
DFS(vertex u)
in[u] = time ++;
for each son v
DFS(v)
out[u] = time++;
The above-mentioned two steps can be considered as a pre-processing operation. Then, for each query, denoted by <v, h>, we find the answer as follows.
Case 1: if h is no more than the depth of v, return "Yes".
Case 2: if v has no posterity that locates in depth h, then return "Yes".
Case 3: Otherwise, find the required vertices in depth h, and judge "Yes" or "No".
It can be said that, Case 1 is easy to solve. Here, Case 2 and Case 3 will utilize binary search (BS) to find the answer. Clearly, we will use BS to find the most left vertex (posterity) and the most right vertex (posterity) in the Depth-list of depth h for the vertex v. The BS exploits the in-time and out-time to find the most left vertex and the most right vertex. For example, if we want to find the most left vertex in depth h for the vertex v, we use the following pseudo-code:
l = 0, r = Depth[h].size() -1, ans_left = -1;
while( l <= r )
m = (l + r) >> 1;
if vertex Depth[h][m] is posterity of v
ans_left = m, r = m -1;
else if the ancestor of Depth[h][m] in depth "dep[v]" is in the left of v
l = m + 1;
else
r = m -1;
Here, we will utilize the in-time and out-time of a vertex to judge that: whether a vertex A is the ancestor of a vertex B, or the left/right one of the ancestor of B in the Depth-list.
An accepted source code: 12519227
I read your code. I didn't get one thing. In the part-> int x = mp[make_pair(v, h)]; if( x == 1 ) puts("Yes"); else if( x == -1 ) puts("No"); else run(v, h); }
Why do you even check for the value of x? Why don't you straight away use run(v, h) everytime? What is the use of even using a map? It will only be helpful if the same inputs are encountered. Right?
It is a memorization technique.
Can you explain me your time complexity? It seems to me that for each of the m query, you do two binary searches, and count the characters between ans1 and ans2. However, if (ans2-ans1) is big, isn't it going to be slow?
I see you used map there. But how does it guarantee fast time complexity? I hope my question makes sense.
How do we check whether the letters form a palindrome? Iterating through all the elements in the range might get a TLE exception.
Please elaborate Problem E also.You have not explained very clearly?
Let's assume f(x1, y1, x2, y2) be the function which gives the number of ways of going from point (x1, y1) to (x2, y2).
Now, the basic recurrence without memoization can be seen as :
Also, one argument in the recursive function is dependent on other 3, if we know x1, y1 and x2, we could compute y2 because the points are such that the manhattan distance beetween (1, 1), (x1, y1) and (n, n) and (x2, y2) are same.
So, we could have three arguments to the recurrence. And as there's no loop inside, time complexity of the solution after memoization would be O(n^3). But, space complexity will also be O(n^3). To make the solution run in required space (256MB), observe the fact that the current layer (equidistant set of points from (0, 0)) is only dependent on next set of layers (points with distance one more) we could write a bottom up dp with O(n^2) space. Storing just last one calculated layer everytime.
I wrote top-down dp with memoization, got Memory Limit Exceeded, couldn't code bottom-up dp properly in time! :'(
thanks a lot :) this is so much clearer (y)
can u tell me more clear how to find y2?
Assuming 1 based indexing and the corners to be at (1,1) and (n, m).
Now, if we are at (x1, y1), it means that the count of total moves is :
moves = (x1 — 1) + (y1 — 1) [Because at each step either x1 increments by one or y1 increments by one]
Similarly, from bottom corner we get
moves = (n — x2) + (m — y2)
So y2 = n + m — x2 — x1 — y1 + 2
The problems were great, but these explanations are a bit lacking. Could you please explain the solutions in more detail?
C can be solved in _ O(nlogn+mlogn) _ using a Segment Tree, storing for each node the number of operation needed to transform the whole segment, and another 2 variables pref,and suff which allows to know if the segment has a "dot"-1prefix or "dot-1suffix" :) is a simple solution but it needs more memory 12518296
I solved it with the same complexity but using binary indexed tree
But this overkilles the problem alot in my opinion
This solution is the sane as before but without logn
For C — regarding "...Quantity of segments can be supported by array." — we actually don't need to keep the segments. Rather we keep only current value of f() — and when we put a new symbol to the string — then f() changes by +-2, +-1 or 0. This depends solely on the old symbol and 2 its neighbors.
12510601
I also tried to solve C this way, but got wrong answer. Could you take a look at my code? 12511578
In the edge cases
else if (t == n - 1)
andelse if (t == 0)
thecur
variable is not updated.Also I believe there can be out of bound issues in those edge cases, when n is 1 — as
s[t - 1]
ands[1]
indexes are accessed there, which is surely beyond the string limits.A hint: you can also avoid dealing with those edge cases if you add a letter to the beginning and to the end of the string. This operation doesn't change f(s). After that your string will be of length n + 2 and all the replacement operations on it will be between indexes 1 and n inclusive — so the neighbours will never be out of string bounds.
This makes code smaller — i.e. less errors possible, faster to type and verify.
This is a general idea in many tasks — instead of dealing with edge cases — extend the field of work and work inside a sub field of that.
this idea can save a lot of time from a newbie's point of view,thankyou!! :)
At first I was trying to come up with a solution similar to the editorial, but then I realised that a change in F is only influenced by the neighbours.
Anyways, here is my solution if anybody needs more help: 12512037
Great, thanks, so simple :) AC 12522984
I am struggling with problem C
Can anyone give me a simplified explanation to it?
Thanks
Consider the simplest case: The string, of length L, is formed by all dots. Clearly f(s) = L - 1.
Imagine there k strings of consecutive dots of length L1, L2, ... Lk, separated by non-dot characters, the answer is just taking the sum of respective reductions, namely,
Let's see how we can perform updates in constant time.
Case 1: A segment's boundary becomes a non dot character. Number of dots reduced by 1, and number of segments is reduced by at most 1, depending on whether the segment is of length 1 or not. So the answer is reduced by at most 1.
Case 2: A segment's boundary is extended by 1, but not merging other segments. Number of dots is increased by 1, number of segments unchanged. So the answer is increased exactly by 1.
Case 3: A new segment is added (of length 1). This is the same as Case 2.
Case 4: One segment is broken by two non empty segments (otherwise, it's just case 1). In this case, number of dots is reduced by 1, the number of segment is increase by 1. So the answer is reduced by 2.
Case 5: Two non empty segments are merged. Number of dots is increased by 1, and the number of segments is reduced by 1. So the answer is increased by 2.
So you need to check neighbors of the changing position to see which case the operation falls into and update the answer in constant time accordingly.
Thanks alot I solved it correctly ... But when i surfed the internet , i found an algorithm (data structure) called suffix array . Can it be used to solve this problem?
Each substitution on s[xi] (ci' -> ci) will only effect s[xi]'s two neighbors(s[xi-1] and s[xi+1], if it has). Only need to recalculate the value on (s[xi-1], s[xi], s[xi+1]).
Автокомментарий: текст был обновлен пользователем josdas (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by josdas (previous revision, new revision, compare).
Hi, I can't figure out what's wrong with my solution for D... Here it is: http://mirror.codeforces.com/contest/570/submission/12521712 Please help!
Problem D : Beware, Even printf , scanf giving TLE ;( using fast I/O got ACCEPTED .
Your solution O(m * log * 26 + n). It is close to time limit.
My solution took 1996 ms. I'm running in the house yelling "Damn!".
Странно, но тест 41 задачи D, валит много решений, из-за пустой строки. Наверное, обидно было, повалиться на этом.
Так получилось из-за того, что количество вершин не являющихся корнем n — 1 и при общем количестве вершин n = 1, вторая строка содержит 0 чисел по условию.
Извиняюсь если это было не понятно.
josdas, мне нужно кое-что разъяснить
Задача B — 12500136
131416663 — это середина числа 262833325, так же как 3 — середина числа 5
В таком случае ответы m-1 и m+1 равно хорошие, разве нет? В первом случае в тесте (5,3) это 1 и 2, во втором это 4 и 5
Получается какой-то кек
Из условий.
Выведите одно целое число — такое значение a, чтобы вероятность победы Андрея была максимальной. Если таких значений несколько, выведите минимальное из них.
Господа, пишущие на Java, объясните пожалуйста, в чём причина того, что решение посланное под Java7 имеет запас почти в 50 мб, а Java8 валится по MLE?
http://mirror.codeforces.com/contest/570/submission/12527893
http://mirror.codeforces.com/contest/570/submission/12527818
А ещё бы понять в чём разница цикла for и метода forEach у ArrayList?
http://mirror.codeforces.com/contest/570/submission/12536065 (RE48)
http://mirror.codeforces.com/contest/570/submission/12536271 (AC)
Заглядывая внутрь интерфейса Iterable видим:
Казалось бы в чём разница:
и
Видать через лямбды вызывается гораздо больше методов, чем через обычный for. По крайней мере выделив 84 мб под стек, у меня лямбды не валятся. В то же время, если выделить вместо 64мб чуть меньше 50 мб, то валится и обычный for. Вообщем, мы ходим по лезвию ножа с такими ограничениями=) Интересно, а поможет ли вывод в отдельный поток с заданием размера стека или же -Xss нельзя овверайдить таким образом?
По поводу forEach. Перед каждым вызовом dfs в стек добавляется вызов forEach и accept. То есть два метода на каждый вызов dfs. Таким образом стек будет забит в 3 раза больше. В то время как for, не будет постянно хранить в стеке методы next() и т.п. (т.е. стек будет состоять только из вызовов dfs).
I am not able to understand why in problem B second variant probability is (n-c+1)/n . why it is not (c+1)/n .
If A is greater than the number of M, we are winning on any value from A to N.
josdas, когда еще будешь писать авторское решение, можешь его писать без define-ов, мне кажется, что так было бы намного легче разобраться в коде(и быстрее)(defin-ы у всех разные)?
Хорошо.
PROBLEM 570C-REPLACEMENT
for the test case:
3 3
...
1 .
2 a
3 b
ans should be:
2
0
0
correct me if i am wrong
Where is the input string?
Yes
F(...) = 2 (... -> .. -> .)
F(.a.) = 0 (.a.)
F(.ab) = 0 (.ab)
For the first hour, I ended up solving the wrong problem C. now I am curious how to approach this problem, If instead of replace the operation was of insert . How would be approach the problem. eg : s="..as..qwert...." first query is 1 h s'="h..as..qwert...."
Instead of an array using a balanced search tree. The need for surgery to insert and retrieve an item.
В D такие жесткие ограничения, чтобы отсечь все лишнее?
Если да, то не получилось. 12551482 O(log2n) на запрос
По Е тоже какое-то очень жесткое ограничение на размер таблицы. Пока не напишешь, непонятно, уложится ли в TL.
В D хотелось отсечь, но джава, а повышение n может МЛить не аккуратные решения за O(n * 26) памяти. По Е отсекали куб памяти, да и ТЛ 4 секунды намекает.
Насчёт 4 секунд согласен
Can someone explain the author's solution of the tree-requests, i am trying to understand the xor part of the code but couldn't find any explanations..Here the link to the author's solution-
http://mirror.codeforces.com/contest/570/submission/12523757
Can you perhaps provide more explanations in your solution to problem 570E? For example, what are stored in the array ou[dd][dd] and in[dd][2 * dd]? What is sotred in the array Si? Also, what does the variable ts represent?
Thank you!
ou[x][y] the position of the cell (x, y) on the diagonal.
in[x][y] the number and position of the diagonal of the coordinate cell.
In D question, I did not understand the XOR part. Could someone explain me?
Problem D.I use technique similar to finding LCA,in order to find parent at i-th depth.But I have time limit,is this normal or the problem is in my code?code
А вы заметили, что в каждой задаче первая строка входных данных : числа n и m?
In 570B Can anyone explain me the case when n is odd and the m is selected at middle of 1 to n range. (Say n=5 and m=3).Can't here we select both n/2 and n/2+2 as answer for a?
hi if you see this comments please do tell me to if you found the ans
Could anyone explain in problem B 570B - Simple Game the case that are n = 1 and m = 1 , how the answer is 1 ,please ?? Although the problem says { The boys agreed that if m and a are located on the same distance from c, Misha wins.}
if you read the output section carefully you will notice that the problem say " If there are multiple such values, print the minimum of them."
so in your case you can choose any number because all numbers there probability is zero but the minimum one is "1".
570D Can also be done using DSU on trees. See this blog.
How do you use DSU on trees in this problem?
Yes. You can see this submission. If you understand the blog, it'll be easy to understand the solution. Do let me know if there's anything confusing in the code.
Got it. Thanks!
C-Replacement has a very simple solution Code : https://mirror.codeforces.com/contest/570/submission/81380215 Explaination: If a new . is added to a position i,(which currently has alphabet) there are 3 cases: 1. if it is causing merging of two groups-in that case i-1 and i+1 will also have . and f(s) will increase by 2. 2. if it is creating a new group-in that case i-1 and i+1 will have alphabets,and no change in f(s). 3. if it is adding to a current group-in that case either i-1 will have . or i+1 will have . but both i-1 and i+1 simultaneously don't have . , in that case f(s) increase by 1 Similarly,If a new alphabet is added in place of dot: if it breaks a group into two groups , f(s) decreases by 2 if it reduces length of a group f(s) decreases by 1 if it takes place of a single . (i.e. no dot is present on left or right) then no change
Can anyone check my submission for problem D? 91924931 I think it's
O(nlog(n) + 26m)
. Am I right? Thank you.Problem $$$E$$$ is a replica of this USACO problem. I guess the USACO problem is a little easier because you don't have to deal with annoying parity stuff, but it's still basically the same problem...
nice round
nice round
570B: If n is odd and m is the middle point,then why a=m-1? Why not a=m+1??
Both have same probability and since m-1<m+1, we use m-1. The problem statement states that "If there are multiple such values, print the minimum of them."
Why does this code get
WA On #14
in the Problem D?