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!
Why don't you tell the problem setter of this match?
Featured Problem Writer: ltdtl
Reminder: The match begins in 3 hours
Thanks for Participating! Here are the Match Editorials https://www.topcoder.com/blog/single-round-match-733-editorials/
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).
I don't see algorithm about Hamiltonian cycle on wikipedia.
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.
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 :)
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).
How to do it in O(n2)?
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.
Reminded me of this problem!
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.
Wait a minute, is he really from DPRK? Oo
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
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...
Are testers (Lewin and dreamoon_love_AA) noticed about it?
Feels bad when the last time me passing the system test is like a year ago lol(and it was in div2).
Div1 250 editorial solution doesn't even pass systest due to precision errors
Fixed!
Thanks :)