Hi!
Topcoder SRM 754 is scheduled to start at 07:00 UTC -4, March 30, 2019. Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins.
Editorials: https://www.topcoder.com/blog/single-round-match-754-editorials/
Thanks to misof for setting the problems and adamant for testing the round.
This is the sixth SRM of Stage 3 of TCO19 Algorithm. This stage will also help you qualify and win reimbursements/tickets to TCO19 Regional Events.
Stage 3 TCO19 Points Leaderboard | Topcoder Java Applet | Next SRM 755 — April 09, 21:00 UTC-4
Stage 3 Leaderboard
All the best!
Forced to solve 1st, left contest after reading 2nd xD
When I opened Medium, I immediately scolded myself "Why didn't you go for the Hard strategy if Medium is 600 and obviously geometry?"
Upon reading it, I asked myself "How would I write a checker for this?", and it was clear in couple moments. Then, not having any better idea, I spent rest of the contest tweaking a random walk solution. It didn't even get through Challenge phase :-)
Didn't you just miss n=1? A random walk solution should absolutely be possible, I had one that was fast enough.
>yfw
Hi Xellos, long time no see. You have a nice CF rating, would be a shame if I organised a contest and something happened to it.
I'll bet you $1000 you can't do that.
Ouch. It's been a while since I misjudged the difficulty of a problem this badly (div1 "medium").
Wait, should I blame the tester for solving it reasonably quickly? ;)
Nah, it's all my bad, and I'm sorry it all turned out this way. We are definitely aiming for much easier medium problems than this one.
I'm especially sad here because I'm quite fond of the hard problem and this way almost nobody had the time to attempt it. Hopefully you'll give it a shot in the practice room :)
If you have the time, I would like to hear your experience with this div1 medium so I can recalibrate my "difficulty estimator" for the future.
I thought it wasn't too hard, but since I didn't manage to pass the last sample, my opinion is clearly not too reliable. The starting idea (2*number of slopes and n=1) was obvious to me, at least.
Apparently, I think this Div1 Medium is a great problem and I appreciate it. I even feel questioning why this announcement blog is not highly rated. I feel like my favorite is Div1 Medium rather than Div1 Hard. And also, I could only solve Div1 Medium during the contest.
In my opinion, I think this problem is not so difficult for Div1 Medium. When I realized that $$$n$$$ equals $$$2 \times$$$ (the number of species of line passing point $$$i$$$ and $$$j$$$), it became a simple construction problem. This was an interesting part of this problem, and I realized in less than 10 minutes.
Why did it became a simple construction problem? That's because we can divide points into "line set" (let the size $$$s_1, s_2, \dots, s_k$$$), and when $$$S = s_1 + s_2 + \cdots + s_k$$$, it will hold:
So I could move to implementation when half of the contest ended (note that I spent quarter of the contest for Div1 Easy). But I made a mistake in "how to place lines without clashing slope". The implementation was not difficult, but I made wrong answer in test of n=100, and I didn't know why I got wrong answer and what is wrong with it. I didn't realize what was wrong, until I wrote the output-checker of my program.
I think that this is why few people solved this problem. I see that many of participants for this problem was "compiled".
I got that construction reduction as well, but I don't really understand your solution. What sizes are the $$$s_i$$$ denoting exactly? Are you saying there are $$$k$$$ different line slopes and the number of points on the $$$i$$$th line will be $$$s_i$$$?
Yeah, the meaning of $$$k$$$ and $$$s_i$$$ is exactly what you're saying. Additionally, if $$$s_i = 1$$$, it is just a single point.
Oops, I forgot to warn that I'm non-representative sample :)
No worries, any sample of size 1 will have that property :)
Hey, the editorial regarding Med. Div 1.
The unit circle part is not clear. And also which segments it is referring to. And those two lines seems to be the crux to the solution.
I dont know if topcoder works like this. But if it is, then they need to change.
What exactly seems wrong to you? On both TC and CF successful hacks usually added to systests.
The "we keep it simple" thing? It sounds as though the systests were intentionally made weak. Hope they're not.
I'm opening 900 over a 600 every day of the week (was 30 mins away from solving it too). It's just the extra value added to the normal 250-500-1000 makes me panic. Also, the opposite is true. Nice problems, thanks.
How to solve Div1-Easy?
I'm sure the editorial will be better, but here's my idea if you cannot wait. I solved in practice room. Define S as the set of points, and N = |S|. Since N<=3000, it means an O(N^3) algorithm is no good. So you cannot check every 3 points, see if they are part of a square, and find the 4th. That would be too easy.
Instead we take every distinct pair of points, which is O(N^2). For each pair of points A, B, compute the two other points C, D that make a square ABCD. Test if C and D are in S, this can be done with set<> data structure in O(log(N)). If C and D are both NOT in S, or both IN S, then move on. Otherwise the one which is NOT in S will be adding a new square, so add it to some other set T.
Final answer will be |T|. Even if somehow every pair results in one point added to T, that is O(N^2) additions, but set operations are logarithmic and O(log(N^2)) = O(log(N)).
Total time is thus O(N^2*log(N)). Can make it O(N^2) with unordered_set<> but it's not necessary to pass.
For the geometry to compute the other points C, D, I had to google formulas because I don't like geometry. But as usual top guys implemented something in 10% of the code that I needed, and I don't understand it yet...
Edit: for a really clean implementation, look at Egor's fastest solution, done in 6:38.