Какое наименьшее количество блоков необходимо, чтобы ответ был $$$\texttt{YES}$$$?
Проверьте предикат на каждом префиксе.
Давайте рассмотрим минимальное количество блоков, которое необходимо, чтобы первые $$$i$$$ высот были возрастающими. Так как высоты неотрицательные и возрастающие они должны выглядеть как $$$0, 1, 2, 3, ..., i - 1$$$, так что минимальная сумма будет $$$\frac{(i - 1) \cdot i}{2}$$$. Оказывается, что это условие достаточное. Если это не так для какого-то префикса $$$i$$$, то мы не можем сделать этот префикс возрастающим (так как суммарное число блоков на префиксе никогда не увеличивается) соответственно ответ $$$\texttt{NO}$$$, иначе ответ $$$\texttt{YES}$$$, так как мы можем двигать блоки с $$$i$$$-й позиции, пока в ней хотя бы $$$i$$$ блоков и получим возрастающие высоты.
Решение на C++: 107892022
Решение на Python: 107892053
Действительно ли задача двумерная?
Как решить задачу, если все $$$y = 0$$$?
Для начала заметим, что задача не двумерная. Если мы меняем $$$x$$$ координату точки, то сумма дистанций по $$$y$$$ не меняется совсем. Так что нам нужно посчитать количество хороших точек на линии сначала с координатами $$$x$$$, потом с $$$y$$$ и перемножить ответы.
Теперь, чтобы посчитать ответ на линии мы можем воспользоваться известным фактом: все точки с минимальным расстоянием лежат между левой и правой медианой. Так что теперь мы можем отсортировать массив и взять элементы на позициях $$$\lfloor \frac{n + 1}{2} \rfloor$$$ и $$$\lfloor \frac{n + 2}{2} \rfloor$$$ и вернуть их разность плюс один.
Решение на C++: 107892065
Решение на Python: 107892085
1486C1 - Найти наибольшее (простая версия)
Бинарный поиск?
Как проверить, находится максимум в правой или левой половине массива за два запроса?
Давайте решать для какого-то подотрезка $$$[l, r)$$$ и $$$mid = (l + r) / 2$$$. Теперь давайте проверим лежит ли максимальный ответ в $$$[l, mid)$$$ или $$$[mid, r)$$$. Давайте найдем второй максимум в $$$[l, r)$$$ и назовем его $$$smax$$$. Теперь представим, что $$$smax$$$ меньше $$$mid$$$ (из соображений симметрии). Теперь если мы спросим $$$[l, mid)$$$ и ответ все еще $$$smax$$$, то максимальный элемент лежит в $$$[l, mid)$$$, иначе он лежит в $$$[mid, r)$$$. Так мы уменьшили отрезок поиска в два раза. Так что результирующее число запросов будет $$$2 \cdot \lceil log_2 10^5 \rceil = 34$$$.
Решение на C++: 107892097
Решение на Python: 107892140
1486C2 - Найти наибольшее (сложная версия)
Спасибо Aleks5d за предложение решения данной подзадачи.
Опять бинарный поиск?
Как решать задачу, если второй максимум находится на первой позиции?
Как узнать находится максимум справа или слева от второго максимума за два запроса?
Найдем второй максимум $$$smax$$$. Теперь проверим лежит ли максимум слева, или справа от $$$smax$$$. Для этого просто спросим $$$[1, smax]$$$ и посмотрим, равен ли ответ $$$smax$$$. Теперь предположим, что максимум оказался справа от $$$smax$$$ (по соображениям симметрии). Тогда нам всего лишь нужно найти минимальный $$$m$$$, такой что на запросе $$$[smax, m]$$$ ответ равен $$$smax$$$. Наименьшее такое $$$m$$$ и будет позицией максимального элемента. Соответственно, мы можем использовать бинпоиск, чтобы найти эту позицию. Суммарное количество запросов получается $$$2 + \lceil log_2 10^5 \rceil = 19$$$.
Решение на C++: 107892122
Решение на Python: 107892144
Как решать задачу, если все значения $$$-1$$$ и $$$1$$$?
ОПЯТЬ бинарный поиск?
Как проверить, что ответ хотя бы $$$x$$$?
Давайте сделаем бинарный поиск по ответу. Теперь проверим, что ответ хотя бы $$$x$$$. Заменим все элементы большие или равные $$$x$$$ на $$$1$$$, а элементы меньшие $$$x$$$ на $$$-1$$$. Теперь если для какого-то подотрезка медиана хотя бы $$$x$$$, то сумма на этом подотрезке положительна! Теперь нам нужно лишь проверить, что существует подотрезок в массиве состоящем из $$$-1$$$ и $$$1$$$ длины хотя бы $$$k$$$ с положительной суммой. Для этого просто посчитаем префиксные суммы и для каждого префикса $$$i$$$ выберем префикс с минимальной суммой из позиций $$$0, 1, ..., i - k$$$, что можно сделать при помощи префиксного минимума за линейное время.
Получаем асимптотику $$$O(nlogn)$$$.
Решение на C++: 107892153
Решение на Python: 107892163
Вы же прочитали, что $$$w$$$ не больше $$$50$$$?
Как нужно изменить граф, чтобы алгоритм дейкстры работал по данному правилу?
Добавьте в граф фейковых вершин и ребер, чтобы все заработало.
Давайте думать о задаче в таком ключе. Для центральной вершины нам важны лишь веса ребер, через которые мы проходим. Так что давайте для каждой вершины $$$v$$$ создадим фейковые вершины $$$(v, w)$$$, где $$$w$$$ — вес последнего ребра по которому мы прошли. Это добавит не более $$$O(M)$$$ вершин в наш граф. Теперь для каждого ребра $$$(u, v, w)$$$ в изначальном графе создадим ребро $$$u \rightarrow (v, w)$$$ веса $$$0$$$. Также для каждой вершины $$$(u, was)$$$ и ребра $$$(u, v, w)$$$ создадим ребро $$$(u, was) \rightarrow v$$$ весом $$$(was + w)^2$$$. Теперь, если запустить алгоритм Дейкстры от вершины $$$1$$$, то мы получим корректные ответы для всех вершин, так как мы просимулировали новое правило при помощи фейковых вершин и ребер. Также мы создадим не более $$$O(M \cdot maxW)$$$ ребер, так как для вершины степени $$$t$$$ мы создадим не более $$$t \cdot maxW$$$ ребер, а сумма всех $$$t$$$ равна $$$2 \cdot M$$$.
Аккуратно реализовав данный алгоритм мы получим $$$O(M \cdot maxW \cdot logM)$$$ или $$$O(M \cdot maxW + MlogM)$$$ по времени и $$$O(M \cdot maxW)$$$ или $$$O(M)$$$ памяти. Любая реализация должна была получать AC.
Решение на C++: 107892178
Подвесьте дерево за какую-нибудь вершину.
После подвешивания дерева, как выглядит вершина пересечения?
После подвешивания дерева, какие два типа пересечения существуют?
Давайте подвесим дерево за какую-нибудь вершин. Теперь вершина пересечения двух путей будет lca для хотя бы одного пути.
Если вершина не является lca для обоих путей, то это означает, что есть два ребра идущих наверх (что невозможно в подвешенном дереве), или они поднимаются по одному ребру, что означает, что у них хотя бы две вершины в пересечении, что также невозможно.
Теперь есть два типа пересечений: с одинаковым lca и разным lca. Давайте посчитаем их по отдельности.
Для каждого пути и его lca найдем поддеревья, в которые этот путь спускается от lca. Получим тройку $$$(lca, subtree1, subtree2)$$$ (если путь не спускается от lca, то заменим на $$$-1$$$), такую что $$$subtree1 < subtree2$$$ или они оба равны $$$-1$$$.
Теперь чтобы посчитать пересечения первого типа мы можем использовать принцип включений-исключений. Запомним все пути, которые имеют одинаковый lca. Теперь нам нужно посчитать число пар путей, таких что у них не совпадает $$$subtree1$$$ и $$$subtree2$$$ (или равен $$$-1$$$). Формула будет $$$cntpath \cdot (cntpath - 1) / 2 - \sum \left(cnt(subtree1, x) + cnt(x, subtree2) - (cnt(subtree1, subtree2) + 1) \right) / 2$$$ (по принципу включений исключений), для всех возможных $$$subtree1$$$ и $$$subtree2$$$, где $$$cntpath$$$ — число путей с данным lca, и $$$cnt(x, y)$$$ — число путей с тройкой $$$(lca, x, y)$$$. Ситуация с $$$-1$$$ примерно такая же, оставляю как упражнение читателю.
Находить пересечения второго типа заметно проще. Нам нужно лишь посчитать число пересечений путей с фиксированным lca и вертикальными путями, которые проходят через это lca (пути необязательно вертикальные, он они содержат и lca и его предка) и после этого вычесть $$$cnt(subtree1)$$$ и $$$cnt(subtree2)$$$, где $$$cnt(x)$$$ — число вертикальных путей, которые спускаются в поддерево $$$x$$$.
После этого мы должны всего-лишь вывести сумму этих чисел. Чтобы посчитать все необходимые функции можно использовать какую-нибудь структуру данных (например переливания) или динамическое программирование по поддеревьям.
Финимальная асимптотика получается $$$O(Mlog^2M)$$$ или $$$O(MlogM)$$$ или даже $$$O(M)$$$, если вы достаточно сильны.
Решение на C++: 107892186
I'll add solution codes as soon as I can. If there are any mistakes, you can PM me.
Pls add more interactive problems as C .
Sad for you :d im__back
Great Contest !!! Nice Problems
Solutions were added. Thank you for participation, you guys are great.
The test for E is weak so that many people use fake algorithm AC it, I think it is unfair!
Is this good or bad? If you don't mind checking of course... https://codeforces.me/contest/1486/submission/107861368
/**/
New?
Editorial with hints. Thank you very much.
seems like bro loves binary search
where are these things in C question solution "fflush(stdout) or cout.flush() in C++;". please include these and if not then why it is not needed
endl does cout.flush inside.
Thanks a lot
C was nice
Amazing problems and solutions!!!!
can someone plz explain this to me for question B: Now to calculate the answer on a line we could use a known fact: point with the smallest summary distance is between left and right median.
think about 4 points : (0,0) (0,1) (0,2) and (0,100). If you are fixing the median between (0,2) and (0,100) the first 3 point will have to move to the right(0,x+1) and that's bad for the solution.
Just imagine: there are n points in line. You are on the leftmost point and walk to the rightmost point. When you begin to walk, the sum of all distance will get smaller until you arrive at the median —— or 2 medians (if n is even, there are 2 medians and you will get a same summary between them)
ohhoo ..nicely explained .. thnx
It is because you want to minimize $$$C = |x-x_1| + .. + |x-x_n|$$$ where $$$x_1\leq x_2\leq ... \leq x_n$$$. You have $$$|x -x_i|+|x-x_{n-i+1}|\geq x_{n-i+1}-x_i$$$; and "=" happens when $$$x_i\leq x\leq x_{n-i+1}$$$. To make it valid for all $$$i$$$, in the case $$$n$$$ is odd, $$$x$$$ must take the value of $$$x_{n/2}$$$, otherwise, $$$x$$$ can take any value from $$$x_{n/2}$$$ to $$$x_{n/2+1}$$$ (the two medians).
Another way to think of it: for any two given points, choosing any point along the line connecting them contributes the same summary distance, i.e. the distance between them. So taking all the points as a whole, you can ignore the left-most and right-most point. You now have a smaller set, and you can keep doing this, until you either have 2 points left (if initial set had an even number of points) or 1 point left. So if you have 2 points left, any point between them will contribute the minimum (the distance between them), as going outside of those 2 points will contribute more than the distance between them. And obviously if you only have 1 point left, that point will contribute 0, and anything else would contribute more.
Is there someone who tried to solve E as a dp[N][2] — minimum distance to reach a node where state 0 means using the second road now and and 1 for the using the first one? I WA o pretest 4,if you can give me your solution. My CODE
I solved it using a similar approach. Here is my code. Hope it helps : )
it's not, but thank you anyway :). I found my mistake. I didn't think about the case when we should use the same edge twice in a row like in this example :
Systests for E seem to be weak, many $$$O(n^2)$$$ solutions including mine (107846073) passed with it.
Some video solutions for A-E, and somehow not FST'ing E
Really liked problem c and great problem set!!
weak pretests in A, didn't include overflow case
what does overflow case mean?
Sum of numbers is greater than MAX_INT
It's literally in the sample case.
I didn't notice that. XD What I meant is a case that gives WA verdict for a submission that contains overflow like this submission 107786541
Thanks for the fast editorials!
C was nice but it would have been better if on exceeding query limit it threw some error other than WA. I thought my code was incorrect but it was exceeding query limit.
What else should it error as?
Something like Query Limit Exceeded.
In interective problems u can use assertion on number of queries to make sure whether it is wrong ans or query limit exceeded
Could you please tell me something about how to use assertion to konw whether or not my submission is query limit exceeded.
Here is an article on assertion article Here is my yesterday code, although it failed still u can see how I used assert. Code link
IMO this gives too much information, like in constructive problems if you print the wrong length you don't get a custom result.
Maybe add
if(totalQueriesMade>40) sleep(5)
and purposely get TLE (assuming your code won't TLE otherwise). Hack-ish, admittedly.WA ON TC2 in prpb A . Can anyone give me whats the mistake.
def solve(): n = int(input()) l = list(map(int, input().split()))
for testis in range(int(input())): solve()
Thanks
UPDATE: ITS SORTED OUT NOW
Test with this:
Why is my solution not correct for A ? I can't think of a case where it may fail;-;...pls someone check 107870406 i wasted 2 hrs on this piece of sheet;-;
You need to read the entire line, even if you find
sum < 0
.Thank you!! I will cry in a corner now:)
You
break
possibly before reading the input. I suggest read all the input before solving the testcase.ur code fails on 3 3 0 0 1 3 0 1 0 3 1 0 0 answer is NO , NO , NO I guess your code guess a different answer. Refer https://codeforces.me/problemset/submission/1486/107870392 the function solve2
sorry I stopped taking input when i got the answer so it messed up further inputs...
Hi,the logic is no8t making any sense to me. Consider this sequence 0 1 2 2 8 9 20. Do you think your solution will give correct output? Even though h-i is negative at i=3, still the sum becomes positive. But do you think in this case a solution is possible?
the logic is correct, I am checking for every input...I broke when I found the ans...didnt take all the inputs, thats why it gave wrong ans
I have the same mistake as you and wa on test2. Fortunately, I solved it.
okwedook Too many fake solution for E, suggest rejudge all submissions .
What do you mean by "fake" solutions?
many O(n^2) brute force solution got accepted during system testing. I hacked some submissions, but there're too many... just like: 107844532 107866549 107865668 107840161 107832126
The system tests for problem E are weak
I agree with you. There are about 50 slow solutions was hacked, why you are can't retest and redistribute the rating?
Just amazing contest,thanks to the autor! Waiting soon for ur next round.
I tried to solve D using ordered set, but I got WA on test case 7. I cant figure out why MY CODE
you get the max median of subarray of length exactly k not at least k
can you explain why length k is not optimum, i think length k should be optimum
n = 3 k = 2
5 2 5
With array $$$[2, 1, 2]$$$ and $$$k = 2$$$, the only possible median for subarrays of length $$$2$$$ is $$$1$$$, but the best possible median is $$$2$$$ attained when we consider the entire array.
Can anyone please tell me why I got an fst on problem C ? WA_CODE
Such a good problem set, make me realize that I need to work hard. And that interactive questions, nice.
I will be thankful if someone recommends good and easy interactive questions, for beginners. Thanks in advance.
The interactive problems sorted by difficulty https://codeforces.me/problemset?order=BY_RATING_ASC&tags=interactive
C was a great question, I'm still confused though on my find_left function.
at first, my mid calculations were the standard (lo + hi) / 2, but this causes infinity loop:
then I changed it to (lo + hi + 1) / 2, then got AC:
full code:
Can anyone with a better understanding of binary search explain why this works?
While hi = lo + 1, like lo is equal to 2 and hi is equal to 3, mid calculated by (lo + hi) / 2 is 2. In this point, you'll get stuck by lo = mid because lo will never change.
See topcoder binary search tutorial.
Yeah, I learned to understand when to return lo and hi, rather than just memoziring it. Thanks!
welcome
I solved E in another way(107874274). I'm not sure whether it is correct or not.
The naive solution is to use Dijkstra's algorithm and two loops to relax. Consider every vertex $$$u$$$. If it is used as middle vertex by some vertex $$$a$$$ and it is going to be used by vertex $$$b$$$.
According to Dijkstra's algorithm, ans[a] <= ans[b] must hold. If dis[a][u] <= dis[b][u], no vertex will be relaxed by $$$b$$$. So for every vertex, I record the minimum dis[a][u]. If it is equal or smaller than dis[b][u] then continue. Otherwise I just run the naive two loops.
Since every vertex will be used as middle vertex at most $$$maxw$$$ times, each relaxtion will call one pq.push. The time complexity may be $$$\mathcal{O}((N+M)logM + maxw\cdot (N+M)logM)$$$(I'm not sure about this)
Can't we solve this for general weight. Means we can construct a new graph in which there is an edge between u and v iff there is exactly one vertex z between u and v in original graph s.t. u-z and v-z are edges in the original graph and weight of uv in new graph will be as defined in the problem. Now simply we should run Dijkstra on this new graph.
What is wrong with this method? Can you please point it out.
In the worst case, the new graph will consist of $$$\binom{M}{2}$$$ edges.
I have solved it for generic weight : https://codeforces.me/contest/1486/submission/108202408
Let me know , if you feel there exist a test case which can hack this solution.
Time complexity looks good to me to pass within the time limit.
E
"For a middle vertex we only...". what is a "middle vertex"?
"is the weight of the last edge...". What is the "last edge", last of what?
"Now for each starting edge..." What is "starting edge" here?
Thanks for commenting your code for today's C. It helps.
okwedook Please answer the spookywooky comment, I have same doubt. I find difficulty in understanding the editorial of Problem E.
Is there anyone else who thanks Errichto whenever they see a binary search problem?
Can someone help me figure out where I am going wrong?
Thanks in advance!
To debug such scenarios, you can stress test your solution as well.
You can write a bruteforce for this problem very easily. e.g.
Keep doing this for many iterations till you find a counter case. This kind of stress testing strategy helps a lot in many problems. You can see my submission for some hints regarding implementing this bruteforce. The code is really messy and unpolished, but I have attached it for reference anyway.
okwedook test cases for E are weak. Many $$$O(N^2)$$$ have been passed. So please consider rejudging all submissions.
Unfortunately we won't rejudge all the submissions Uphacks are already added to tests, so from this point all the solutions will be judged with updated tests Sorry for the inconvenience
I don't think they are added . Still O(n^2) submissions are getting AC
I thought it has time complexity O(log n) but it's O(n).
It seems that every interval like $$$[1,2],[3,4],\cdots,[n-1,n]$$$ will cost 1 query and the number of those intervals is $$$\Omega(n)$$$. In addition, there are other intervals that will cost 1 query.
How to solve D by two pointers?
I am getting runtime error on testcase 6 for the E problem , here is the link of my submission , can some one please check it!!, What I have done is kept n*51 states and edge of weight 0 between (u,0) & (v,w) , edge of weight (a+w)^2 between (u,a) & (v,w) , for the edge u,v with weight w given in question, I applied dijkstras on transformed graph..
how are you making sure that you always travel two edges at once?
In problem D, I know that we can use binary search as described in the editorial. But I noticed that if $$$x$$$ is too small, we cannot find a sufficient subarray. Consider the first example in the statement of list $$$[1, 2, 3, 2, 1], k = 3$$$. Assume that we want to check if it is obtainable the median of $$$1$$$ or not. But we cannot choose from $$$[1, 2, 3, 2, 1]$$$ a subarray of length at least $$$3$$$ that has the median is $$$1$$$.
How can we overcome this?
The binary search asks the question: is there a subarray of some length with a median of at least 1?
So we replace all elements that are 1 or more in the array with a 1, and those that are less than 1 with a -1, resulting in [1, 1, 1, 1, 1]. We can find a subarray of length at least 3 with the median 1, so it follows that the answer is 1 or more.
After reading the solution to the problem D — wow that is very smart. The binary search never ceases to amaze me. Thank you for the beautiful problem (and the solution)
Can anyone please explain the formula of problem F?
I'm not sure what the official solution is, but I can try to explain my solution to F. Consider a vertex $$$u$$$, and say we want to count all pairs of paths that have $$$u$$$ as their unique common vertex. First arbitrarily root the tree at $$$1$$$. We break the paths into $$$4$$$ types:
For a fixed $$$u$$$, we can take care of all pairs of paths that contains vertex paths easily, so we ignore those. We can pair any up path and down path. We may also pair through paths and down paths that do not overlap. We may also pair a down path with a down path if they do not overlap. We can easily count all these quantities using Heavy Light Decomposition and LCA.
Submission link
About C: Actually we can do this with only 18 queries.
Here's my code: 107897123
I can't explain code clearly, it is copyed from my code in C1 and edited a little. (Code in C1: 107895318)
Maybe someone could explain how this worked or hack it?
Amazing solutions!!!Orz
It seems to me that D, E are too technical and without ideas (it was immediately clear to me from the statesment what to do), but they are still funny
https://codeforces.me/contest/1486/submission/107832284 can anyone point out why is this solution wrong, I ran query overall range and then ran two queries for f, mid and mid+1,l if I find the same index in either of the answers then I search in that range or If I don't find any matching index I go the half opposite to that previous queries
n=3 array=[1,2,3]
Thanks for the "Hint" part! Super helpful! :D
When will I become a CM? :-(
107905723 In line 150, you are initializing p with INT_MAX, it should be zero because if you don't consider any element ie prev sum, the value of p should be 0.
Yeah, I got that. Thanks though.
It's been a pain using the CF system tester to debug an interactive problem like C (even the asserts return nothing, just a Runtime Error). Here's a brief snippet in case anyone else would like to test this locally. It basically generates n different numbers (permutation from 1 to n) and shuffles them.
Instead of doing cout/cin operations, as you would do in the actual solution, here you could just call the ask() function and it would give you the second maximum for that range (each call takes O(n) time — so you would obviously time out if your overall solution is not some form of binary search / log(n))
Can someone please help me where my code is failing. TIA.
107911405
Worst case needs O(n) queries. Try:
[7 6 5 4 3 2 1 8]
But I am always halving the search space? Can't seem to figure out the error in my logic.
mid==l
is possible, and when you callbinarysearch(mid+1, r)
, you are decreasing the search space by size 1, not halving it.More importantly it sometimes gives wrong answer. Try
4 5 6 1 2 3
Oh I got it. I made 2 variables mid and and middle and got confused between them :(
In the editorial solution of problem c2,in binary search l+1<r is used in while loop instead of l<r used usually.can someone explain the logic behind?
Let's consider the case when
smax<maxpos
(the firstwhile
loop in the code). The loop invariant property is that the range[l,..,r]
always contains both,2021-02-19smax
andmaxpos
. It is beneficial to break the loop just whenl
andr
become adjacent (i.e. whenr - l > 1
becomes false) because now the only way for the above property to hold is thatl==smax
andr==maxpos
, and we can immediately outputr
(orr+1
, in case of 1-based indexing).why is it like the range
[l...r]
will contain both smax and maxpos like in the example:1 4 3 2 5
the loop will break atl=3
andr=4
whereas the index of smax is '1'(0 indexing).Oops.. the claim about containing of
smax
is not true at all.. Feeling stupid now.I'm getting this error in C1 and C2 problem " wrong answer Integer parameter [name=query_l] equals to 100000, violates the range [1, 99999]" Can anybody help to fix that this is my code
I think it because you need to do query at l,r where l!=r
yeah, it is fixed thanks a lot!
Quality of editorials have increased a lot from past few months.
Can you please explain problem E, not able to get what the editorial says.
"For a middle vertex we only...". what is a "middle vertex"?
"is the weight of the last edge...". What is the "last edge", last of what?
"Now for each starting edge..." What is "starting edge" here?
If you use SPFA in E,you will be TLE.
Good problems, moderate difficulty, but weak tests of E.
Can someone please explain problem C2 didn't get the logic from the editorial. Thanks in advance :)
see my submission, here d is 1 for right direction and -1 for left direction.
I can't get why my solution is giving me a wrong ans at test 7 of question D. My approach is a little different from the editorial. https://codeforces.me/contest/1486/submission/107932779
You get the max median of subarray of size exactly k not at least k so you bug on 3 2 2 1 2 Your answer is 1 true answer is 2
oh got it, I missed the at least part. Thanks a lot man!
In C2 solution and find_left binary search why do we return hi instead of lo?
Cause it's the first element to get the needed answer as written in the editorial
Can you please tell the logic behind using
r-l>1
instead of usuall<r
in binary search in the editorial solution?I use binary search with subsegment $$$[l, r)$$$, so it means I look at elements $$$l, l+1, \ldots r - 1$$$. This is called a half-interval (in russian at least). That's why $$$[l, l+1)$$$ contains only one element.
Thanks! If i use l<r, the program stucks in infinite loop like in the sample test case
5 1 4 2 3
it goes like:why so?
Well, because l is always less than r. That's the beauty of half-interval.
Can it be generalised that when we should use
l<r
and whenl+1<r
in binary search or is it just for this specific problem?I always write binary search this way. Just use half-intervals and you'll be happy. Consider it like this: l is minimal possible value and r is the first value, that is most definitely working out for you. You can rotate the problem (make segment $$$(l, r]$$$ and code wouldn't change at all (only checks and output).
ok,thanks a lot!
Thanks for your explanation, really appreciate it!
It would be really great, if you could elaborate on these points —
Minimal with respect to what condition?
You mean the first True value?
If the answer is in range $$$[1, n]$$$ you would use $$$[1, n + 1)$$$ or $$$(0, n]$$$. That easy, just add 1 (or -1) when needed and cover all the possible answers. Actually $$$(0, n +1)$$$ should work fine too.
What are the initial conditions for l and r, in case I use your
half-interval
technique?You can refer to this comment.
Okay, got it, my bad :)
What does "wrong answer Integer parameter [name=query_r] equals to 49218, violates the range [50000, 100000]" mean? What am I missing? This is in testcase 5 problem C1
Check whether l == r. The length of a range should be more than 1.
Can someone check my code for problem C. Still cant figure out the corner case I'm missing.
$$$prev$$$ would be different if $$$x \neq prev$$$.
Same mistake
Inefficient solution
Efficient solution
Thanks a lot.
I can't explain me why my solution is wrong for problem A, can anyone help me? https://codeforces.me/contest/1486/submission/107785526
You need to read all n numbers
Can someone tell why it is giving wrong output 107936839
If n = 5 and inputs are 2 1 1 1 1, then for loop breaks in the fourth iteration and the last one is acting as n for next test case.
How did you debug so fast... I'm a beginner and often unable to find out mistake in my own code and often waste much time finding out mistakes, please tell how to do that
I had done the same mistake in a round.
Why is this getting WA on testcase 3 ? can anyone help me. https://codeforces.me/contest/1486/submission/107964080
Can someone elaborate how you all are creating graph before applying Dijkstra? (problem E)
I have considered $$$0$$$ based indexing of nodes to save memory.
Since weights of all edges is between $$$1$$$ and $$$50$$$ . For each node say $$$nd$$$ , create $$$51$$$ nodes say $$$nd*51$$$,$$$nd*51+1$$$,$$$nd*51+2$$$,....$$$nd*51+50$$$.
Now for each edge $$$x,y,w$$$ as input , make edges $$$(x,y,w)$$$ and $$$(y,x,w)$$$ as shown in following code since edges are bidirectional.
Let's understand how Dijkstra will work here with example :
consider nodes $$$0,1,2$$$ . Suppose edge length between $$$0$$$ and $$$1$$$ is $$$e_0$$$ and edge length between $$$1$$$ to $$$2$$$ is $$$e_1$$$. Thus distance between $$$0$$$ and $$$2$$$ is $$$(e_0+e_1)*(e_0+e_1)$$$ by using definition in question.
First we will insert $$$0$$$ to priority queue . Since $$$0$$$ is connected to $$$1*51+e_0$$$ with edge length $$$0$$$ , $$$(0,1*51+e_0)$$$ will be inserted in priority queue. Also $$$1*51+e_0$$$ is connected to $$$2*51$$$ with edge length $$$(e_0+e_1)*(e_0+e_1)$$$ , thus $$$((e_0+e_1)*(e_0+e_1),2*51)$$$ will be inserted to priority queue .Hence distance between $$$0$$$ and $$$2$$$ is $$$(e_0+e_1)*(e_0+e_1)$$$.
Now try to scale above example to any number of vertices and it will be clear why it works.
priority queue based implementation : 107975317 set based implementation : 107975265
In the editorial's code for C2, why is the binary search done over 0...n-1 and not 1...n, I've already noticed that the answer is being returned after incrementing it by one.
I guess it wasn't necessary
In problem D, I dont understand why the answer is monotonic. Suppose the array is [6, 1, 1, 1, 1, 7, 8], k = 3, the answer exist for x = 7(ie subarray [1, 7, 8]), hence according to the editorial the answer is atleast 7, this means answer for x = 6 should also exist, but there is no subarray of length >= 3 for which 6 is the median.
Did I miss something? Any help is appreciated.
When your $$$check()$$$ function returns $$$true$$$ for some value $$$x$$$, it does not mean that there will be a subarray with median $$$x$$$, it means that the median is atleast $$$x$$$.
Except for the LCA part, I have had a nearly-linear implementation for task F.
My submission 108017714
So you are strong enough:)
Actually, I have written a pretty neat data structure to get RMQ in O(1) online (so it can handle LCA online of course).
I didn't understand why you praised me until I actually read your editorial. :)
I am not going to show off. However, I would like to add my little bit to nowadays's problem approaching style.
In my opinion, the (nearly)-linear algorithm is the easiest to implement, without using any heavy data structure. Back in to the old days, the people who know HLD / LCT is the true master. XD
Would you mind explaining how you obtained the triples (lca, subtree1, subtree2) in linear time (if you remember the problem by now and are willing lol)? I'm too lazy to read code, especially for a problem with such a long implementation.
I did it for each vertex pair $$$(u, v)$$$ by computing the $$$(depth[u] - depth[lca(u, v)] - 1)$$$th ancestor of $$$u$$$, and the same for $$$v$$$. So I couldn't get rid of the log factor :(
The problem is that given $$$u$$$ and $$$v$$$ where $$$v$$$ is an ancestor of $$$u$$$, we would like to know in which subtree of $$$v$$$ that $$$u$$$ lies.
We can perform a DFS on the tree, and keep track of an array $$$\mathrm{current}[v]$$$, which is the current subtree of the vertex $$$v$$$ we are in. When reaching the vertex $$$u$$$, $$$\mathrm{current}[v]$$$ is what we need.
This approach is conceptually simpler than what I had done in my code, and the only drawback is that we have to do DFS twice. One for LCA and one for the subtree query.
My code is more complicated as I solved LCA and subtree query in one DFS as I remember.
Ah, I understand, thank you so much! I suck at using the idea that you can maintain an array of size $$$O(n)$$$ during the dfs, it just makes my brain explode for some reason lol.
A similar idea is that while visiting vertex $$$u$$$, maintain a stack $$$s$$$ consisting of the vertices along the path from the root to $$$u$$$ (in order). Then $$$current[v]$$$ is equivalent to $$$s[depth[v] + 1]$$$. I think the latter idea seems more intuitive to me, but maybe it's just because I've seen it before.
I am observing about a 2x difference between the runtimes of two solutions, by just changing the way I am indexing the array. I understand that this is because of different localities of reference between the solutions.
Yet, I am not able to figure out why one of these has a higher locality of reference. If someone can help me figure out the same, it will be greatly appreciated.
These are the two submissions: 108047029 108047388
I was trying to solve C2 but I am not quite understanding where the queries are running out. According to me, I am asking only one query before dividing the segment any further, so I think my queries shouldn't be more than 20.
My code: 108106042
In problem B, do we not need to consider unique points for x? suppose we have (0,0) (6,1) (8,2) (8,3) (8,4) and (10,4). Then vector for x will have <0,6,8,8,8,10> and the ans for this will be size = 6 x[3] — x[2] + 1 that is 1 but answer should be 3 (6,7,8)? pls help.
Why do you think the answer should be 3? The answer is 1(only 8).
for 6: the sum of distance is 16.
for 7: the sum of distance is 14.
for 8: the sum of distance is 12. Cleary, The minimal distance is for 8 only.
In E I combined all pairs of consecutive edges into a single edge and applied djikstra to the modified graph. It is giving WA on test 5. Please someone explain my mistake. Here is my solution 108800090
I am getting wrong answer on test case 16 in problem D and I am not able to find the error. Here 108604409 is my submission. If anyone can help..
I am having the same issue https://codeforces.me/contest/1486/submission/112127483, could you figure out the issue?
Nope, I couldn't. But seems like you figured it out. What was the issue?
The issue is with the initialization of the minimum vector, it should begin with zero value. See the difference in these two submissions for clarity:
https://codeforces.me/contest/1486/submission/112135909 (WA 10th case)
https://codeforces.me/contest/1486/submission/112136806 (Accepted)
Добрый день. Спасибо Вам большое! Наверное все же в D нужно стартовое r указать равное 2e5+1, иначе вылетит ошибка,например на таком тесте
5 2
1 7 8 1 1
Внимательно прочитайте условие задачи. Данный тест некорректен.
I had been trying to solve problem E, and in failing to do so, tried to look for a solution in the editorial. However, I found the editorial for E a bit unclear, and both my brain cells struggled hard to comprehend it. Fortunately, I found kostia244's (sorry for the ping) solution in the standings page, which was quite clear and understandable to me, and was finally able to solve the problem after 1010 attempts. Hence, I decided to explain my (rather kostia244's) solution, just in case someone drops by here in future. So here it goes:
We maintain $$$dist[N][W]$$$, where $$$dist[i][j]$$$ stores the distance of node $$$i$$$ from node $$$1$$$ and the weight of the last visited edge is $$$j$$$. Initally $$$dist[i][j]=\infty$$$. To perform dijkstra on the graph, we maintain a heap, $$$q$$$ (or set, depends on your taste) which contains an item with three parameters:
1. the vertex, $$$u$$$
2. distance of the $$$u$$$ from the first vertex, $$$d$$$
3. weight of the edge through which we reached $$$u$$$, $$$w_{last}$$$
We relax the vertices in the following fashion:
If $$$w_{last} \ne 0$$$, it means we reached $$$u$$$ from another vertex $$$u_{prev}$$$, and the sum of the edge weight between $$$u$$$ and $$$u_{prev}$$$($$$w_{u_{prev}u}$$$) and the distance of $$$u_{prev}$$$ from node $$$1$$$, is stored in $$$w_{last}$$$. Now if we want to go to a new vertex $$$u_{next}$$$ from $$$u$$$, according to the problem, we can travel from $$$u_{prev}$$$ to $$$u_{next}$$$ with cost $$$(w_{u_{prev}u}+w_{uu_{next}})^2$$$. Hence, we update $$$dist[u_{next}][0]=(w_{u_{prev}u}+w_{uu_{next}})^2$$$, and push $$$u_{next}$$$ into the heap with no overhead cost, which means for $$$u_{next}$$$, $$$w_{last}=0$$$.
Otherwise, if $$$w_{last}=0$$$, it means we can reach $$$u$$$ from node $$$0$$$, with cost $$$dist[u][0]$$$. Hence, if we want to travel to an adjacent vertex $$$u_{next}$$$, we update $$$dist[u_{next}][w_{uu_{next}}]=dist[u][0]+w_{uu_{next}}$$$, and push $$$u_{next}$$$ into the heap with an overhead cost ($$$=w_{last}$$$) of $$$w_{uu_{next}}$$$, and we move on in life.
Now, the answer for $$$u$$$ is $$$dist[u][0]$$$, and we print it accordingly.
C++ implementation.
nice problemset
Nice editorial
who think problem d is over rated?