### hmehta's blog

By hmehta, history, 2 months ago,

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

• +13

 » 2 months ago, # | ← Rev. 2 →   +11 Countdown to the round: https://www.timeanddate.com/countdown/generic?p0=98&iso=20210724T12&msg=SRM%20810
 » 2 months ago, # |   +19
•  » » 2 months ago, # ^ |   -15 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
 » 2 months ago, # | ← Rev. 2 →   +3 500: I already forgot that kind of segment tree :(.
•  » » 2 months ago, # ^ |   +48 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.
•  » » » 2 months ago, # ^ |   0 Nice trick, it'll work on non-random data right?Fortunately I didn't forget that kind of segtree.
•  » » » » 2 months ago, # ^ |   +3 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.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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).
•  » » » » » 2 months ago, # ^ |   0 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$).
•  » » » » » » 2 months ago, # ^ |   0 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?
•  » » » » » » » 2 months ago, # ^ |   +3 Why? We don't even need to go to $[0,2]$ from $[0,4]$ since we already see there that the range is covered.
•  » » » » » » » » 2 months ago, # ^ |   0 It's starting to make sense now. It's different from how I usually think about a segment tree. Thanks for explaining.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Just to make sure I understand, the probability of a collision for long long ids can be estimated to be at most1-(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.
•  » » » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   0 Why 250-point problem was so difficult that a lot of people ended up failing system test?
•  » » 2 months ago, # ^ |   0 It sure was tricky for a 250.
 » 2 months ago, # | ← Rev. 2 →   0 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!
•  » » 2 months ago, # ^ |   +1
•  » » » 2 months ago, # ^ |   0 Thanks!!