hmehta's blog

Topcoder SRM 810
By hmehta, history, 3 years ago, In English

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

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Countdown to the round: https://www.timeanddate.com/countdown/generic?p0=98&iso=20210724T12&msg=SRM%20810

→ Reply
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Editorial draft is available here

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

500: I already forgot that kind of segment tree :(.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice trick, it'll work on non-random data right?

      Fortunately I didn't forget that kind of segtree.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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).

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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$$$).

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              Why? We don't even need to go to $$$[0,2]$$$ from $$$[0,4]$$$ since we already see there that the range is covered.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                It's starting to make sense now. It's different from how I usually think about a segment tree. Thanks for explaining.

                → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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!

→ Reply