hmehta's blog

Topcoder SRM 733
By hmehta, history, 7 years ago, In English

Topcoder SRM 733 is scheduled to start at 12:00 UTC -4, April 14, 2018.

Featured Problem Writer: ltdtl Update: Match Editorials: https://www.topcoder.com/blog/single-round-match-733-editorials/

SRM 733 will give you a chance to move up the ranks to get an automatic qualification to Round 2 of TCO18 Algorithm Track.

You will be able to register for the SRM in the Arena or Applet 4 hours prior to the start of the match. Registration closes 5 minutes before the match begins, so make sure that you are all ready to go.

Don’t know how to compete in Topcoder SRMs?

Check out this guide to know how to compete in an SRM.

You can compete using:

  • Topcoder Web Arena(Beta) — Please watch this video for step by step guide.

  • Topcoder Java Applet — You can refer to this guide here to set up the applet. (Note that those who have Java 8 installed on their machine will see a security issue — You will have to add Topcoder in security exceptions in Java Control Panel. Please refer to the details in the guide here)

All the best!

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

Comments Comments (22)
| Write comment?
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Why don't you tell the problem setter of this match?

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

Reminder: The match begins in 3 hours

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

Thanks for Participating! Here are the Match Editorials https://www.topcoder.com/blog/single-round-match-733-editorials/

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

1000 div1: google [hamiltonian cycle in a tournament graph], or just go directly to [Wikipedia](https://en.wikipedia.org/wiki/Tournament_(graph_theory)).

It's not nice giving problems like "implement something written in the internet" for an online contest... (and yes, I didn't manage to implement it correctly — but this is a different question, problems should be about ideas, not about googling and implementing).

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

    I don't see algorithm about Hamiltonian cycle on wikipedia.

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

      It says "build a path, then construct a cycle in a similar manner". It indeed works like this, but not entirely obvious — so either download the paper from the wikipedia references, or (easier) just google and find the exact algorithm, for example.

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

        Well, it's not same enough. For path you can always add one vertex, in cycle sometimes you need two add two at a time. Here is article in russian :)

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

      Proof of the fact it always exists (if tournament if strongly connected) is constructive. It can be as is converted to O(N^3) algorithm, and quite easy to O(N^2) or O(N^3/32).

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

        How to do it in O(n2)?

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

          Count a lot of numbers of edges between different sets to find good vertex to add in O(n) time. You can check details in my submission.

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

    Reminded me of this problem!

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

    This author had the last round too, solutions to div1 medium and hard were found in a book and div1 medium was googlable directly. I'm not very surprised.

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

    div1 500: google [number of ways to add edges tree] -> first link gives the exact formula https://math.stackexchange.com/questions/640205/numbers-of-ways-k-1-edges-to-be-added-to-k-connected-components-to-make-th

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

      Wtf? Even in editorial it is mentioned that this is a classic problem and another example of CF problem is provided...

      I just simply didn't expect such a shit so I didn't even think about googling...

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

Feels bad when the last time me passing the system test is like a year ago lol(and it was in div2).

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

Div1 250 editorial solution doesn't even pass systest due to precision errors

→ Reply