Блог пользователя hmehta

Автор hmehta, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      Fortunately I didn't forget that kind of segtree.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +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.

      • »
        »
        »
        »
        3 года назад, # ^ |
        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).

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 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$$$).

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 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?

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится +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.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
3 года назад, # |
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!