CFR 8.62 PvP

Imagine voting for 1.8 pvp

wtf, why 1,8 is winning? 1.8 pvp is trash.

1.8 going to win, there are many servers out there still running on 1.8 because of pvp

As his classmate, I also want to thank him

9kin orz orz orz

What evil Madoka did for you?(

It's Ez. It is Binary search.

your wish is granted

But you need to ask nicely...

and as a participant, I ask for a steak to the testers before the round starts.

Usually it works like that.

Hopefully.

xd

I tried it with mos but got TLE ? Can you explain why ?

I got TLE doing this ;-;.
I think its because of my map spam :skull:

Can you please explain this?

For every node, calculate maximum distance to any other node.

For each $$$k$$$, each node with maximum distance to some other node $$$< k$$$ will be in its own component, and all nodes with maximum distance to some other node $$$\ge k$$$ will be in the same component.

For each vertex find the maximum distance from all other nodes. Store these values in an array. Sort this array, then apply binary search for each value of k from 1 to n. The index at which k is supposed to appear is the answer for that k.

This is the correct approach. You need to come up with a fast way to check for each parabola if there exists some good $$$k$$$.

Yes it is the correct appraoch. But checking this way will take O(n2) time if you try to brute force the solution. Use binary search for b and it will be solved in O(nlogn).

Binary Search

same idea, bro! my solution

It wasn't a very good problem imo

but no needs of it. you just need to solve condition on roots.

Do you need to know anything about their tangents? I thought you just need to know how to solve quadratic equations.

no binary lifting is needed to solve D

I usually pray for graph and tree problems (since they're fun) and hope for no geometry/hard math lol. Was quite surprised when I saw a geo problem as C.

got E accepted with Mo. If you calculated maximum of numbers with set, that's slow

You can solve E without Mo's.

Bucket nodes based on their values. Iterate over those buckets in decreasing order of value. Then, only buckets of size 2 matter:

• If the bucket has size 1, then it is impossible to be a "value"
• If the bucket has size 3, then every edge cut would result in a subtree having $$$\geq$$$ 2 nodes with that value. In this case, we can assign every un-assigned edge that value and stop here.

Consider the first time we encounter a bucket of size 2. Call the nodes $$$a$$$ and $$$b$$$, and their value $$$k$$$. If an edge is not on the path from $$$a$$$ to $$$b$$$, then it must have the value $$$k$$$. We can assign them by iterating over every node on the path from $$$a$$$ to $$$b$$$, and then doing a DFS from each of these nodes, avoiding moving on edges on the path from $$$a$$$ to $$$b$$$ (since we still don't know their value yet).

After this, our graph has been reduced to a path, making things easier. The next bucket of size 2 (say $$$u$$$ and $$$v$$$), we can set all the edges that aren't on the intersection of $$$Path(a, b)$$$ and $$$Path(u,v)$$$. You can do this by only doing the above DFS from two nodes (think about how you would implement this). The remaining edges are once again a path, so we can keep repeating this step.

if you want to overkill it like me, yes

i felt it was quite standard , i guess this problem was inspired from the problem -> calculate the diameter of a tree

it was straightforward for me. Don't know will get FST or not..

that's what she said

you can search for the nearest k from b by sorting the k's and then use binary search

yes, the parabola does not touch any line if (b-k)^2 < 4ac . so you need to find a value of k which satisfies that inequality from the given values of k, which can be done using binary search to avoid TLE

You checked whether a parabola can have a suitable line individually for each line which requires O(N * M) total Time, hence the TLE. In the quadratic formula, you know that D = (b — k) ^ 2 — 4 * a * c, here the only value that is not constant when the slopes vary is (b-k), now as you may know for a line to not touch(D == 0) / intersect(D > 0) the parabola, the equation D have to be has to be a negative value i.e D < 0. Since the only varying quantity in the equation is (b-k), you can try to reduce the absolute difference between b & k. A fast way to do this is by sorting all the given slopes and then binary searching on the nearest value to the selected b. This would reduce the Time Complexity to O(M * log(N)). To know about finding the closest value from a given set of integers to a certain value N in (O(log N)), you can refer to this article: https://www.geeksforgeeks.org/find-closest-number-array/

Take a look at Ticket 16798 from CF Stress for a counter example.

Same question

At first i thought that the contest was good but then my C FSTed so I think it was complete garbage (this is a joke i absolutely enjoyed it)

Specialist community welcome you with open heart :)

F2 ~ D, lol

Can you explain D in more detail?

I solved E with small to large, but by using the observation that if the same number appears at least three times it can be a minimum, you can have a way simpler solution

why use sqrt, when $$$(b - k) ^ 2 < 4ac$$$ is perfectly fine as it is

While I'm not really a proponent of following a topic-specific practice routine. Since you asked -

You could refer to CSES' graph section. Alternatively, you could also filter problems on Codeforces by the tag — "graphs", solving them in descending order of solves.

An issue that might come up on Codeforces is that you might encounter problems that can be solved even without applying graph algorithms tagged as "graphs", this happens when the problem also has some solution/intuition related to graphs. It's not really a bad thing either, maybe a welcome exposure to additional variations on graphs.

As for improving, identify the challenges. Are you lacking in identifying the solution or are you unable to implement your ideas? If it's the former, take more time before jumping to implement, and maybe try out a few test cases yourself. If it's the latter, stop, and don't hurry. Implementation improves with practice, but you need to streamline the process. Read others' codes. How do the top competitors implement the solution? Learn from them. More often than not, you'll find that their solution is much more clear and concise as compared to yours, and after adopting those patterns/practices, with time, you should find your implementation skills improving as well.

Edit: Fixed language

If you do a linear traverse on the array line and print the value of check(a, b, c, line[i]) you will see something like: (0 is false and 1 is true)

0 0 ... 0 0 1 1 ... 1 1 0 0 ... 0 0

So check() is not a monotonic function and cannot be used to search the best k.

Instead, and observing the previous array and the check() function, we should search for the value that is the nearest to b. This is done by using std::lower_bound() on line and checking the previous, current and next value in the array, if exists.

but C is not geometry -_~

what if variable it points to the the end of vector? Your code fails.

your solution is wrong

I think you are missing lower bound that is "t1" in your case may not exist.

what if t1 is equal to n+1, that is undefined behavior and differs from compiler, also maybe is a floating point error, using pow maybe gives rounding error, but I bet on the first.