hmehta's blog

Topcoder Single Round Match 799 — Postponed by an hour
By hmehta, history, 4 years ago, In English

Topcoder SRM 799 is scheduled to start at 12:00 UTC-5 on February 6, 2021.

Registration is now open for the SRM in the Arena or Applet and closes at 11:55 UTC-5. The coding phase will start at 12:05 UTC-5, so make sure that you are all ready to go.

Thanks to IH19980412 for writing the problem set. Also thanks to misof for testing and coordinating the round.

This SRM will award points towards Stage 3 of TCO21 and also the qualifications for TCO21 Regional Events

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

. . . .

UPD: The contest will start an hour later from the scheduled time. It will now start at 13:00 UTC-5 on February 6, 2021

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

Comments Comments (10)
| Write comment?
»
4 years ago, # |
  Vote: I like it +92 Vote: I do not like it

Hi hmehta, this seems to clash with 1 hour of the Quora Programming contest, which perhaps a large fraction of the community would want to do. Is it possible to delay the SRM by 1 hour? Delaying on a Saturday should hopefully not lose much participation.

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

    Hey! Sorry for the delay here!

    We have moved the contest by an hour :)

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

How to solve the MapleTree Problem. The Editorial is not clear.

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

    The editorial + this code should give you the solution. It is a self-explanatory O(N^2) solution. To me, the trickiest part was why can we delete the vertices and keep the tree connected.

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

      It took me too long to understand this code. I believe the most genius part of the code is the way leaves are being chosen, which ensures that a chosen leaf will always be part of the diameter for any subset of the active nodes. As far as I understand, this solution would have failed if he/she had chosen the leaves in some other way (say, by selecting any node with degree at most 1).

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

        Yes, but this is the way to find the diameter. In the case of positive edge weights, the diameter will always be a path between 2 leaves. You need to find the farthest leaf (l1) from the root and then find the farthest leaf (l2) from l1. l1 and l2 are the endpoints of the diameter. Now, when you will remove the vertices in this order, you will be continually removing leaves, so the tree remains connected.

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

          Yes, but we are not finding a leaf node l2 for a leaf node l1, such that the path l1 to l2 is a diameter, but actually processing all diameters with l1 being at one end of it, then deleting l1. This is not possible if we choose any leaf vertex as l1, instead of the farthest from a random active root node. That, to me looks like the most interesting part of the solution.

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

            Ok, I thought that this is another standard way to find the diameter of the tree (except dp).

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

Waiting for the full editorial :/

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

Is SRM 799 rated? My rating didn't change after it.

→ Reply