Topcoder SRM 810 is scheduled to start at 12:00 UTC-4 on July 24, 2021.
Registration is now open for the SRM in the Arena or Applet and closes at 11:55 UTC-4. The coding phase will start at 12:05 UTC-4, so make sure that you are all ready to go. Click here to what time it starts in your area
Please take a look at our How to Compete guide to understand Topcoder Algorithm rounds better.
Some Important Links:: Match Results (match results, rating changes, challenges, individual test case results), Problem Archive, Problem Writing, Algorithm Rankings, Editorials and Older Editorials(SRM 710 and before),
Best of luck!
- The Topcoder Team
Countdown to the round: https://www.timeanddate.com/countdown/generic?p0=98&iso=20210724T12&msg=SRM%20810
Editorial draft is available here
Request: From next time, can we have a video editorial right after the contest for 30 mins? Like how tourist has done for his round? cc: hmehta
500: I already forgot that kind of segment tree :(.
No need to segment tree: initialize each road ID with 0, and for each pair XOR all IDs on any segment between them with a random number. In the end delete all roads in a group with the same XOR to minimize the cost.
Nice trick, it'll work on non-random data right?
Fortunately I didn't forget that kind of segtree.
Sure, doesn't rely on input randomness.
We basically want to group roads that are on the same side of any cut. If two roads are on different side of at least one cut, XOR of their IDs is as equidistributed as your random numbers.
Does the segment tree approach rely on the fact that we only need to query the whole range (from $$$0$$$ to $$$N-1$$$)? I feel like if we would need to query arbitrary ranges then updates/queries can become $$$O(N)$$$ (but maybe I don't understand it properly).
No, querying an arbitrary range is straightforward. The important thing is that there's no lazy propagation. For each node, I remember the number of ranges that fully cover it and the cost I'd get if this number was zero (and the sum of $$$C_i$$$).
Let's say we first add 1 to the range $$$[0, 4]$$$ and then query the range $$$[0, 2]$$$ (which is a child of $$$[0, 4]$$$). Won't it give $$$0$$$ as a result then since we don't propagate?
Why? We don't even need to go to $$$[0,2]$$$ from $$$[0,4]$$$ since we already see there that the range is covered.
It's starting to make sense now. It's different from how I usually think about a segment tree. Thanks for explaining.
Just to make sure I understand, the probability of a collision for long long ids can be estimated to be at most
1-(1-1/2^64)*(1-2/2^64)*...*(1-200000/2^64) < 1-(1-200000/2^64)^200000 = 200000*200000/2^64-(200000 choose 2)*(200000/2^64)^2 + ...
so something like 3*10^-9 would be an upper bound.
The order of magnitude is correct. See [wiki page](https://en.wikipedia.org/wiki/Birthday_problem#Probability_of_a_shared_birthday_(collision)) for all sorts of bounds.
Hey misof,hmehta! sorry for tagging, in every topcoder problem's solve count description I can see "Categories", is there a way I can search problem with categories? I can't find where to search for it.
Thanks!
https://community.topcoder.com/tc?module=ProblemArchive